Cryptology ePrint Archive: Report 2020/811

Another Look at Extraction and Randomization of Groth's zk-SNARK

Karim Baghery and Markulf Kohlweiss and Janno Siim and Mikhail Volkhov

Abstract: Due to the simplicity and performance of zk-SNARKs they are widely used in real-world cryptographic protocols, including blockchain and smart contract systems. Simulation Extractability (SE) is a necessary security property for a NIZK argument to achieve Universal Composability (UC), a common requirement for such protocols. Most of the works that investigated SE focus on its strong variant which implies proof non-malleability. In this work we investigate a relaxed weaker notion, that allows proof randomization, while guaranteeing statement non-malleability, which we argue to be a more natural security property. First, we show that it is already achievable by Groth16, arguably the most efficient and widely deployed SNARK nowadays. Second, we show that because of this, Groth16 can be efficiently transformed into a black-box weakly SE NIZK, which is sufficient for UC protocols. To support the second claim, we present and compare two practical constructions, both of which strike different performance trade-offs: * Int-Groth16 makes use of a known transformation that encrypts the witness inside the SNARK circuit. We instantiate this transformation with an efficient SNARK-friendly encryption scheme. * Ext-Groth16 is based on the SAVER encryption scheme (Lee et al.) that plugs the encrypted witness directly into the verification equation, externally to the circuit. We prove that Ext-Groth16 is black-box weakly SE and, contrary to Int-Groth16, that its proofs are fully randomizable.

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

Date: received 29 Jun 2020, last revised 6 Oct 2020

Contact author: mikhail volkhov at ed ac uk

Available format(s): PDF | BibTeX Citation

Note: Updated from technical report to an extended version.

Version: 20201006:171906 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]