The mathematics behind PQC: the codes

Introduction

In addition to lattices, the foundation of lattice-based cryptography, another mathematical structure used to construct post-quantum cryptography schemes is error-correcting codes, more briefly codes.

The codes originated in the context of telecommunications to detect and correct errors that may occur in the transmission of a message through a noisy communication channel; their task is to allow the recipient to read the message as it was sent even if it has changed during transmission. At the same time, they are now widely used in the field of post-quantum cryptography: in fact, computational problems that are difficult even for a quantum computer to solve can be built on them.

Cryptosystems defined on such problems belong to the class called code-based cryptography. This branch of asymmetric cryptography originated in the late 1970s with the public-key encryption scheme of Robert McEliece (1978), later seeing other relevant achievements such as the work (dual version of McEliece) of Harald Niederreiter (1986) and the digital signature scheme devised by Courtois, Finiasz and Sendrier (2001).

Code-based cryptography is thus coeval with the much better-known RSA, and it is precisely because of its longevity that it has proven to be reliable over time, going so far as to be a major player in the NIST standardization process.

Click the link to read the full article.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Giuseppe D’Alconzo, graduated in Mathematics with a specialization in Cryptography at the University of Trento, in 2019 he carried out an internship at Telsy, dealing with Multiparty Computation and Attribute-Based Encryption. He is currently a PhD student in Pure and Applied Mathematics at the Politecnico di Torino, with a “Post-Quantum Cryptography” scholarship within the UniversiTIM program and in collaboration with the Telsy Research Group.