Welcome to the resource topic for 2024/786
Title:
Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit
Authors: Fukang Liu, Mohammad Mahzoun, Willi Meier
Abstract:It is well-known that a system of equations becomes easier to solve when it is overdefined. In this work, we study how to overdefine the system of equations to describe the arithmetic oriented (AO) ciphers Friday, Vision, and RAIN, as well as a special system of quadratic equations over \mathbb F_{2^{\ell}} used in the post-quantum signature scheme Biscuit. Our method is inspired by Courtois-Pieprzyk’s and Murphy-Robshaw’s methods to model AES with overdefined systems of quadratic equations over \mathbb F_2 and \mathbb F_{2^8}, respectively. However, our method is more refined and much simplified compared with Murphy-Robshaw’s method, since it can take full advantage of the low-degree \mathbb F_2-linearized affine polynomials used in Friday and Vision, and the overdefined system of equations over \mathbb F_{2^{\ell}} can be described in a clean way with our method. For RAIN, we instead consider quadratic Boolean equations rather than equations over large finite fields \mathbb F_{2^{\ell}}. Specifically, we demonstrate that the special structure of RAIN allows us to set up much more linearly independent quadratic Boolean equations than those obtained only with Courtois-Pieprzyk’s method. Moreover, we further demonstrate that the underlying key-recovery problem in Biscuit (NIST PQC Round 1 Additional Signatures) can also be described by solving a much overdefined system of quadratic equations over \mathbb F_{2^{\ell}}. On the downside, the constructed systems of quadratic equations for these ciphers cannot be viewed as semi-regular, which makes it challenging to upper bound the complexity of the Gr"{o}bner basis attack. However, such a new modelling method can significantly improve the lower bound of the complexity of the Gr"{o}bner basis attacks on these ciphers, i.e., we view the complexity of solving a random system of quadratic equations of the same scale as the lower bound. How to better estimate the upper and lower bounds of the Gr"{o}bner basis attacks on these ciphers based on our modelling method is left as an open problem.
ePrint: https://eprint.iacr.org/2024/786
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 .