Reset table-security, introduced by Canetti, Gold Reich, 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 reset table security, simultaneous reset ability, introduced by Barak, Gold Reich, Goldwasser and Lindell (FOCS'01), requires reset table security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous reset table security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous reset table security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: - Every language in NP has an omega(1)-round simultaneously reset table witness indistinguishable argument system. - Every language in NP has a (polynomial-round) simultaneously reset table zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve reset table-security.
展开▼