225 citations · 278 across the 25 of their papers we have counts for
31 papers
Secret Sharing from Non-Extractable Randomness
Divesh Aggarwal
Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key…
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 $\ve…
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…
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…
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…
Lattice Based Crypto breaks in a Superposition of Spacetimes
Divesh Aggarwal, Shashwat Agrawal, Rajendra Kumar
We explore the computational implications of a superposition of spacetimes, a phenomenon hypothesized in quantum gravity theories. This was initiated by Shmueli (2024) where the au…
Engineering an Efficient Approximate DNF-Counter
Mate Soos, Uddalok Sarkar, Divesh Aggarwal +3
Model counting is a fundamental problem in many practical applications, including query evaluation in probabilistic databases and failure-probability estimation of networks. In thi…
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
Recursive lattice reduction -- A framework for finding short lattice vectors
Divesh Aggarwal, Thomas Espitau, Spencer Peters +1
We propose a recursive lattice reduction framework for finding short non-zero vectors or dense sublattices of a lattice. The framework works by recursively searching for dense subl…
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar
Recent work [BGS17,ABGS19] has shown SETH hardness of CVP in the norm for any that is not an even integer. This result was shown by giving a Karp reduction from -SA…
Quantum secure non-malleable codes in the split-state model
Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain
Non-malleable-codes introduced by Dziembowski, Pietrzak and Wichs [DPW18] encode a classical message in a manner such that tampering the codeword results in the decoder either…
Extractors: Low Entropy Requirements Colliding With Non-Malleability
Divesh Aggarwal, Eldon Chung, Maciej Obremski
The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories: (1) Constructions where one source has min-entropy…
Quantum Measurement Adversary
Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain +1
Multi-source-extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. Quantum multi-source-extractors were considered by Kasher and Kemp…
Dimension-Preserving Reductions Between SVP and CVP in Different -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +2
We show a number of reductions between the Shortest Vector Problem and the Closest…
A -Time Algorithm for -SVP and -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
We show a -time algorithm that finds a (non-zero) vector in a lattice with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathca…
A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices
Divesh Aggarwal, Eldon Chung
Blömer and Seifert showed that is NP-hard to approximate by giving a reduction from to for constant approximation factors as lo…
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…
Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev +1
We show a number of fine-grained hardness results for the Closest Vector Problem in the norm (), and its approximate and non-uniform variants. First, we sh…
Slide Reduction, Revisited---Filling the Gaps in SVP Approximation
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen +1
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the f…
An improved constant in Banaszczyk's transference theorem
Divesh Aggarwal, Noah Stephens-Davidowitz
$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that \[ μ(\lat) λ_1(\lat^*) < \big( 0.1275 + o(1) \big) \cdot n \…
Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Divesh Aggarwal, Priyanka Mukhopadhyay
Blomer and Naewe[BN09] modified the randomized sieving algorithm of Ajtai, Kumar and Sivakumar[AKS01] to solve the shortest vector problem (SVP). The algorithm starts with $N = 2^{…
(Gap/S)ETH Hardness of SVP
Divesh Aggarwal, Noah Stephens-Davidowitz
We prove the following quantitative hardness results for the…