Cryptology ePrint Archive: Report 2014/284

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

Rafail Ostrovsky and Alessandra Scafuro and Muthuramakrishnan Venkitasubramaniam

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 security 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, Ostrovsky, 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.

Category / Keywords: foundations / zero knowledge, resettable soundness, black-box construction

Date: received 23 Apr 2014, last revised 29 May 2014

Contact author: alescafu at gmail com

Available format(s): PDF | BibTeX Citation

Note: Acknowledge Section added

Version: 20140529:073217 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]