Noah Stephens-Davidowitz

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 57

Top Topics

Continuous Valued

Message Transmission

Extended Abstract

Top Venues

IACR Cryptol. ePrint Arch.

Electron. Colloquium Comput. Complex.

Publications

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