Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy

Vipul Goyal; Amit Sahai

Paper 2008/545

Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy

Vipul Goyal and Amit Sahai

Abstract

Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which ``marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.

Note: Simplified proofs and improved writeup

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Merged with a paper by Yi Deng and appeared in FOCS 2009
Contact author(s): vipul goyal @ gmail com
History: 2009-10-23: revised; 2008-12-29: received; See all versions
Short URL: https://ia.cr/2008/545
License: CC BY

BibTeX

@misc{cryptoeprint:2008/545,
      author = {Vipul Goyal and Amit Sahai},
      title = {Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/545},
      year = {2008},
      url = {https://eprint.iacr.org/2008/545}
}