Rafail Ostrovsky - Publications

Simultaneous Resettability from One-Way Functions

Kai-Min Chung, Rafail Ostrovsky, Rafail Pass, Ivan Visconti


Resettable-security introduced by Canetti, Golderich, Goldwasser and Micali (STOC'00) considers the security of cryptographic two-party protocols ( in particular zero-knowledge arguments) in a setting where the attacker may "reset" or "rewind" one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak Goldericj, Goldeasser and Lindell (FOCS'01), requires resettable security to hold for bothparties in the context of zero-knowledge, both the soundness and the zero-knowledge conditions reain robust to reseting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only-oneway functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system: Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.

comment: FOCS 2013 pp: 60-69

Fetch PDF file of the paper

Back to Publications List