Low-Rank Parity-Check codes : Generalization and Improved Decoding for Low-Rank Parity-Check Codes

Abstract

I 1978 foreslo McEliece en kryptografisk nøkkelforankringsmekanisme basert på kodeteori. Det underliggende matematiske problemet med å dekode en tilfeldig lineær kode ble bevist å være NP-fullstendig av McEliece og Berlekamp samme år. På grunn av den overdrevne størrelsen på nøklene ble kryptografi basert på koder ikke tatt i bruk av industrien, som foretrakk algoritmer basert på problemer med heltallsfaktorisering (RSA-kryptosystemet) og det diskrete logaritmeproblemet (Diffie-Hellmannøkkelutveksling). I 1994 beviste Shor at disse to problemene kan løses i polynomtid av en kvantecomputer. Siden da har forskning innen post-quantum kryptografi blitt av større interesse, og code based kryptografi er blant de mest lovende grenene innen dette feltet.

I 1992 foreslo Gabidulin, Paramonov og Tretjakov å bruke rank-metric koder for code based kryptografi. Den største fordelen med å bruke rank-metric koder er at dette gjør det mulig å redusere størrelsen på den offentlige nøkkelen. Problemet med GPT-cryptosystem er at det bruker Gabidulin-koder som er kjent for å ha en sterk algebraisk struktur. Dette systemet ble angrepet i 2005 av Overbeck. Ved å utnytte den rike strukturen til Gabidulin-koder, fant han en måte å gjenopprette en tilsvarende privat nøkkel fra den offentlige nøkkelen. Nylig oppdaget av LRPC-koder i 2013 av Gaborit, Murat, Ruatta og Zemor, åpner veien for nye kryptografiske bruksområder for rank-metric koder. På grunn av mangel på struktur virker disse kodene svært robuste mot angrep for gjenoppretting av nøkkel.

Bidraget til feltet presentert i denne avhandlingen kan deles inn i to retninger: å finne nye dekodable rank-metric koder lignende LRPC-koder og forbedre den eksisterende dekoderalgoritmen for LRPC-koder.

Artikkel I: Ved å blande kontrollparitetsekviasjoner der koeffisientene er i Fq ⊂ Fqm og tilfeldig genererte kontrollparitetsekviasjoner der koeffisientene er i Fqm, oppnår vi en kode med svært god ytelse med hensyn til dekodingsevne. Dessverre ble den samme familien oppdaget tidligere med en lignende konstruksjon i [9]. Artikkel II: Vi generaliserte ideen om LRPC-koder for matrisekoder i Fmq×n ved å utstyre vektorrommet Fmq med et generisk bilinært produkt .T : Fmq x Fmq -> Fmq som spiller rollen som standardproduktet over Fqm. Artikkel III: Vi forbedrer dekodingen av LRPC-koder på en lignende måte som i [10]. Artikkel IV: Vi begrenser oss til en underfamilie av begrensede grad LRPC-koder, dvs. LRPC-koder som tillater en kontrollparitetsmatrise der inngangene er i et delrom Vα,d = ⟨1, α, . . . , αd−1⟩Fq ⊆ Fqm. Denne begrensningen gjør det mulig for oss å betydelig forbedre feilkorrigeringskapasiteten for denne typen koder.

Avhandlingen er en samling av fire artikler og er strukturert som følger. I det første kapittelet går vi gjennom noen essensielle forutsetninger innen diskret matematikk og kodeteori, vi forklarer hva rank-metric koder er, beskriver Gabidulin-koder, GPT-cryptosystem og det nevnte angrepet fra Overbeck. I det andre kapittelet beskriver vi LRPC-koder og den kryptografiske protokollen ROLLO som bruker dem. I kapittel 3 presenterer vi kort de viktigste ideene og bidragene for hver av de fire artiklene. Til slutt er kapittel 4 en samling av fullversjonen av de fire artiklene beskrevet i det tredje kapittelet.

In 1978 McEliece proposed a cryptographic key encapsulation mechanism based on coding theory. The underlying mathematical problem of decoding a random linear code was proven to be NP-complete by McEliece and Berlekamp in the same year. Due to the excessive size of the keys, code-based cryptography was not adopted by the industry which favoured algorithms based on the problems of integer factorization (RSA cryptosystem) and the discrete logarithm problem (Diffie-Hellman key exchange). In 1994 Shor proved that these two problems can be solved in polynomial time by a quantum computer. Since then, research in post-quantum cryptography has become of wider interest and code-based cryptography is among the most promising branches of this field.

In 1992 Gabidulin, Paramonov and Tretjakov proposed to use rank-metric codes for codebased cryptography. The main advantage of using rank-metric codes is that this allows to reduce the size of the public key. The problem with the GPT cryptosystem is that it makes use of Gabidulin codes which are known to have a strong algebraic structure. This scheme was attacked in 2005 by Overback. Exploiting the rich structure of Gabidulin codes, he found a way to recover an equivalent private key from the public key. More recently, the discovery of LRPC codes in 2013 by Gaborit, Murat, Ruatta and Zemor, open the way to new cryptographic applications for rank-metric codes. Due to their lack of structure, these codes seem very robust against a key recovery attack.

The contribution to the field presented in this thesis can be divided in two directions: finding new decodable rank-metric codes similar to LRPC codes and improve the existing decoding algorithm for LRPC codes. • Paper I: mixing parity-check equations whose coefficients are in Fq ⊂ Fqm and randomly generated parity-check equations whose coefficients are in Fqm, we obtain a code with a very good performance in terms of decoding capability. Unfortunately, with a similar construction, the same family was already discovered in [9]. • Paper II: we generalized the idea of LRPC codes for matrix codes in Fmq×n equipping the vector space Fmq with a generic bilinear product .T : Fmq x Fmq -> Fmq which plays the role of the standard product over Fqm. • Paper III: we improve the decoding of LRPC codes in a similar fashion as in [10]. • Paper IV: we restrict ourselves to a subfamily of bounded-degree LRPC codes, i.e. the LRPC codes admitting a parity-check matrix whose entries are all in a subspace Vα,d = ⟨1, α, . . . , αd−1⟩Fq ⊆ Fqm. This restriction allows us to greatly improve the error correction capability for this type of codes.

The thesis is a collection of four papers and is structured as follows. In the first chapter, we go through some essential preliminaries in discrete mathematics and coding theory, we explain what rank-metric codes are, describe the Gabidulin codes, the GPT cryptosystem and the aforementioned attack due to Overback. In the second chapter, we describe the LRPC codes and the cryptographic protocol ROLLO which makes use of them. In Chapter 3, we briefly present the main ideas and contributions for each of the four papers. Finally, Chapter 4 is a collection of the full version of the four papers described in the third chapter.