Estimation of the Hardness of the Learning with Errors Problem with a Restricted Number of Samples.

Daniele Micciancio

Andrej Bogdanov, Siyao Guo, Daniel Masny +2 more

We show the following reductions from the learning with errors problem (LWE) to the learning with rounding problem (LWR): (1) Learning the secret and (2) distinguishing samples from random strings is at least as hard for LWR as it is for LWE for efficient algorithms if the number of samples is no larger than O(q/Bp), where q is the LWR modulus, p is the rounding modulus, and the noise is sampled from any distribution supported over the set {−B,..., B}. Our second result generalizes a theorem of Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013) and provides an alternate proof of it. Unlike Alwen et al., we do not impose any number theoretic restrictions on the modulus q. The first result also extends to variants of LWR and LWE over polynomial rings. As additional results we show that (3) distinguishing any number of LWR samples from random strings is of equivalent hardness to LWE whose noise distribution is uniform over the integers in the range [−q/2p,..., q/2p) provided q is a multiple of p and (4) the “noise flooding” technique for converting faulty LWE noise to a discrete Gaussian distribution can be applied whenever q = Ω(B

Robert Fitzpatrick

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois +1 more

The Module Learning With Errors ( $$\text {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 $$\text {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 $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret for any $$1 \le \eta \ll q$$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {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 $$\text {M-LWE}$$ with large uniform secret and uniform $$\eta $$ -bounded error is at least as hard as the standard $$\text {M-LWE}$$ problem, if the number of samples m is close to the module rank d and with further restrictions on $$\eta $$ . The latter result can be extended to provide the hardness of search $$\text {M-LWE}$$ with uniform $$\eta $$ -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.

Elena Grigorescu, Lev Reyzin, Santosh Vempala

Kishore K

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.