Solving the Learning Parity with Noise Problem Using Quantum Algorithms

The Learning Parity with Noise (LPN) problem is a famous cryptographic problem consisting in recovering a secret from noised samples. This problem is usually solved via reduction techniques, that is, one reduces the original instance to a smaller one before substituting back the recovered unknowns and starting the process again. There has been an extensive amount of work where time-memory trade-offs, optimal chains of reductions or different solving techniques were considered but hardly any of them involved quantum algorithms. In this work, we are interested in studying the improvements brought by quantum computers when attacking the LPN search problem in the sparse noise regime. Our primary contribution is a novel efficient quantum algorithm based on Grover’s algorithm which searches for permutations achieving specific error patterns. This algorithm non-asymptotically outperforms the known techniques in a low-noise regime while using a low amount of memory.