You are looking at a specific version 20160411:065033 of this paper. See the latest version.

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-knowledgecommon reference stringbilinear 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.