### Lift-and-Shift: Obtaining Simulation Extractable Subversion and Updatable SNARKs Generically

Behzad Abdolmaleki, Sebastian Ramacher, and Daniel Slamanig

##### Abstract

Zero-knowledge proofs and in particular succinct non-interactive zero-knowledge proofs (so called zk-SNARKs) are getting increasingly used in real-world applications, with cryptocurrencies being the prime example. Simulation extractability (SE) is a strong security notion of zk-SNARKs which informally ensures non-malleability of proofs. This property is acknowledged as being highly important by leading companies in this field such as Zcash and supported by various attacks against the malleability of cryptographic primitives in the past. Another problematic issue for the practical use of zk-SNARKs is the requirement of a fully trusted setup, as especially for large-scale decentralized applications finding a trusted party that runs the setup is practically impossible. Quite recently, the study of approaches to relax or even remove the trust in the setup procedure, and in particular subversion as well as updatable zk-SNARKs (with latter being the most promising approach), has been initiated and received considerable attention since then. Unfortunately, so far SE-SNARKs with aforementioned properties are only constructed in an ad-hoc manner and no generic techniques are available. In this paper we are interested in such generic techniques and therefore firstly revisit the only available lifting technique due to Kosba et al. (called COCO) to generically obtain SE-SNARKs. By exploring the design space of many recently proposed SNARK- and STARK-friendly symmetric-key primitives we thereby achieve significant improvements in the prover computation and proof size. Unfortunately, the COCO framework as well as our improved version (called OCOCO) is not compatible with updatable SNARKs. Consequently, we propose a novel generic lifting transformation called Lamassu. It is built using different underlying ideas compared to COCO (and OCOCO). In contrast to COCO it only requires key-homomorphic signatures (which allow to shift keys) covering well studied schemes such as Schnorr or ECDSA. This makes Lamassu highly interesting, as by using the novel concept of so called updatable signatures, which we introduce in this paper, we can prove that Lamassu preserves the subversion and in particular updatable properties of the underlying zk-SNARK. This makes Lamassu the first technique to also generically obtain SE subversion and updatable SNARKs. As its performance compares favorably to OCOCO, Lamassu is an attractive alternative that in contrast to OCOCO is only based on well established cryptographic assumptions.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2020
DOI
10.1145/3372297.3417228
Keywords
Zero-knowledgesimulation extractabilitySNARKupdatable SNARKsubversion SNARK
Contact author(s)
sebastian ramacher @ ait ac at
daniel slamanig @ ait ac at
History
2020-08-24: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/062

CC BY

BibTeX

@misc{cryptoeprint:2020/062,
author = {Behzad Abdolmaleki and Sebastian Ramacher and Daniel Slamanig},
title = {Lift-and-Shift: Obtaining Simulation Extractable Subversion and Updatable SNARKs Generically},
howpublished = {Cryptology ePrint Archive, Paper 2020/062},
year = {2020},
doi = {10.1145/3372297.3417228},
note = {\url{https://eprint.iacr.org/2020/062}},
url = {https://eprint.iacr.org/2020/062}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.