Geodesic
On algorithmic implementation of 16-bit S-boxes with ARX and Butterfly structures
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 101-107.

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

Implementations of non-linear mappings of vector space $V_n$ (s-boxes $n \times n$) as lookup-tables are memory intensive. It requires $n2^n$ bits to store $n$-bit s-box. That is why the existing block ciphers use s-boxes of relatively small size ($8\times8$ bit — AES, Kuznyechik, $6\times4$ bit — DES). New constructions of $16$-bit algorithmically implementable s-boxes with improved performance and cryptographic properties (in comparison with the existing methods) are proposed. The first method is based on ARX (Add-Rotate-XOR) structure, using low-cost computations in software and hardware. The second method is based on butterfly structure, using $8$-bit precomputed s-boxes to build $16\times16$ ones. Maximum expected differential probability, maximum expected linear probability and minimum nonlinear order over all linear combinations of the components of proposed s-boxes with ARX structure are $ 18/2^{16} $, $ 764/2^{15} $ and $15$, respectively and of suggested s-boxes with Butterfly structure are $ 10/2^{16} $, $ 512/2^{15} $ and $15$, respectively. It is established that the use of the proposed $16$-bit s-boxes in the round substitutions of AES and Kuznyechik block ciphers significantly lowers the upper bounds of differential and linear probabilities for two and four rounds of these algorithms.
Keywords: $16$-bit s-box, algorithmic implementation of s-boxes, Butterfly, maximum differential probability, maximum linear probability, nonlinear order.
Mots-clés : ARX 
@article{PDMA_2019_12_a31,
     author = {S. M. Komissarov},
     title = {On algorithmic implementation of 16-bit {S-boxes} with {ARX} and {Butterfly} structures},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {101--107},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a31/}
}
TY  - JOUR
AU  - S. M. Komissarov
TI  - On algorithmic implementation of 16-bit S-boxes with ARX and Butterfly structures
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 101
EP  - 107
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a31/
LA  - ru
ID  - PDMA_2019_12_a31
ER  - 
%0 Journal Article
%A S. M. Komissarov
%T On algorithmic implementation of 16-bit S-boxes with ARX and Butterfly structures
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 101-107
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a31/
%G ru
%F PDMA_2019_12_a31
S. M. Komissarov. On algorithmic implementation of 16-bit S-boxes with ARX and Butterfly structures. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 101-107. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a31/

[1] Menyachikhin A., “Spectral-linear and spectral-difference methods for generating cryptographically strong S-boxes”, CTCrypt Preproc. (Yaroslavl, 2016), 232–252 https://mjos.fi/doc/rus/CTCrypt2016Preproceedings.pdf

[2] Fomichev V. M., Lolich D. M., Yuzbashev A. V., “Algoritmicheskaya realizatsiya s-boksov na osnove modifitsirovannykh additivnykh generatorov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 102–104

[3] Bobrov V. M., Komissarov S. M., “O svoistvakh dvukh klassov s-boksov razmera 16$\times$16”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 57–61

[4] Jimenez R. A., Generation of 8-bit s-boxes Having Almost Optimal Cryptographic Properties Using Smaller 4-bit s-boxes and Finite Field Multiplication, Havana University, Institute of Cryptography, Havana, 2017 http://www.cs.haifa.ac.il/õrrd/LC17/paper60.pdf | MR

[5] Fomin D. B., “New Classes of 8-bit Permutations Based on a Butterfly Structure”, CTCrypt (Suzdal, 2018) https://ctcrypt.ru/files/files/2018/09_Fomin.pdf | MR

[6] Wood C. A., Large Substitution Boxes with Efficient Combinational Implementations, Thesis, Rochester Institute of Technology, 2013

[7] Daemen J., Rijmen V., The Design of Rijndael, AES — the Advanced Encryption Standard, Springer Verlag, 2002 | MR | Zbl

[8] AlTawy R., Youssef A. M., “A meet in the middle attack on reduced round Kuznyechik”, IEICE Trans., 98-A (2015), 2194–2198 | DOI | MR

[9] Park S., Sung S.H., Lee S., Lim J., “Improving the upper bound on the maximum differential and the maximum linear hull probability for SPN structures and AES”, LNCS, 2887, 2003, 247–260 | Zbl