Paper 2001/109

New Notions of Soundness and Simultaneous Resettability in the Public-Key Model

Yunlei ZHAO

Abstract

I n this paper, some new notions of soundness in public-key model are presented. We clarify the relationships among our new notions of soundness and the original 4 soundness notions presented by Micali and Reyzin. Our new soundness notions also characterize a new model for ZK protocols in public key model: weak soundness model. By ``weak” we mean for each common input x selected by a malicious prover on the fly, x is used by the malicious prover at most a-priori bounded polynomial times. The weak soundness model just lies in between BPK model and UPK model. Namely, it is weaker than BPK model but stronger than UPK model. In the weak soundness model (also in the UPK model, since weak soundness model implies UPK model), we get a 3-round black-box rZK arguments with weak resettable soundness for NP. Note that simultaneous resettability is an important open problem in the field of ZK protocols. And Reyzin has proven that there are no ZK protocols with resettable soundness in the BPK model. It means that to achieve simultaneous resettability one needs to augment the BPK model in a reasonable fashion. Although Barak et al. [BGGL01] have proven that any language which has a black-box ZK arguments with resettable soundness is in BPP. It is the weak soundness that makes us to get simultaneous resettability. More interestingly, our protocols work in a somewhat ``parallel repetition” manner to reduce the error probability and the verifier indeed has secret information with respect to historical transcripts. Note that in general the error probability of such protocols can not be reduced by parallel repetition. [BIN97] At last, we give a 3-round non-black-box rZK arguments system with resettable soundness for NP in the preprocessing model in which a trusted third party is assumed. Our construction for such protocol is quite simple. Note that although the preprocessing model is quite imposing but it is still quite reasonable as indicated in [CGGM00]. For example, in many e-commerce setting a trusted third party is often assumed. The critical tools used in this paper are: verifiable pseudorandom functions, zap and complexity leveraging. To our knowledge, our protocols are also the second application of verifiable pseudorandom functions. The first application is the 3-round rZK arguments with one-time soundness for NP in the public-key model as indicated by Micali and Reyzin [MR01a].

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. have not published
Keywords
rZKVRFzapcomplexity leveraging
Contact author(s)
CSYLZHAO @ cityu edu hk
History
2001-12-18: received
Short URL
https://ia.cr/2001/109
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/109,
      author = {Yunlei ZHAO},
      title = {New Notions of Soundness and Simultaneous Resettability  in the Public-Key Model},
      howpublished = {Cryptology ePrint Archive, Paper 2001/109},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/109}},
      url = {https://eprint.iacr.org/2001/109}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.