IACR News item: 18 February 2016
Irene Giacomelli, Jesper Madsen, Claudio Orlandi
ePrint Report
In this paper we describe ZKBoo1, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-of-concept implementation. As an highlight, we can generate (resp. verify) a non-interactive proof for the SHA-1 circuit in approximately 13ms (resp. 5ms), with a proof size of 444KB.
Our techniques are based on the MPC-in-the-head approach to zero-knowledge of Ishai et al. (IKOS), which has been successfully used to achieve significant asymptotic improvements. Our contributions include:
1) A thorough analysis of the different variants of IKOS, which highlights their pro and cons for prac- tically relevant soundness parameters;
2) A generalization and simplification of their approach, which leads to faster Σ-protocols (that can be made non-interactive using the Fiat-Shamir heuristic) for statements of the form I know x such that y = f(x) (where f is a circuit and y a public value);
3) A case study, where we provide explicit protocols, implementations and benchmarking of zero- knowledge protocols for the SHA-1 and SHA-256 circuits.
Additional news items may be found on the IACR news page.