We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or superpolynomial simulation. That is, we construct a zero knowledge protocol \prod such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of \prod, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier.

Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties? inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC 2004).

We obtain an \tilde O(n)-round protocol under the assumption that one-to-one one-way functions exist. This can be improved to \tilde O(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol.