3-message zero knowledge against human ignorance

Nir Bitansky, Zvika Brakerski, Yael Kalai, Omer Paneth, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The notion of Zero Knowledge has driven the field of cryptography since its conception over thirty years ago. It is well established that two-message zero-knowledge protocols for NP do not exist, and that four-message zero-knowledge arguments exist under the minimal assumption of one-way functions. Resolving the precise round complexity of zero-knowledge has been an outstanding open problem for far too long. In this work, we present a three-message zero-knowledge argument system with soundness against uniform polynomial-time cheating provers. The main component in our construction is the recent delegation protocol for RAM computations (Kalai and Paneth, TCC 2016B and Brakerski, Holmgren and Kalai, ePrint 2016). Concretely, we rely on a three-message variant of their protocol based on a key-less collisionresistant hash functions secure against uniform adversaries as well as other standard primitives. More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against real-world adversaries, which we formalize following Rogaway’s “human-ignorance” approach (VIETCRYPT 2006): in a nutshell, we give an explicit uniform reduction from any adversary breaking the soundness of our protocol to finding collisions in the underlying hash function.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
EditorsAdam Smith, Martin Hirt
PublisherSpringer Verlag
Pages57-83
Number of pages27
ISBN (Print)9783662536407
DOIs
StatePublished - 2016
Event14th International Conference on Theory of Cryptography, TCC 2016-B - Beijing, China
Duration: Oct 31 2016Nov 3 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9985 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Theory of Cryptography, TCC 2016-B
Country/TerritoryChina
CityBeijing
Period10/31/1611/3/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of '3-message zero knowledge against human ignorance'. Together they form a unique fingerprint.

Cite this