A full day of cryptography talks in the Paris area.
Home / About
The sixth Paris Area Crypto Day will be held on 30.11.2017 (Thu) at ENS.
| 13:30 - 14:30 | Yuval Ishai Secure Arithmetic Computation with Constant Computational Overhead |
| 14:40 - 15:40 | Jens Groth Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability |
| 15:45 - 16:30 | Coffee & Snacks @ S16, ENS |
Secure Arithmetic Computation with Constant Computational Overhead
Yuval Ishai (Technion)
Motivated by the goal of efficient secure computations on sensitive numerical data, we present a protocol for securely computing arithmetic circuits that requires only a constant (amortized) number of arithmetic operations per gate. This applies to the model of security against passive (or “semi-honest”) adversaries. Our protocol is based on new cryptographic assumptions that can be viewed as natural arithmetic analogues of well studied assumptions. Beyond the asymptotic result, a key building block in our protocol can yield concrete efficiency improvements for natural secure computation tasks.
Joint work with Benny Applebaum, Ivan Damgård, Michael Nielsen, and Lior Zichron
Linear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability
Jens Groth (UCL)
We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses O(N) multiplications and the verifier only uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact.
Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the primitives we obtain linear-time zero-knowledge proofs.