Resettably Sound Zero-Knoweldge Arguments from OWFs - the (semi) Black-Box way.

Abstract

We show how to construct a O(1)-round resettably-sound zero-knowledge argument of knowledge based on one-way functions where additionally the construction and proof of se-curity is black-box. Zero-knowledge proofs (ZK) are fundamental cryptographic constructs used in numerous applications. Formalized using a “simulation ” paradigm, ZK requires that for every malicious verifier there exists a “simulator ” that can indistinguishably reproduce the view of the verifier in an interaction with the honest prover. Resettable-soundness introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS 01) additionally demands the soundness property to hold even if the malicious prover is allowed to “reset ” and “restart ” the verifier. Using the breakthrough non-black-box technique of Barak (FOCS 01) they also provided a constant-round construction of a resettably-sound ZK argument relying on the existence of collision-resistance hash-functions. This construction and subsequent constructions all rely on the underlying cryptographic primitive in a non black-box way. Recently, Goyal, Ostro-vsky, Scafuro and Visconti (STOC 14) showed how to extend the Barak’s technique to obtain a construction and proof of security that relies on the collision-resistant hash-function in a black-box manner while still having a non black-box simulator. Such a construction is referred to as semi black-box. From the work of Chung, Pass and Seth (STOC 13) we know that the minimal assumption required to construct resettably-sound ZK argument is the existence of one-way functions. In this work we close the gap between (semi) black-box and non black-box constructions by showing a black-box (round-efficient) resettably-sound argument relying on one-way functions only. 1