Succint Non-Interactive Arguments of Knowledge, or SNARKS, have received a lot of attention recently because of their application to provide privacy guarantees in the ZeroCash cryptocurrency. For a long time, few constructions were known and the SNARK was thought to be an elusive, mysterious creature as in the famous poem of Lewis Carroll, the Hunting of the SNARK. We now have constructions over elliptic curves which can convince a verifier of the satisfiability of circuits of arbitrary size with a constant size, very short proof. The downside is that the constructions are based on very strong and controversial assumptions, also called “knowledge assumptions”, which are even known to be non-falsifiable. Unfortunately, there are known impossibility results which indicate that the use of such assumptions is unavoidable if one wants to have succint proofs.

This talk tries to answer the following research question: how much succintness does one need to give up to get rid of Knowledge Assumptions? More specifically, I will first show how to reduce the size of zero-knowledge proofs of quadratic equations (in the standard model under falsifiable assumptions). This result can be seen as an aggregation of Groth-Sahai proofs for quadratic equations, which was left as an open problem in previous work. The key technique for this result is an aggregation technique which appeared as part of a SNARK construction.

Next, I will discuss the application of these techniques to get CircuitSat proofs with improved asymptotic complexity. When the input of the circuit is not private, like some applications to verifiable computation require, our proof depends only on the depth of the circuit. This is the first asymptotic improvement we are aware of (in the standard model and under falsifiable assumptions) since the first proof due to Groth, Ostrovsky and Sahai in 2006, which is linear in the number of circuit gates.