Publication
Error-correcting codes play a crucial role in communication systems, ensuring the accurate and reliable transmission of data in the presence of noise and interference. Informally, these codes encode messages by adding redundancy in such a way that errors during transmission can be detected and corrected. A large family of error-correcting codes consists of those that are linear, namely those that can be regarded as finite-dimensional vector spaces over a finite field.
A fundamental property of random linear codes is the provable hardness of decoding noisy codewords without knowledge of the error distribution, thereby making code-based cryptosystems attractive for post-quantum cryptography. Among the post-quantum alternative candidates selected by NIST, code-based candidates usually feature an algebraic structure richer than random linear codes, yet the most efficient attacks, be them classical or quantum, remain generic and exponential in the size of the parameters.
The first part of the thesis is dedicated to constructing post-quantum cryptographic primitives. More precisely, we design a hash proof system from a code-based post-quantum encryption scheme, and derive, almost for free, a witness encryption scheme and a password-based authenticated key exchange protocol. To address the lack of a generic hash proof system, we also describe a purely arithmetic construction of a post-quantum witness encryption scheme whose security is related to lattice problems.
The second part of the thesis focuses on quantum algorithms solving the decoding problem and explores their effectiveness, both in time and memory, against similar problems. More concretely, we design and improve quantum attacks against the Learning Parity with Noise problem, as well as the asymptotic complexity of quantum information set decoding algorithms.