Search-to-decision reduction speeds up solving noisy linear equations
Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
Cryptography and Security
Summary
The paper looks at a problem where you have a secret code hidden in noisy math puzzles and want to find the secret. The authors present a way to convert the problem of finding the secret into a decision problem without needing extra puzzle samples or big computing costs, even if the numbers involved are very large. This helps with important cryptographic tasks that rely on similar puzzles. Their method works best when the main number, called the modulus, is a prime number.
What this means in practice
- •For cryptographic engineers: Optimize cryptographic schemes based on LWE and LWR by efficiently converting search problems to decision problems without increasing sample sizes, even on large moduli.
- •For security protocol developers: Enable secure design of cryptographic functions relying on noisy linear equations by handling large prime moduli with better performance guarantees.
A theory result. No direct application yet.
Authors
Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan
Abstract
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$.