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.
- The Modelling task is the first step. We will start from the original cryptographic problem and design algebraic and logical models equivalent to it. The project will concentrate mainly on multivariate cryptography schemes, with a particular focus on the the remaining candidates in the NIST competion. Other extensions such as coding based-schemes or elliptic curve cryptography might be possible.
- The SAT Solving task is dedicated to designing a SAT solver based on the which will treat XOR-CNF logical formulas. A possible starting point is the WDSAT solver, but ideally we hope to adapt it following the CDCL paradigm.
- The Hybrid Methods task will concentrate on comparing the SAT solving approach to classical algebraic cryptanalysis, mainly Gröbner basis, linearization algorithms, Joux and Vitse's crossbread algorithm etc.
- Finally, the Security Evaluation task will conclude the project. The analysis and experiments performed during the SAT solving and the hybrid methods task will allow us to draw our conclusions regarding the sizes of cryptographic keys.
We are hiring!
- A master internship is available in Amiens. If you are interested, contact us!
