Noah Stephens-Davidowitz

81 papers A* 12A 8Journal 44Unranked 16
YearRankTypeTitle / Venue / Authors
2026 J jnl
Advanced cryptography from lattice isomorphism - new constructions of IBE and FHE.
IACR Cryptol. ePrint Arch.
Huck Bennett, Zhengnan Lai, Noah Stephens-Davidowitz
2025 J jnl
Difficulties Constructing Lattices With Exponential Kissing Number From Codes.
IEEE Trans. Inf. Theory
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2025 — conf
Guarding the Signal: Secure Messaging with Reverse Firewalls.
CRYPTO (8)
Yevgeniy Dodis, Bernardo Magri, Noah Stephens-Davidowitz, Yiannis Tselekounis
2025 J jnl
Guarding the Signal: Secure Messaging with Reverse Firewalls.
IACR Cryptol. ePrint Arch.
Yevgeniy Dodis, Bernardo Magri, Noah Stephens-Davidowitz, Yiannis Tselekounis
2025 J jnl
Range avoidance, Arthur-Merlin, and TFNP.
Electron. Colloquium Comput. Complex.
Surendra Ghentiyala, Zeyong Li, Noah Stephens-Davidowitz
2025 — conf
Recursive lattice reduction - A framework for finding short lattice vectors.
SOSA
Divesh Aggarwal, Thomas Espitau, Spencer Peters, Noah Stephens-Davidowitz
2025 A conf
The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions.
ITCS
Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
2024 J jnl
Difficulties Constructing Lattices with Exponential Kissing Number from Codes.
CoRR
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2024 A conf
More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More.
APPROX/RANDOM
Surendra Ghentiyala, Noah Stephens-Davidowitz
2024 J jnl
More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more.
CoRR
Surendra Ghentiyala, Noah Stephens-Davidowitz
2024 J jnl
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices.
Electron. Colloquium Comput. Complex.
Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
2023 — conf
Just How Hard Are Rotations of $\mathbb {Z}^n$? Algorithms and Cryptography with the Simplest Lattice.
EUROCRYPT (5)
Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz
2023 A* conf
Lattice Problems beyond Polynomial Time.
STOC
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2023 J jnl
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.
Electron. Colloquium Comput. Complex.
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz
2023 J jnl
Recursive lattice reduction - A framework for finding short lattice vectors.
CoRR
Divesh Aggarwal, Thomas Espitau, Spencer Peters, Noah Stephens-Davidowitz
2023 — conf
Revisiting Time-Space Tradeoffs for Function Inversion.
CRYPTO (2)
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2023 A conf
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems.
APPROX/RANDOM
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2022 J jnl
Lattice Problems Beyond Polynomial Time.
CoRR
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2022 A conf
On Seedless PRNGs and Premature Next.
ITC
Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, Stefano Tessaro
2022 J jnl
On Seedless PRNGs and Premature Next.
IACR Cryptol. ePrint Arch.
Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, Stefano Tessaro
2022 J jnl
Revisiting Time-Space Tradeoffs for Function Inversion.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2021 — conf
A 2
EUROCRYPT (1)
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
2021 A* conf
Dimension-Preserving Reductions Between SVP and CVP in Different
SODA
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz
2021 J jnl
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms.
CoRR
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz
2021 A* conf
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else).
SODA
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2021 J jnl
Just how hard are rotations of ℤ
IACR Cryptol. ePrint Arch.
Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz
2021 — conf
No Time to Hash: On Super-Efficient Entropy Accumulation.
CRYPTO (4)
Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
2021 J jnl
No Time to Hash: On Superefficient Entropy Accumulation.
IACR Cryptol. ePrint Arch.
Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
2021 J jnl
On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization.
Electron. Colloquium Comput. Complex.
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz
2021 — conf
On the Hardness of Average-Case k-SUM.
APPROX-RANDOM
Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2021 A conf
Online Linear Extractors for Independent Sources.
ITC
Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
2021 J jnl
Online Linear Extractors for Independent Sources.
IACR Cryptol. ePrint Arch.
Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
2020 J jnl
A 2
CoRR
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
2020 — conf
Extractor Lower Bounds, Revisited.
APPROX-RANDOM
Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro, Noah Stephens-Davidowitz
2020 — conf
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP.
CRYPTO (2)
Tamalika Mukherjee, Noah Stephens-Davidowitz
2020 J jnl
On the Hardness of Average-case k-SUM.
CoRR
Zvika Brakerski, Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2020 — conf
Slide Reduction, Revisited - Filling the Gaps in SVP Approximation.
CRYPTO (2)
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz
2019 A conf
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic.
CCC
Noah Stephens-Davidowitz
2019 J jnl
A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic.
CoRR
Noah Stephens-Davidowitz
2019 J jnl
Extractor Lower Bounds, Revisited.
Electron. Colloquium Comput. Complex.
Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro, Noah Stephens-Davidowitz
2019 J jnl
Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else).
CoRR
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2019 J jnl
Kissing Numbers and Transference Theorems from Generalized Tail Bounds.
SIAM J. Discret. Math.
Stephen D. Miller, Noah Stephens-Davidowitz
2019 J jnl
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP.
IACR Cryptol. ePrint Arch.
Tamalika Mukherjee, Noah Stephens-Davidowitz
2019 A* conf
SETH-Hardness of Coding Problems.
FOCS
Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2019 J jnl
SETH-hardness of Coding Problems.
Electron. Colloquium Comput. Complex.
Noah Stephens-Davidowitz, Vinod Vaikuntanathan
2019 J jnl
Slide Reduction, Revisited - Filling the Gaps in SVP Approximation.
CoRR
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-Davidowitz
2018 A* conf
(Gap/S)ETH hardness of SVP.
STOC
Divesh Aggarwal, Noah Stephens-Davidowitz
2018 J jnl
Generalizations of Banaszczyk's transference theorems and tail bound.
IACR Cryptol. ePrint Arch.
Stephen D. Miller, Noah Stephens-Davidowitz
2018 — conf
Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP).
SOSA
Divesh Aggarwal, Noah Stephens-Davidowitz
2018 — conf
New (and Old) Proof Systems for Lattice Problems.
Public Key Cryptography (2)
Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz
2017 J jnl
(Gap/S)ETH Hardness of SVP.
CoRR
Divesh Aggarwal, Noah Stephens-Davidowitz
2017 A* conf
A reverse Minkowski theorem.
STOC
Oded Regev, Noah Stephens-Davidowitz
2017 J jnl
An Inequality for Gaussians on Lattices.
SIAM J. Discret. Math.
Oded Regev, Noah Stephens-Davidowitz
2017 J jnl
How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs.
Algorithmica
Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs
2017 A* conf
Implementing BP-Obfuscation Using Graph-Induced Encoding.
CCS
Shai Halevi, Tzipora Halevi, Victor Shoup, Noah Stephens-Davidowitz
2017 J jnl
Implementing BP-Obfuscation Using Graph-Induced Encoding.
IACR Cryptol. ePrint Arch.
Shai Halevi, Tzipora Halevi, Victor Shoup, Noah Stephens-Davidowitz
2017 J jnl
Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP).
CoRR
Divesh Aggarwal, Noah Stephens-Davidowitz
2017 J jnl
New (and Old) Proof Systems for Lattice Problems.
IACR Cryptol. ePrint Arch.
Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz
2017 — —
On the Gaussian Measure Over Lattices.
Noah Stephens-Davidowitz
2017 A* conf
On the Quantitative Hardness of CVP.
FOCS
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2017 J jnl
On the Quantitative Hardness of CVP.
CoRR
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
2017 J jnl
Pseudorandomness of Ring-LWE for Any Ring and Modulus.
IACR Cryptol. ePrint Arch.
Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
2017 A* conf
Pseudorandomness of ring-LWE for any ring and modulus.
STOC
Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
2016 A* conf
Discrete Gaussian Sampling Reduces to CVP and SVP.
SODA
Noah Stephens-Davidowitz
2016 — conf
Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines.
CRYPTO (1)
Yevgeniy Dodis, Ilya Mironov, Noah Stephens-Davidowitz
2016 A conf
On the Lattice Distortion Problem.
ESA
Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz
2016 J jnl
On the Lattice Distortion Problem.
CoRR
Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz
2016 — conf
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One.
APPROX-RANDOM
Noah Stephens-Davidowitz
2015 — conf
Cryptographic Reverse Firewalls.
EUROCRYPT (2)
Ilya Mironov, Noah Stephens-Davidowitz
2015 J jnl
Discrete Gaussian Sampling Reduces to CVP and SVP.
CoRR
Noah Stephens-Davidowitz
2015 J jnl
Message Transmission with Reverse Firewalls - Secure Communication on Corrupted Machines.
IACR Cryptol. ePrint Arch.
Yevgeniy Dodis, Ilya Mironov, Noah Stephens-Davidowitz
2015 J jnl
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One.
CoRR
Noah Stephens-Davidowitz
2015 J jnl
Solving the Closest Vector Problem in $2^n$ Time - The Discrete Gaussian Strikes Again!
CoRR
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
2015 A* conf
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
FOCS
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz
2015 A* conf
Solving the Shortest Vector Problem in 2
STOC
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
2014 J jnl
Cryptographic Reverse Firewalls.
IACR Cryptol. ePrint Arch.
Ilya Mironov, Noah Stephens-Davidowitz
2014 — conf
How to Eat Your Entropy and Have It Too - Optimal Recovery Strategies for Compromised RNGs.
CRYPTO (2)
Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs
2014 J jnl
How to Eat Your Entropy and Have it Too - Optimal Recovery Strategies for Compromised RNGs.
IACR Cryptol. ePrint Arch.
Yevgeniy Dodis, Adi Shamir, Noah Stephens-Davidowitz, Daniel Wichs
2014 A conf
On the Closest Vector Problem with a Distance Guarantee.
CCC
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
2014 J jnl
On the Closest Vector Problem with a Distance Guarantee.
CoRR
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
2014 J jnl
Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling.
CoRR
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz