Succinct arguments for bilinear group arithmetic: Practical structure-preserving cryptography

Lai RWF, Malavolta G, Ronge V (2019)

Publication Language: English

Publication Type: Conference contribution

Publication year: 2019

Publisher: Association for Computing Machinery

Pages Range: 2057-2074

Conference Proceedings Title: Proceedings of the ACM Conference on Computer and Communications Security

Event location: London GB

ISBN: 9781450367479

URI: https://dl.acm.org/citation.cfm?id=3354262

DOI: 10.1145/3319535.3354262

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.

Authors with CRIS profile

Wai Fu Lai Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Viktoria Ronge Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

Additional Organisation(s)

Graduiertenkolleg 2475 Cyberkriminalität und Forensische Informatik

Related research project(s)

Cyberkriminalität und forensische Informatik (Cybercrime) Oct. 1, 2019 - March 31, 2024

Involved external institutions

Carnegie Mellon University US United States (USA) (US)

How to cite

APA:

Lai, R.W.F., Malavolta, G., & Ronge, V. (2019). Succinct arguments for bilinear group arithmetic: Practical structure-preserving cryptography. In Proceedings of the ACM Conference on Computer and Communications Security (pp. 2057-2074). London, GB: Association for Computing Machinery.

MLA:

Lai, Russell W. F., Giulio Malavolta, and Viktoria Ronge. "Succinct arguments for bilinear group arithmetic: Practical structure-preserving cryptography." Proceedings of the 26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London Association for Computing Machinery, 2019. 2057-2074.

BibTeX: Download