**Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model**

*Yi Deng and Giovanni Di Crescenzo and Dongdai Lin*

**Abstract: **We consider a type of zero-knowledge protocols that are of interest
for their practical applications within networks like the Internet:
efficient zero-knowledge arguments of knowledge that remain secure
against concurrent man-in-the-middle attacks. As negative results in
the area of concurrent non-malleable zero-knowledge imply that
protocols in the standard setting (i.e., under no setup assumptions)
can only be given for trivial languages, researchers have studied
such protocols in models with setup assumptions, such as the common
reference string (CRS) model. This model assumes that a reference
string is honestly created at the beginning of all interactions and
later available to all parties (an assumption that is satisfied, for
instance, in the presence of a trusted party).

A growing area of research in Cryptography is that of reducing the setup assumptions under which certain cryptographic protocols can be realized. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in $\mathcal{NP}$), under the (minimal) assumption of the existence of a one-way function family. We also show time-efficient instantiations of our protocol, in which the transformation from a 3-round honest-verifier zero-knowledge argument of knowledge to a 4-round concurrently non-malleable zero-knowledge argument of knowledge for the same relation incurs only $\mathcal{O}(1)$ (precisely, a {\em small} constant) additional modular exponentiations, based on known number-theoretic assumptions. Furthermore, the APK model is motivated by the consideration of some man-in-the-middle attacks in models with setup assumptions that had not been considered previously and might be of independent interest.

We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.

**Category / Keywords: **cryptographic protocols / Zero-Knowledge Protocols, Concurrently Non-Malleability, Public-Key Models

**Date: **received 12 Sep 2006

**Contact author: **ydeng at is iscas ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20060913:220808 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]