Resettably-Sound Resettable Zero Knowledge in Constant Rounds
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 requi
- PDF / 861,557 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 198 Views
University of California, Los Angeles, CA, USA {wutichai,rafail}@cs.ucla.edu 2 Universit` a di Salerno, Fisciano, Italy [email protected]
Abstract. In FOCS 2001 Barak et al. conjectured the existence of zeroknowledge 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 -round concurrent zeroknowledge argument system into an O()-round resettable zeroknowledge 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 Γ we obtain a constant-round resettable zero-knowledge argument system Λ. 2. We then show that by carefully embedding Λ inside Γ (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 constantround resettably-sound concurrent zero-knowledge argument system Δ. 3. Finally, we apply a transformation due to Deng et al. to Δ obtaining a resettably-sound resettable zero-knowledge argument system Π, the main result of this work. While our round-preserving transform for resettable zero knowledge requires one-way functions only, both Λ, Δ and Π 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). c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 111–138, 2017. https://doi.org/10.1007/978-3-319-70503-3_4
112
1
W. Chongchitmate et al.
Introduction
Private randomness is essential for many cryptographic tasks, including zeroknowledge (ZK) proofs [24]. A natural question regards the possibility of having ZK proofs in applications where the computing machine is stateless and not equipped with a continuous source of randomness. Resettable zero knowledge. The above question was put forth by Canetti et al. [8]. In particular, they considered a cheating verifier that mounts a reset attack, where provers are forced to execute the protocol multiple times possibly on the same inputs and random tapes, and without the ability to maintain states between executions. Thes
Data Loading...
