On algorithmic implementation of 16-bit S-boxes with ARX and Butterfly structures

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.