The math behind the PQC: Syndrome Decoding Problem

Introduction

Cryptographic schemes starring in the NIST standardization process belonging to the code-based cryptography family are constructed from a problem called the Decoding Problem.

Given a code and a vector, the problem consists in finding the closest code word (according to a certain metric) to the vector.

In particular, the Syndrome Decoding Problem (SD) underlies the McEliece (1978) and Niederreiter (1986) cryptosystems that gave rise to the branch of asymmetric cryptography called code-based cryptography.

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.