## Cryptographic Proof SystemsA proof system is a two-party protocol between a prover and a verifier, where the goal of the prover is to convince the verifier that some statement is true. In this project, we study and construct new proof systems that satisfy special properties such as zero-knowledge (where we require that the proof does not reveal anything more about the statement other than its truth) and succinctness (where proofs are short and can be verified quickly). ## Batch Arguments for NP and More from Standard Bilinear Group Assumptions
Abstract:
A non-interactive batch argument for NP provides a way to amortize the cost of NP verification across multiple instances. They enable a prover to convince a verifier of multiple NP statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance. In this work, we give the first construction of a non-interactive batch
argument for NP from standard assumptions on groups with bilinear maps
(specifically, from either the subgroup decision assumption in composite-order
groups or from the \( k \)-Lin assumption in prime-order groups for any \( k \ge 1 \)).
Previously, batch arguments for NP were only known from
LWE, or a combination of multiple assumptions, or from non-standard/non-falsifiable assumptions.
Moreover, our work introduces a new As corollaries to our main construction, we also obtain the first publicly-verifiable non-interactive delegation scheme for RAM programs with a CRS of sublinear size (in the running time of the RAM program), as well as the first aggregate signature scheme (supporting bounded aggregation) from standard assumptions on bilinear maps.
**Paper:**[PDF], [ePrint Version]**Talk:**[Video]
BibTeX:
@misc{WW22, author = {Brent Waters and David J. Wu}, title = {Batch Arguments for {NP} and More from Standard Bilinear Group Assumptions}, misc = {Full version available at \url{https://eprint.iacr.org/2022/336}}, year = {2022} } ## On Succinct Arguments and Witness Encryption from Groups
Abstract:
Succinct non-interactive arguments (SNARGs) enable proofs of NP statements
with very low communication. Recently, there has been significant work in both
theory and practice on constructing SNARGs with very short proofs. Currently,
the state-of-the-art in succinctness is due to Groth (Eurocrypt 2016) who
constructed a SNARG from In this work, we first construct a concretely-efficient designated-verifier
(preprocessing) SNARG with inverse polynomial soundness, where the proof
consists of just 2 group elements in a We then turn to the question of constructing arguments where the proof
consists of a
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{BIOW20, author = {Ohad Barta and Yuval Ishai and Rafail Ostrovsky and David J. Wu}, title = {On Succinct Arguments and Witness Encryption from Groups}, booktitle = {{CRYPTO}}, year = {2020} } ## New Constructions of Statistical NIZKs: Dual-Mode DV-NIZKs and More
Abstract:
Non-interactive zero-knowledge proofs (NIZKs) are important primitives in
cryptography. A major challenge since the early works on NIZKs has been to
construct NIZKs with a In this work, we develop new techniques for constructing statistical NIZK
arguments. First, we construct statistical DV-NIZK arguments from the Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{LPWW20, author = {Beno{\^{i}}t Libert and Alain Passel{\`{e}}gue and Hoeteck Wee and David J. Wu}, title = {New Constructions of Statistical {NIZKs}: Dual-Mode {DV-NIZKs} and More}, booktitle = {{EUROCRYPT}}, year = {2020} } ## New Constructions of Reusable Designated-Verifier NIZKs
Abstract:
Non-interactive zero-knowledge arguments (NIZKs) for NP are an important cryptographic primitive, but we currently only have instantiations under a few specific assumptions. Notably, we are missing constructions from the learning with errors (LWE) assumption, the Diffie-Hellman (CDH/DDH) assumption, and the learning parity with noise (LPN) assumption. In this paper, we study a relaxation of NIZKs to the We also consider an extension of reusable DV-NIZKs to the In this work, we give new constructions of (reusable) DV-NIZKs and MDV-NIZKs using generic primitives that can be instantiated under CDH, LWE, or LPN.
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{LQRWW19, author = {Alex Lombardi and Willy Quach and Ron D. Rothblum and Daniel Wichs and David J. Wu}, title = {New Constructions of Reusable Designated-Verifier {NIZKs}}, booktitle = {{CRYPTO}}, year = {2019} } ## Multi-Theorem Preprocessing NIZKs from Lattices
Abstract:
Non-interactive zero-knowledge (NIZK) proofs are fundamental to modern
cryptography. Numerous NIZK constructions are known in both the random oracle
and the common reference string (CRS) models. In the CRS model, there exist
constructions from several classes of cryptographic assumptions such as
trapdoor permutations, pairings, and indistinguishability obfuscation. Notably
absent from this list, however, are constructions from standard In this work, we make progress on this problem by giving the first
construction of a We begin by constructing a multi-theorem preprocessing NIZK directly from
context-hiding homomorphic signatures. Then, we show how to efficiently
implement the preprocessing step using a new cryptographic primitive called
**Paper:**[PDF], [Journal Version], [ePrint Version]
BibTeX (Conference):
@inproceedings{KW18, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, booktitle = {{CRYPTO}}, year = {2018} } BibTeX (Journal):
@article{KW20, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, journal = {J. Cryptology}, volume = {33}, number = {3}, pages = {619--702}, year = {2020} } ## Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
Abstract:
Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we first construct a lattice-based SNARG candidate with quasi-optimal succinctness (where the argument size is quasilinear in the security parameter). Further extension of our methods yields the first SNARG (from any assumption) that is quasi-optimal in terms of both prover overhead (polylogarithmic in the security parameter) as well as succinctness. Moreover, because our constructions are lattice-based, they plausibly resist quantum attacks. Central to our construction is a new notion of linear-only vector encryption which is a generalization of the notion of linear-only encryption introduced by Bitansky et al. (TCC 2013). We conjecture that variants of Regev encryption satisfy our new linear-only definition. Then, together with new information-theoretic approaches for building statistically-sound linear PCPs over small finite fields, we obtain the first quasi-optimal SNARGs. We then show a surprising connection between our new lattice-based SNARGs and
the concrete efficiency of program obfuscation. All existing obfuscation
candidates currently rely on multilinear maps. Among the constructions that
make black-box use of the multilinear map, obfuscating a circuit of even
moderate depth (say, 100) requires a multilinear map with multilinearity
degree in excess of 2
**Paper:**[PDF], [ePrint Version]**Talk:**[Video]
BibTeX:
@inproceedings{BISW17, author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu}, title = {Lattice-Based {SNARGs} and Their Application to More Efficient Obfuscation}, booktitle = {{EUROCRYPT}}, year = {2017} } ## Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices
Abstract:
Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient
privacy-preserving proofs of membership for general \( \mathsf{NP} \) languages.
Our focus in this work is on Our construction follows the general blueprint of Bitansky et al. (TCC 2013) and Boneh et al. (Eurocrypt 2017) of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We develop a concretely-efficient lattice-based instantiation of this compiler by considering quadratic extension fields of moderate characteristic and using linear-only vector encryption over rank-2 module lattices.
**Paper:**[PDF], [ePrint Version]**Code:**[Github]
BibTeX:
@inproceedings{ISW21, author = {Yuval Ishai and Hang Su and David J. Wu}, title = {Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices}, booktitle = {ACM Conference on Computer and Communications Security ({ACM} {CCS})}, year = {2021} } ## Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs
Abstract:
Succinct non-interactive arguments (SNARGs) enable verifying NP computations
with significantly less complexity than that required for classical NP
verification. In this work, we focus on simultaneously minimizing the proof
size and the prover complexity of SNARGs. Concretely, for a security parameter \( \lambda \),
we measure the asymptotic cost of achieving soundness error \( 2^{-\lambda} \)
against provers of size \( 2^\lambda \). We say a SNARG
is This work gives the first quasi-optimal SNARG for Boolean circuit
satisfiability from a concrete cryptographic assumption. Our construction
takes a two-step approach. The first is an information-theoretic construction
of a quasi-optimal linear multi-prover interactive proof (linear MIP) for
circuit satisfiability. Then, we describe a generic cryptographic compiler
that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by
relying on the notion of linear-only vector encryption over rings introduced
by Boneh et al. Combining these two primitives yields the first quasi-optimal
SNARG based on linear-only vector encryption. Moreover, our linear MIP
construction leverages a new Finally, we consider (designated-verifier) SNARGs that provide
**Paper:**[PDF], [ePrint Version]
BibTeX:
@inproceedings{BISW18, author = {Dan Boneh and Yuval Ishai and Amit Sahai and David J. Wu}, title = {Quasi-Optimal {SNARGs} via Linear Multi-Prover Interactive Proofs}, booktitle = {{EUROCRYPT}}, year = {2018} } |