We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.
We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.
The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.
The Module Learning With Errors ( M-LWE ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that M-LWE with uniform η -bounded secret for any 1≤η≪q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of M-LWE with large uniform secret and uniform η -bounded error is at least as hard as the standard M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on η . The latter result can be extended to provide the hardness of search M-LWE with uniform η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.
We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).
The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction is incomparable to the classical reduction in terms of sample complexity and query complexity. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over ℤq where q is a prime. In short, this theorem states that, if a hardcore predicate a・s (mod q) can be predicted with probability distinctly greater than (1/q) with respect to a uniformly random a ∈ ℤqn, then it is possible to determine s ∈ ℤqn.
We introduce a continuous analogue of the Learning with Errors (LWE) problem,
which we name CLWE. We give a polynomial-time quantum reduction from worst-case
lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees
to those of LWE. Alternatively, our result can also be seen as opening new
avenues of (quantum) attacks on lattice problems. Our work resolves an open
problem regarding the computational complexity of learning mixtures of
Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As
an additional motivation, (a slight variant of) CLWE was considered in the
context of robust machine learning (Diakonikolas et al.~FOCS 2017), where
hardness in the statistical query (SQ) model was shown; our work addresses the
open question regarding its computational hardness (Bubeck et al.~ICML 2019).
This note describes a key exchange method based on the ring-LWE (RLWE)
assumption. It builds upon several results, including Regev's
landmark quantum reduction from certain worst case lattice problems
(approx. GapSVP and SIVP) to random instances of the search variant of
a particular learning problem (LWE). It also builds on the follow on
work of Lyubashevsky, Peikert and Regev on the average case hardness
of the RLWE search variant for polynomially bounded numbers of RLWE
samples, along with novel applications of automorphism groups in
number fields for a RLWE search to decision reduction (thereby
demonstrating pseudorandomness of RLWE in these number fields).
Subsequently, these results were adopted for the construction of
Diffie-Hellman like key exchange methods by Peikert, and then by
Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who
proposed efficient variants of such protocols. Subsequent work by
Peikert proposed another efficient variant, phrased as a key
encapsulation method, incorporating a low bandwidth reconciliation
technique allowing two parties to exactly agree on a uniformly
distributed secret value from noisy RLWE instances. This was followed
by a concrete instantiation with parameter sets by Bos, Costello,
Naehrig, Stebila, followed by another instantiation by Alkim, Ducas,
Poppelmann and Schwabe with the same ring polynomial but a smaller
modulus and a different reconciliation method. Unlike most other
public key cryptography based key exchange methods, it is believed
that RLWE based key exchange would remain secure in the event that an
adversary is able to build a quantum computer. This document is a
product of the Crypto Forum Research Group (CFRG).