Paper 2006/423

Perfect NIZK with Adaptive Soundness

Masayuki Abe and Serge Fehr

Abstract

This paper presents a very simple and efficient adaptively-sound perfect NIZK argument system for any NP-language. In contrust to recently proposed schemes by Groth, Ostrovsky and Sahai, our scheme does not pose any restriction on the statements to be proven. Besides, it enjoys a number of desirable properties: it allows to re-use the common reference string (CRS), it can handle arithmetic circuits, and the CRS can be set-up very efficiently without the need for an honest party. We then show an application of our techniques in constructing efficient NIZK schemes for proving arithmetic relations among committed secrets, whereas previous methods required expensive generic NP-reductions. The security of the proposed schemes is based on a strong non-standard assumption, an extended version of the so-called Knowledge-of-Exponent Assumption (KEA) over bilinear groups. We give some justification for using such an assumption by showing that the commonly-used approach for proving NIZK arguments sound does not allow for adaptively-sound statistical NIZK arguments (unless NP is in P/poly). Furthermore, we show that the assumption used in our construction holds with respect to generic adversaries that do not exploit the specific representation of the group elements. We also discuss how to avoid the non-standard assumption in a pre-processing model.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of TCC 07 paper.
Keywords
NIZKadaptive soundnessKEA
Contact author(s)
Serge Fehr @ cwi nl
History
2006-11-19: received
Short URL
https://ia.cr/2006/423
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/423,
      author = {Masayuki Abe and Serge Fehr},
      title = {Perfect NIZK with Adaptive Soundness},
      howpublished = {Cryptology ePrint Archive, Paper 2006/423},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/423}},
      url = {https://eprint.iacr.org/2006/423}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.