# Cryptographic Proof Systems

A 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

Contributors: Brent Waters and David J. Wu

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 direct approach for batch verification and avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches.

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.

Resources:

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

Contributors: Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu

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 bilinear maps where the proof consists of just 3 group elements.

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 standard (generic) group. This leads to a 50% reduction in concrete proof size compared to Groth's construction. We follow the approach of Bitansky et al. (TCC 2013) who describe a compiler from linear PCPs to SNARGs in the preprocessing model. Our improvement is based on a new linear PCP packing technique that allows us to construct 1-query linear PCPs which can then be compiled into a SNARG (using ElGamal encryption over a generic group). An appealing feature of our new SNARG is that the verifier can precompute a statement-independent lookup table in an offline phase; verifying proofs then only requires 2 exponentiations and a single table lookup. This makes our new designated-verifier SNARG appealing in settings that demand fast verification and minimal communication.

We then turn to the question of constructing arguments where the proof consists of a single group element. Here, we first show that any (possibly interactive) argument for a language $$\mathcal{L}$$ where the verification algorithm is “generic” (i.e., only performs generic group operations) and the proof consists of a single group element, implies a witness encryption scheme for $$\mathcal{L}$$. We then show that under a yet-unproven, but highly plausible, hypothesis on the hardness of approximating the minimal distance of linear codes, we can construct a 2-message laconic argument for NP where the proof consists of a single group element. Under the same hypothesis, we obtain a witness encryption scheme for NP in the generic group model. Along the way, we show that under a conceptually-similar but proven hardness of approximation result, there is a 2-message laconic argument for NP with negligible soundness error where the prover's message consists of just 2 group elements. In both settings, we obtain laconic arguments (and linear PCPs) with linear decision procedures. Our constructions circumvent a previous lower bound by Groth on such argument systems with linear decision procedures by relying on imperfect completeness. Namely, our constructions have vanishing but not negligible completeness error, while the lower bound of Groth implicitly assumes negligible completeness error of the underlying argument. Our techniques thus highlight new avenues for designing linear PCPs, succinct arguments, and witness encryption schemes.

Resources:

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

Contributors: Benoît Libert, Alain Passelègue, Hoeteck Wee, and David J. Wu

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 statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such “statistical NIZK arguments” are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models.

In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are “malicious-designated-verifier” NIZKs), and moreover, they satisfy a “dual-mode” property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.

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.

Resources:

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

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

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 designated-verifier setting (DV-NIZK), where a trusted setup generates a common reference string together with a secret key for the verifier. We want reusable schemes, which allow the verifier to reuse the secret key to verify many different proofs, and soundness should hold even if the malicious prover learns whether various proofs are accepted or rejected. Such reusable DV-NIZKs were recently constructed under the CDH assumption, but it was open whether they can also be constructed under LWE or LPN.

We also consider an extension of reusable DV-NIZKs to the malicious designated-verifier setting (MDV-NIZK). In this setting, the only trusted setup consists of a common random string. However, there is also an additional untrusted setup in which the verifier chooses a public/secret key needed to generate/verify proofs, respectively. We require that zero-knowledge holds even if the public key is chosen maliciously by the verifier. Such reusable MDV-NIZKs were recently constructed under the “one-more CDH” assumption, but constructions under CDH/LWE/LPN remained open.

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.

Resources:

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

Contributors: Sam Kim and David J. Wu

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 lattice assumptions. While there has been partial progress in realizing NIZKs from lattices for specific languages, constructing NIZK proofs (and arguments) for all of NP from standard lattice assumptions remains open.

In this work, we make progress on this problem by giving the first construction of a multi-theorem NIZK for NP from standard lattice assumptions in the preprocessing model. In the preprocessing model, a (trusted) setup algorithm generates proving and verification keys. The proving key is needed to construct proofs and the verification key is needed to check proofs. In the multi-theorem setting, the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zero- knowledge. Existing constructions of NIZKs in the preprocessing model (or even the designated-verifier model) that rely on weaker assumptions like one-way functions or oblivious transfer are only secure in a single-theorem setting. Thus, constructing multi-theorem NIZKs in the preprocessing model does not seem to be inherently easier than constructing them in the CRS model.

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 blind homomorphic signatures. This primitive may be of independent interest. Finally, we show how to leverage our new lattice-based preprocessing NIZKs to obtain new malicious-secure MPC protocols purely from standard lattice assumptions.

Resources:

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

Contributors: Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu

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 2100. In this work, we show that an ideal obfuscation of both the decryption function in a fully homomorphic encryption scheme and a variant of the verification algorithm of our new lattice-based SNARG yields a general-purpose obfuscator for all circuits. Finally, we give some concrete estimates needed to obfuscate this “obfuscation-complete” primitive. We estimate that at 80-bits of security, a (black-box) multilinear map with ≈212 levels of multilinearity suffices. This is over 280 times more efficient than existing candidates, and thus, represents an important milestone towards implementable program obfuscation for all circuits.

Resources:

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

Contributors: Yuval Ishai, Hang Su, and David J. Wu

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 post-quantum zkSNARKs, with a focus on minimizing proof size. Currently, there is a $$1000\times$$ gap in the proof size between the best pre-quantum constructions and the best post-quantum ones. Here, we develop and implement new lattice-based zkSNARKs in the designated-verifier preprocessing model. With our construction, after an initial preprocessing step, a proof for an $$\mathsf{NP}$$ relation of size $$2^{20}$$ is just over 16 KB. Our proofs are $$10.3\times$$ shorter than previous post-quantum zkSNARKs for general $$\mathsf{NP}$$ languages. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a $$42\times$$ reduction in proof size and a $$60\times$$ reduction in the prover's running time, all while achieving a much higher level of soundness. Compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is $$131\times$$ longer, but both the prover and the verifier are faster (by $$1.2\times$$ and $$2.8\times$$, respectively).

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.

Resources:

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

Contributors: Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu

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 quasi-optimally succinct if its proof length is $$\tilde{O}(\lambda)$$, and that it is quasi-optimal, if moreover, its prover complexity is only polylogarithmically greater than the running time of the classical NP prover. We show that this definition is the best we could hope for assuming that NP does not have succinct proofs. Our definition strictly strengthens the previous notion of quasi-optimality introduced in the work of Boneh et al. (Eurocrypt 2017).

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 robust circuit decomposition primitive that allows us to decompose a circuit satisfiability instance into several smaller circuit satisfiability instances. This primitive may be of independent interest.

Finally, we consider (designated-verifier) SNARGs that provide optimal succinctness for a non-negligible soundness error. Concretely, we put forward the notion of “1-bit SNARGs” that achieve soundness error 1/2 with only one bit of proof. We first show how to build 1-bit SNARGs from indistinguishability obfuscation, and then show that 1-bit SNARGs also suffice for realizing a form of witness encryption. The latter result highlights a two-way connection between the soundness of very succinct argument systems and powerful forms of encryption.

Resources:

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}
}
`