Efficient Non-interactive Proof Systems for Bilinear Groups

Jens Groth; Amit Sahai

Paper 2007/155

Efficient Non-interactive Proof Systems for Bilinear Groups

Jens Groth and Amit Sahai

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. SICOMP 41 (5), 1193-1232, 2012
DOI: 10.1137/080725386
Keywords: non-interactive zero-knowledge common reference string bilinear group
Contact author(s): j groth @ ucl ac uk
History: 2016-04-11: last of 3 revisions; 2007-05-07: received; See all versions
Short URL: https://ia.cr/2007/155
License: CC BY

BibTeX

@misc{cryptoeprint:2007/155,
      author = {Jens Groth and Amit Sahai},
      title = {Efficient Non-interactive Proof Systems for Bilinear Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/155},
      year = {2007},
      doi = {10.1137/080725386},
      url = {https://eprint.iacr.org/2007/155}
}