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

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 TIRAMISU (In Italian, TIRAMISU literally means "lift me up"), as a construction to build NIZK arguments that can achieve updatable BB-SE, which we define as a new variant of BB-SE. This new variant allows updating the public parameters, therefore eliminating the need for a trusted third party, while unavoidably relies on a 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). TIRAMIsu uses an efficient public-key encryption with updatable keys which may be of independent interest. We instantiate 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.