## CryptoDB

### Alessandro Chiesa

#### Publications

Year
Venue
Title
2019
EUROCRYPT
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size $O(\log ^2 n)$O(log2n); it can be produced with $O(n \log n)$O(nlogn) field operations and verified with O(n). At 128 bits of security, proofs are less than ${250}\,\mathrm{kB}$250kB even for several million constraints, more than $10{\times }$10× shorter than prior SNARGs with similar features.A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed–Solomon codeword over any subgroup of a field.We also provide $\texttt {libiop}$libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.
2019
TCC
Succinct non-interactive arguments (SNARGs) are highly efficient certificates of membership in non-deterministic languages. Constructions of SNARGs in the random oracle model are widely believed to be post-quantum secure, provided the oracle is instantiated with a suitable post-quantum hash function. No formal evidence, however, supports this belief.In this work we provide the first such evidence by proving that the SNARG construction of Micali is unconditionally secure in the quantum random oracle model. We also prove that, analogously to the classical case, the SNARG inherits the zero knowledge and proof of knowledge properties of the PCP underlying the Micali construction. We thus obtain the first zero knowledge SNARG of knowledge (zkSNARK) that is secure in the quantum random oracle model.Our main tool is a new lifting lemma that shows how, for a rich class of oracle games, we can generically deduce security against quantum attackers by bounding a natural classical property of these games. This means that in order to prove our theorem we only need to establish classical properties about the Micali construction. This approach not only lets us prove post-quantum security but also enables us to prove explicit bounds that are tight up to small factors.We additionally use our techniques to prove that SNARGs based on interactive oracle proofs (IOPs) with round-by-round soundness are unconditionally secure in the quantum random oracle model. This result establishes the post-quantum security of many SNARGs of practical interest.
2019
TCC
We study the problem of delegating computations via interactive proofs that can be probabilistically checked. Known as interactive oracle proofs (IOPs), these proofs extend probabilistically checkable proofs (PCPs) to multi-round protocols, and have received much attention due to their application to constructing cryptographic proofs (such as succinct non-interactive arguments). The relevant complexity measures for IOPs in this context are prover and verifier time, and query complexity.We construct highly efficient IOPs for a rich class of nondeterministic algebraic computations, which includes succinct versions of arithmetic circuit satisfiability and rank-one constraint system (R1CS) satisfiability. For a time-T computation, we obtain prover arithmetic complexity $O(T \log T)$ and verifier complexity polylog(T). These IOPs are the first to simultaneously achieve the state of the art in prover complexity, due to [14], and in verifier complexity, due to [7]. We also improve upon the query complexity of both schemes.The efficiency of our prover is a result of our highly optimized proof length; in particular, ours is the first construction that simultaneously achieves linear-size proofs and polylogarithmic-time verification, regardless of query complexity.
2017
EUROCRYPT
2017
EUROCRYPT
2017
TCC
2017
JOFC
2016
TCC
2016
TCC
2015
EPRINT
2015
EUROCRYPT
2014
CRYPTO
2014
EPRINT
2014
EPRINT
2014
EPRINT
2013
TCC
2013
CRYPTO
2012
CRYPTO

Crypto 2019
Eurocrypt 2018
TCC 2017