3 papers
cs.CR2026
Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan
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…
cs.CR2026
Towards Worst-case Hardness for Low-Noise LPN
Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen +2
The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives…
cs.CR2025
Improved Search-to-Decision Reduction for Random Local Functions
Kel Zin Tan, Prashant Nalini Vasudevan
A random local function defined by a -ary predicate is one where each output bit is computed by applying to randomly chosen bits of its input. These represent natura…