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.Category / Keywords: zero knowledge, witness indistinguishability, non-malleability, Date: received 28 Jul 2006, last revised 1 Mar 2007 Contact author: visconti at dia unisa it Available format(s): PDF | BibTeX Citation 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. Version: 20070301:113749 (All versions of this report) Short URL: ia.cr/2006/256 Discussion forum: Show discussion | Start new discussion