On the use of structured codes for cryptographic applications

The upcoming advent of quantum computers poses a serious threat on most of modern public key cryptosystems, which are commonly based on hard mathematical problems such as the integer factorization or the discrete logarithm. It has indeed been proven that quantum algorithms can be used to solve such problems in polynomial time. Thus, we strongly need to move to a class of new cryptographic primitives, constructed upon mathematical problems for which no efficient quantum solver exists. For this reason, the corresponding schemes are normally defined post-quantum. Code-based cryptosystems are among the most promising ones. Security of such schemes is based on hard problems arising from the coding theory, such as that of decoding a random linear code, which is a well known NP-complete problem, for which no efficient quantum solver is known. Despite a largely recognized security, the main drawback of code-based cryptosystems is represented by the large public key sizes. Indeed, in such schemes the public key is the representation of an error correcting code, whose length must be sufficiently large to guarantee correction of a non trivial amount of errors. The most meaningful example is that of the original McEliece cryptosystem, named after its inventor Robert McEiece that, in 1978, de facto initiated the area of code-based cryptography. The original McEliece proposal, based on Goppa codes, is still essentially unbroken, and additionally yields to a very low algorithmic complexity. However, the scheme, due to its large public key size, has experienced very few practical applications. In this work we investigate solutions to address the public key size problem. A common strategy is that of replace the original choice of Goppa codes with a more convenient family of codes (for instance, codes correcting more errors or admitting a compact representation). A well assessed strategy to face this issue is that of relying on codes having a large and known automorphism group: in such cases, indeed, the whole code can be completely represented by a bunch of its codewords. Thus, when codes of this type are used to derive the public key, compactness in the code representation may be achieved, with the obvious result of reducing the public key size. However, this choice may represent a security flaw, since it the end it consists in adding some constraints to the employed code which, to enable correct correction, necessarily needs to already have a significant amount of structure. In a few words, this choice somehow reduces the security of the scheme, in a way that depends not only on the chosen family of codes, but also on the strength of the imposed geometric symmetry. While this fact certainly represents a major issue for some families of algebraic codes, it is not the case for pseudo-random codes, i.e., codes that admit a random-like fashion design. The most significant case is that of Low-Density Parity-Check (LDPC) codes, codes whose only constraint is that of being represented through a sparse parity-check matrix (i.e., with a low number of set entries). This property guarantees the existence of efficient probabilistic decoding techniques, that can correct non trivial amount of errors with an algorithmic complexity that grows linearly with the code length. When such codes are employed, a regular geometrical structure can be safely introduced to obtain very compact keys and, at the same, high algorithmic efficiency, without no significant security reduction. However, with respect to algebraic codes, LDPC codes are characterized by a completely new venue of attacks, which come from the sparse inner structure and from the intrinsic probabilistic nature of the decoder. In this work we investigate the use of such codes in modern public key cryptosystems. We describe the main properties of LDPC decoding techniques, and provide methodologies to assess their error correction performances. We describe cryptographic primitives based on LDPC codes and analyze both classical and modern cryptanalysis techniques.

L'imminente avvento dei computer quantistici rappresenta una seria minaccia per la maggior parte dei moderni sistemi crittografici a chiave pubblica, che sono comunemente basati su problemi matematici difficili come la fattorizzazione intera o il logaritmo discreto. È stato infatti dimostrato che gli algoritmi quantistici possono essere utilizzati per risolvere tali problemi in tempo polinomiale.