ZKBoo: Faster Zero-Knowledge for Boolean Circuits

Authors: 

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.

Open Access Media

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,
}
Download
Giacomelli PDF
View the slides

Presentation Video 

Presentation Audio

Award: 
Best Student Paper