Algebraic cryptanalysis for post-quantum cryptography

Welcome on the page of ANR project POSTCRYPTUM.

This project is funded by Agence Nationale de la Recherche, the AID and the DGA , through the ASTRID 2020 program.

Principal investigator Sorina Ionica

Project duration 01-01-2021 au 31-12-2023.

Project overview

Among well-established techniques in cryptanalysis, algebraic attacks are methods to describe the scheme as a system of polynomial equations, and consequently reduce its security to the hardness of solving the associated system. POSTCRYPTUM aims at designing efficient algebraic attacks, for several classes of cryptosystems which may be modelled as a binary polynomial system. Several methods may be considered for solving multivariate polynomial systems over finite fields. One approach are Gröbner basis algorithms, which proved themselves to be a powerful tool for cryptanalysis in 2003, when they were used to solve a HFE challenge. Since then, they have been extensively used in cryptography. However, the Gröbner basis algorithm has exponential complexity and in the binary case, experimental results on multivariate cryptography schemes have shown that Bouillaguet et al.'s exhaustive search and Joux-Vitse's crossbread method give better results than the Gröbner basis approach.

In addition, we note that the case of boolean systems may also be treated as a satisfiability problem, since boolean polynomials can be used to represent constraints. Once this transformation is done, one can use SAT solvers to enumerate solutions for the corresponding logical formula. In this latter case, some promising results have been obtained in Monika Trimoska's thesis, on the index calculus attack for elliptic curves discrete logarithm. The approach is not new, since attempts to use SAT solvers for cryptanalytic problems have been done in the past for other cryptosystems, mainly for stream ciphers. However, satisfiability techniques remain little known and little explored by cryptographers. Moreover, most SAT solvers were designed to answer industrial large size problems and they completely ignore the algebraic nature of cryptographic instances.

POSTCRYPTUM brings together researchers specialized in cryptography and satisfiability, with the common goal of designing new dedicated methods for solving binary polynomial systems of cryptographic origin.

Project main lines

This project is subdivided in four tasks.

We are hiring!