Skip to main content
USENIX
  • Conferences
  • Students
Sign in
  • Home
  • Attend
    • Registration Information
    • Registration Discounts
    • Venue, Hotel, and Travel
    • Students and Grants
    • Co-located Workshops
  • Program
    • At a Glance
    • Technical Sessions
  • Activities
    • Birds-of-a-Feather Sessions
    • Poster Session
    • Work-in-Progress Reports (WiPs)
  • Sponsorship
  • Participate
    • Instructions for Authors and Speakers
    • Call for Papers
      • Important Dates
      • Symposium Organizers
      • Symposium Topics
      • Refereed Papers
      • Symposium Activities
      • Submitting Papers
  • About
    • Symposium Organizers
    • Questions
    • Services
    • Help Promote
    • Past Symposia
  • Home
  • Attend
  • Program
  • Activities
  • Sponsorship
  • Participate
  • About

sponsors

Platinum Sponsor
Gold Sponsor
Silver Sponsor
Silver Sponsor
Silver Sponsor
Silver Sponsor
Bronze Sponsor
Bronze Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Industry Partner
Industry Partner

help promote

USENIX Security '16 button

Get more
Help Promote graphics!

connect with usenix


  •  Twitter
  •  Facebook
  •  LinkedIn
  •  Google+
  •  YouTube

twitter

Tweets by USENIXSecurity

usenix conference policies

  • Event Code of Conduct
  • Conference Network Policy
  • Statement on Environmental Responsibility Policy

You are here

Home » ZKBoo: Faster Zero-Knowledge for Boolean Circuits
Tweet

connect with us

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.

Irene Giacomelli, Aarhus University

Jesper Madsen, Aarhus University

Claudio Orlandi, Aarhus University

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

MP3 Download

Download Audio

Award: 
Best Student Paper
  • Log in or    Register to post comments

Platinum Sponsors

Gold Sponsors

Silver Sponsors

Bronze Sponsors

Media Sponsors & Industry Partners

© USENIX

  • Privacy Policy
  • Contact Us