Cryptology ePrint Archive: Report 2019/969

Succinct Arguments for Bilinear Group Arithmetic: Practical Structure-Preserving Cryptography

Russell W. F. Lai and Giulio Malavolta and Viktoria Ronge

Abstract: In their celebrated work, Groth and Sahai [EUROCRYPT'08, SICOMP' 12] constructed non-interactive zero-knowledge (NIZK) proofs for general bilinear group arithmetic relations, which spawned the entire subfield of structure-preserving cryptography. This branch of the theory of cryptography focuses on modular design of advanced cryptographic primitives. Although the proof systems of Groth and Sahai are a powerful toolkit, their efficiency hits a barrier when the size of the witness is large, as the proof size is linear in that of the witness.

In this work, we revisit the problem of proving knowledge of general bilinear group arithmetic relations in zero-knowledge. Specifically, we construct a succinct zero-knowledge argument for such relations, where the communication complexity is logarithmic in the integer and source group components of the witness. Our argument has public-coin setup and verifier and can therefore be turned non-interactive using the Fiat-Shamir transformation in the random oracle model. For the special case of non-bilinear group arithmetic relations with only integer unknowns, our system can be instantiated in non-bilinear groups. In many applications, our argument system can serve as a drop-in replacement of Groth-Sahai proofs, turning existing advanced primitives in the vast literature of structure-preserving cryptography into practically efficient systems with short proofs.

Category / Keywords: zero knowledge

Original Publication (with minor differences): ACM CCS '19

Date: received 26 Aug 2019, last revised 30 Aug 2019

Contact author: russell lai at cs fau de, giulio malavolta at hotmail it, viktoria ronge at cs fau de

Available format(s): PDF | BibTeX Citation

Version: 20190830:093233 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]