Alex Lombardi

According to our database, Alex Lombardi authored at least 32 papers between 2017 and 2024.

Collaborative distances:

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

2024

SNARGs under LWE via Propositional Proofs.

Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2024

Universal SNARGs for NP from Proofs of Correctness.

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

IACR Cryptol. ePrint Arch., 2024

2023

A one-query lower bound for unitary synthesis and breaking quantum cryptography.

Alex Lombardi, Fermi Ma, John Wright

IACR Cryptol. ePrint Arch., 2023

SNARGs for Monotone Policy Batch NP.

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

IACR Cryptol. ePrint Arch., 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

IACR Cryptol. ePrint Arch., 2022

Quantum Advantage from Any Non-Local Game.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

IACR Cryptol. ePrint Arch., 2022

Boosting Batch Arguments and RAM Delegation.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

IACR Cryptol. ePrint Arch., 2022

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

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 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

IACR Cryptol. ePrint Arch., 2022

Succinct Classical Verification of Quantum Computation.

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

IACR Cryptol. ePrint Arch., 2022

Correlation-Intractable Hash Functions via Shift-Hiding.

Alex Lombardi, Vinod Vaikuntanathan

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

2021

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

Alex Lombardi, Fermi Ma, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2021

Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge).

Justin Holmgren, Alex Lombardi, Ron Rothblum

Electron. Colloquium Comput. Complex., 2021

2020

Statistical ZAPR Arguments from Bilinear Maps.

Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

IACR Cryptol. ePrint Arch., 2020

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

Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2020

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

Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2020

Does Fiat-Shamir Require a Cryptographic Hash Function?

Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach

IACR Cryptol. ePrint Arch., 2020

2019

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

Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

IACR Cryptol. ePrint Arch., 2019

Lattice Trapdoors and IBE from Middle-Product LWE.

Alex Lombardi, Vinod Vaikuntanathan, Thuy-Duong Vuong

IACR Cryptol. ePrint Arch., 2019

A Note on Key Agreement and Non-Interactive Commitments.

Alex Lombardi, Luke Schaeffer

IACR Cryptol. ePrint Arch., 2019

New Constructions of Reusable Designated-Verifier NIZKs.

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

IACR Cryptol. ePrint Arch., 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

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

IACR Cryptol. ePrint Arch., 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

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

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

Zvika Brakerski, Alex Lombardi, Gil Segev, 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