Paper 2006/256

Constant-Round Concurrent NMWI and its relation to NMZK

Rafail Ostrovsky, Giuseppe Persiano, and Ivan Visconti


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
zero knowledgewitness indistinguishabilitynon-malleability
Contact author(s)
visconti @ dia unisa it
2007-03-01: last of 2 revisions
2006-08-02: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.