Geodesic
On the guaranteed number of activations in $\mathsf{XS}$-circuits
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 7-20 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

$\mathsf{XS}$-circuits describe cryptographic primitives that utilize two operations on binary words of fixed length: bitwise modulo $2$ addition ($\mathsf{X}$) and substitution ($\mathsf{S}$). The words are interpreted as elements of a field of characteristic $2$. In this paper, we develop a model of $\mathsf{XS}$-circuits according to which several instances of a simple round circuit containing only one $\mathsf{S}$ operation are linked together and form a compound circuit called a cascade. $\mathsf{S}$ operations of a cascade are interpreted as independent round oracles. When a cascade processes a pair of different inputs, some round oracles get different queries, these oracles are activated. The more activations, the higher security guarantees against differential cryptanalysis the cascade provides. We introduce the notion of the guaranteed number of activations, that is, the minimum number of activations over all choices of the base field, round oracles and pairs of inputs. We show that the guaranteed number of activations is related to the minimum distance of the linear code associated with the cascade. It is also related to the minimum number of occurrences of units in segments of binary linear recurrence sequences whose characteristic polynomial is determined by the round circuit. We provide an algorithm for calculating the guaranteed number of activations. We show how to use this algorithm to deal with linear activations related to linear cryptanalysis. 
@article{MVK_2021_12_2_a1,
     author = {S. V. Agievich},
     title = {On the guaranteed number of activations in~$\mathsf{XS}$-circuits},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {7--20},
     year = {2021},
     volume = {12},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a1/}
}
TY  - JOUR
AU  - S. V. Agievich
TI  - On the guaranteed number of activations in $\mathsf{XS}$-circuits
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 7
EP  - 20
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a1/
LA  - en
ID  - MVK_2021_12_2_a1
ER  - 
%0 Journal Article
%A S. V. Agievich
%T On the guaranteed number of activations in $\mathsf{XS}$-circuits
%J Matematičeskie voprosy kriptografii
%D 2021
%P 7-20
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a1/
%G en
%F MVK_2021_12_2_a1
S. V. Agievich. On the guaranteed number of activations in $\mathsf{XS}$-circuits. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 7-20. http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a1/

[1] Agievich S., “XS-circuits in Block Ciphers”, Matematicheskie Voprosy Kriptografii, 10:2 (2019), 7–30

[2] Albrecht M., Grassi L., Rechberger C., Roy A., Tiessen T., “MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity”, ASIACRYPT 2016, Lect. Notes Comput. Sci., 10031, 2016, 191–219

[3] Avanzi R., A salad of block ciphers, Cryptology ePrint Archive, Report 2016/1171, , 2016 https://eprint.iacr.org/2016/1171

[4] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, CRYPTO '90, Lect. Notes Comput. Sci., 537, 1991, 2–21

[5] Bogdanov A., Shibutani K., “Generalized Feistel networks revisited”, Des. Codes Cryptogr., 66 (2013), 75–97

[6] Daemen J., Cipher and hash function design strategies based on linear and differential cryptanalysis, 1995 https://cs.ru.nl/ ̃ joan/papers/JDA_Thesis_1995.pdf

[7] Daemen J., Rijmen V., “The wide trail design strategy”, Cryptography and Coding 2001, Lect. Notes Comput. Sci., 2260, 2001, 222–238

[8] Diffie W., Ledin G., SMS4 Encryption algorithm for wireless networks, Cryptology ePrint Archive, Report 2008/329, , 2008 https://eprint.iacr.org/2008/329

[9] Huffman W. C., Pless V., Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003

[10] Liddl R., Niederreiter H., Finite Fields, Cambridge Univ. Press, New York, USA, 1997

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

[12] MacWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier Science, 1977

[13] Wu S., Wang M., Security evaluation against differential cryptanalysis for block cipher structures, Cryptology ePrint Archive, Report 2011/551, , 2011 https://eprint.iacr.org/2011/551

[14] Zhang J., Wu W., Zheng Y., “Security of SM4 against (related-key) differential cryptanalysis”, ISPEC 2016, Lect. Notes Comput. Sci., 10060, 2016, 65–78

[15] Zhang M., Liu J., Wang X., The upper bounds on differential characteristics in block cipher SMS4, Cryptology ePrint Archive, Report 2010/155, , 2010 https://eprint.iacr.org/2010/155

[16] Zheng Y., Matsumoto T., Imai H., “On the construction of block ciphers provably secure and not relying on any unproved hypotheses”, CRYPTO'89 Proceedings, Lect. Notes Comput. Sci., 435, 1990, 461–480