Code-Based Cryptography – PN-III-P1-1.1-PD-2019-0285

CodeBasedCrypto is a two year research project funded by the Romanian Ministry of Education and Research, CNCS- UEFISCDI, project number PN-III-P1-1.1-PD-2019-0285, within PNCDI III.

Its major goal is to understand in depth the security of the main public key cryptosystems, based on the theory of error correcting codes. More exactly, during this two years period we will focus our attention on evaluating the security, from a theoretical as well as practical point of view, of the main candidates for the NIST standardization process on post-quantum cryptography.

We also keep an updated ResearchGate webpage of this project.

Scope and objectives

In this project we propose to study here one of the solutions to post-quantum cryptography, that will probably be used by all Internet users in the long-term. This proposal in motivated by the recent advances in Quantum Computing, and by the standardization process initiated by the NIST for quantum secure public key cryptography. Major actors from the cryptographic and cybersecurity community emphasize the urgency of moving towards quantum safe cryptography, reason why we will analyze the security of most promising code-based encryption schemes.

This project has two major objectives: firstly, to determine and analyze other types of weak keys in state-of-the-art encryption schemes, and secondly, to cryptanalyze, using more efficient algorithms, code-based encryption schemes based on algebraic codes such as the binary Goppa codes, the Reed-Muller codes, or the polar codes. In order to achieve our goals, we propose to study the problem of code equivalence for the aforementioned code families and use the latest formalism for describing polar and Reed-Muller codes as Decreasing Monomial codes. We will use various techniques such as, squaring, puncturing, shortening, and test our arguments by developing scripts using the MAGMA software.

The outputs of this project are the following: a better understanding and knowledge regarding the security of the schemes, articles regarding the security of these protocols published in proceedings of International conferences and journals, and presentations of our results at national and international conferences.

Achievements and Impact

We have a better understanding of the vulnerabilities and of the physical security of the Classic McEliece proposal. We have managed to propose two hybrid attacks, in which the encrypted message was decrypted by an adversary having access to some physical components where the encryption was performed. The physical part of the attacks were either LASER-fault injection or Side-channel attacks, while the algorithmic part was dealing with a modified syndrome decoding problem, called Integer Syndrome Decoding Problem. (Profiled Side-channel attacks on McEliece, Message recovery using laser fault injection on McEliece, Integer syndrome decoding problem). More on this topic and publications/presentations can be found in List of Publications and Hybrid attacks on Classic McEliece.
We revealed the structure of self-dual monomial codes and their impact in cryptography. We have discovered new properties of self-dual monomial codes, such as square code dimension, shorten/ punctured code properties, discrete derivative of the monomial code. With these properties at hand we proposed to applications related to cryptography: a thinner distinguisher for the McEliece variant based on this type of codes, as well as a security analysis of this scheme. Our result point out a similar level of security as for the most secure parameters in the Sidelnikov’s cryptosystem. (Structural properties of self-dual monomial codes). More on this topic and publications/presentations can be found in List of Publications and Monomial codes.
We have a larger algebraic framework that explains algorithms from the Information Set Decoding class. An algebraic formalism based on the Generalized Inverse of a matrix for solving the syndrome decoding problem. The formalism explains almost all ISD techniques and the power of linear algebra. The main advantage of this framework is that allows for a unified vision of the coding theory problems. We have also determined a tight reduction between the Syndrome Decoding optimization problem and MIN-SAT affine, a well-known and studied boolean problem. (GI based decoding). More on this topic and publications/presentations can be found in List of Publications and Generalized Inverse Based Decoding.
We have a new class of polynomial solvable modified syndrome decoding problems. Previous known results on the complexity of the Syndrome Decoding Problem showed intervals of weight where the problem becomes easy. By means of GI-Decoding we have enlarged the interval with a square root of the code length (verified in simulations). Also, recent publications show that Information Set Decoding with additional hints (obtained by some side-channel measurements) could decrease the complexity of solving Syndrome Decoding Problem. However, these improvements are small and the overall complexity remains exponential in the code parameters. We have demonstrated that when the side information is an integer estimation of the syndrome vector we have an algorithm that solves the modified version of the Syndrome Decoding Problem in polynomial time. This results has a significant implication, in the sens that such extra-information should always be avoided, by any means. More on this topic and publications/presentations can be found in List of Publications and Modified syndrome decoding problem.
There is a generalization of the concept of weak keys for BIKE cryptosystem, keys that could be used as backdoors. We have seen that existing weak keys were already subject to some backdoor insertions in the original QC-MDPC cryptosystem. We have extended the concept of weak keys, to some new configurations based on an algebraic description. The concept uses a modified Extended Euclidean Algorithm and based on some initial conditions it allows to retrieve a private key from a public key of the BIKE scheme in polynomial time. The conditions are rather restrictive, in the sense that the probability of having such configurations oi rather small when sampling is done uniformly at random from the set of private keys. However, it points out that backdoors based on weak keys are significantly easier to built that expected. Also, avoiding such vulnerable keys can be done in the implementation process, by modifying the key generation step integrating a verificat. The work is in progress and a future preprint article will be made available.

Conferences

IEEE ISIT, June 2022, Espoo, Finland (1 article)
CBCrypto 2022, May 2022, Trontheim, Norway (2 abstracts)
CryptArchi, May 2022, Porquerolles, France (1 abstract)
ICCCC, May 2022, Oradea, Romania (1 article)
WSTC, Mars 2022, Sinaia, Romania (2 contributed talks)
Eurocrypt, May 2021, Zagreb, Croatia (1 article)
SOFa, December 2022, Arad, Romania (4 articles)