International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit

Authors:
Fukang Liu , Tokyo Institute of Technology
Mohammad Mahzoun , Eindhoven University of Technology
Willi Meier , FHNW
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: Overdefined polynomial systems have the potential to lead to reduced complexity in solving procedures. 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.
BibTeX
@inproceedings{asiacrypt-2024-34564,
  title={Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit},
  publisher={Springer-Verlag},
  author={Fukang Liu and Mohammad Mahzoun and Willi Meier},
  year=2024
}