International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Perfect NIZK with Adaptive Soundness

Masayuki Abe
Serge Fehr
Search ePrint
Search Google
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.
  title={Perfect NIZK with Adaptive Soundness},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / NIZK, adaptive soundness, KEA},
  note={Full version of TCC 07 paper. 13469 received 16 Nov 2006},
  author={Masayuki Abe and Serge Fehr},