Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

Andrej Bogdanov; Kel Zin Tan; Prashant Nalini Vasudevan

Source-linked AI summary

Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan

arXiv:2610.12913v1Oct 9, 2026cs.CR

TL;DR

Noisy Linear Equations includes cryptographic learning problems for which search-to-decision reductions are useful, but known reductions can lose parameters or scale with the modulus or noise. This paper gives a parameter-preserving reduction based on noise-tolerant perturbations and Fourier recovery. For prime q, it yields polynomial-time LWE reductions even for exponentially large q when σ/q is inverse-polynomial; for composite q, the output can be a list containing a small multiple of the secret.

Problem
Known search-to-decision reductions for Noisy Linear Equations can fail to preserve parameters or have complexity polynomial in the modulus or noise, despite the value of search-to-decision equivalence for cryptographic applications.
Source: §1 · p. 3
Method
The paper constructs a parameter-preserving reduction for noise functions tolerant of small perturbations and uses threshold prediction and Fourier coefficients to recover a list containing a small multiple of the secret.
Source: §1.1 · p. 5
Results
The reduction gives polynomial-time LWE search-to-decision reductions for exponentially large q when σ/q is inverse-polynomial, and for general q can output a list containing c·x for small c.
Source: §1.1 · p. 5
Takeaways & Limitations
For prime q, the reduction preserves the problem parameters while allowing polynomial running time when the modulus is exponentially large and the noise-to-modulus ratio is inverse-polynomial.
Source: §1.1 · p. 5
For composite q, exact recovery from the output list is conditional on q being prime or c being coprime to q, and on having a verification algorithm.
Source: Heavy Fourier Coefficients · p. 8

Abstract

from arXiv · show

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/σ)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $σ$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $σ/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $σ$, and $q$), or had complexity that scaled polynomially with either $σ$ or the largest prime factor of $q$.

1 Introduction

The introduction motivates tight search-to-decision reductions for cryptographic learning problems and identifies parameter loss or dependence on the modulus or noise in prior reductions. The paper presents a parameter-preserving reduction and sketches a threshold-prediction and Fourier-recovery approach.

1 Introduction

Prior reductions either fail to preserve parameters or have complexity polynomial in the modulus or noise magnitude.The paper frames preserving samples and variables, alongside efficient running time, as desirable for tight search-to-decision equivalence.Source: §1 · pp. 3–5

1.1 Our Results

For LWE, the reduction preserves n, m, q, and σ with running time poly(n, m, log q, q/σ); for LWR, it preserves n, m, q, and p with running time poly(n, m, log q, p).Source: §1.1 · p. 5
The LWE reduction remains polynomial-time for exponentially large q when σ/q is inverse-polynomial.Source: §1.1 · p. 5
For B-smooth noise over prime q, search runs in poly(n, m, log q, q/Bε, T) time with success probability ˜Ω(Bε/q).The result applies when small ℓ∞ perturbations leave the noisy-output distribution close to its original distribution.Source: §1.1 · p. 5
For general composite q, the algorithm outputs a list containing c·x for a small c; when c is not coprime to q, this may reveal only partial information about x.The paper identifies exact recovery for arbitrary composite q without secret restrictions as an open problem.Source: §1.1 · pp. 5–6

1.2 Technical Overview

Earlier reductions that iterate over possible secret values incur complexity proportional to the guess domain, while the new approach seeks a threshold signal about an inner product.Source: §1.2 · p. 7, Threshold Distinguisher · p. 7

Threshold Distinguisher.

The threshold predictor perturbs the instance using v yᵀ: small inner products are absorbed by the noise, whereas large ones overwhelm it and randomize the instance.Source: Threshold Distinguisher · p. 7

Heavy Fourier Coefficients.

The predictor has a heavy Fourier coefficient at a small multiple c·x, enabling an algorithm to recover a list containing that multiple.The analysis connects the predictor to a threshold function whose Fourier weight is concentrated on small multiples of x.Source: Heavy Fourier Coefficients · p. 8

2 Preliminaries

The preliminaries define the noisy linear-equations setting and establish assumptions and noise-tolerance properties used by the reduction. They also introduce the Fourier-analysis tools used later.

2 Preliminaries

Noisy Linear Equations is parameterized by sample count, secret dimension, and a noise function; LWE uses discrete-Gaussian error added modulo q.LWR is also defined as a noisy linear-equations problem, with rounding modulus p<q.Source: §2 · p. 9

2.1 Coprime secret

The proof assumes gcd(x,q)=1, an event that occurs with probability exponentially close to 1 for a randomly sampled secret.The probability can be calculated using the Chinese Remainder Theorem.Source: §2.1 · p. 9

2.2 Noise Tolerance

Noise tolerance captures when small perturbations to the noisy codeword Ax leave the output distribution close to the original, a property used by the reduction.The definition considers bounded b and perturbations v in {0,b}^m.Source: §2.2 · p. 10
For LWE, B(R, ε) is at least min(2εσ/√m, floor(q/4 − 1)).The bound is stated for the LWE noise function with parameter σ.Source: §2.2 · p. 10
For LWR, B(R, ε) is at least min(qε/(pm), floor(q/4 − 1)).The bound applies to rounding modulus p<q.Source: §2.2 · p. 11

2.3 Fourier Analysis

The Fourier preliminaries choose a q-ary basis and state the Fourier transform, inverse transform, and Parseval–Plancherel tools.The notation sets ωq=e^(−2πi/q).Source: §2.3 · pp. 11–12

3 Reduction

The reduction converts a decision algorithm for Noisy Linear Equations into a search procedure that outputs a list containing a nonzero multiple of the secret, using a threshold distinguisher and learning significant Fourier coefficients; the completed procedure succeeds with probability Ω(ε′).

3 Reduction

The theorem outputs a list of size ˜O(1/(ε′)^2) containing c·x for some nonzero c ∈ Zq with |c| ≤ 32/(ε′)^2, in time poly(n, m, log q, 1/ε′, T), with success probability Ω(ε′).Source: §3 · p. 12

3.1 Threshold Distinguisher

The threshold distinguisher uses the decision algorithm to distinguish |⟨y, x⟩q| ≤ B from |⟨y, x⟩q| > B.A hybrid argument uses the noisy instance as its initial hybrid and a random instance as its terminal hybrid, yielding a distinguishing gap.Source: §3.1 · pp. 12–13

3.2 Terminal Hybrid

When gcd(x, q) = 1, the terminal hybrid is statistically close to uniform, using the leftover hash lemma and a hybrid argument over the rows of V.The text states that each row’s hash output is close to uniform, with the row-wise distance increased by at most a factor of m across all rows.Source: §3.2 · p. 14

3.3 Correlation With Threshold Function

Using the same parameter definitions as in Lemma 3.2, Corollary 3.8 gives a conditional-probability difference of at least ε/4t: P(y,A,R(Ax))=1 conditioned on S(y,x)=1 minus the probability conditioned on S(y,x)=−1.Source: §3.3 · p. 15

3.5 Fourier analysis of f

For the threshold function f, |f_hat(c)| ≤ 1/(q|sin(cπ/q)|), a bound used to control light and heavy frequency weights.Source: §3.5 · pp. 18–19

3.6 Learning Significant Fourier Coefficients

The Learning Significant Fourier Coefficients algorithm from Akavia, Goldwasser and Safra finds all coefficients of magnitude at least α; there are at most 1/α^2 such coefficients.Source: §3.6 · pp. 19–20
The Fourier-coefficient procedure finds coefficients of magnitude at least α except with probability o(α), in time poly(n, log q, 1/α).Source: §3.6 · p. 20

3.7 Proof of Theorem 3.1

A ε′/2-good instance occurs with probability at least ε′/8, and in such an instance Lemma 3.12 guarantees a nonzero c ∈ Zq.Here ε′ = Bε/2qt; the passage’s bound on |c| is incomplete.Source: §3.7 · p. 20
The reduction outputs a list containing c·x, where c ≠ 0, with size at most ˜O(1/(ε′)^2) and runtime poly(n, m, log q, 1/ε′, T).It applies the algorithm from Theorem 3.15; T is the decision-problem algorithm’s running time.Source: §3.7 · p. 20
The algorithm succeeds with probability ε′/8 − o(ε′) = Ω(ε′), accounting for obtaining a good instance and the list algorithm returning correctly.Source: §3.7 · p. 20

4 Corollaries

The corollaries give LWE/LWR search algorithms that recover a list containing a small multiple of the secret, then state conditions under which exact recovery is possible. Verification can improve the exact-recovery success bound, while matching secret distributions are required for the reduction to extend beyond uniform secrets.

4 Corollaries

For LWE/LWR, a decision distinguisher yields a list containing c·x for small c in time poly(n, m, log q, 1/ε′, T), with ε′ settings tied to the noise model.The corollary assumes a decision algorithm with time T and advantage ε; LWE and LWR use separate ε′ settings tied respectively to σ and the rounding modulus p.Source: §4 · p. 20
The reduction also applies to nonuniform secret distributions when the search and decision problems use the same secret distribution.Source: §4 · p. 21

4.1 Exact Secret Recovery

Exact recovery applies when a recovery algorithm can map c·x and c back to x; stated settings include prime q or secrets satisfying c·max_i x_i ≤ q.For binary-secret LWE, the passage gives uniform x over {0, 1}^n with |c| < q as an example.Source: §4.1 · p. 21
Without verification, randomly selecting a list element and multiplier still permits recovery, with success probability Ω((ε′)^5).When verification is available, it can identify a correct answer among tested recovery outputs.Source: §4.1 · p. 21
With a recovery algorithm, exact search runs in time poly(n, m, log q, 1/ε′, TD, TG) with success probability at least ˜Ω((ε′)^5).The stated corollary assumes both a decision algorithm and a recovery algorithm.Source: §4.1 · p. 22
With verification, exact search has success probability at least ˜Ω(ε′) for the stated LWE and LWR sample/noise regimes.The conditions are n log q ≪ m log(q/σ), σ ≪ o(p) for LWE, and n log q ≪ m log p, p ≪ q for LWR.Source: §4.1 · pp. 21–22

A.1 Hybrid Argument

The proof passage begins by invoking T_V.

A.1 Hybrid Argument

The proof of Proposition 3.5 begins by invoking T_V.Source: §A.1 · p. 24