Noah Stephens-Davidowitz

IEEE Trans. Inf. Theory, 2025

Recursive lattice reduction - A framework for finding short lattice vectors.

[BibT_eX]

[DOI]

Thomas Espitau

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions.

[BibT_eX]

[DOI]

Surendra Ghentiyala

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Guarding the Signal: Secure Messaging with Reverse Firewalls.

[BibT_eX]

[DOI]

Bernardo Magri

Yiannis Tselekounis

Proceedings of the Advances in Cryptology - CRYPTO 2025, 2025

2024

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices.

[BibT_eX]

[DOI]

Surendra Ghentiyala

Electron. Colloquium Comput. Complex., 2024

More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More.

[BibT_eX]

[DOI]

Surendra Ghentiyala

Proceedings of the Approximation, 2024

2023

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Lattice Problems beyond Polynomial Time.

[BibT_eX]

[DOI]

Vinod Vaikuntanathan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Just How Hard Are Rotations of $\mathbb {Z}^n$? Algorithms and Cryptography with the Simplest Lattice.

[BibT_eX]

[DOI]

Atul Ganju

Pura Peetathawatchai

Proceedings of the Advances in Cryptology - EUROCRYPT 2023, 2023

Revisiting Time-Space Tradeoffs for Function Inversion.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

On Seedless PRNGs and Premature Next.

[BibT_eX]

[DOI]

Sandro Coretti

Harish Karthikeyan

Stefano Tessaro

Proceedings of the 3rd Conference on Information-Theoretic Cryptography, 2022

2021

No Time to Hash: On Superefficient Entropy Accumulation.

[BibT_eX]

[DOI]

Zhiye Xie

IACR Cryptol. ePrint Arch., 2021

Just how hard are rotations of ℤn? Algorithms and cryptography with the simplest lattice.

[BibT_eX]

[DOI]

Atul Ganju

Pura Peetathawatchai

IACR Cryptol. ePrint Arch., 2021

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms.

[BibT_eX]

[DOI]

CoRR, 2021

Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else).

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A 2n/2-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP.

[BibT_eX]

[DOI]

Zeyong Li

Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021

No Time to Hash: On Super-Efficient Entropy Accumulation.

[BibT_eX]

[DOI]

Zhiye Xie

Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021

Online Linear Extractors for Independent Sources.

[BibT_eX]

[DOI]

Zhiye Xie

Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

On the Hardness of Average-Case k-SUM.

[BibT_eX]

[DOI]

Zvika Brakerski

Vinod Vaikuntanathan

Proceedings of the Approximation, 2021

2020

A 2n/2-Time Algorithm for √n-SVP and √n-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP.

[BibT_eX]

[DOI]

Zeyong Li

CoRR, 2020

Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP.

[BibT_eX]

[DOI]

Tamalika Mukherjee

Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020

Slide Reduction, Revisited - Filling the Gaps in SVP Approximation.

[BibT_eX]

[DOI]

Jianwei Li

Phong Q. Nguyen

Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020

Extractor Lower Bounds, Revisited.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Kissing Numbers and Transference Theorems from Generalized Tail Bounds.

[BibT_eX]

[DOI]

Stephen D. Miller

SIAM J. Discret. Math., 2019

SETH-Hardness of Coding Problems.

[BibT_eX]

[DOI]

Vinod Vaikuntanathan

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Generalizations of Banaszczyk's transference theorems and tail bound.

[BibT_eX]

[DOI]

Stephen D. Miller

IACR Cryptol. ePrint Arch., 2018

(Gap/S)ETH hardness of SVP.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP).

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

New (and Old) Proof Systems for Lattice Problems.

[BibT_eX]

[DOI]

Navid Alamati

Chris Peikert

Proceedings of the Public-Key Cryptography - PKC 2018, 2018

2017

On the Gaussian Measure Over Lattices.

[BibT_eX]

[DOI]

PhD thesis, 2017

An Inequality for Gaussians on Lattices.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Pseudorandomness of ring-LWE for any ring and modulus.

[BibT_eX]

[DOI]

Chris Peikert

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A reverse Minkowski theorem.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

On the Quantitative Hardness of CVP.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Implementing BP-Obfuscation Using Graph-Induced Encoding.

[BibT_eX]

[DOI]

Shai Halevi

Tzipora Halevi

Victor Shoup

Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017

2016

Discrete Gaussian Sampling Reduces to CVP and SVP.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Lattice Distortion Problem.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines.

[BibT_eX]

[DOI]

Ilya Mironov

Proceedings of the Advances in Cryptology - CRYPTO 2016, 2016

Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Cryptographic Reverse Firewalls.

[BibT_eX]

[DOI]

Ilya Mironov

Proceedings of the Advances in Cryptology - EUROCRYPT 2015, 2015

2014

Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling.

[BibT_eX]

[DOI]

CoRR, 2014

How to Eat Your Entropy and Have It Too - Optimal Recovery Strategies for Compromised RNGs.

[BibT_eX]

[DOI]

Adi Shamir

Daniel Wichs

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

On the Closest Vector Problem with a Distance Guarantee.

[BibT_eX]

[DOI]