Paper 2006/256
Constant-Round Concurrent NMWI and its relation to NMZK
Rafail Ostrovsky, Giuseppe Persiano, and Ivan Visconti
Abstract
One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: 1) We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. 2) We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions). 3) It is known that every zero-knowledge (ZK) argument is also a witness indistinguishable (WI) argument, but not vice-versa, i.e. ZK is not contained in WI. Rather surprisingly, we show that NMWI and NMZK argument systems are incomparable. That is, we show that there exists a NMZK argument system that is not a NMWI argument system and we also show that there is a NMWI argument system that is not a NMZK argument system. 4) We show that our constant-round NMWI argument system is also secure under a concurrent man-in-the-middle attack, i.e., it is a concurrent constant-round NMWI argument system. This is somewhat surprising since the question of a constant-round concurrent NMZK argument system is still open. 5) We then turn our attention to Bare Public-Key (BPK) model. We show how to expand upon our concurrent NMWI result in the plain model to obtain a constant-round concurrent NMZK argument system for any NP language in the BPK model.
Note: This new version shows that NMWI proofs and NMZK proofs are incomparable. A new version including the extensions to general concurrent composition will be uploaded later.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- zero knowledgewitness indistinguishabilitynon-malleability
- Contact author(s)
- visconti @ dia unisa it
- History
- 2007-03-01: last of 2 revisions
- 2006-08-02: received
- See all versions
- Short URL
- https://ia.cr/2006/256
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/256, author = {Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti}, title = {Constant-Round Concurrent {NMWI} and its relation to {NMZK}}, howpublished = {Cryptology ePrint Archive, Paper 2006/256}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/256}}, url = {https://eprint.iacr.org/2006/256} }