Academic
Publications
Efficient Non-interactive Proof Systems for Bilinear Groups

Efficient Non-interactive Proof Systems for Bilinear Groups,10.1007/978-3-540-78967-3_24,Jens Groth,Amit Sahai

Efficient Non-interactive Proof Systems for Bilinear Groups   (Citations: 87)
BibTex | RIS | RefWorks Download
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 theo- retical purposes to the large class of practical cryptographic protocols based on bilinear groups.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...We note that several systems such as BGN encryption [15], Groth-Ostrovsky-Sahai NIZK proofs [32], traitor tracing [16] , and predicate encryption [17,36] were originally developed in the composite order setting, but later variants were developed in prime order groups [31,48,33,35,25,26,37] 4 .I deally, a...

    Allison Lewkoandet al. Decentralizing Attribute-Based Encryption

    • ...It is, however, much less efficient and more complicated than the scheme in [18] since it employs the Groth-Sahai NIZK protocols [10] as building blocks...

    Tatsuaki Okamotoet al. Efficient Attribute-Based Signatures for Non-monotone Predicates in th...

    • ...For consistency with the Groth-Sahai methodology [GS08], we also say commitment instead of encryption, as their commitments to group elements, which we will use, are extractable, i.e., we can recover the committed value (and thus “decrypt”) using an extraction key...
    • ...This PoK is instantiated with Groth-Sahai (GS) commitments and proofs [GS08] for pairing-product equations (PPE), and the message space consists of pairs of group elements...
    • ...Commitments. We instantiate Com, defined in Section 2, by the commitment scheme based on SXDH from [GS08]...
    • ...In order to instantiate Proof for Com ,w e use the proof system from [GS08], which was shown to be randomizable in [BCC + 09]...
    • ...While Groth and Sahai [GS08] show simulation of proofs of satisfiability of equations, where the simulator produces all the commitments, we require a novel type of simulation: given commitments to certain variables of an equation, we have to simulate the remaining commitments and the proof of validity...

    Georg Fuchsbauer. Commuting Signatures and Verifiable Encryption

    • ...Our constructions use the following building blocks, from which they inherit their security: Witness-indistinguishable Groth-Sahai proofs for languages over pairing-friendly groups [GS08] and Waters signatures derived from the scheme in [Wat05] and used in [BW06]...
    • ...The global proof on the message and the randomness, which we denote by Π =( ΠM ,Π r), can be done with randomizable commitments and proofs, using the Groth-Sahai methodology [GS08, FP09], and consists of 9k +1 8� + 6 group elements (where k and � are the respective bit lengths of messages and of the 414 O. Blazy et al...

    Olivier Blazyet al. Signatures on Randomizable Ciphertexts

    • ...To instantiate this proof, we suggest the efficient proof system of Groth and Sahai [24],...
    • ...A natural question is whether one can obtain UC-security by replacing our interactive proofs with the non-interactive Groth-Sahai proofs [24]...

    Matthew Greenandet al. Practical Adaptive Oblivious Transfer from Simple Assumptions

Sort by: