8 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…
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…
Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
Divesh Aggarwal, Dexter Kwan
Worst-case to average-case reductions are a cornerstone of complexity theory, providing a bridge between worst-case hardness and average-case computational difficulty. While recent…
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable c…
Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters
Divesh Aggarwal, Tomasz Kazana, Maciej Obremski
Algebraic Manipulation Detection (AMD) codes is a cryptographic primitive that was introduced by Cramer, Dodis, Fehr, Padro and Wichs. They are keyless message authentication codes…