
Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers
S. A. Davydov^{a}, Yu. D. Shkuratov^{b} ^{a} JSRPC «Kryptonite», Moscow
^{b} Lomonosov Moscow State University, Moscow
Abstract:
Linear transformations over $\mathbb{F}_2$ with high branch number are studied. New class of transformations is proposed — transformations, corresponding to the multiplication in the ring $\mathbb{F}_2[x]/f(x)$. An important subclass of this class is studied in detail — transformations defined by circulant matrices over $\mathbb{F}_2$. It is shown that for the software implementation of this class of transformations it is sufficient to use two instructions from the (extended) set of processor instructions and store only one row of the matrix. It is proposed to decompose any matrix over $\mathbb{F}_2$ into the sum of products of diagonal matrices and matrices corresponding to the multiplication in the ring $\mathbb{F}_2[x]/f(x)$. The number of summands is estimated in the case of known $f(x)$, the efficiency of the software implementation is justified. In the case of unknown $f(x)$ some probabilistic relations between matrix rows are derived. For any circulant matrix over $\mathbb{F}_{2^{s}}$ and $f(x) = x^{n}+1$ the number of summands does not exceed $s$ in the general case and does not exceed $k$ in the case when each element of the matrix has only $k$ nonzero loworder digits. AES and Whirlpool matrices have been decomposed using this method into two and four summands.
Key words:
linear transformation, branch number, MDS matrix, circulant matrix, matrix decomposition, software implementation of linear transformation.
Received 02.IX.2023
Citation:
S. A. Davydov, Yu. D. Shkuratov, “Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers”, Mat. Vopr. Kriptogr., 15:2 (2024), 29–46
Linking options:
https://www.mathnet.ru/eng/mvk468https://doi.org/10.4213/mvk468 https://www.mathnet.ru/eng/mvk/v15/i2/p29

Statistics & downloads: 
Abstract page:  46  Fulltext PDF :  2  References:  5  First page:  2 
