25th USENIX Security Symposium has ended
Back To Schedule
Friday, August 12 • 2:30pm - 3:00pm
ZKBoo: Faster Zero-Knowledge for Boolean Circuits

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

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.

Friday August 12, 2016 2:30pm - 3:00pm PDT
Zilker Ballroom 3

Attendees (3)