CryptoDB
An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums
| Authors: | |
|---|---|
| Download: | |
| 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 {\it monomial prediction}, which can be employed to determine the presence or absence of a monomial in the product of the coordinate functions of a vectorial Boolean function $\bs f$ by counting the number of the so-called {\it monomial trails} across a sequence of simpler functions whose composition is $\bs f$. Under the framework of the monomial prediction, we formally prove that most algorithms for detecting division properties in previous 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. This algebraic formulation gives more insights into division properties and inspires new search strategies. With the monomial prediction, we obtain the {\it 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. |
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30678,
title={An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums},
booktitle={Advances in Cryptology - ASIACRYPT 2020},
publisher={Springer},
doi={10.1007/978-3-030-64837-4_15},
author={Kai Hu and Siwei Sun and Meiqin Wang and Qingju Wang},
year=2020
}