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.

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, the main challenge in this setting is to provide security with respect to adaptive concurrent composition of protocols and also the non-malleability property, where the ``man-in-the-middle'' attacks are prevented. Despite much research effort, we do not know how to implement many basic tasks in this setting (which features concurrent composition and man-in-the-middle attacks). Indeed, even for tasks such as zero-knowledge proofs, which play an essential role in Cryptography, it is not known how to construct a protocol in a way that satisfies both security guarantees simultaneously.

In this paper, we consider a slightly weaker notion than zero-knowledge, namely witness indistinguishability of proofs, which never-the-less is an extremely important building block in Cryptography. Despite its importance, neither formulations nor constructions that satisfy both concurrent composition and resiliency against man-in-the-middle attacks were known.

The main contribution of this paper is to put forward the definition of concurrent non-malleable witness indistinguishability (in fact, we show two different definitions) and show a constant-round construction using non-black-box techniques. Furthermore, we show that this construction allow us to solve some important open problems.
More specifically, based on our construction of a constant-round input-adaptive concurrent non-malleable witness-indistinguishable argument of knowledge, we construct a constant-round input-adaptive concurrent non-malleable zero-knowledge argument of knowledge in the Bare Public-Key Model (the BPK model in short) that has been first proposed in [Canetti et al., STOC 2000]. The BPK model makes very minimal set-up assumptions, therefore our result improves the current state-of-the-art as previous results required either the existence of trusted third parties (trusted PKI, common reference string), or made physical assumptions (common reference string) or achieved only quasi security (simulation in super-polynomial time) or quasi concurrency (timing assumptions, bounded concurrency) or non-adaptivity.

By plugging our results into known constructions, we achieve constant-round zero-knowledge and then (n-1)-secure multi-party computation under general concurrent composition in the BPK model.