Cryptology ePrint Archive: Report 2020/811

Groth16 SNARKs are Randomizable and (Weakly) Simulation Extractable

Markulf Kohlweiss and Mikhail Volkhov

Abstract: Due to its simplicity, succinctness, and performance, Groth16 is currently the most widely deployed succinct (zero-knowledge) argument of knowledge (SNARK) system. Groth16 is known to be perfectly zero-knowledge and knowledge sound in the generic (and algebraic) group model. However, the existing security arguments for Groth16 are silent about the soundness of the proof system in the presence of simulated proofs --- a common requirement for both the composable security and game-hopping style security analysis of protocols built using such argument systems. This important gap let to a line of work on simulation-extractable, also called simulation knowledge sound, succinct proof systems. Groth16 itself cannot satisfy the strongest notion of simulation-extractability that implies proof non-malleability --- in fact, proofs are perfectly randomizable. Surprisingly, in this short note we show that Groth16 does satisfy a weaker notion of simulation-extractability implying statement non-malleability. This property is often sufficient for typical applications that motivate the use of strong simulation-extractability. Notably, one can obtain UC security using efficient compilers.

Category / Keywords: cryptographic protocols / zero knowledge, NIZK, zk-SNARK, simulation extractability, QAP, algebraic group model

Date: received 29 Jun 2020, last revised 1 Jul 2020

Contact author: mikhail volkhov at ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200701:185202 (All versions of this report)

Short URL: ia.cr/2020/811


[ Cryptology ePrint archive ]