Concurrent And Resettable Zero-Knowledge With Registered Public-Keys

Zero-knowledge plays a central role in the ?eld of cryptography and is the accepted method-ology to de?ne and prove security of various cryptographic tasks. With the far and widesweeping popularity of the Internet and smart-card based E-commerce over Internet, muchrecent research attention has been paid on the security threats of zero-knowledge protocolswhen they are executing in concurrent and resettable settings. Extensive recent research e?orts have established that constant-round concurrent/resettablezero-knowledge for non-trivial languages cannot be achieved in the plain model without setupassumptions. To achieve constant-round concurrent/resettable zero-knowledge, several fa-mous computational models have been introduced, among which the bare public-key (BPK)model is the weakest and also the most appealing one. (In this thesis, we will refer to the BPKmodel and its variants as general public-key models.) Unfortunately, up to now we do notknow how to construct concurrent/resettable zero-knowledge with concurrent veri?er secu-rity (i. e. concurrent soundness and concurrent witness extraction) for non-trivial languages.That is, all previous concurrent/resettable zero-knowledge systems in the BPK model onlyguarantee concurrent and resettable zero-knowledge for concurrent prover security but donot guarantee concurrent soundness and concurrent witness extraction for concurrent veri?ersecurity. However, zero-knowledge protocols that guarantee both concurrent prover securityand concurrent veri?er security are really desirable in most Internet based and smart-cardbased applications (e. g. secure smart-card based E-commerce over Internet). In this thesis, we investigate and show how to achieve both practical and general zero-knowledge systems that can be securely run in concurrent and resettable settings with bothconcurrent prover security and concurrent veri?er security in general public-key models.Since zero-knowledge plays a central role in the modern cryptography, and also since thefar and wide sweeping popularity of the Internet and smart-card based E-commerce overInternet, our works are of both practical and theoretical signi?cant consequences. For concurrent zero-knowledge, we present two implementations for constant-round black-box concurrent zero-knowledge argument of knowledge that enjoys concurrent veri?er secu-rity (concurrent soundness and concurrent witness extraction) in the BPK model: A practicalconstruction that is under the DLP assumption and runs in 6-round without going throughgeneral NP-reductions for any language that admits Σ-protocols; And a general construc-tion that runs in 4-round (that is optimal) for any language in NP under only one-wayfunctions. To our knowledge, both the practical protocol and the general protocol stand forthe current state-of-the-art concurrent zero-knowledge with setup assumptions. For resettable zero-knowledge, we introduced a new registered public-key model: the weakpublic-key (WPK) model. The WPK model just lies between the BPK model introduced iiby Canetti, Goldreich, Goldwasser and Micali (STOC00) and the upper-bounded public-key(UPK)model introduced by Micali and Reyzin (CRYPTO01) and is well-motivated in thesmart-card based E-commerce over distributed client/server settings. We then show how toachieve min-round (3-round) resettable zero-knowledge arguments for NP with concurrentsoundness in the WPK model. Our this work (on resettable zero-knowledge with concur-rent soundness in the WPK model) is a signi?cant improvement and extension of the workof Micali and Reyzin on resettable zero-knowledge in the UPK model (EUROCRYPT01).Furthermore, since it is a well-known open problem whether constant-round resettable zero-knowledge systems with concurrent soundness for NP exist in the generous BPK model ornot, our this work makes a signi?cant step for ?nally solving this important open problem.