Paper 2019/969

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

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


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.

Available format(s)
Publication info
Published elsewhere. Minor revision.ACM CCS '19
zero knowledge
Contact author(s)
russell lai @ cs fau de
giulio malavolta @ hotmail it
viktoria ronge @ cs fau de
2019-08-30: revised
2019-08-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Russell W.  F.  Lai and Giulio Malavolta and Viktoria Ronge},
      title = {Succinct Arguments for Bilinear Group Arithmetic: Practical Structure-Preserving Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/969},
      year = {2019},
      doi = {10.1145/3319535.3354262},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.