Search papers, labs, and topics across Lattice.
This paper explores the potential of quantum algorithms, specifically inspired by Regev's work on lattice problems and the hidden dihedral subgroup problem, to address the Learning Parity with Noise (LPN) problem, a challenge critical to post-quantum cryptography. The approach leverages neighborhoods of binary fields to construct a function approximating Simon's promise, aiming to generate new LPN samples. While not directly recovering the secret parity vector, the algorithm aims to iteratively reduce the problem size by generating enough new samples to eliminate variables.
Could quantum algorithms offer a new angle on breaking crypto primitives based on the Learning Parity with Noise (LPN) problem?
The learning parity with noise (LPN) problem is a well-established computational challenge whose difficulty is critical to the security of several post-quantum cryptographic primitives such as HQC and Classic McEliece. Classically, the best-known attacks involve information set decoding methods which are exponential in complexity for parameterisations of interest. In this paper we investigate whether quantum methods might offer alternative approaches. The line of inquiry is inspired by Regev's relating of certain lattice problems to the hidden dihedral subgroup problem. We use neighbourhoods of binary fields to produce a function close to fulfilling Simon's promise with difference equal to the secret parity vector. Although unlikely to recover the secret parity vector directly, running Simon's algorithm essentially produces new LPN samples. This gives the hope that we might be able to produce enough new samples to ignore one or more variables and iteratively reduce the problem. We make no claim that these methods will necessarily be competitive with existing approaches, merely that they warrant deeper investigation.
