Cryptology ePrint Archive: Report 2008/233

On Resettably-Sound Resttable Zero Knowledege Arguments

Yi Deng and Dongdai Lin

Abstract: We study the simultaneous resettability problem, namely whether resettably-sound resettable ZK arguments for non-trivial languages exist (posed by Barak et al. [BGGL FOCS'01]), in both the plain model and the bare public-key (BPK for short) model. Under general hardness assumptions, we show: 1. in the BPK model, there exist constant-round (full-fledged) resettably-sound resettable ZK arguments for NP. This resolves a main problem in this model that remained open since the Micali and Reyzin's identification of notions of soundness [MR Crypto 2001] in the BPK model. the plain model, there exist constant-round (unbounded) resettably-sound class-bounded resettable ZK (as defined by Deng and Lin in [DL Eurocrypt 2007]) arguments for NP. This improves the previous result of Deng and Lin [Eurocrypt 2007] in that the DL construction for class-bounded resettable ZK argument achieves only a weak notion of resettable-soundness. The crux of these results is a construction of constant-round instance-dependent (full-fledged) resettably-sound resettable WI argument of knowledge (IDWIAOK for short) for any NP statement of the form x_0\in L_0 or x_1\in L_1, a notion also introduced by Deng and Lin [Eurocrypt 2007], whose construction, however, obtains only weak resettable-soundness when x_0\notin L_0. Our approach to the simultaneous resettability problem in the BPK model is to make a novel use of IDWIAOK, which gives rise to an elegant structure we call \Sigma-puzzles. Given the fact that all previously known resettable ZK arguments in the BPK model can be achieved in the plain model when ignoring round complexity, we believe this approach will shed light on the simultaneous resettability problem in the plain model.

Category / Keywords: foundations / instance-dependent WI, simultaneous resettability, zero knowledge.

Date: received 22 May 2008, withdrawn 9 Nov 2008

Contact author: ydeng at is iscas ac cn

Available format(s): (-- withdrawn --)

Version: 20081109:072747 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]