Paper 2020/474

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

Karim Baghery and Mahdi Sedaghat

Abstract

In CRYPTO'18, Groth et al. introduced the $\textit{updatable}$ CRS model that allows bypassing the trust in the setup of NIZK arguments. Zk-SNARKs are the well-known family of NIZK arguments that are ubiquitously deployed in practice. In applications that achieve $\textit{universal composability}$, e.g. Hawk [S&P'16], Gyges [CCS'16], Ouroboros Crypsinous [S&P'19], the underlying SNARK is lifted by the $\texttt{COCO}$ framework [Kosba et al.,2015] to achieve Black-Box Simulation Extractability (BB-SE). The $\texttt{COCO}$ framework is designed in the standard CRS model, consequently, all BB-SE NIZK arguments built with it need a trusted setup phase. In a promising research direction, recently subversion-resistant and updatable SNARKs are proposed that can eliminate/bypass the needed trust in schemes. However, none of the available subversion-resistant/updatable schemes can achieve BB-SE, as Bellare et al.'s result from ASIACRYPT'16 shows that achieving simultaneously Sub-ZK (ZK without trusting a third party) and BB extractability is impossible. In this paper, we propose $\texttt{Tiramisu}$, as construction to build BB-SE NIZK arguments in the $\textit{updatable}$ CRS model. Similar to the $\texttt{COCO}$, $\texttt{Tiramisu}$ is suitable for modular use in larger cryptographic systems and allows building BB-SE NIZK arguments, but with $\textit{updatable}$ parameters. Our results show that one can bypass the impossibility of achieving Sub-ZK and BB extractability in the updatable CRS model. In new constructions, in the cost of updating, all parties can eliminate the trust on a third-party and the protocol satisfies ZK and BB-SE. Meanwhile, we define public-key cryptosystems with updatable keys and present an efficient construction based on the El-Gamal cryptosystem which can be of independent interest. We instantiate $\texttt{Tiramisu}$ and present efficient BB-SE zk-SNARKs with updatable parameters that can be used in protocols like Hawk, Gyges, Ouroboros Crypsinous while allowing the end-users to update the parameters and eliminate the needed trust.

Note: In Italian, Tiramisu literally means "pull me up, lift me up", or more literally "pull it up".