**
Perfect Non-Interactive Zero Knowledge for NP
**

*
Jens Groth, Rafail Ostrovsky, Amit Sahai
*

**
Abstract:
**
Non-interactive zero-knowledge (NIZK) proof systems are
fundamental cryptographic primitives used in many constructions, in-
cluding CCA2-secure cryptosystems, digital signatures, and various cryp-
tographic protocols. What makes them especially attractive, is that they
work equally well in a concurrent setting, which is notoriously hard for
interactive zero-knowledge protocols. However, while for interactive zero-
knowledge we know how to construct statistical zero-knowledge argu-
ment systems for all NP languages, for non-interactive zero-knowledge,
this problem remained open since the inception of NIZK in the late
1980's. Here we resolve two problems regarding NIZK:
* We construct the first perfect NIZK argument system for any NP
language.
* We construct the first UC-secure NIZK argument for any NP lan-
guage in the presence of a dynamic/adaptive adversary.
While it is already known how to construct efficient prover computa-
tional NIZK proofs for any NP language, the known techniques yield
large common reference strings and large proofs. Another contribution
of this paper is NIZK proofs with much shorter common reference string
and proofs than previous constructions.

KEYWORDS: Non-interactive zero-knowledge, universal composability, non-malleability.

**comment:**
Preliminary version in Proceedings
of The 25th International Cryptology Conference, (EUROCRYPT-2006) Springer-Verlag/IACR
Lecture Notes in
Computer Science.

Fetch PostScript file of the
paper.ps or
Fetch PDF file of the
paper.pdf

Back to Publications List |