Alex Lombardi

Alex Lombardi

Auto-generated profile, based on publicly available information

Alex Lombardi

Princeton University, Princeton, USA

Research Focus & Metrics

Representative Publications

View All Publications
2 June 2023
Verified
Conference Paper
Open access
YKYael Kalai
Yael Kalai
ALAlex Lombardi
Alex Lombardi
VVVinod Vaikuntanathan
Vinod Vaikuntanathan
DWDaniel Wichs
Daniel Wichs
We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly (m)· k1−є, where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly (m, logk), which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with succinctness poly(logT). Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARGs and SNARGs with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions. Along the way, we prove an equivalence between BARGs and a new notion of SNARGs for (deterministic) RAM computations that we call “flexible RAM SNARGs with partial input soundness.” This is the first demonstration that SNARGs for deterministic computation (of any kind) imply BARGs. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARGs (Devadas et. ‍al. FOCS 2022).

10 June 2024
Verified
Conference Paper
Open access
ALAlex Lombardi
Alex Lombardi
FMFermi Ma
Fermi Ma
JWJohn Wright
John Wright
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

10 June 2024
Verified
Conference Paper
Open access
ZJZhengzhong Jin
Zhengzhong Jin
YKYael Kalai
Yael Kalai
ALAlex Lombardi
Alex Lombardi
VVVinod Vaikuntanathan
Vinod Vaikuntanathan
We construct a succinct non-interactive argument (SNARG) system for every NP language L that has a propositional proof of non-membership, i.e. of x∉ L. The soundness of our SNARG system relies on the hardness of the learning with errors (LWE) problem. The common reference string (CRS) in our construction grows with the space required to verify the propositional proof, and the size of the proof grows poly-logarithmically in the length of the propositional proof. Unlike most of the literature on SNARGs, our result implies SNARGs for languages L with proof length shorter than logarithmic in the deterministic time complexity of L. Our SNARG improves over prior SNARGs for such “hard” NP languages (Sahai and Waters, STOC 2014, Jain and Jin, FOCS 2022) in several ways: 1) For languages with polynomial-length propositional proofs of non-membership, our SNARGs are based on a single, polynomial-time falsifiable assumption, namely LWE. 2) Our construction handles super-polynomial length propositional proofs, as long as they have bounded space, under the subexponential LWE assumption. 3) Our SNARGs have a transparent setup, meaning that no private randomness is required to generate the CRS. Moreover, our approach departs dramatically from these prior works: we show how to design SNARGs for hard languages without publishing a program (in the CRS) that has the power to verify NP witnesses. The key new idea in our construction is what we call a “locally unsatisfiable extension” of the NP verification circuit {Cx}x. We say that an NP verifier has a locally unsatisfiable extension if for every x∉L, there exists an extension Ex of Cx that is not even locally satisfiable in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow Ex to be depend arbitrarily on x rather than being efficiently constructible. In this work, we show – via a “hash-and-BARG” for a hidden, encrypted computation – how to build SNARGs for all languages with locally unsatisfiable extensions. We additionally show that propositional proofs of unsatisfiability generically imply the existence of locally unsatisfiable extensions, which allows us to deduce our main results. As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

15 June 2025
Verified
Conference Paper
Open access
ZJZhengzhong Jin
Zhengzhong Jin
YKYael Tauman Kalai
Yael Tauman Kalai
ALAlex Lombardi
Alex Lombardi
SMSurya Mathialagan
Surya Mathialagan

9 June 2026
Verified
Conference Paper
Open access
LDLalita Devadas
Lalita Devadas
SHSamuel B. Hopkins
Samuel B. Hopkins
YKYael Tauman Kalai
Yael Tauman Kalai
PKPravesh K. Kothari
Pravesh K. Kothari
ALAlex Lombardi
Alex Lombardi
SMSurya Mathialagan
Surya Mathialagan