IEEE ITW 2021, Virtually from Kanazawa, Japan
Currently-used public-key cryptosystems based on number-theoretic problems are threatened by the possibility that large-scale quantum computers will be built in the near future; Shor’s algorithm is able to solve these seemingly hard problems in polynomial time on such computers. In this context, the National Institute of Standards and Technology (NIST) has initiated a standardization process for public key encryption (PKE) schemes, key encapsulation mechanisms (KEM), and signatures. The standardization process has now reached Round 3, where lattice-based and code-based cryptography play a prominent role. These code-based cryptosystems include most prominently the classical McEliece system. Their security is based on hard computational problems in coding theory, and encryption and decryption often correspond to en- and decoding of an error-correcting code.
The goal of this tutorial is to provide an overview of important existing code-based cryptosystems, their security, and current challenges in the area of code-based cryptosystems. We will thereby consider amongst others systems based on Goppa, Moderate-Density-Parity-Check (MDPC), and rank-metric codes.