4 papers
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…
Hardness Amplification for (Sparse) LPN
Divesh Aggarwal, Rishav Gupta, Li Zeyong
We prove new hardness amplification results for Learning Parity with Noise () and its sparse variants. In , the goal is to recover a secret $\v…
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
Rishav Gupta, Bingkai Lin, Xin Zheng
We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (), yields tight lower bounds for approximating the parameterized Maximum…
Mind the Gap? Not for SVP Hardness under ETH!
Divesh Aggarwal, Rishav Gupta, Aditya Morolia +1
We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al.\ \cite{BHIRW24}, wh…