RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2023 Issue 16, Pages 78–81 (Mi pdma613)

Mathematical Methods of Cryptography

Additional optimization of the guaranteed number of activations in $\mathsf{XS}$-circuits computation algorithm

D. R. Parfenova, A. O. Bakharevbc

a Novosibirsk State University, Department of Information Technologies
b Novosibirsk State University, Mechanics and Mathematics Department
c Mathematical Center in Akademgorodok, Novosibirsk

Abstract: We propose an additional optimization to the Guaranteed Number of Activations (GNA) computation algorithm. The main idea of this optimization is to replace linear dependence checks based on the matrix rank computations with suffix checks of paths corresponding to partitions in the search tree. Proposed algorithm has been implemented and is two times faster than the previous solution. Using an optimized version of the GNA computation algorithm, we carried out several computational experiments. As a result, we refuted several hypothesis and proposed a scalable $\mathsf{XS}$-circuit construction with an optimal GNA value.

Keywords: guaranteed number of activations, $\mathsf{XS}$-circuit, differential cryptanalysis.

UDC: 519.7 + 004.056.55

DOI: 10.17223/2226308X/16/20



© Steklov Math. Inst. of RAS, 2024