Paper 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.

Note: Update of Sonic description.