Tiramisu: Black-Box Simulation Extractable NIZKs in the Updatable CRS Model

Karim Baghery and Mahdi Sedaghat

Abstract

Zk-SNARKs, as the most efficient NIZK arguments in terms of proof size and verification, are ubiquitously deployed in practice. In applications like Hawk [S&P'16], Gyges [CCS'16], Ouroboros Crypsinous [S&P'19], the underlying zk-SNARK is lifted to achieve Black-Box Simulation Extractability (BB-SE) under a trusted setup phase. To mitigate the trust in such systems, we propose $\texttt{Tiramisu}$, as a construction to build NIZK arguments that can achieve $\textit{updatable BB-SE}$, which we define as a new variant of BB-SE. This new variant allows $\textit{updating}$ the public parameters, therefore eliminating the need for a trusted third party, while unavoidably relies on a $\textit{non-black-box}$ extraction algorithm in the setup phase. In the cost of one-time individual CRS update by the parties, this gets around a known impossibility result by Bellare et al. from ASIACRYPT'16, which shows that BB extractability cannot be achieved with subversion ZK (ZK without trusting a third party). $\texttt{Tiramisu}$ uses an efficient public-key encryption with updatable keys which may be of independent interest. We instantiate $\texttt{Tiramisu}$, implement the overhead, and present efficient BB-SE zk-SNARKs with updatable parameters that can be used in various applications while allowing the end-users to update the parameters and eliminate the needed trust.

Note: - This is the full version of the CANS'21 paper. - In Italian, Tiramisu literally means "lift me up".

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.CANS 2021 – 20th International Conference on Cryptology and Network Security
Keywords
zk-SNARKsUpdatable CRSBlack-Box Simulation ExtractabilityCOCO framework
Contact author(s)
baghery karim @ gmail com
ssedagha @ esat kuleuven be
History
2021-09-28: last of 4 revisions
See all versions
Short URL
https://ia.cr/2020/474

CC BY

BibTeX

@misc{cryptoeprint:2020/474,
author = {Karim Baghery and Mahdi Sedaghat},
title = {Tiramisu: Black-Box Simulation Extractable NIZKs in the Updatable CRS Model},
howpublished = {Cryptology ePrint Archive, Paper 2020/474},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/474}},
url = {https://eprint.iacr.org/2020/474}
}

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