Irene Giacomelli, Jesper Madsen, and Claudio Orlandi, Aarhus University
Awarded Best Student Paper
Abstract:
In this paper we describe ZKBoo, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-ofconcept 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:
A thorough analysis of the different variants of IKOS, which highlights their pros and cons for practically relevant soundness parameters;
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 = Ø(x)” (where Ø is a circuit and y a public value);
A case study, where we provide explicit protocols, implementations and benchmarking of zero-knowledge protocols for the SHA-1 and SHA-256 circuits.
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
BibTeX
@inproceedings {197203,
author = {Irene Giacomelli and Jesper Madsen and Claudio Orlandi},
title = {{ZKBoo}: Faster {Zero-Knowledge} for Boolean Circuits},
booktitle = {25th USENIX Security Symposium (USENIX Security 16)},
year = {2016},
isbn = {978-1-931971-32-4},
address = {Austin, TX},
pages = {1069--1083},
url = {https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/giacomelli},
publisher = {USENIX Association},
month = aug
}
Twitter
Facebook
LinkedIn
Google+
YouTube
connect with us