3-Message Zero Knowledge Against Human Ignorance

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

  • PDF / 655,741 Bytes
  • 27 Pages / 439.37 x 666.142 pts Page_size
  • 108 Downloads / 218 Views

DOWNLOAD

REPORT


3

MIT, Cambridge, USA [email protected] 2 Weizmann, Rehovot, Israel Microsoft Research, Cambridge, USA 4 Boston University, Boston, USA

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. N. Bitansky—Research supported in part by DARPA Safeware Grant, NSF CAREER Award CNS-1350619, CNS-1413964 and by the NEC Corporation. Z. Brakerski—Supported by the Israel Science Foundation (Grant No. 468/14), the Alon Young Faculty Fellowship, Binational Science Foundation (Grant No. 712307) and Google Faculty Research Award. O. Paneth—Supported by the Simons award for graduate students in Theoretical Computer Science and an NSF Algorithmic foundations grant 1218461. V. Vaikuntanathan—Research supported in part by DARPA Grant number FA875011-2-0225, NSF CAREER Award CNS-1350619, NSF Grant CNS-1413964 (MACS: A Modular Approach to Computer Security), Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship, NEC Corporation and a Steven and Renee Finn Career Development Chair from MIT. c International Association for Cryptologic Research 2016  M. Hirt and A. Smith (Eds.): TCC 2016-B, Part I, LNCS 9985, pp. 57–83, 2016. DOI: 10.1007/978-3-662-53641-4 3

58

1

N. Bitansky et al.

Introduction

The fascinating notion of zero knowledge, conceived over thirty years ago by Goldwasser, Micali and Rackoff [GMR89], has been the source of a great many ideas that revolutionized cryptography, including the simulation paradigm and passive-to-active security transformations [GMW91,FLS99,Bar01,IKOS09]. A central and persistent open question in the theory of zero knowledge is that of round complexity (also called message complexity), which refers to the number of messages that the prover and the verifier must exchange in a zero-knowledge protocol. The seminal work of Goldreich, Micali and Wigderson