Paper 2020/474

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

Karim Baghery and Mahdi Sedaghat


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)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.CANS 2021 – 20th International Conference on Cryptology and Network Security
zk-SNARKsUpdatable CRSBlack-Box Simulation ExtractabilityCOCO framework
Contact author(s)
baghery karim @ gmail com
ssedagha @ esat kuleuven be
2021-09-28: last of 4 revisions
2020-04-28: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.