International Association
for Cryptologic Research

Zero-knowledge proofs have driven the field of cryptography since their 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 protocol with soundness against uniform cheating provers. The main component in our construction is the recent delegation protocol for RAM computations (Kalai and Paneth, ePrint 2015). Concretely, we rely on a 3-message variant of their protocol based on keyless collision-resistant hash functions against uniform adversaries and sub-exponentially-secure fully homomorphic encryption.

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.