Geodesic
Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers
Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 2, pp. 29-46 
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. Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 2, pp. 29-46. http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a2/
@article{MVK_2024_15_2_a2,
     author = {S. A. Davydov and Yu. D. Shkuratov},
     title = {Circulant matrices over $\mathbb{F}_2$ and their use for the construction of~efficient linear transformations with high branch numbers},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {29--46},
     year = {2024},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a2/}
}
TY  - JOUR
AU  - S. A. Davydov
AU  - Yu. D. Shkuratov
TI  - Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers
JO  - Matematičeskie voprosy kriptografii
PY  - 2024
SP  - 29
EP  - 46
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a2/
LA  - ru
ID  - MVK_2024_15_2_a2
ER  - 
%0 Journal Article
%A S. A. Davydov
%A Yu. D. Shkuratov
%T Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers
%J Matematičeskie voprosy kriptografii
%D 2024
%P 29-46
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2024_15_2_a2/
%G ru
%F MVK_2024_15_2_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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 low-order digits. AES and Whirlpool matrices have been decomposed using this method into two and four summands.

[1] Shannon C. E., “Communication theory of secrecy systems”, Bell System Tech. J., 28:4 (1949), 656–715 ; Shennon K., “Teoriya svyazi v sekretnykh sistemakh”, Raboty po teorii informatsii i kibernetike, IL, M., 1963, 333–402 | DOI | MR | Zbl

[2] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 4 (1990), 3–72 | DOI | MR

[3] Matsui M., “Linear cryptanalysis method for DES cipher”, EUROCRYPT '93, Lect. Notes Comput. Sci., 765, 1994, 386–397 | DOI | Zbl

[4] Malyshev F. M., “Dvoistvennost raznostnogo i lineinogo metodov v kriptografii”, Matematicheskie voprosy kriptografii, 5:3 (2014), 35–47 | DOI | Zbl

[5] Kishan G., Indranil R., “Cryptographically significant MDS matrices based on circulant and circulant-like matrices for lightweight applications”, Cryptogr. and Communic., 7 (2015), 257–287 | DOI | MR | Zbl

[6] Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Funktsiya kheshirovaniya. GOST R 34.11 — 2012, Standartinform, M., 2013, 25 pp.

[7] Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Blochnye shifry. GOST R 34.12 — 2015, Standartinform, M., 2015, 25 pp.

[8] Guo J., Peyrin T., Poschmann A., “The PHOTON family of lightweight hash functions”, CRYPTO 2011, Lect. Notes Comput. Sci., 6841, 2011, 222–239 | DOI | Zbl

[9] Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers, ISO/IEC 18033-3, 2010

[10] Diffie W., Ledin G., SMS4 encryption algorithm for wireless networks, IACR Cryptology ePrint Archive, Paper 2008/329, 2008 https://eprint.iacr.org/2008/329.pdf

[11] Information technology — Security techniques — Hash-functions — Part 3: Dedicated hash-functions, ISO/IEC 10118-3, 2004

[12] Dorokhin S.V., Kachkov S.S., Sidorenko A.A., “Realizatsiya blochnogo shifra “Kuznechik” s ispolzovaniem vektornykh instruktsii”, Trudy MFTI, 10:4 (2018), 45–53

[13] Lemire D., Kaser O., “Faster 64-bit universal hashing using carry-less multiplications”, J. Cryptogr. Eng., 6 (2015), 171–185 | DOI

[14] Fog A., Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs, Techn. Univ. of Denmark, 1996–2022, 469 pp. https://agner.org/optimize/instruction_tables.pdf

[15] Gueron S., “Intel's New AES instructions for enhanced performance and security”, FSE 2009, Lect. Notes Comput. Sci., 5665, 2009, 51–66 | DOI | Zbl