TY - GEN
T1 - 3-message zero knowledge against human ignorance
AU - Bitansky, Nir
AU - Brakerski, Zvika
AU - Kalai, Yael
AU - Paneth, Omer
AU - Vaikuntanathan, Vinod
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84994393176&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994393176&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53641-4_3
DO - 10.1007/978-3-662-53641-4_3
M3 - Conference contribution
AN - SCOPUS:84994393176
SN - 9783662536407
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 57
EP - 83
BT - Theory of Cryptography - 14th International Conference, TCC 2016-B, Proceedings
A2 - Smith, Adam
A2 - Hirt, Martin
PB - Springer Verlag
T2 - 14th International Conference on Theory of Cryptography, TCC 2016-B
Y2 - 31 October 2016 through 3 November 2016
ER -