Alex Lombardi

I am an Assistant Professor of Computer Science at Princeton. Prospective students interested in cryptography (classical or quantum) are encouraged to apply to our PhD program.

Previously, I was a Simons-Berkeley postdoctoral fellow hosted by Shafi Goldwasser. Before that, I was a graduate student in computer science at MIT, where I was fortunate to be advised by Vinod Vaikuntanathan.

My current interests lie mainly in the theory and foundations of cryptography, although I am broadly interested in theoretical computer science.

Contact: firstname dot lastname @ princeton.edu

Publications

My publications are listed below.

Alternatively, you can use Google Scholar, DBLP, or the Cryptology ePrint Archive (search by name).

Conference Publications

SNARGs under LWE via Propositional Proofs

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

STOC 2024

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

Alex Lombardi, Fermi Ma, and John Wright

STOC 2024, QIP 2024.

SNARGs for Monotone Policy Batch NP

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

CRYPTO 2023

Boosting Batch Arguments and RAM Delegation

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

STOC 2023

Quantum Advantage from Any Non-Local Game

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

STOC 2023

SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption

Yael Tauman Kalai, Alex Lombardi, and Vinod Vaikuntanathan

EUROCRYPT 2023

PPAD is as Hard as LWE and Iterated Squaring

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

TCC 2022

Post-Quantum Insecurity from LWE

Alex Lombardi, Ethan Mook, Willy Quach, and Daniel Wichs

TCC 2022

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

Alex Lombardi, Fermi Ma, and Nicholas Spooner

FOCS 2022, QIP 2023

Succinct Classical Verification of Quantum Computation

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

CRYPTO 2022

Correlation-Intractable Hash Functions via Shift-Hiding

Alex Lombardi and Vinod Vaikuntanathan

ITCS 2022

Does Fiat-Shamir Require a Cryptographic Hash Function?

Yilei Chen, Alex Lombardi, Fermi Ma, and Willy Quach

CRYPTO 2021

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

Justin Holmgren, Alex Lombardi, and Ron D. Rothblum

STOC 2021

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

Alex Lombardi and Vinod Vaikuntanathan

CRYPTO 2020

Statistical ZAPR Arguments from Bilinear Maps

Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs

EUROCRYPT 2020

Lattice Trapdoors and IBE from Middle-Product LWE

Alex Lombardi, Vinod Vaikuntanathan, and Thuy Duong Vuong

TCC 2019

New Constructions of Reusable Designated-Verifier NIZKs

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

CRYPTO 2019

Fiat-Shamir: From Practice to Theory

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

STOC 2019

Part I: Fiat-Shamir from Simpler Assumptions
Part II: NIZK and Correlation Intractability from Circular-Secure FHE
Conference Proceedings (merge of Parts I and II, abbreviated)

Succinct Garbling Schemes from Functional Encryption through a Local Simulation Paradigm

Prabhanjan Ananth and Alex Lombardi

TCC 2018

Cryptographic Hashing from Strong One-Way Functions

Justin Holmgren and Alex Lombardi

FOCS 2018

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

Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan

EUROCRYPT 2018

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

Alex Lombardi and Vinod Vaikuntanathan

TCC 2017

Manuscripts

2-Message Publicly Verifiable WI from (Subexponential) LWE

Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs

A Note on Key Agreement and Non-Interactive Commitments

Alex Lombardi and Luke Schaeffer

Minimizing the Complexity of Goldreich's Pseudorandom Generator

Alex Lombardi and Vinod Vaikuntanathan

Theses

Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic (PhD Thesis)

Alex Lombardi

Low Complexity Pseudorandom Generators and Indistinguishability Obfuscation (Master's Thesis)

Alex Lombardi

Alex Lombardi

I am an Assistant Professor of Computer Science at Princeton. Prospective students interested in cryptography (classical or quantum) are encouraged to apply to our PhD program.

Previously, I was a Simons-Berkeley postdoctoral fellow hosted by Shafi Goldwasser. Before that, I was a graduate student in computer science at MIT, where I was fortunate to be advised by Vinod Vaikuntanathan.

My current interests lie mainly in the theory and foundations of cryptography, although I am broadly interested in theoretical computer science.

Contact: firstname dot lastname @ princeton.edu

Publications

My publications are listed below.

Alternatively, you can use Google Scholar, DBLP, or the Cryptology ePrint Archive (search by name).

Conference Publications

Fiat-Shamir: From Practice to Theory

Manuscripts

Theses

Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic (PhD Thesis)

Low Complexity Pseudorandom Generators and Indistinguishability Obfuscation (Master's Thesis)

Teaching

Fall 2024: COS 433/533 (Cryptography)

Fall 2023: COS 533 (Advanced Cryptography)

Fall 2019: 6.876 Advanced Topics in Cryptography (Cryptographic Proofs).

Spring 2018: 6.875 Cryptography and Cryptanalysis (as a TA)

Service

Program Committees: STOC 2025, EUROCRYPT 2025, TCC 2024, CRYPTO 2024, FOCS 2023, ITCS 2023, TCC 2022, EUROCRYPT 2022, TCC 2021