Fast and designated-verifier friendly zk-SNARKs in the BPK model

Abstract Zero knowledge succinct non-interactive arguments of knowledge protocol (zk-SNARK) is an application oriented variant of zero knowledge proof, which enables a prover to convince a verifier that a statement is true, without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities and high efficiency, it has been widely deployed in various blockchain based applications to provide privacy and scalability. While these applications place high demands on small proof size, fast verification and decentralization, currently available zk-SNARK with the shortest proof size and the fastest verification speed is in the common reference string (CRS) model, that is they require the trusted setup. After the pioneering results proposed by Bellare et al. in ASIACRYPT 2016, there have been lots of efforts to construct zk-SNARKs that satisfy subversion zero knowledge (S-ZK) and standard soundness from the zk-SNARK in the CRS model. These constructions could be regarded secure in the bare public key (BPK) model because that the equivalence between S-ZK in the CRS model, and uniform non-black-box zero knowledge in the BPK model has been proved by Abdolmaleki et al. in PKC 2020. Thus, compared to the CRS model, the BPK model better characterizes decentralized blockchain based application such as cryptocurrencies and anonymous credentials. In this study, by leveraging the power of random oracle (RO) model, we proposed the first publicly verifiable non-uniform ZK zk-SNARK scheme in the BPK model maintaining comparable efficiency with its conventional counterpart, which can also be compatible with the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain an efficient designated-verifier zk-SNARK. We achieve this goal by only adding a constant number of elements into the CRS, and using an unconventional but natural method to transform Groth’s zk-SNARK in EUROCRYPT 2016. In addition, we propose a new speed-up technique that provides a trade-off. Specifically, if a logarithmic number of elements are added into the CRS, according to different circuits, the CRS verification time in our construction could be approximately 9–23% shorter than that in the conventional counterpart.