Paper 2020/474

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 $\mathtt{\text{Tiramisu}}$, as a construction to build NIZK arguments that can achieve $\mathit{\text{updatable BB-SE}}$, which we define as a new variant of BB-SE. This new variant allows $\mathit{\text{updating}}$ the public parameters, therefore eliminating the need for a trusted third party, while unavoidably relies on a $\mathit{\text{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). $$ uses an efficient public-key encryption with updatable keys which may be of independent interest. We instantiate $$, 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".