Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Field Switching in Learning Parity with Noise

Marshall Ball, Saroja Erabelli, Mingyuan Wang, Zhiheng Wang

Published Nov 5, 2026• 0 citations
Publisher
DOI
10.1007/978-3-032-43588-0_14

Related papers

Solving the Learning Parity with Noise Problem Using Quantum Algorithms

Bénédikt Tran, Serge Vaudenay B

Lecture notes in computer science•Jan 1, 2022•1 citation

On Noise-Tolerant Learning of Sparse Parities and Related Problems

Elena Grigorescu, Lev Reyzin, Santosh Vempala

Lecture notes in computer science•Jan 1, 2011•23 citations

An improved algorithm for learning sparse parities in the presence of noise

Di Yan, Yu Yu, Hanlin Liu +2 more

Theoretical Computer Science•Apr 30, 2021•5 citations

Feature learning via mean-field Langevin dynamics: classifying sparse parities and beyond

Taiji Suzuki, Denny C.-Y. Wu, Kazusato Oko +1 more

neural information processing systems•Jan 1, 2023•0 citations

Low Noise LPN: Key dependent message secure public key encryption an sample amplification

Nico Döttling

Cryptographic schemes based on the learning parity with noise (LPN) problem have several very desirable aspects: low computational overhead, simple implementation and conjectured post‐quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this study, the authors construct the first standard model public key encryption scheme with key dependent message security based solely on the low‐noise LPN problem. Additionally, they establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, they show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

IET Information Security•Apr 11, 2016•2 citations

Quantum approaches to learning parity with noise

Daniel Shiu

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.

arXiv:2602.19819•Feb 23, 2026•0 citations
Cryptographic schemes based on the learning parity with noise (LPN) problem have several very desirable aspects: low computational overhead, simple implementation and conjectured post‐quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this study, the authors construct the first standard model public key encryption scheme with key dependent message security based solely on the low‐noise LPN problem. Additionally, they establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, they show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended 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.