Error Correcting Codes in Post-Quantum Cryptography
John-Marc Desmarais · 2020
This thesis gives an overview of the currently most mature key encapsulation mechanisms (KEMs) based on the theory of error correcting codes.It includes an introduction to the theory of error correcting codes in so much as it applies to these systems and how it can be used to encapsulate keys through a public key (PK) cryptosystem.In order to add context to the KEMs, first the required basics of coding theory and a selection of some of the most common error correcting codes are covered.Then, we revisit public key cryptosystems, key encapsulation, and the security threat models that are being used.This is followed by a thorough description of the current NIST candidates for KEM using post-quantum cryptography: Classic McEliece, BIKE, LEDAcrypt, and HQC.We do not include rank metric methods such as ROLLO and RQC, which were NIST candidates until the second round, since they involve different features than those studied in this thesis.The thesis is intended as a survey of current methods being used in this field.We also establish some of the problems which may pose interesting for further research.iii In 1994, Shor [62] came up with a few algorithms for quantum computers that made the previously computationally infeasible problems of factoring large numbers and finding discrete logarithms of numbers in modular rings suddenly feasible.In the subsequent decades, this did not have much effect on the popularity of RSA as a standard for asymmetric encryption.But, now in the advent of quantum computers of increasing bit sizes, this problem has returned.At the same time, the large key sizes required by code-based systems are no longer as much of an issue due to increasing access to high speed networks.In 2016, the National Institute of Standards and Technology (NIST) published a call for proposals for post-quantum cryptosystems that would not be based on the hardness of factoring large numbers or of finding discrete logarithms.This thesis provides a thorough description of the Round 2 Candidates of this competition which are based upon coding theory.These are Classic McEliece, BIKE, LEDAcrypt, and HQC. Thesis StructureChapter 2 covers coding theory as is necessary to understand the current state of the art in code-based cryptography.It begins with a description of the theory of error correcting codes and then describes several of the most popular code systems currently in use including Hamming Codes, BCH codes, Low-Density Parity-Check (LDPC) codes, Medium-Density Parity-Check (MDPC) codes, and Quasi-cyclic (QC) codes.Chapter 3 introduces public key cryptosystems and how coding theory fits into this paradigm.It then presents the leading contenders for code-based KEM in Round 3 of the NIST standardization competition, announced in July 2020, including Classic McEliece, BIKE, and HQC, as well as second round contender LEDAcrypt.For each of these proposals, we describe in detail the problem on which the security is based, the system parameters, key generations, encapsulation, decapsulation, attacks on the system, and a security analysis.Chapter 4 concludes with a summary of the findings and includes some potential areas for future research.