International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Non-interactive Proof Systems for Bilinear Groups

Authors:
Jens Groth
Amit Sahai
Download:
URL: http://eprint.iacr.org/2007/155
Search ePrint
Search Google
Abstract: Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.
BibTeX
@misc{eprint-2007-13437,
  title={Efficient Non-interactive Proof Systems for Bilinear Groups},
  booktitle={IACR Eprint archive},
  keywords={foundations / Non-interactive witness-indistinguishability, non-interactive zero-knowledge, common reference string, bilinear group},
  url={http://eprint.iacr.org/2007/155},
  note={In submission, this is the full paper j.groth@ucl.ac.uk 13856 received 27 Apr 2007, last revised 8 Dec 2007},
  author={Jens Groth and Amit Sahai},
  year=2007
}