**Concurrent Non-Malleable Zero Knowledge**

*Boaz Barak and Manoj Prabhakaran and Amit Sahai*

**Abstract: ** 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
super-polynomial simulation. That is, we construct a zero knowledge
protocol $\Pi$ such that for every polynomial-time adversary that
can adaptively and concurrently schedule polynomially many
executions of $\Pi$, 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.

**Category / Keywords: **foundations / zero-knowledge

**Publication Info: **Full version of a paper in FOCS 2006

**Date: **received 19 Oct 2006, last revised 21 Oct 2006

**Contact author: **mmp at uiuc edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **minor edits

**Version: **20061021:190556 (All versions of this report)

**Short URL: **ia.cr/2006/355

[ Cryptology ePrint archive ]