Cryptology ePrint Archive: Report 2017/925

Resettably-Sound Resettable Zero Knowledge in Constant Rounds

Wutichai Chongchitmate and Rafail Ostrovsky and Ivan Visconti

Abstract: In FOCS 2001 Barak et al. conjectured the existence of zero-knowledge arguments that remain secure against resetting provers and resetting verifiers. The conjecture was proven true by Deng et al. in FOCS 2009 under various complexity assumptions and requiring a polynomial number of rounds. Later on in FOCS 2013 Chung et al. improved the assumptions requiring one-way functions only but still with a polynomial number of rounds.

In this work we show a constant-round resettably-sound resettable zero-knowledge argument system, therefore improving the round complexity from polynomial to constant. We obtain this result through the following steps.

1. We show an explicit transform from any $\ell$-round concurrent zero-knowledge argument system into an $O(\ell)$-round resettable zero-knowledge argument system. The transform is based on techniques proposed by Barak et al. in FOCS 2001 and by Deng et al. in FOCS 2009. Then, we make use of a recent breakthrough presented by Chung et al. in CRYPTO 2015 that solved the longstanding open question of constructing a constant-round concurrent zero-knowledge argument system from plausible polynomial-time hardness assumptions. Starting with their construction $\Gamma$ we obtain a constant-round resettable zero-knowledge argument system $\Lambda$.

2. We then show that by carefully embedding $\Lambda$ inside $\Gamma$ (i.e., essentially by playing a modification of the construction of Chung et al. against the construction of Chung et al.) we obtain the first constant-round resettably-sound concurrent zero-knowledge argument system $\Delta$.

3. Finally, we apply a transformation due to Deng et al. to $\Delta$ obtaining a resettably-sound resettable zero-knowledge argument system $\Pi$, the main result of this work.

While our round-preserving transform for resettable zero knowledge requires one-way functions only, both $\Lambda, \Delta$ and $\Pi$ extend the work of Chung et al. and as such they rely on the same assumptions (i.e., families of collision-resistant hash functions, one-way permutations and indistinguishability obfuscation for P/poly, with slightly super-polynomial security).

Category / Keywords: cryptographic protocols / zero knowledge, resettable ZK, resettable soundness, constant-Round, indistinguishability obfuscation

Original Publication (in the same form): IACR-TCC-2017

Date: received 21 Sep 2017, last revised 24 Sep 2017

Contact author: wutichai at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20170924:225645 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]