Cryptology ePrint Archive: Report 2021/511

On Simulation-Extractability of Universal zkSNARKs

Markulf Kohlweiss and Michał Zając

Abstract: In this paper we show that a wide class of (computationally) special-sound proofs of knowledge which have unique response property and are standard-model zero-knowledge are simulation-extractable when made non-interactive by the Fiat--Shamir transform. We prove that two efficient updatable universal zkSNARKs---Plonk (Gabizon et al. 19) and Sonic~(Maller et al. 19)---meet these requirements and conclude by showing their weak simulation-extractability. As a side result we also show that relying security on rewinding and Fiat--Shamir transform often comes at a great price of inefficient (yet still polynomial time) knowledge extraction and the security loss introduced by these techniques should always be taken into account.

Category / Keywords: cryptographic protocols / simulation-extractability, zksnark, nizk, fiat-shamir transformation

Date: received 19 Apr 2021, last revised 5 May 2021

Contact author: m p zajac at gmail com

Available format(s): PDF | BibTeX Citation

Note: Update of Sonic description.

Version: 20210505:205404 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]