Paper 2016/163

ZKBoo: Faster Zero-Knowledge for Boolean Circuits

Irene Giacomelli, Jesper Madsen, and Claudio Orlandi

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-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 practically relevant soundness parameters; 2) A generalization and simplification of their approach, which leads to faster Sigma-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;

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. MINOR revision.USENIX Security Symposium
Keywords
zero knowledge
Contact author(s)
giacomelli @ cs au dk
History
2016-08-12: last of 6 revisions
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/163
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/163,
      author = {Irene Giacomelli and Jesper Madsen and Claudio Orlandi},
      title = {ZKBoo: Faster Zero-Knowledge for Boolean Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2016/163},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/163}},
      url = {https://eprint.iacr.org/2016/163}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.