TY - JOUR

T1 - Optimization of the algorithm to compute the guaranteed number of activations in XS-circuits and its application to the analysis of block ciphers

AU - Parfenov, Denis

AU - Bakharev, Aleksandr

AU - Kutsenko, Aleksandr

AU - Belov, Aleksandr

AU - Atutova, Natalia

N1 - The work is supported by the Mathematical Center in Akademgorodok under the Agreement No. 075-15-2022-282 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2025/3/25

Y1 - 2025/3/25

N2 - The guaranteed number of activations (GNA) is an important characteristic to determine the effectiveness of differential cryptanalysis of a given XS-circuit. In this paper, we propose an approach to optimize the known algorithm for GNA computation based on the branch and bound method. We also analyze special matrices that define XS-circuit. The experiments show that the proposed algorithm significantly outperforms the existing approach. In this paper, we prove that canonical forms of XS-circuit and its dual coincide, providing the strict connection between the guaranteed number of linear and differential activations. The circuits with the extremal values of GNA are studied. We made several hypotheses based on computational experiments. One of the hypotheses is that there are no XS-circuits of dimension greater than 2, which achieve an optimal GNA on every round.

AB - The guaranteed number of activations (GNA) is an important characteristic to determine the effectiveness of differential cryptanalysis of a given XS-circuit. In this paper, we propose an approach to optimize the known algorithm for GNA computation based on the branch and bound method. We also analyze special matrices that define XS-circuit. The experiments show that the proposed algorithm significantly outperforms the existing approach. In this paper, we prove that canonical forms of XS-circuit and its dual coincide, providing the strict connection between the guaranteed number of linear and differential activations. The circuits with the extremal values of GNA are studied. We made several hypotheses based on computational experiments. One of the hypotheses is that there are no XS-circuits of dimension greater than 2, which achieve an optimal GNA on every round.

KW - Branch and bound method

KW - Differential cryptanalysis

KW - Guaranteed number of activations

KW - Linear cryptanalysis

KW - XS-circuit

UR - https://www.mendeley.com/catalogue/2ece0d21-6126-3d4e-aea0-2ca207b7d04c/

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-105000807687&origin=inward&txGid=e904e24e7e4e9e47c4b7e63a2531917a

U2 - 10.1007/s13389-025-00374-8

DO - 10.1007/s13389-025-00374-8

M3 - Article

VL - 15

JO - Journal of Cryptographic Engineering

JF - Journal of Cryptographic Engineering

SN - 2190-8516

IS - 1

M1 - 4

ER -