## 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). ## 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.
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
BibTeX:
@inproceedings{KW18, author = {Sam Kim and David J. Wu}, title = {Multi-Theorem Preprocessing {NIZKs} from Lattices}, booktitle = {{CRYPTO}}, year = {2018} } ## 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
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} } ## 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
λ, we measure the asymptotic cost of achieving soundness error
2 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
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} } |