One of the central questions in cryptography 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. Despite much research effort, we do
not know how to implement many basic tasks in this setting. We consider
the notion of witness indistinguishability of a proof, which is an
extremely important building block in cryptography. Despite its
importance, neither formulations nor protocols that satisfy resiliency
against man-in-the-middle attacks were known. We put forward the
definition of concurrent non-malleable witness indistinguishability and
show a constant-round protocol using non-black-box techniques.
Furthermore, based on our constant-round concurrent non-malleable
witness-indistinguishable argument of knowledge in the plain model, we
show a constant-round concurrent non-malleable zero-knowledge argument
of knowledge in the Bare Public-Key Model.