**
Efficiency Preserving Transformations for Concurrent Non-Malleable Zero Knowledge
**

*
Rafail Ostrovsky, Omkant Pandey, Ivan Visconti
*

**
Abstract:
**

Ever since the invention of Zero-Knowledge by Goldwasser, Micali,
and Rackoff[1], Zero-Knowledge has become a
central building block in cryptography - with numerous applications,
ranging from electronic cash to digital signatures. The properties
of *Zero*-Knowledge range from the most simple (and not particularly
useful in practice) requirements, such as honest-verifier
zero-knowledge to the most demanding (and most useful in
applications) such as non-malleable and concurrent zero-knowledge.
In this paper, we study the complexity of *efficient*
zero-knowledge reductions, from the first type to the second type.
More precisely, under a standard complexity assumption (DDH),
on input a public-coin honest-verifier statistical zero knowledge
argument of knowledge Π for a language L we show a compiler
that produces an argument system Π for L that is concurrent
non-malleable zero-knowledge (under non-adaptive inputs -- which is
the best one can hope to
achieve [2,3].
If k is the security parameter, the overhead of our compiler
is as follows:

- The round complexity of Π is r+\tilde{O}(\log k) rounds, where $r$ is the round complexity of Π'.
- The new prover P (resp., the new verifier V) incurs an additional overhead of (at most) r+k \tilde(O)(\log^2 k) modular exponentiations. If tags of length \tilde{O}(\log k) are provided, the overhead is only r+\tilde(O)\log ^2 k) modular exponentiations.

**comment:**
Preliminary version in TCC 2010.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |