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

본문 미리보기

arXiv:2610.12913v1 Announce Type: new 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