Welcome to the resource topic for 2021/1285
Title:
Convexity of division property transitions: theory, algorithms and compact models
Authors: Aleksei Udovenko
Abstract:Integral cryptanalysis is a powerful tool for attacking symmetric primitives, and division property is a state-of-the-art framework for finding integral distinguishers. This work describes new theoretical and practical insights into traditional bit-based division property. We focus on analyzing and exploiting monotonicity/convexity of division property and its relation to the graph indicator. In particular, our investigation leads to a new compact representation of propagation, which allows CNF/MILP modeling for larger S-Boxes, such as 16-bit Super-Sboxes of lightweight block ciphers or even 32-bit random S-boxes. This solves the challenge posed by Derbez and Fouque (ToSC 2020), who questioned the possibility of SAT/SMT/MILP modeling of 16-bit Super-Sboxes. As a proof-of-concept, we model the Super-Sboxes of the 8-round LED by CNF formulas, which was not feasible by any previous approach. Our analysis is further supported by an elegant algorithmic framework. We describe simple algorithms for computing division property of a set of n-bit vectors in time O(n2^n), reducing such sets to minimal/maximal elements in time O(n2^n), computing division property propagation table of an n\times m-bit S-box and its compact representation in time O((n+m)2^{n+m}). In addition, we develop an advanced algorithm tailored to “heavy” bijections, allowing to model, for example, a randomly generated 32-bit S-box.
ePrint: https://eprint.iacr.org/2021/1285
Talk: https://www.youtube.com/watch?v=yB4-n-CpKsM
Slides: https://iacr.org/submit/files/slides/2021/asiacrypt/asiacrypt2021/13/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .