Paper 2005/290

Perfect Non-Interactive Zero Knowledge for NP

Jens Groth, Rafail Ostrovsky, and Amit Sahai

Abstract

Non-interactive zero-knowledge (NIZK) systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic 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 argument 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 protocols for any NP language in the presence of a dynamic/adaptive adversary. While it was already known how to construct efficient prover computational NIZK proofs for any NP language, the known techniques yield large common reference strings and large NIZK proofs. As an additional implication of our techniques, we considerably reduce both the size of the common reference string and the size of the proofs.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Non-interactive zero-knowledgeuniversal composabilitynon-malleability
Contact author(s)
jg @ cs ucla edu
History
2005-09-01: received
Short URL
https://ia.cr/2005/290
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/290,
      author = {Jens Groth and Rafail Ostrovsky and Amit Sahai},
      title = {Perfect Non-Interactive Zero Knowledge for {NP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/290},
      year = {2005},
      url = {https://eprint.iacr.org/2005/290}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.