Constant-Round Concurrent NMWI and Its Relation to NMZK. Revised version of [65], ECCC

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: • 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 indistinguish-able proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • 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). • It is known that every zero-knowledge (ZK) argument is also a witness indistinguishable (WI) argument, but not vice-versa, i.e. ZK ( 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. • We show that our constant-round NMWI argument system is also secure under a con-current man-in-the-middle attack, i.e., it is a concurrent constant-round NMWI ar-gument system. This is somewhat surprising since the question of a constant-round concurrent NMZK argument system is still open. • We then turn our attention to Bare Public-Key (BPK) model. We show how to ex-pand 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