Paper 2020/1048

An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums

Kai Hu, Siwei Sun, Meiqin Wang, and Qingju Wang

Abstract

Since it was proposed in 2015 as a generalization of integral properties, the division property has evolved into a powerful tool for probing the structures of Boolean functions whose algebraic normal forms are not available. We capture the most essential elements for the detection of division properties from a pure algebraic perspective, proposing a technique named as monomial prediction, which can be employed to determine the presence or absence of a monomial in any product of the coordinate functions of a vectorial Boolean function $\boldsymbol f$ by counting the number of the so-called monomial trails across a sequence of simpler functions whose composition is $\boldsymbol f$. Under the framework of the monomial prediction, we formally prove that most algorithms for detecting division properties in literature raise no false alarms but may miss. We also establish the equivalence between the monomial prediction and the three-subset bit-based division property without unknown subset presented at EUROCRYPT 2020, and show that these two techniques are perfectly accurate. The monomial prediction technique can be regarded as a purification of the definitions of the division properties without resorting to external multisets. This algebraic formulation gives more insights into division properties and inspires new search strategies. With the monomial prediction, we obtain the exact algebraic degrees of TRIVIUM up to 834 rounds for the first time. In the context of cube attacks, we are able to explore a larger search space in limited time and recover the exact algebraic normal forms of complex superpolies with the help of a divide-and-conquer strategy. As a result, we identify more cubes with smaller dimensions, leading to improvements of some near-optimal attacks against 840-, 841- and 842-round TRIVIUM.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
Division PropertyMonomial PredictionDetection AlgorithmAlgebraic DegreeCube AttackTRIVIUM
Contact author(s)
hukai @ mail sdu edu cn
siweisun isaac @ gmail com
mqwang @ sdu edu cn
qingju wang @ uni lu
History
2020-09-01: received
Short URL
https://ia.cr/2020/1048
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1048,
      author = {Kai Hu and Siwei Sun and Meiqin Wang and Qingju Wang},
      title = {An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1048},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1048}},
      url = {https://eprint.iacr.org/2020/1048}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.