Alex Lombardi

According to our database, Alex Lombardi authored at least 34 papers between 2017 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2025

Strong random unitaries and fast scrambling.

Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, Hsin-Yuan Huang

CoRR, September, 2025

Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions.

Rahul Ilango, Alex Lombardi

Electron. Colloquium Comput. Complex., 2025

Universal SNARGs for NP from Proofs of Correctness.

Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography.

Alex Lombardi, Fermi Ma, John Wright

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

SNARGs under LWE via Propositional Proofs.

Zhengzhong Jin, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Boosting Batch Arguments and RAM Delegation.

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

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

Quantum Advantage from Any Non-local Game.

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

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

SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

Proceedings of the Advances in Cryptology - EUROCRYPT 2023, 2023

SNARGs for Monotone Policy Batch NP.

Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, Omer Paneth

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

2022

Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic

Alex Lombardi

PhD thesis, 2022

Post-quantum Insecurity from LWE.

Alex Lombardi, Ethan Mook, Willy Quach, Daniel Wichs

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

PPAD is as Hard as LWE and Iterated Squaring.

Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, Ron D. Rothblum

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

Correlation-Intractable Hash Functions via Shift-Hiding.

Alex Lombardi, Vinod Vaikuntanathan

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably.

Alex Lombardi, Fermi Ma, Nicholas Spooner

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Succinct Classical Verification of Quantum Computation.

James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang

Proceedings of the Advances in Cryptology - CRYPTO 2022, 2022

2021

Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge).

Justin Holmgren, Alex Lombardi, Ron D. Rothblum

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Does Fiat-Shamir Require a Cryptographic Hash Function?

Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach

Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021

2020

Multi-Input Correlation-Intractable Hash Functions via Shift-Hiding.

Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2020

Statistical ZAPR Arguments from Bilinear Maps.

Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

Proceedings of the Advances in Cryptology - EUROCRYPT 2020, 2020

Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs.

Alex Lombardi, Vinod Vaikuntanathan

Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020

2019

2-Message Publicly Verifiable WI from (Subexponential) LWE.

Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

IACR Cryptol. ePrint Arch., 2019

A Note on Key Agreement and Non-Interactive Commitments.

Alex Lombardi, Luke Schaeffer

IACR Cryptol. ePrint Arch., 2019

Lattice Trapdoors and IBE from Middle-Product LWE.

Alex Lombardi, Vinod Vaikuntanathan, Thuy-Duong Vuong

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Fiat-Shamir: from practice to theory.

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

New Constructions of Reusable Designated-Verifier NIZKs.

Alex Lombardi, Willy Quach, Ron D. Rothblum, Daniel Wichs, David J. Wu

Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

2018

Cryptographic Hashing From Strong One-Way Functions.

Justin Holmgren, Alex Lombardi

IACR Cryptol. ePrint Arch., 2018

Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE.

Ran Canetti, Alex Lombardi, Daniel Wichs

IACR Cryptol. ePrint Arch., 2018

Fiat-Shamir From Simpler Assumptions.

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum

IACR Cryptol. ePrint Arch., 2018

Succinct Garbling Schemes from Functional Encryption Through a Local Simulation Paradigm.

Prabhanjan Ananth, Alex Lombardi

Proceedings of the Theory of Cryptography - 16th International Conference, 2018

Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and Their Applications).

Justin Holmgren, Alex Lombardi

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions.

Zvika Brakerski, Alex Lombardi, Gil Segev, Vinod Vaikuntanathan

Proceedings of the Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29, 2018

2017

On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation.

Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2017

Minimizing the Complexity of Goldreich's Pseudorandom Generator.

Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2017

Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation.

Alex Lombardi, Vinod Vaikuntanathan

Proceedings of the Theory of Cryptography - 15th International Conference, 2017