Witness-Succinct Universally-Composable SNARKs

Chaya Ganesh; Yashvanth Kondi; Claudio Orlandi; Mahak Pancholi; Akira Takahashi; Daniel Tschudi

Paper 2022/1618

Witness-Succinct Universally-Composable SNARKs

Chaya Ganesh

, Indian Institute of Science Bangalore

Yashvanth Kondi, Aarhus University

Claudio Orlandi

, Aarhus University

Mahak Pancholi, Aarhus University

Akira Takahashi

, University of Edinburgh

Daniel Tschudi

, Concordium

Abstract

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.

Note: Full version

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2023
DOI: 10.1007/978-3-031-30617-4_11
Keywords: SNARK Universal Composability Simulation Extractability
Contact author(s): chaya @ iisc ac in
ykondi @ cs au dk
orlandi @ cs au dk
mahakp @ cs au dk
takahashi akira 58s @ gmail com
dt @ concordium com
History: 2023-04-26: revised; 2022-11-20: received; See all versions
Short URL: https://ia.cr/2022/1618
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1618,
      author = {Chaya Ganesh and Yashvanth Kondi and Claudio Orlandi and Mahak Pancholi and Akira Takahashi and Daniel Tschudi},
      title = {Witness-Succinct Universally-Composable SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1618},
      year = {2022},
      doi = {10.1007/978-3-031-30617-4_11},
      note = {\url{https://eprint.iacr.org/2022/1618}},
      url = {https://eprint.iacr.org/2022/1618}
}