Resettably Sound Zerp-Knowledge Arguments from OWFs - The (Semi) Black-Box Way
Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramanian
Abstract:
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 nonblack-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 nonblack-box stimulator. (Such a construction is referred to as semi blackbox.) Plugging that implementation in the complier due to Barak's et. al. yields the first ressettably-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 [STOC 13], 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.
comment: TCC 2015 pp: 345-374
Fetch PDF file of the paper
| Back to Publications List |