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

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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2019/969

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

Russell W. F. Lai, 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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. ACM CCS '19
DOI: 10.1145/3319535.3354262
Keywords: zero knowledge
Contact author(s): russell lai @ cs fau de
giulio malavolta @ hotmail it
viktoria ronge @ cs fau de
History: 2019-08-30: revised; 2019-08-29: received; See all versions
Short URL: https://ia.cr/2019/969
License: CC BY

BibTeX

@misc{cryptoeprint:2019/969,
      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{https://eprint.iacr.org/2019/969}},
      url = {https://eprint.iacr.org/2019/969}
}