Paper 2014/284

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

Rafail Ostrovsky, Alessandra Scafuro, and Muthuramakrishnan Venkitasubramaniam


We construct a constant-round resettably-sound zero-knowledge argument of knowledge based on black-box use of any one-way function. Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell [FOCS 01] and is a strengthening of the soundness requirement in interactive proofs demanding that soundness should hold even if the malicious prover is allowed to “reset” and “restart” the verifier. In their work they show that resettably-sound ZK arguments require non-black-box simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak [FOCS 01]. All known implementations of Barak’s non-black-box technique required non-black-box use of a collision-resistance hash-function (CRHF). Very recently, Goyal, Ostrovsky, Scafuro and Visconti [STOC 14] showed an implementation of Barak’s technique that needs only black-box access to a collision-resistant hash-function while still having a non-black-box simulator. (Such a construction is referred to as semi black-box.) Plugging this implementation in the BGGL’s construction yields the first resettably-sound ZK arguments based on black-box use of CRHFs. However, from the work of Chung, Pass and Seth [STOC 13] and Bitansky and Paneth [STOC13], we know that resettably-sound ZK arguments can be constructed from non-black-box use of any one-way function (OWF), which is the minimal assumption for ZK arguments. Hence, a natural question is whether it is possible to construct resettably-sound zero-knowledge arguments from black-box use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between black-box and non-black-box constructions for resettably-sound ZK arguments.

Note: The protocol has been modified to address an issue regarding using signatures based on one-way functions.

Available format(s)
Publication info
Preprint. MINOR revision.
zero knowledgeresettable soundnessblack-box construction
Contact author(s)
alescafu @ gmail com
2014-10-09: last of 3 revisions
2014-04-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rafail Ostrovsky and Alessandra Scafuro and Muthuramakrishnan Venkitasubramaniam},
      title = {Resettably Sound Zero-Knoweldge Arguments from OWFs - the (semi) Black-Box way},
      howpublished = {Cryptology ePrint Archive, Paper 2014/284},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.