A Unified Framework for Non-universal SNARKs

Abstract

We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have relatively simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth’s SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK relies on few additional conditions. We prove security in a weaker, more realistic version of the algebraic group model. We characterize SAP, SSP, and QSP in terms of QAP; this allows one to use a SNARK for QAP directly for other languages. Our results allow us to construct a family of SNARKs for different languages and with different security properties following the same proof template. Some of the new SNARKs are more efficient than prior ones. In other cases, the new SNARKs cover gaps in the landscape, e.g., there was no previous ASE or Sub-ZK SNARK for SSP or QSP.

1 Introduction

There are many different SNARKs [21,22,23, 30, 31, 36] that differ in the target language and the security objectives. Common target languages correspond to specific quadratic constraint satisfaction systems, and the choice of language depends on the application. The languages QAP [21] and SAP [23, 25] are useful when arguing about arithmetic circuits, while QSP [21, 31] and SSP [13] are handy when arguing about Boolean circuits.¹ While QAP, providing efficient reductions to arithmetic circuits, is the most useful language in general applications like cryptocurrencies [8], other languages have their applications. In particular, SSP is widely used in applications where Boolean circuits come naturally like in, say, shuffle arguments, [16].

The choice of security objectives depends on the application. Knowledge-soundness is often sufficient, but simulation-extractability (SE) is needed to get UC-security [12]. On the other hand, not having SE can be beneficial in applications that need malleability. Finally, security properties evolve. Both Sub-ZK (subversion zero-knowledge [1, 3, 7, 17]; the argument stays zero-knowledge even if the CRS is not trusted) and non-black-box SE [25] for SNARKs were defined in 2017, after most of the mentioned zk-SNARKs were proposed. [1, 3, 17] showed that the most efficient known SNARK by Groth [23] is Sub-ZK.

This has resulted in an era of SNARK proliferation: there exist knowledge-sound SNARKs for the mentioned four languages, some of which are Sub-ZK or SE. Groth and Maller [25] proposed a non-black-box strong any-simulation-extractable (SASE) SNARK that is only slightly less efficient than Groth’s SNARK [23]. Recall that knowledge-soundness means that a successful prover must know the witness, and SE means that the knowledge-soundness holds even if the prover had access to the simulation oracle, [37]. Dodis et al. [15] defined different variants of SE, see Sect. 2 for more information. Intuitively, in an ASE SNARK, one is allowed to maul an argument to a different argument for the same statement, while this is not allowed in a SASE SNARK. (Non-)black-box SE means that a (non-)black-box extractor extracts the witness. Black-box ASE is sufficient to obtain UC security.

However, the Groth-Maller SNARK is for the SAP language [23, 25]. Since SAP has an efficient reduction from arithmetic circuits with squaring gates instead of general multiplication gates, the SNARK from [25] works with approximately two times larger circuits than SNARKs for the QAP language. While non-black-box SASE is insufficient to obtain UC security, it is a stronger security notion than knowledge-soundness. In particular, a much simpler transformation suffices to obtain UC security when one starts with non-black-box SE SNARKs [5]. Due to the use of SAP, this transformation is twice as costly as the ones starting from SE SNARKs for QAP. Other known simulation-extractable Sub-ZK SNARKs include [10], which works in the random oracle model, and [4], based on updatable signature schemes.

Recently, [6] showed that Groth’s SNARK [23] satisfies the weaker non-black-box any-simulation-property ASE. As argued in [6, 29], (black-box or non-black-box) ASE is sufficient in many applications. The only known SE SNARKs are for QAP and SAP, and no previous efficient SE or Sub-ZK SNARKs are known for SSP or QSP.

Finally, [1, 3] proved the knowledge-soundness of Groth’s SNARK in the generic group model (GGM) with hashing. The “with hashing” part means that one allows the adversaries to use (say) elliptic curve hashing to create random group elements without knowing their discrete logarithms. More modern knowledge-soundness (and ASE) proofs of SNARKs are given in the algebraic group model (AGM, [19]). Unfortunately, the AGM proof of Groth’s SNARK in [19] does not allow the adversaries to hash. Proving the knowledge-soundness of Groth’s SNARK in the AGM “with hashing” seems to be still an open problem.

We aim to consolidate SNARK research by investigating how the choice of security properties and target language influences an argument system’s design. This is important as only a few researchers have in-depth knowledge of secure SNARK design. It is easy for even well-established research groups to err in such an endeavor; see, for example, [11, 18, 20, 35] for related cryptanalysis. The resulting complexity can be seen when following through the soundness proofs in say [23, 25]. Each existing SNARK has a tailored construction with a tailored security proof in its specific security models, and even verifying all the security proofs for all mentioned SNARKs is probably well beyond the most talented cryptographer’s capability.

This brings us to the main goal of this paper:

Construct a SNARK framework for a multitude of languages (e.g., QAP, SAP, QSP, and SSP) and satisfying a multitude of security objectives (knowledge-soundness vs. ASE, ZK vs. Sub-ZK) that allows for (1) a (relatively) simple security proof that can be easily modified to cover all the languages and security objectives, and (2) results in ASE and Sub-ZK SNARKs that are almost as efficient as the most efficient known knowledge-sound non-Sub-ZK SNARKs. Additionally, (3) prove their security in a realistic version of AGM “with hashing”.

Our Contributions. We propose a family of $2 \cdot 2 \cdot 4 = 16$ SNARKs that contains both knowledge-sound and ASE, and both ZK and Sub-ZK SNARKs, for all four mentioned languages (QAP, SAP, QSP, SSP). While the derivation of the first two SNARKs (namely, knowledge-sound no-Sub-ZK and its ASE version) is complicated, we obtain the other fourteen SNARKs with minor additional work. Thus, we obtain a framework for efficient random-oracle-less pairing-based SNARKs for both arithmetic and Boolean circuits. Previous knowledge-sound SNARKs for all four languages were each published in a separate paper, with corresponding ASE and Sub-ZK versions being proposed later, if at all.

The new knowledge-sound zk-SNARK $\mathsf {S_{qap}}$ for QAP is similar to Groth’s SNARK [23], except it has only two trapdoors instead of five. We replace 3 trapdoors with a well-chosen power of one trapdoor. After an even more careful choice of the powers, we also achieve CRS-verifiability [1, 3] and thus Sub-ZK; otherwise, the Sub-ZK version is precisely the same and thus also as efficient. Unlike Groth, who proposed his SNARK without explaining how he arrived at the construction, we thoroughly motivate each step of it. This enables researchers aiming for a different goal to deviate from the construction at the appropriate point.Importantly, we provide a simpler knowledge-soundness proof.

To prove ASE, we observe that due to the structure of the new SNARKs, an ASE adversary can successfully use at most one simulation query answer in the forgery attempt. We show that if the adversary used one query answer, this was necessarily a SASE and not an ASE attack. The ASE of $\mathsf {S_{qap}}$ follows. It is non-trivial that one-time ASE suffices. Moreover, unexpectedly, all powers of the trapdoor that result in $\mathsf {S_{qap}}$ being knowledge-sound result in it also being ASE.

We prove knowledge-soundness and ASE in a more realistic version of the AGM. The knowledge-soundness proof in [23] was given in the generic group model, while [19] provided an AGM proof. However, [19] considers adversaries that are purely algebraic and in particular do not have a capability to create random group elements without knowing their discrete logarithms. In our proofs, the adversary has such a capacity. We consider this proof (and the corresponding realistic version of the AGM) to be another major contribution of this paper.

Based on an observation about algebraic relations between the languages, we modify $\mathsf {S_{qap}}$ to cover SAP, QSP, and SSP. Hence, almost automatically, we obtain a family of knowledge-sound (or ASE), and zero-knowledge (or Sub-ZK) SNARKs for four different languages.

Table 1. Efficiency comparison of QAP/SAP/SSP/QSP-based random-oracle-less SNARKs $\varPsi$. $m$ (or $\tilde{m}$) and $n$ (or $\tilde{n}$) denote the number of wires and gates (or constraints) in the solutions. “$\checkmark$” (“$\approx$”) means that the corresponding SNARK (its slight modification) is Sub-ZK, with a citation to the Sub-ZK construction if needed. “$\mathfrak {m}_{\iota }$” (“$\mathfrak {a}_{\iota }$”) denotes scalar multiplication (addition) in group $\mathbb {G}_{\iota }$, “$\mathfrak {p}$” denotes pairing, and $\mathfrak {g}_{\iota }$ denotes the representation length of a $\mathbb {G}_{\iota }$ element in bits. In the case of $|\mathsf {crs}|$ and ’s computation, we omit constant or $m_{0}$-dependent addends like $+ (m_{0}+ 3) \mathfrak {g}_{1}$. We omit field operations and membership tests since they are dominated by significantly costlier group operations. $\mathsf {S_{sap}}$, $\mathsf {S_{ssp}}$, and $\mathsf {S_{ssp}}$ are described in the full version, [33].

Table 1 compares the efficiency of random-oracle-less SNARKs. It is fair to compare SNARKs for the same language; a comparison of SNARKs for different languages (for example, QAP vs. SAP) has to account for the complexity of the reduction from circuits to these languages. Note that [31] described a reduction from Boolean circuits to QSP and a linear PCP [9] for QSP but did not describe a SNARK. In all constructions, most of the prover’s scalar multiplications in Table 1 are multi scalar-multiplications. As seen from the table, the new ASE SNARK for SAP is more efficient than the (SASE) SNARK for SAP by Groth and Maller. No previous SE or Sub-ZK SNARKs were known for SSP or QSP, and Groth’s SNARK for QAP was only proven to be ASE in [6].

1.1 Technical Overview

In Sect. 3, we propose a knowledge-sound zk-SNARK $\mathsf {S_{qap}}$ for QAP. The argument consists of evaluations² $[A(x, y)]_{1}, [B(x, y)]_{2},[C_{s}(x, y)]_{1}$ of three bivariate polynomials $A(X, Y), B(X, Y), C_{s}(X, Y)$ at a random point (x, y). Here, $[A(x, y)]_{1}, [B(x, y)]_{2}$ commit to the vector of left and right inputs to all gates, while $[C_{s}(x, y)]_{1}$ combines a commitment to the vector of all output wires with the rest of the argument. The verifier checks that a bivariate polynomial $\mathcal {V}$, that depends in a known way on $A, B, C_{s}$, evaluates to 0 at the same point.

As in [23], we aim to make $[C_{s}(x, y)]_{1}$ to be computable only by the honest prover. The prover has access to the CRS that contains the evaluation of well-chosen polynomials at (x, y) in both $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$. We optimize to get an efficient SNARK while not sacrificing (much) in the knowledge-soundness proof’s simplicity. $\mathsf {S_{qap}}$ is very similar to Groth’s SNARK [23]; however, it uses only two trapdoors instead of five. This distinction is important: in [23], only two out of five trapdoors are used in simulation; thus, the other three trapdoors seem not to be needed. In general, it is important to minimize the number of components to the bare minimum so that the importance of each component is well understood. In $\mathsf {S_{qap}}$, we use well-chosen powers of one trapdoor y as substitutes for four out of the five trapdoors of Groth’s SNARK. (A similar technique to use one trapdoor to align “interesting” monomials together was used, e.g., in [24].)

Knowledge-Soundness Proof And A More Realistic Variant of The AGM. The knowledge-soundness proof is in the algebraic group model (AGM [19]). In the AGM, one considers algebraic adversaries that always know a linear relationship between their output and input group elements. As an important difference with the AGM of [19], we additionally allow the cheating prover to sample random elements of $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$. Such an extension of the generic group model is well-known, [1, 3, 7], but not established in the case of the AGM. It is also well understood why this extension is needed since otherwise, one can prove the security of false knowledge assumptions. Really, without this extension, one can prove that if an adversary on input $[1]_{1}$ outputs $[y]_{1}$, it must know y. This assumption does not hold since it is easy to generate random group elements by using hash-then-increment or elliptic curve hashing.

Fuchsbauer et al. [19] give an adversary access to a programmable random oracle [34] $\mathcal {O}$. can create a random group element by querying $\mathcal {O}$ that returns a uniformly random group element. In the security proof, one allows the reduction to program $\mathcal {O}$ by creating random group elements together with their discrete logarithms. Unfortunately, since the reduction knows the discrete logarithms, also in this model, one can prove the security of the above false knowledge assumption. We overcome this issue by using a different oracle simulation strategy by defining two adversaries (one for each trapdoor x and y) and by using two different oracle programming strategies. This results in the first known knowledge-soundness and ASE proof of (a version) of Groth’s SNARK [23] in a variant of the AGM with hashing where false knowledge assumptions like the above cannot be proven. This result is of independent importance.

Choosing Powers of y. The way we choose the powers of y is interesting by itself. In the security proof, $A, B, C_{s}$ are chosen maliciously and depend on additional indeterminates. Let Y be an indeterminate corresponding to y and $\boldsymbol{X}^*$ be the vector of all indeterminates, except Y, in the knowledge-soundness or ASE proof. $\boldsymbol{X}^*$ includes X (the indeterminate corresponding to x), indeterminates created when the adversary samples random group elements, and (in the case of ASE) indeterminates created by simulator queries. Since the adversary is algebraic, the polynomials $A(X)$, $B(X)$, and $C_{s}(X)$ belong to the span of the polynomials in the CRS, the random oracle answers, and (in the case of the ASE) the simulator answers. We use the AGM extractor to extract their maliciously chosen coefficients in this span, allowing us to recover the coefficients of the (Laurent) polynomial $\mathcal {V}$. The verification guarantees that $\mathcal {V}(\boldsymbol{x}^*, y) = 0$, where the trapdoor $\boldsymbol{x}^*$ instantiates the indeterminate $\boldsymbol{X}^*$.

The knowledge-soundness proof considers two cases, when $\mathcal {V}(\boldsymbol{X}^*, Y) = 0$ and $\mathcal {V}(\boldsymbol{X}^*, Y) \ne 0$ as a polynomial. Consider the first case. Then, $\mathcal {V}(\boldsymbol{X}^*, Y) = \sum \mathcal {V}_{Y^i} (\boldsymbol{X}^*) Y^i$ for known polynomials $\mathcal {V}_{Y^i} (\boldsymbol{X}^*)$, where i is a linear combination of the coefficients of a public but initially undetermined integer tuple $\boldsymbol{\varDelta } = (\alpha , \beta , \gamma , \delta , \eta )$. We prove that an algebraic prover is honest iff $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for six critical values i. (In Groth’s security proof, the number of critical values is significantly larger.) We choose $\boldsymbol{\varDelta }$ so that the corresponding six critical values i are distinct from each other and all other non-critical values j; in this case, we say that $\boldsymbol{\varDelta }$ is soundness-friendly. Moreover, we choose $\boldsymbol{\varDelta }$ so that the SNARK is relatively efficient. For example, we require that for all critical i, |i| is as small as possible, and check if there is a way to make some non-critical values j to coincide (this can shorten the CRS).

Finding a suitable $\boldsymbol{\varDelta }$, satisfying all the restrictions, is a moderately complex optimization problem. In particular, the number of non-zero coefficients of $V_{Y^i} (\boldsymbol{X}^*)$ (even in the knowledge-soundness proof and without allowing the adversary to create new indeterminates) is at least 30, depending on the SNARK. Because of the complexity of the problem, we used an exhaustive computer search to find $\boldsymbol{\varDelta }$. Due to the use of exhaustive search, exponents in the resulting SNARKs (see Eq. (11) for a recommended value of $\boldsymbol{\varDelta }$ and Eq. (12) for the description of the CRS when using this value of $\boldsymbol{\varDelta }$) may look somewhat obscure. However, the soundness-friendliness of the results of the exhaustive search are easy to verify manually (intuitively, this corresponds to checking that when $\boldsymbol{\varDelta }$ is instantiated as in Eq. (11), then the critical six entries in Eq. (10) are different from each other and all other entries). It is easy to find suboptimal choices of the exponents; however, such choices will usually not be sufficient for Sub-ZK. We feel that using exhaustive search adds to the strength of this paper.

Other Results. In Sect. 4, we prove that $\mathsf {S_{qap}}$ is ASE. We use the same proof strategy as in the case of knowledge-soundness. By analyzing the coefficients of $\mathcal {V}$, we get that the ASE adversary can use the result of at most one simulation query in the forgery attempt. If she used none, ASE follows from the knowledge-soundness. If she used one, then, due to an easily satisfiable additional requirement on the QAP instance, she was performing a SASE attack that is not an attack in the sense of ASE. For this proof to work, one needs $\boldsymbol{\varDelta }$ to satisfy additional restrictions on $\boldsymbol{\varDelta }$; however, we will show that any soundness-friendly $\boldsymbol{\varDelta }$ satisfies these requirements. Thus, any version of $\mathsf {S_{qap}}$ that is knowledge-sound is ASE, modulo a small, easily satisfiable, technical restriction.

As we mentioned before, $\mathsf {S_{qap}}$ is very similar to Groth’s SNARK. Groth proved knowledge-soundness in the case of symmetric pairings, and this implies knowledge-soundness in the case of asymmetric pairing. Asymmetric pairings are much more efficient than symmetric pairings and thus strongly preferred in practice. We obtain a simpler direct knowledge-soundness proof by explicitly assuming that the pairing is asymmetric. One corollary of our knowledge-sound proof is the up to our knowledge novel observation that Groth’s SNARK has a simple knowledge-soundness proof given that one uses asymmetric pairings. Having simpler (or alternative) security proofs is important by itself due to the easier verifiability; simpler proofs can also result in the construction of other protocols. We also use a more realistic variant of the AGM to prove knowledge-soundness. (The use of this variant of the AGM makes the security proof somewhat more complex again.) Moreover, we emphasize that the number of critical values i is much larger when one follows Groth’s original proof.

Our goal was not to duplicate Groth’s SNARK but to construct an efficient SNARK with a simple knowledge-soundness proof. Our exposition of the derivation of $\mathsf {S_{qap}}$ can also be seen as an intuitive pedagogical re-derivation of (a slight variant of) the most efficient existing pairing-based SNARK.

Fig. 1.

Algebraic relations between languages.

We make $\mathsf {S_{qap}}$ subversion-zero knowledge (Sub-ZK). According to the template of [1, 3], we construct a public CRS verification algorithm that checks that the CRS corresponds to some trapdoor, and then use a knowledge assumption to recover the trapdoor and simulate the argument. For the CRS-verifiability, we restrict the choice of $\boldsymbol{\varDelta }$ even more. This suffices: all new SNARKs are Sub-ZK when choosing $\boldsymbol{\varDelta }$ carefully. We then use the standard BDH-KE [1, 3] knowledge assumption to recover the trapdoor and simulate the argument.

In the full version [33], we consider the languages SAP [23, 25], SSP [13], and QSP [21, 31]. We explain their algebraic relation to QAP, and use it to lift $\mathsf {S_{qap}}$ to the setting of the corresponding languages. In the case of SSP and QSP, the algebraic relation is not obvious; we explain it in detail in the full version [33]. See Fig. 1 for a brief summary. This summary becomes clear later (e.g., QAP states that $U \mathbbm {z}\circ V \mathbbm {z}= W \mathbbm {z}$ for an input-witness vector $\mathbbm {z}$, while SAP states that $U \mathbbm {z}\circ U \mathbbm {z}= W \mathbbm {z}$ since $U = V$; here, U, V, and W are relation-dependent matrices that characterize the languages as constraint satisfaction problems), but we decided to have it here for an early reference.³

Our SNARK for SAP (and SSP) has a slightly different ASE proof compared to the SNARK for QAP. Previous research handled all four languages separately, and our (simple) relations seem to be novel in the case of SSP and QSP. We propose the first known either Sub-ZK or ASE SNARKs for SSP and QSP, and more generally, for Boolean circuits. Importantly, the new Sub-ZK ASE SNARK for SSP is more efficient than the knowledge-sound non-Sub-ZK SNARK of [13].

This work supersedes [32]. While the idea of using only two trapdoors is already present in [32], there are too many changes to enlist.

1.2 Further Work

Applications. We concentrate on the construction of the SNARKs themselves and leave possible applications for future work. The most evident efficiency benefit is in the case of the SSP, where the verifier computes only 3 pairings instead of 6 in [13]. This may result in more efficient shuffle arguments [16] that rely on SNARKs for SSP. The ASE and Sub-ZK properties of the new SNARKs, on the other hand, have the potential to guarantee the same properties in similar applications. For example, given the new ASE SNARK for SSP, it may be possible (but we leave it to future work) to construct an ASE shuffle argument.

Universal SNARKs. There is an even more significant SNARK proliferation when one also considers universal SNARKs. Within this paper, we only study SNARKs with circuit-dependent CRSs. Universal SNARKs deserve their own several papers, especially since much less is known in that scenario. (E.g., efficient SE universal SNARKs have only been proposed in a recent eprint [28].) However, some of the results of the current paper (like the relation between QAP, SAP, SSP, and QSP) are also interesting in the context of universal SNARKs. We are not aware, e.g., of any efficient universal SNARKs for SSP.

2 Preliminaries

For a matrix $\boldsymbol{A}$, $\boldsymbol{A}_{i}$ denotes its ith row and $\boldsymbol{A}^{(j)}$ denotes its jth column. Let ${\text {vect}}(\boldsymbol{A})$ be the vectorization of matrix , ${\text {vect}}(\boldsymbol{A}) = (A_{1 1}, A_{1 2}, \ldots , A_{1 m}, A_{2 1}, \ldots , A_{nm})$. denotes the set of univariate polynomials of degree $\le d$ over . PPT denotes probabilistic polynomial-time; is the security parameter. Let be an arbitrary negligible function, and be an arbitrary polynomial function. We write if . For an algorithm , is the image of , that is, the set of valid outputs of . denotes the random tape of (for given ), and denotes the uniformly random choice of r from . By we denote the fact that , given an input $\mathbbm {x}$ and a randomizer r, outputs y.

Assume $n$ is a power of two. Let $\omega$ be the $n$th primitive root of unity modulo p. ($\omega$ exists, given that $n\mid (p - 1)$.) Then, $Z(X) := \prod _{i = 1}^n(X - \omega ^{i - 1})$ is the unique degree $n$ monic polynomial such that $Z(\omega ^{i - 1}) = 0$ for all $i \in [1, n]$. For $i \in [1, n]$, let $\ell _{i} (X)$ be the ith Lagrange polynomial, the unique degree $n- 1$ polynomial such that $\ell _{i} (\omega ^{i - 1}) = 1$ and $\ell _{i} (\omega ^{j - 1}) = 0$ for $i \ne j$. Given , $\ell _{i} (\chi )$ for $i \in [1, n]$ can be computed efficiently. Clearly, $L_{\boldsymbol{k}} (X) := \sum _{i = 1}^nk_{i} \ell _{i} (X)$ is the interpolating polynomial of $\boldsymbol{k}$ at points $\omega ^{i - 1}$, with $L_{\boldsymbol{k}} (\omega ^{i - 1}) = k_{i}$.

Bilinear Groups. Let be an upper bound of the size of a circuit in the SNARKs. A bilinear group generator returns $(p, \mathbb {G}_{1}, \mathbb {G}_{2}, \mathbb {G}_{T}, \hat{e})$, where $\mathbb {G}_{1}$, $\mathbb {G}_{2}$, and $\mathbb {G}_{T}$ are three additive cyclic groups of prime order p, and $\hat{e}: \mathbb {G}_{1} \times \mathbb {G}_{2} \rightarrow \mathbb {G}_{T}$ is a non-degenerate efficiently computable bilinear pairing. Assume $n\mid (p - 1)$. As in say [7], we assume that is deterministic and cannot be subverted. (In practice, one can use a standardized curve.) We require the bilinear pairing to be Type-3; that is, there is no efficient isomorphism between $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$. We use the standard bracket notation, writing $[c]_{\iota }$ to denote $c P_{\iota }$ where $P_{\iota }$ is a fixed generator of $\mathbb {G}_{\iota }$. Note that $P_{\iota }$ is not given in . We denote $\hat{e}([a]_{1}, [b]_{2})$ by $[a]_{1} \bullet [b]_{2}$. We use freely the bracket notation together with matrix notation, for example, $\boldsymbol{A} \boldsymbol{B} = \boldsymbol{C}$ iff $[\boldsymbol{A}]_{1} \bullet [\boldsymbol{B}]_{2} = [\boldsymbol{C}]_{T}$.

Assumptions. Let $\mathcal {T}_{1}, \mathcal {T}_{2}$ be sets of small integers. is $(\mathcal {T}_{1}, \mathcal {T}_{2})$-PDL (Power Discrete Logarithm) secure if for any non-uniform PPT adversary ,

If $\mathcal {T}_{1} = [0, n]$, then we talk about the $(n, \mathcal {T}_{2})$-PDL assumption. The case $\mathcal {T}_{2} = [0, n]$ is dual.

The BDH-KE assumption [1, 3] holds for , if for every PPT adversary , there exists a PPT extractor , such that

BDH-KE is one of the weakest known knowledge assumptions in the asymmetric pairing-based setting.

Algebraic Group Model (AGM). AGM is a new idealized model [19] used to prove the security of a cryptographic assumption, protocol, or a primitive. In addition, [19] proposed to combine the random oracle (RO) model with the AGM, allowing the adversary to create random group elements. Essentially, in the AGM with random oracles, one assumes that each PPT algorithm is algebraic in the following sense. Assume ’s input includes $[\boldsymbol{x_{\iota }}]_{\iota }$ and no other elements from the group $\mathbb {G}_{\iota }$. Moreover, has an access to random oracles $\mathcal {O}_{\iota }$, $\iota \in \{1, 2\}$, such that $\mathcal {O}_{\iota }$ samples and outputs a random element $[q_{\iota k}]_{\iota }$ from $\mathbb {G}_{\iota }$. The oracle access models the ability of to create random group elements without knowing their discrete logarithms $q_{\iota k}$. However, a reduction can program [34] the random oracle so that it knows $q_{\iota k}$. Intuitively, one assumes that if outputs group elements $[\boldsymbol{y}_{\iota }]_{\iota }$, then knows matrices $\boldsymbol{N}_{\!\iota }$ and $([\boldsymbol{q}_{1}, \boldsymbol{q}_{2}]_{1})$, such that while the reduction also knows $\boldsymbol{q}_{\iota }$.

Formally, a PPT algorithm is ( -)algebraic if there exists an efficient extractor , such that for any PPT-sampleable distribution family ,

$\mathcal {O}_{\iota }$, $\iota \in \{1, 2\}$ is an oracle that samples and returns a random element from $\mathbb {G}_{\iota }$. $[\boldsymbol{q}_{\iota }]_{\iota }$ is the list of all elements output by $\mathcal {O}_{\iota }$. We denote the version of the AGM where the reduction can program $\mathcal {O}_{\iota }$, by first sampling a random element $q_{\iota k}$ from and then returning $\boldsymbol{q}_{\iota k}$, as $\text {RO}_{\mathsf {fkl}}$-AGM. The $\text {RO}_{\mathsf {fkl}}$-AGM states that, given such programmable random oracles, for any PPT-sampleable $\mathscr {D}$ and PPT algebraic .

SNARKs. Let $\mathsf {RG}$ be a relation generator, such that returns a polynomial-time decidable binary relation together with auxiliary information . Here, $\mathbbm {x}$ is a statement, and $\mathbbm {w}$ is a witness. We assume that is explicitly deductible from the description of $\mathbf {R}$. Intuitively, is the common auxiliary input to the honest parties, the adversary, and the corresponding extractor. We assume that for a well-defined $n$. (Recall that the choice of p and thus of the groups $\mathbb {G}_{\iota }$ depends on $n$ and that is not subvertible.) Let be an -language.

A non-interactive zero-knowledge (NIZK) argument system $\varPsi$ for $\mathsf {RG}$ consists of five PPT algorithms: First, a probabilistic CRS generator $\mathsf {G}$ that, given , outputs $(\mathsf {crs}, \mathsf {td})$ where $\mathsf {crs}$ is a CRS and $\mathsf {td}$ is a simulation trapdoor. Otherwise, it outputs a special symbol $\bot$. For the sake of efficiency and readability, we divide $\mathsf {crs}$ into (the part needed by the prover) and (the part needed by the verifier). Within this paper, $\mathsf {crs}$ explicitly encodes $\mathbf {R}$. We also implicitly assume that $\mathsf {crs}$ encodes . Second, a probabilistic CRS verifier $\mathsf {CV}$ that, given $\mathsf {crs}$, returns either 0 (the CRS is malformed) or 1 (the CRS is well-formed). $\mathsf {CV}$ is only required to exist in the case of Sub-ZK argument systems. Third, a probabilistic prover that, given for , outputs an argument $\pi$. Otherwise, it outputs $\bot$. Fourth, a probabilistic verifier that, given , returns either 0 (reject) or 1 (accept). Fifth, a probabilistic simulator that, given $(\mathsf {crs}, \mathsf {td}, \mathbbm {x})$, outputs an argument $\pi$.

A NIZK argument system must be complete (an honest verifier accepts an honest verifier), knowledge-sound (if a prover makes an honest verifier accept, then one can extract from the prover a witness $\mathbbm {w}$), and zero-knowledge (there exists a simulator that, knowing the CRS trapdoor but not the witness, can produce accepting statements with the verifier’s view being indistinguishable from the view when interacting with an honest prover). A Sub-ZK argument system [1, 3] must additionally satisfy Sub-ZK (zero-knowledge holds even if the CRS is maliciously generated); for this, one requires CRS-verifiability ($\mathsf {CV}$ only accepts a CRS if there exists a trapdoor $\mathsf {td}$ corresponding to it).

We will now give the formal definitions. Let $\varPsi$ be a non-interactive argument. $\varPsi$ is perfectly complete for $\mathsf {RG}$, if for all , , and ,

$\varPsi$ is computationally (adaptively) knowledge-sound for $\mathsf {RG}$, if for every PPT , there exists a PPT extractor , such that for all ,

A knowledge-sound argument system is called an argument of knowledge.

$\varPsi$ is statistically composable zero-knowledge for $\mathsf {RG}$, if for all , , and computationally unbounded , , where

$\varPsi$ is perfectly composable Sub-ZK for $\mathsf {RG}$ if one requires that $\varepsilon ^{zk}_{0} = \varepsilon ^{zk}_{1}$.

$\varPsi$ is statistically composable Sub-ZK for $\mathsf {RG}$, if for any PPT subverter $\mathcal {S}$ there exists a PPT , such that for all , all , and all computationally unbounded , , where

$\varPsi$ is perfectly composable Sub-ZK for $\mathsf {RG}$ if one requires that $\varepsilon ^{zk}_{0} = \varepsilon ^{zk}_{1}$.

A SNARK (succinct non-interactive argument of knowledge) is a NIZK argument system where the argument is sublinear in the input size.

Simulation-Extractability (SE). An SE argument system [14, 37] stays knowledge-sound even if the soundness adversary has access to the simulation oracle. SE is motivated by applications like non-malleability and UC security.

Dodis et al. [15] differentiated between several favors of SE. In the case of any-simulation-extractability (ASE), the simulator can be queried with any (potentially false) statements while in the case of true-simulation-extractability (TSE), the simulator can only be queried with true statements. The adversary wins if she can come up with a new argument for a statement she has not queried a simulation for. In the case of strong any-simulation-extractability (SASE), the adversary wins even if she can come up with a new argument for a statement she has queried a simulation for. ASE suffices for UC security.

Groth and Maller [25] define SE SNARKs, where one requires that for each PPT knowledge-soundness adversary with oracle access to the simulator, there exists a non-black-box extractor that can extract the witness. [25]’s definition of SE corresponds to non-black-box SASE, [15]. We assume implicitly SE means non-black-box SE. [25] proved that the argument of any (non-black-box) SASE SNARK consists of at least three group elements and that there should be at least two verification equations. They proposed a SASE SNARK for the SAP (Square Arithmetic Program) language that meets the lower bounds.

The following definition of the SASE property corresponds to the definition of SE SNARKs in [25, Definition 2.10]. All definitions are inspired by the corresponding black-box definitions from [15].

Fig. 2.

Any-simulation (ASE) and strong any-simulation (SASE) experiments. The part is only present in the boxed (i.e., SASE) experiment.

Let $\varPsi$ be a SNARK for the relation $\mathbf {R}$. Let $\mathsf {x} \in \{\mathsf {ase}, \mathsf {sase}\}$. Define , where the experiment is depicted in Fig. 2. Then, (i) $\varPsi$ is non-black-box any-simulation-extractable (ASE) if for any PPT there exists a PPT extractor , such that . (ii) $\varPsi$ is non-black-box strong any-simulation-extractable (SASE) if for any PPT there exists a PPT extractor , such that .

3 Knowledge-Sound SNARK for QAP

Next, we will describe the new knowledge-sound SNARK $\mathsf {S_{qap}}$. Its construction emphasizes two objectives: (i) simple soundness proof in the AGM and (ii) efficiency. $\mathsf {S_{qap}}$ is similar to Groth’s SNARK from EUROCRYPT 2016 [23] (shown to be Sub-ZK in [17]), with two major differences: (1) the use of only two trapdoors instead of five, and (2) an alternative, much more straightforward, knowledge-soundness proof in the case of asymmetric pairings. On the other hand, Groth provided a more complex knowledge-soundness proof that is valid for both asymmetric and symmetric pairings.

QAP. Quadratic Arithmetic Program (QAP) was introduced in [21] as a language where for an input $\mathbbm {x}$ and witness $\mathbbm {w}$, can be verified by using a parallel quadratic check. QAP has an efficient reduction from the (either Boolean or Arithmetic) Circuit-SAT. Thus, an efficient zk-SNARK for QAP results in an efficient zk-SNARK for Circuit-SAT.

We consider arithmetic circuits that consist only of fan-in-2 multiplication gates, but either input of each multiplication gate can be any weighted sum of wire values, [21]. Let $m_{0}< m$ be a non-negative integer. For an arithmetic circuit, let $n$ be the number of multiplication gates, $m$ be the number of wires, and $m_{0}$ be the number of public inputs.

Let . For the sake of efficiency, we require the existence of the $n$th primitive root of unity modulo p, denoted by $\omega$. Let U, V, and W be instance-dependent matrices and let $\mathbbm {z}$ be a witness. A QAP is characterized by the constraint $U \mathbbm {z}\circ V \mathbbm {z}= W \mathbbm {z}$. For $j \in [1, m]$, define $u_{j} (X) := L_{U^{(j)}} (X)$, $v_{j} (X) := L_{V^{(j)}} (X)$, and $w_{j} (X) := L_{W^{(j)}} (X)$ to be interpolating polynomials of the jth column of the corresponding matrix. Thus, . Let $u (X) = \sum \mathbbm {z}_{j} u_{j} (X)$, $v (X) = \sum \mathbbm {z}_{j} v_{j} (X)$, and $w (X) = \sum \mathbbm {z}_{j} w_{j} (X)$. Then $U \mathbbm {z}\circ V \mathbbm {z}= W \mathbbm {z}$ iff $Z(X) \mid u (X) v (X) - w (X)$ iff $u (X) v (X) \equiv w (X) \pmod {Z(X)}$ iff there exists a polynomial h(X) such that $u (X) v (X) - w (X) = h(X) Z(X)$.

An QAP instance $\mathcal {I}_{\mathsf {qap}}$ is equal to . This instance defines the following relation:

(1)

where $u (X) = \sum _{j = 1}^m\mathbbm {z}_{j} u_{j} (X)$, $v (X) = \sum _{j = 1}^m\mathbbm {z}_{j} v_{j} (X)$, and $w (X) = \sum _{j = 1}^m\mathbbm {z}_{j} w_{j} (X)$ as above. That is, if there exists a (degree $\le n- 2$) polynomial $h(X)$, such that the following key equation holds:

$$\begin{aligned} \textstyle \chi (X) := u (X) v (X) - w (X) - h(X) Z(X) = 0 , \end{aligned}$$

(2)

On top of checking Eq. (2), the verifier also needs to check that u(X), v(X), and w(X) are correctly computed: that is, that (i) the first $m_{0}$ coefficients $\mathbbm {z}_{j}$ in u(X) are equal to the public inputs, and (ii) u(X), v(X), and w(X) are all computed by using the same coefficients $\mathbbm {z}_{j}$ for $j \le m$.

SNARK Derivation. Let u(X) , v(X), w(X), and $\chi (X)$ be as in Sect. 2. Recall from Eq. (2) that the key equation of QAP states that the prover is honest iff $\chi (X) = 0$, that is, $h(X) := (u (X) v (X) - w (X)) / Z(X)$ is a polynomial. We will use bivariate polynomials like $A(X, Y)$. The indeterminate X is related to the definition of QAP. The indeterminate Y groups together correct X-polynomials in the security proof; such a grouping approach was also used in say [24]. The argument in the new template consists of three elements, $\pi = ([\mathsf {a}, \mathsf {c}_{s}]_{1}, [\mathsf {b}]_{2})$, where $\mathsf {a}= A(x, y)$, $\mathsf {b}= B(x, y)$, and $\mathsf {c}_{s}= C_{s}(x, y)$ for well-defined polynomials $A(X, Y)$, $B(X, Y)$, and $C_{s}(X, Y)$. Intuitively, $[\mathsf {a}]_{1}$ is a succinct commitment to u(X), $[\mathsf {b}]_{2}$ is a succinct commitment to v(X), and $[\mathsf {c}_{s}]_{1}$ is the “actual” argument that at the same time commits to w(X).

As in all most efficient random-oracle-less zk-SNARKs [21, 23, 31, 36], we aim to make $[\mathsf {c}_{s}]_{1}$ to be computable only by the honest prover. The prover has access to the CRS that contains the evaluation of well-chosen polynomials at (x, y) in both $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$. The knowledge-soundness proof is in the AGM. There, we show that if the verification polynomial $\mathcal {V}(X, Y) = 0$, and $A(X, Y)$, $B(X, Y)$, and $C_{s}(X, Y)$ are in the span of the polynomials in the CRS, then it must hold that $\chi (X) = 0$ and thus the prover is honest.

More precisely, let $\boldsymbol{\varDelta } := (\alpha , \beta , \gamma , \delta , \eta )$ be a tuple of small integers chosen later. We will give a complete derivation of the new SNARK. We will also derive the conditions $\boldsymbol{\varDelta }$ has to satisfy for the SNARK to be knowledge-sound; in Sects. 5 and 4, we add more conditions to achieve both CRS-verifiability (and thus Sub-ZK) and ASE. We find it instructional to go first through the process with unfixed $\boldsymbol{\varDelta }$. In Eq. (11), we propose a setting of $\boldsymbol{\varDelta }$ that is sufficient to obtain all knowledge-soundness, ASE, and CRS-verifiability.

For randomizers $r_{a}$ and $r_{b}$ needed to make the commitment hiding, define

$$\begin{aligned} \begin{aligned} A(X, Y) := r_{a}Y^{\alpha } + u (X) Y^{\beta }, \quad B(X, Y) := r_{b}Y^{\alpha } + v (X) Y^{\beta } \end{aligned} \end{aligned}$$

(3)

to be “commitments” to u(X) and v(X). We use different powers of Y to separate the randomness from the committed values. Define also

$$\begin{aligned} \begin{aligned} C(X, Y) :=\,&(A(X, Y) + Y^\gamma ) (B(X, Y) + Y^\delta ) - Y^{\gamma + \delta } \\ =\,&u (X) Y^{\beta + \delta } + v (X) Y^{\beta + \gamma } + u (X) v (X) Y^{2 \beta } + R(X, Y) Y^\alpha \\ =\,&P(X, Y) + (u (X) v (X) - w (X)) Y^{2 \beta } + R(X, Y) Y^\alpha \end{aligned} \end{aligned}$$

(4)

where $P(X, Y) := u (X) Y^{\beta + \delta } + v (X) Y^{\beta + \gamma } + w (X) Y^{2 \beta }$ and $R(X, Y) := r_{b}(A(X, Y) + Y^{\gamma }) + r_{a}(v (X) Y^{\beta } + Y^{\delta })$.

The inclusion of $Y^\gamma$ and $Y^\delta$ in the definition of $C(X, Y)$ serves three goals. First, it introduces the addend $P(X, Y) = \sum _{j = 1}^{m} \mathbbm {z}_{j} P_{j} (X, Y)$, where

$$\begin{aligned} P_{j} (X, Y) := u_{j} (X) Y^{\beta + \delta } + v_{j} (X) Y^{\beta + \gamma } + w_{j} (X) Y^{2 \beta }; \end{aligned}$$

(5)

this makes it easier to verify that uses the same coefficients $\mathbbm {z}_{j}$ when computing $[\mathsf {a}]_{1}$, $[\mathsf {b}]_{2}$, and $[\mathsf {c}_{s}]_{1}$. Second, it makes it possible to verify that uses the correct public input. Third, the coefficient of $Y^{2 \beta }$, $u (X) v (X) - w (X)$, divides by $Z(X)$ iff the prover is honest. That is, it is $h (X) Z(X)$ for some polynomial h(X) iff the prover is honest and thus $\mathbbm {x}\in \mathcal {L}_{\mathcal {I}_{\mathsf {qap}}}$.

On top of $\chi (X) = 0$, it must be possible to check that the public input $(\mathbbm {z}_{j})_{j = 1}^{m_{0}}$ is correct. To this end, we define polynomials $C_{s}(X, Y)$ and $C_{p} (X, Y)$, s.t. $C(X, Y) = C_{p} (X, Y) Y^\eta + C_{s}(X, Y) Y^\alpha$. Here, $[\mathsf {c}_{p}]_{1} = [C_{p} (x, y)]_{1}$ is recomputed by the verifier and thus $C_{p} (X, Y)$ must not depend on $\mathbbm {z}_{j}$ for $j > m_{0}$ (i.e., on the secret information). To minimize the verifier’s computation, $C_{p} (X, Y)$ has only $m_{0}$ addends. $C_{s}$ depends both on public and secret inputs, and only an honest prover should be able to compute $[\mathsf {c}_{s}]_{1} = [C_{s}(x, y)]_{1}$. Thus, we define

$$\begin{aligned} \begin{aligned} C_{p} (X, Y) :=&\textstyle \sum _{j = 1}^{m_{0}} \mathbbm {z}_{j} P_{j} (X, Y) Y^{-\eta } \\ C_{s}(X, Y) :=&\textstyle \sum _{j = m_{0}+ 1}^m\mathbbm {z}_{j} P_{j} (X, Y) Y^{-\alpha } + (u (X) v (X) - w (X)) Y^{2 \beta - \alpha } + R(X, Y) . \end{aligned} \end{aligned}$$

(6)

Fig. 3.

The new SNARK $\mathsf {S_{qap}}$. Moreover, $\mathsf {S_{qsp}}$ is exactly like $\mathsf {S_{qap}}$, except $w_{j} (X) = 0$.

Here, we use the factors $Y^\eta$ and $Y^\alpha$ to separate the public input and the witness in the security proof. For efficiency reasons, we use $Y^\alpha$, instead of a new power of Y: now $C_{s}(X, Y)$ has an addend $r_{b}A(X, Y)$ that reuses the value $A(X, Y)$.

As mentioned before, the SNARK argument is $\pi = ([\mathsf {a}, \mathsf {c}_{s}]_{1}, [\mathsf {b}]_{2})$. The verifier recomputes $[\mathsf {c}_{p}]_{1} \leftarrow [C_{p} (x, y)]_{1}$ and $[C(x, y)]_{T} \leftarrow [\mathsf {c}_{p}]_{1} \bullet [y^\eta ]_{2} + [\mathsf {c}_{s}]_{1} \bullet [y^\alpha ]_{2}$. Then, the verifier checks that $C(x, y)$ is computed correctly by checking that $C(x, y) = (A(x, y) + y^\gamma ) (B(x, y) + y^\delta ) - y^{\gamma + \delta }$.

We are now ready to describe the SNARK $\mathsf {S_{qap}}$, see Fig. 3. The CRS consists of elements needed by the honest prover, the honest verifier, and the simulator. We will explain the simulator in the proof of Theorem 1. The CRS has two trapdoors (x and y), but the simulator uses only one of them (y). ([1, 3] formalized the difference by defining two different types of trapdoors, CRS trapdoors $\mathsf {td_{crs}}$ and simulation trapdoors $\mathsf {td_{sim}}$. In $\mathsf {S_{qap}}$, $\mathsf {td_{crs}}= (x, y)$ and $\mathsf {td_{sim}}= y$.)

Security Intuition. We prove knowledge-soundness in the AGM with random oracles. Recall that an algebraic adversary can use the oracle $\mathcal {O}_{\iota }$, $\iota \in \{1, 2\}$, to create new random group elements $[q_{1 i}]_{\iota }$. Let $\boldsymbol{Q}_{\iota }$ be the vector of corresponding indeterminates in $\mathbb {G}_{\iota }$. Let $\boldsymbol{X} = (X, \boldsymbol{Q}_{1}, \boldsymbol{Q}_{2}, Y)$ (resp., $\boldsymbol{x} = (x, \boldsymbol{q}_{1}, \boldsymbol{q}_{2}, y)$) be the tuple of all indeterminates (resp., corresponding random integers).

Write the CRS in Fig. 3 as $\mathsf {crs}= (\mathsf {crs}_{1}, \mathsf {crs}_{2})$, where $\mathsf {crs}_{\iota } = [(f (x, y))_{f \in \varGamma _{\iota }}]_{\iota }$ for a public set $\varGamma _{\iota }$ of polynomials. For example, $\varGamma _{2} = \{Y^\alpha , Y^\delta , Y^\eta \} \cup \{X^j Y^\beta \}_{j = 0}^{n- 1}$. (As an optimization, the CRS of $\mathsf {S_{qap}}$ also includes $\smash {[y^{\gamma + \delta }]_{T}}$, but it can be recomputed from the available elements in $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$.) Since we work in the AGM, the malicious prover is algebraic and thus we can extract matrices $\boldsymbol{N}_{\!1}$ and $\boldsymbol{N}_{\!2}$, such that and . This means, that we can write $\mathsf {a}= A^\dagger (\boldsymbol{x})$, $\mathsf {b}= B^\dagger (\boldsymbol{x})$, and $\mathsf {c}_{s}= C_{s}^\dagger (\boldsymbol{x})$, where $A^\dagger (\boldsymbol{X})$, $B^\dagger (\boldsymbol{X})$, and $C_{s}^\dagger (\boldsymbol{X})$ are maliciously computed polynomials with known coefficients. We can recover all coefficients of $A^\dagger (\boldsymbol{X})$, $B^\dagger (\boldsymbol{X})$, and $C_{s}^\dagger (\boldsymbol{X})$ from $\boldsymbol{N}_{\!1}$ and $\boldsymbol{N}_{\!2}$, as follows:

$$\begin{aligned} \begin{aligned} A^\dagger (\boldsymbol{X}) :=\,&\textstyle \sum _{j = 1}^{m_{0}} a^*_{j} P_{j} (X, Y) Y^{-\eta } + \sum _{j = m_{0}+ 1}^{m} a^*_{j} P_{j} (X, Y) Y^{-\alpha } + r_{a}Y^\alpha \\&+\, \textstyle u_{a} (X) Y^\beta + h_{a} (X) Z(X) Y^{2 \beta - \alpha } + a_{\gamma } Y^\gamma + a_{\delta } Y^{\delta } + \sum _{k} q_{a k} Q_{1 k} ,\\ C_{s}^\dagger (\boldsymbol{X}) :=\,&\textstyle \sum _{j = 1}^{m_{0}} c^*_{j} P_{j} (X, Y) Y^{-\eta } + \sum _{j = m_{0}+ 1}^{m} c^*_{j} P_{j} (X, Y) Y^{-\alpha } + r_{c}Y^\alpha \\&+\, \textstyle u_{c} (X) Y^\beta + h_{c} (X) Z(X) Y^{2 \beta - \alpha } + c_{\gamma } Y^\gamma + c_{\delta } Y^{\delta } + \sum _{k} q_{c k} Q_{1 k} ,\\ B^\dagger (\boldsymbol{X}) :=\&\textstyle r_{b}Y^{\alpha } + v_{b} (X) Y^{\beta } + b_{\delta } Y^{\delta } + b_{\eta } Y^{\eta } + \sum _{k} b_{qk} Q_{2 k} , \end{aligned} \end{aligned}$$

(8)

where, say , , and .

The verification equation Eq. (7) guarantees $\mathcal {V}(\boldsymbol{x}) = 0$, where

$$\begin{aligned} \mathcal {V}(\boldsymbol{X}) := (A^\dagger (\boldsymbol{X}) + Y^\gamma ) (B^\dagger (\boldsymbol{X}) + Y^\delta ) - Y^{\gamma + \delta } - C_{p} (X, Y) Y^{\eta } - C_{s}^\dagger (\boldsymbol{X}) Y^{\alpha } . \end{aligned}$$

(9)

Note that $C_{p}$ is honestly computed. Since we know all coefficients of polynomials like $A^\dagger (\boldsymbol{X})$, we also know all coefficients of $\mathcal {V}(\boldsymbol{X})$.

On the Use of AGM. In the knowledge-soundness proof, we assume that the knowledge-soundness adversary is algebraic and then break the PDL assumption. More precisely, with use the AGM with random oracles. However, we note that $\text {RO}_{\mathsf {fkl}}$-AGM is not realistic since it allows to prove the security of false knowledge assumptions.⁴ Really, consider the assumption that any PPT adversary , that on input $[1]_{1}$ generates $[x]_{1}$, must know x. This assumption is false in the settings where has access to an efficient method (e.g., hash-and-increment or elliptic curve hashing) of creating random group elements without knowing their discrete logarithms. However, in the $\text {RO}_{\mathsf {fkl}}$-AGM, one can extract an integer vector $\boldsymbol{N}$ and group element vector $[\boldsymbol{q}]_{1}$, such that $[x]_{1} = \boldsymbol{N}^\top \left[ {\begin{matrix}1 \\ \boldsymbol{q}\end{matrix}}\right] _{1} = N_{1} [1]_{1} + \sum _{i \ge 1} N_{1 + i} [q_{i}]_{1}$. Moreover, the reduction can program the random oracle by first creating the discrete logarithms $q_{k}$ of each coordinate of $[\boldsymbol{q}]_{1}$. Then, $[x]_{1} = (N_{1} + \sum _{i \ge 1} N_{1 + i}) [1]_{1}$ and thus the reduction can output its discrete logarithm $x \leftarrow N_{1} + \sum _{i \ge 1} N_{1 + i}$. One has exactly the same issue when using AGM without random oracles (in this case, $\boldsymbol{q}$ has length 0).

The problem is that the reduction knows $\boldsymbol{q}$ and can thus compute x. The knowledge of $\boldsymbol{q}$ should be impossible if has created $[q_{k}]_{1}$ by using elliptic curve hashing. We modify the AGM with random oracles so that one can still prove the security of (thought to be) secure knowledge assumptions but not of assumptions of the above type. The first idea is to restrict the way the reduction is allowed to program the random oracle: given that the input of the reduction (who aims to break the PDL assumption) is , we require that the reduction programs the random oracle $\mathcal {O}_{\iota }$ by creating random integers and then outputting $s [x]_{\iota } + t$. Such “linear programming” was already used in [19] but in a different context. For example, it was used to implicitly create other CRS trapdoors from and in one case (the security proof of the RO-model BLS signature) also to program the random oracle. However, our usage of this strategy is in a novel context and for a novel goal.

We modify the strategy of AGM with random oracles of [19] even further. When using the described “linear programming” strategy to construct a PDL adversary that obtains input, depending on one trapdoor (say, x), and then uses this to create a multivariate $\mathsf {crs}$ for the knowledge-soundness adversary . For the reduction to be successful, creates other trapdoors (notably, including $q_{\iota k}$) implicitly as linear functions of x. E.g., sets $[y]_{1} \leftarrow s_{y} [x]_{1} + t_{y} [1]_{1}$, for random $s_{y}$ and $t_{y}$, and similarly $[y^i]_{1} \leftarrow [(s_{y} x + t_{y})^i]_{1}$; this assumes that $[1, x, \ldots , x^i]_{1}$ are given in the CRS. In the security proof, this means that one can write $\mathcal {V}$ as a univariate (Laurent) polynomial $\mathcal {V}_{x} (X) = \mathcal {V}(\boldsymbol{X})$ and then use a polynomial factorization algorithm to compute x in the case $\mathcal {V}(\boldsymbol{X}) \ne 0$ but $\mathcal {V}(\boldsymbol{x}) = 0$.

This strategy has some undesirable properties. First, for every monomial $[x^i y^j]_{\iota }$ in the CRS, we need to give $[x^{i + j}]_{\iota }$ as an input to the PDL adversary. Since $\max i, \max j < \max (i + j)$ and $(n+ 1, n')$-PDL is stronger than $(n, n')$-PDL in the AGM, one uses a stronger PDL assumption. Second, this strategy is challenging to implement when, as in our case, the CRS depends on the negative powers of some trapdoors. Really, given $[1 / x^{i}]_{1}$ for various i-s, it is presumably hard to compute $[1 / {(s x + t)^j}]_{1}$ for $j > 1$ and random s and t; due to this reason, the “linear programming” strategy cannot be used to prove the knowledge-soundness of $\mathsf {S_{qap}}$ (or Groth’s SNARK since it also involves negative powers of trapdoors).⁵ Finally, the degree of $\mathcal {V}_{x}$ is related to the total degree of $\mathcal {V}$.

We use a different strategy. We define two different adversaries, one aiming to compute x (given a PDL input that depends on x) and another aiming to compute y (given a PDL input that depends on y). Both adversaries generate the second trapdoor randomly. The reduction programs the oracles differently, by using the “linear programming” strategy in one case and the $\text {RO}_{\mathsf {fkl}}$ strategy in another case. (This is detailed in Fig. 4.) As a direct benefit, inside the reduction, we deal with polynomials of smaller degrees. Moreover, instead of giving $[x^{i + j}]_{\iota }$ to the adversary, we give $[x^i]_{\iota }$ as an input to one adversary and $[y^j]_{\iota }$ to another adversary. Hence, we can potentially rely on a weaker PDL assumption. Finally, since the second adversary ( in Fig. 4) uses the $\text {RO}_{\mathsf {fkl}}$ strategy, it is easy to handle CRS elements of type $[y^{-1}]_{1}$ since one chooses y randomly. On the other hand, since the first adversary uses the “linear programming” strategy, one cannot prove the security of the false knowledge assumption described above.

On the Choice of Exponents. Another complicated part of the knowledge-soundness proof is the analysis of what happens if $\mathcal {V}(\boldsymbol{X}) \ne 0$ as a Laurent polynomial, but the verification succeeds, that is, $\mathcal {V}(\boldsymbol{x}) = 0$. Let $\boldsymbol{X}^* = (X, \boldsymbol{Q}_{1}, \boldsymbol{Q}_{2})$ and $\boldsymbol{x}^* = (x, \boldsymbol{q}_{1}, \boldsymbol{q}_{2})$. Writing $\mathcal {V}(\boldsymbol{X}) = \sum _{i} \mathcal {V}_{Y^i} (\boldsymbol{X}^*) Y^i$ for known Laurent polynomials $\mathcal {V}_{Y^i} (\boldsymbol{X}^*)$, we get $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for each i. There are 29 non-trivial coefficients $\mathcal {V}_{Y^i} (\boldsymbol{X}^*)$, for $i \in$

(10)

It is possible but very tedious to show that from $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for each twenty nine i-s, we get that $\chi (X) = 0$ and thus, the prover is honest. To simplify the knowledge-soundness proof, we constructed $\mathsf {S_{qap}}$ so that there exists a small set $\mathsf {Crit}$ of six elements, such that $\chi (X) = 0$ follows from $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for $Y^i \in \mathsf {Crit}$.

For this idea to work, we need to restrict the choice of $\boldsymbol{\varDelta }$: namely, $\boldsymbol{\varDelta }$ has to be such that the exponents in $\mathsf {Crit}$ are different from each other and all other exponents of Y in $\mathcal {V}(\boldsymbol{X})$. More precisely, define $\mathsf {Coeff}:= \{Y^i : \mathcal {V}_{Y^i} (\boldsymbol{X}^*) \ne 0\}$,

$$ \mathsf {Crit}:= \{Y^{2 \beta }, Y^{\beta + \gamma }, Y^{\beta + \delta }, Y^{\gamma + \delta }, Y^{\gamma + \eta }, Y^{2 \delta }\}, $$

and let $\overline{\mathsf {Crit}} := \mathsf {Coeff}\setminus \mathsf {Crit}$ be the “symbolic” complement of $\mathsf {Crit}$; that is, $Y^j \in \overline{\mathsf {Crit}}$ if j is symbolically not the same as one of the exponents in $\mathsf {Crit}$, so $|\mathsf {Coeff}| = 29$ and $|\overline{\mathsf {Crit}}| = 29 - 6 = 23$. We the 6 critical coefficients in Eq. (10), not highlighted coefficients correspond to coefficients in $\overline{\mathsf {Crit}}$.

We say that $\boldsymbol{\varDelta }$ is soundness-friendly if $\mathsf {Crit}$ consists of mutually different powers of Y ($|\mathsf {Crit}| = 6$) and $\mathsf {Crit}\cap \overline{\mathsf {Crit}} = \emptyset$. We will give a concrete soundness-friendly suggestion for $\boldsymbol{\varDelta }$ in Eq. (11). We depict the critical coefficients $\mathcal {V}_{Y^i} (\boldsymbol{X}^*)$, $Y^i \in \mathsf {Crit}$, in Table 2. (The last rows in Table 2 are only relevant for the ASE proof in Sect. 4.) In the knowledge-soundness proof of Theorem 1, we show that if $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for $Y^i \in \mathsf {Crit}$, then $\chi (X) = 0$ and thus the prover is honest.

3.1 Security Theorem

Theorem 1

Let be a QAP instance. Let $\mathsf {S_{qap}}$ be the SNARK in Fig. 3. Let $\mathcal {T}^x_{\iota }$ be the minimal set of exponents i such that the CRS of $\mathsf {S_{qap}}$ in Fig. 3 can be computed by an algebraic adversary given $[x^i : i \in \mathcal {T}^x_{1}]_{1}, [x^i : i \in \mathcal {T}^x_{2}]_{2}$ and y. We define $\mathcal {T}^y_{\iota }$ dually.

(1) Assume $\boldsymbol{\varDelta }$ is soundness-friendly. Then, $\mathsf {S_{qap}}$ is knowledge-sound in the AGM under the $(\mathcal {T}^{x}_{1}, \mathcal {T}^{x}_{2})$-PDL and the $(\mathcal {T}^{y}_{1}, \mathcal {T}^{y}_{2})$-PDL assumptions.

(2) $\mathsf {S_{qap}}$ is perfectly zero-knowledge.

Here, $\mathcal {T}^x_{1} = [0, 2 n- 2]$, $\mathcal {T}^x_{2} = [0, n- 1]$, $\mathcal {T}^y_{1} = \{\beta - \alpha + \delta , \beta - \alpha + \gamma , 2 \beta - \alpha , \alpha , \beta , 2 \beta - \alpha , \gamma , \delta , \beta - \eta + \delta , \beta - \eta + \gamma , 2 \beta - \eta \}$, and $\mathcal {T}^y_{2} = \{\alpha , \beta , \delta , \eta \}$. This can be contrasted to [19] that provided an AGM knowledge-soundness proof under the stronger $([1, 2 n- 1], [1, 2 n- 1])$-PDL assumption.

We emphasize that the following knowledge-soundness proof depends minimally on the concrete SNARK: the only intrinsically $\mathsf {S_{qap}}$-dependent part is the analysis of the abort probability. The rest of the proof can essentially be copied to the knowledge-soundness (and ASE) proofs of all following SNARKs.

Table 2. $\mathsf {S_{qap}}$: the critical coefficients in the knowledge-soundness proof (up, left), addends to the same coefficients in the ASE proof (up, right), and coefficients that only occur in the ASE proof (bottom). Here, $\tilde{\mathbbm {z}}_{j} = \mathbbm {z}_{j} - b_{\eta } a^*_{j}$ for $j \le m_{0}$, $\tilde{\mathbbm {z}}_{j} = c^*_{j} - r_{b}a^*_{j}$ for $j > m_{0}$, $u (X) = \sum _{j = 1}^m\tilde{\mathbbm {z}}_{j} u_{j} (X)$, $v (X) = \sum _{j = 1}^{m} \tilde{\mathbbm {z}}_{j} v_{j} (X)$, $w (X) = \sum _{j = 1}^m\tilde{\mathbbm {z}}_{j} w_{j} (X)$, and $h (X) = h_{c} (X) - r_{b}h_{a} (X)$.

Proof

Let be an algebraic knowledge-soundness adversary. Assume that outputs $(\mathbbm {x}, \pi )$, such that accepts with a non-negligible probability . Let $\mathsf {crs}= (\mathsf {crs}_{1}, \mathsf {crs}_{2})$, with $\mathsf {crs}_{\iota } = [\{f (\boldsymbol{x})\}_{f \in \varGamma _{\iota }}]_{\iota }$, as before. Since is algebraic and the distribution of $\mathsf {crs}$ is PPT-sampleable, there exists an extractor , such that with probability , where , succeeds.

Fig. 4.

The adversaries , $z \in \{x, y\}$, and how they emulate $\mathcal {O}_{\iota }$ to in the proof of Theorem 1. The parts where the two adversaries differ are boxed. entries are only in and its emulation, and entries are only in and its emulation. E.g., samples a random x and samples a random y.

We construct two different PDL adversaries, and , see Fig. 4. Intuitively, the main difference between them is that they use the knowledge-soundness adversary , whose input depends on either x or y, to break PDL with respect to x or y, correspondingly.

Let $z \in \{x, y\}$ and $Z \in \{X, Y\}$, correspondingly. obtains an input $\mathbbm {x}_{z} = ([z^{k}: k \in \mathcal {T}^z_{1}]_{1}, [z^{k}: k \in \mathcal {T}^z_{2}]_{2})$. Intuitively, reduces the actions of to a univariate case by sampling the second trapdoor (y or x) uniformly at random. The verification equation states that $\mathcal {V}(\boldsymbol{x}^*, y) = 0$, where $\mathcal {V}(\boldsymbol{X}^*, Y)$ is a known Laurent polynomial due to the use of the AGM. The adversary aborts if $\mathcal {V}(\boldsymbol{X}^*, Y) = 0$ as a Laurent polynomial. The most complicated part of the proof is to show that if is successful, then $\mathcal {V}(\boldsymbol{X}^*, Y) \ne 0$ and thus the abort on this step is never executed. (For this, we need to analyze the six critical coefficients of $\mathcal {V}$, and we will do it at the end of the proof.)

Otherwise, we choose a polynomial f(Z), such that $f (Z) \ne 0$ but $f (z) = 0$. Note that samples the oracle answers $q_{\iota k}$ uniformly at random, while sets implicitly $q_{\iota k} \leftarrow s_{\iota k} x + t_{\iota k}$. (Differently from [19], we only use this technique in the case of .) Thus, $\boldsymbol{Q}_{\iota } = \boldsymbol{s}_{\iota } X + \boldsymbol{t}_{\iota }$. If $\mathcal {V}(\boldsymbol{X}^*, Y) \ne 0$ but $\mathcal {V}(\boldsymbol{x}^*, Y) = 0$, then $\mathcal {V}' (X, Y) := \mathcal {V}(X, \boldsymbol{s}_{1} X + \boldsymbol{t}_{1}, \boldsymbol{s}_{2} X + \boldsymbol{t}_{2}, Y)$ satisfies $\mathcal {V}' (x, Y) = 0$. We set f(X) to be equal to some non-zero coefficient $\mathcal {V}'_{i} (X) \ne 0$ of $\mathcal {V}' (X, Y) = \sum \mathcal {V}'_{i} (X) Y^i$.

finds all the roots of f(Z) and then checks which of the roots is equal to z by using information given in her input. For this, we define event if $\mathcal {V}(\boldsymbol{x}^*, Y) = 0$ as a Laurent polynomial, where x is either the value imminent in the input of or sampled by . aborts if and otherwise finds y. aborts if and otherwise finds x. Clearly,

Analysis of the abort probability in step (*). Both and abort if $\mathcal {V}(\boldsymbol{X}^*, Y) = 0$ as a Laurent polynomial. Assume now that $\mathcal {V}(\boldsymbol{X}) = 0$, thus $\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for $Y^i \in \mathsf {Crit}$. We must show that (a) the critical coefficients are as in Table 2 and (b) from “$\mathcal {V}_{Y^i} (\boldsymbol{X}^*) = 0$ for $Y^i \in \mathsf {Crit}$” it follows that $\chi (X) = 0$.

One can derive a by inspection (we verified it by using computer algebra), assuming that $\mathsf {Crit}$ satisfies the theorem conditions. For example, the coefficient of $Y^{\gamma + \delta }$ in $\mathcal {V}(\boldsymbol{X})$ is $(a_{\gamma } + 1) (b_{\delta } + 1) - 1$ since the coefficient of $Y^{\gamma + \delta }$ in $(A^\dagger (\boldsymbol{X}) + Y^{\gamma }) (B^\dagger (\boldsymbol{X}) + Y^{\delta })$ is $(a_{\gamma } + 1) (b_{\delta } + 1)$. Other coefficients can be checked similarly.

Now, b follows. Really, since $\mathcal {V}_{Y^{\gamma + \delta }} (\boldsymbol{X}^*) = b_{\delta } + a_{\gamma } (b_{\delta } + 1) = 0$, we get $a_{\gamma } = - b_{\delta } / (b_{\delta } + 1)$. Thus, . Since $\mathcal {V}_{Y^{\gamma + \eta }} (\boldsymbol{X}^*) = (a_{\gamma } + 1) b_{\eta } = 0$ and $a_{\gamma } \ne -1$, we get $b_{\eta } = 0$. Thus, for $j \le m_{0}$. Since $\mathcal {V}_{Y^{2 \delta }} (\boldsymbol{X}^*) = (b_{\delta } + 1) a_{\delta } = 0$ and $b_{\delta } \ne - 1$, we get $a_{\delta } = 0$. From the remaining coefficients, we get $(b_{\delta } + 1) u_{a} (X) = u (X)$, $(a_{\gamma } + 1) v_{b} (X) = v (X)$, and $u (X) v (X) - w (X) = Z(X) h(X)$. Thus, .

To see that accepts, note that $(\mathsf {a}+ y^\gamma ) (\mathsf {b}+ y^\delta ) - \mathsf {c}_{s}y^\alpha - \mathsf {c}_{p} y^\eta - y^{\gamma + \delta } = de+ dy^\delta + ey^\gamma - (de+ dy^\delta + ey^\gamma - \mathsf {c}_{p} y^\eta ) - \mathsf {c}_{p} y^\eta = 0$. ’s output comes from the correct distribution since $\mathsf {a}$ and $\mathsf {b}$ are individually uniform in , and $\mathsf {c}$ is chosen so that accepts.    $\square$

Efficiency. Compared to [23], see Table 1, $\mathsf {S_{qap}}$ has fewer trapdoors but otherwise the same complexity. For example, has $(m- m_{0}) + 1 + n+ (n- 1) + 1 = m+ 2 n- m_{0}+ 1$ elements from $\mathbb {G}_{1}$ and $n+ 2$ elements from $\mathbb {G}_{2}$. Moreover, has $m_{0}+ 1$ elements from $\mathbb {G}_{1}$, 3 elements from $\mathbb {G}_{2}$, and one element from $\mathbb {G}_{T}$. Since and have one common element in $\mathbb {G}_{1}$ then $|\mathsf {crs}| = (m+ 2 n+ 2) \mathfrak {g}_{1} + (n+ 4) \mathfrak {g}_{2} + \mathfrak {g}_{T}$. (Recall that $\mathfrak {g}_{\iota }$ denotes the representation length of an element of $\mathbb {G}_{\iota }$.) Clearly, $[\mathsf {a}]_{1}$ can be computed from $[y^\alpha ]_{1}$ and $[x^i y^\beta ]_{1}$ by using $n+ 1$ scalar multiplications. It takes $\approx m+ 2 n$ additional scalar multiplications to compute $[\mathsf {c}]_{1}$.

A Soundness-Friendly Choice of $\boldsymbol{\varDelta }$. Recall that we need to find values for $\boldsymbol{\varDelta } = (\alpha , \ldots )$, such that $\mathsf {Crit}\cap \overline{\mathsf {Crit}} = \emptyset$ and $|\mathsf {Crit}| = 6$. We require that both sets $\varGamma _{1}$ and $\varGamma _{2}$ contain a non-zero monomial corresponding to $Y^0 = 1$ (then we can publish $[1]_{1}$ and $[1]_{2}$) and that the values i, for which $i \in \mathcal {T}^y_{1} \cup \mathcal {T}^y_{2}$, have as small absolute values as possible. The latter makes the PDL assumption somewhat more reasonable and additionally enables us to construct a CRS verification algorithm and thus prove Sub-ZK [1, 3] in Sect. 5. We are also interested in minimizing the CRS length.

Since there are many coefficients to take into account, we have a moderately hard optimization problem. We used a computer search to find all possible values for $\alpha , \beta , \ldots$ under the restriction that each has an absolute value at most 7. See Table 3 for the full list of found tuples $\boldsymbol{\varDelta }$. Note that for each $\boldsymbol{\varDelta } = (\alpha , \beta , \ldots )$, this table contains also $-\boldsymbol{\varDelta } = (-\alpha , -\beta , \ldots )$.

We recommend to use the following setting:

$$\begin{aligned} \alpha = 0, \beta = -2, \gamma = -3, \delta = 7, \eta = 2. \end{aligned}$$

(11)

As we will see in Sects. 5 and 4, this is one of the settings that allow obtaining both ASE and Sub-ZK security. Assuming the setting of Eq. (11), and

(12)

In addition, our computer search tries to minimize the CRS length, but none of the choices of $\boldsymbol{\varDelta }$ in Table 3 results in a shorter CRS.

Table 3. Soundness-friendly values of $\boldsymbol{\varDelta }$ with each parameter having absolute value $\le 7$. “$\checkmark$” in the last column means that this choice of $\boldsymbol{\varDelta }$ results in a Sub-ZK SNARK

On 2-Phase Updatability. Each of $Y^\alpha , Y^\beta , \ldots$ can be changed to an independent indeterminant, $Y_{\alpha }, Y_{\beta }, \ldots$, without invalidating the knowledge-soundness (or ASE) proof. This offers us the flexibility of choosing the number of trapdoors. In particular, Kohlweiss et al. proved recently [27] that Groth’s SNARK [23] is two-phase updatable. Similarly, $\mathsf {S_{qap}}$ is two-phase updatable, when one defines three trapdoors, x, y, z, and uses well-chosen powers of z instead of $y^{\alpha }$ and $y^{\eta }$ throughout the construction of $\mathsf {S_{qap}}$. Then, one can update x and y in the first and z in the second phase. We will omit further discussion.

4 Any-Simulation Extractability of $\mathsf {S_{qap}}$

Next, we prove that $\mathsf {S_{qap}}$ is ASE. The ASE proof is similar to the knowledge-soundness proof Theorem 1. The main difference is the handling of the case when $\mathcal {V}(\boldsymbol{X}) = 0$ as a Laurent polynomial. We use some monomials of $\mathcal {V}(\boldsymbol{X})$ to simplify the formulas and then arrive at a crossroad: in one case, the adversary did not use simulation query results, and thus we are back to the knowledge-soundness proof. In the second case, the adversary used some of the query results; then, we use specific coefficients of $\mathcal {V}(\boldsymbol{X})$ to argue that she used the result of precisely one query. After that, we show that the adversary used the same input to the simulator in this query as in the forgery attempt. (This result relies on an additional assumption that each $u_{j} (X)$, for $j \le m_{0}$, is linearly independent of all other $u_{i} (X)$, $i \le m$. This assumption can be easily satisfied by adding to the QAP $m_{0}$ dummy constraints $u_{j} \cdot 1 = u_{j}$, similarly to [21].) Hence, this is not an ASE but a SASE attack, and thus not valid in our context. Thus, $\mathsf {S_{qap}}$ is ASE.

In the ASE proof, the algebraic adversary also sees the outputs of the simulator. Thus, has more inputs than in the knowledge-soundness proof. Let $\boldsymbol{\sigma }_{k} = (\sigma _{k j})_{j = 1}^{m_{0}}$ be the maliciously chosen simulator input that the adversary used, instead of $(\mathbbm {z}_{j})_{j = 1}^{m_{0}}$, during the kth query. Let $\boldsymbol{X} = (X, \boldsymbol{Q}_{1}, \boldsymbol{Q}_{2}, \boldsymbol{D}, \boldsymbol{E}, Y)$ and $\boldsymbol{X}^* = (X, \boldsymbol{Q}_{1}, \boldsymbol{Q}_{2})$, where $D_{k}$ (resp., $E_{k}$) is the indeterminate corresponding to the trapdoor $d= d_{k}$ (resp., $e= e_{k}$) generated by the simulator during the kth query. Observing Fig. 3, answers with $([d_{k}, y^{-\alpha } ((d_{k} e_{k} + y^\delta d_{k} + y^\gamma e_{k}) - \sum _{j = 1}^{m_{0}} \sigma _{k j} P_{j} (x, y))]_{1}, [e_{k}]_{2})$. Thus, in the ASE proof, $A^\dagger (\boldsymbol{X})$, $B^\dagger (\boldsymbol{X})$, and $C_{s}^\dagger (\boldsymbol{X})$ have the following additional addends:

$$\begin{aligned} A^\dagger (\boldsymbol{X}) =&\textstyle \ldots + \textstyle \sum _{k} s_{a 1 k} D_{k} + \sum _{k} s_{a 2 k} Y^{-\alpha } ((D_{k} E_{k} + Y^{\delta } D_{k} + Y^{\gamma } E_{k}) - \sum _{j = 1}^{m_{0}} \sigma _{k j} P_{j} (X, Y)) ,\\ C_{s}^\dagger (\boldsymbol{X}) =&\textstyle \ldots + \textstyle \sum _{k} s_{c 1 k} D_{k} + \sum _{k} s_{c 2 k} Y^{-\alpha } ((D_{k} E_{k} + Y^{\delta } D_{k} + Y^{\gamma } E_{k}) - \sum _{j = 1}^{m_{0}} \sigma _{k j} P_{j} (X, Y)),\\ B^\dagger (\boldsymbol{X}) =&\ldots + \textstyle \sum _{k} s_{b k} E_{k}. \end{aligned}$$

Here, the coefficients like $s_{a 1 k}$ are chosen by the adversary. Let $\mathcal {V}(\boldsymbol{X}) = \sum _{i_{1}, i_{2}, i_{3}, i_{4}, k_{1}, k_{2}, k_{3}} \mathcal {V}_{Y^{i_{1}} D_{k_{1}}^{i_{2}} E_{k_{2}}^{i_{3}} E_{k_{3}}^{i_{4}}} (\boldsymbol{X^*}) Y^{i_{1}} D_{k_{1}}^{i_{2}} E_{k_{2}}^{i_{3}} E_{k_{3}}^{i_{4}}$. The addition of new addends to polynomials like $\smash {A^\dagger (\boldsymbol{X})}$ means that the existing critical coefficients of $\mathcal {V}_{Y^{i_{1}} \cdots }$ of $\mathcal {V}(\boldsymbol{X})$ change by extra addends; we have denoted these extras by $\hat{\mathcal {V}}_{Y^i \cdots }$ in Table 2. Moreover, there are a number of new critical coefficients, depicted in the bottom of Table 2. For example, $\mathcal {V}_{Y^{\beta + \delta }} (\boldsymbol{X}^*) = (b_{\delta } + 1) u_{a} (X) + a_{\delta } v_{b} (X) - u (X) + \sum _{k} (s_{c 2 k} - r_{b}s_{a 2 k}) \sum _{j} \sigma _{k j} u_{j} (X)$ and, for any k, $\smash {\mathcal {V}_{Y^{\gamma } E_{k}} (\boldsymbol{X}^*) = r_{b}s_{a 2 k} + (a_{\gamma } + 1) s_{b k} - s_{c 2 k}}$. Since here, the index $\smash {Y^{i_{1}} D_{k_{1}}^{i_{2}} E_{k_{2}}^{i_{3}} E_{k_{3}}^{i_{4}}}$ of $\mathcal {V}_{Y^{i_{1}} \cdots }$ depends on a non-constant number of indeterminates, here both $\smash {\mathsf {Coeff}_{se} := \{Y^{i_{1}} D_{k_{1}}^{i_{2}} E_{k_{2}}^{i_{3}} E_{k_{3}}^{i_{4}}: \mathcal {V}_{Y^{i_{1}} D_{k_{1}}^{i_{2}} E_{k_{2}}^{i_{3}} E_{k_{3}}^{i_{4}}} (\boldsymbol{X}^*) \ne 0\}}$ and

$$\begin{aligned} \mathsf {Crit}_{se} =&\{Y^{2 \beta }, Y^{\beta + \gamma }, Y^{\beta + \delta }, Y^{\gamma + \delta }, Y^{\gamma + \eta }, Y^{2 \delta }\} \cup \{Y^{-\alpha + 2 \delta } D_{k}\}_{k} \cup \{Y^\gamma E_{k}\}_{k} \cup \\&\{D_{k_{1}} E_{k_{2}}\}_{k_{1}, k_{2}} \cup \{Y^{\delta } D_{k}\}_{k} \cup \{Y^\beta E_{k}\}_{k} \end{aligned}$$

also contain a non-constant number of coefficients. For example, $\mathsf {Crit}_{se}$ contains $D_{k_{1}} E_{k_{2}}$ for any $k_{1}, k_{2} \le q_{s}$, where $q_{s}$ is the number of simulation queries. However, there are only 12 “families” of critical coefficients, and the members of the same family (say $D_{1} E_{2}$ and $D_{7} E_{2}$) can be analyzed similarly.

For $\mathsf {Crit}_{se}$ to consist of different monomials and for $\mathsf {Crit}_{se} \cap \overline{\mathsf {Crit}}_{se}$, the new critical monomials $Y^{i_{1}} D_{k}^{i_{2}} E_{k}^{i_{3}}$ (see Table 2, the last 6 monomials) must be different from all other monomials. We say that $\boldsymbol{\varDelta }$ is ASE-friendly if these conditions are satisfied. While the number of additional monomials in $\mathsf {Crit}$ and $\mathsf {Coeff}$ is huge, ascertaining that the new critical monomials are unique is relatively easy, even if tedious, since one needs to guarantee that for each fixed $(i_{2}, i_{3})$, if $\smash {Y^{i_{1}} D_{k}^{i_{2}} E_{k}^{i_{3}} \in \mathsf {Crit}_{se}}$ and $\smash {Y^{i'_{1}} D_{k}^{i_{2}} E_{k}^{i_{3}} \in \mathsf {Coeff}_{se}}$ then $i_{1} \ne i'_{1}$. By inspection, one can establish that it means the following.

• 1. (a) When $i_{2} = 1$ and $i_{3} = 0$, we need $-\alpha + 2 \delta \ne \delta$ (i.e., $\delta \ne \alpha$, which follows from the fact that $Y^{\beta + \delta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$) and $-\alpha + 2 \delta , \delta \not \in \{\alpha , \beta , -\alpha + \beta + \delta , \eta , -\alpha + \delta + \eta \}$. This guarantees, say, that $Y^{-\alpha + 2 \delta } D_{k}$ (which is a critical monomial) is not equal to $Y^{-\alpha + \delta + \eta } D_{k}$.

• 2. (b) When $i_{2} = 0$ and $i_{3} = 1$, we need $\gamma \ne \beta$ and $\gamma , \beta \not \in \{\alpha , -\alpha +2 \beta , -\alpha +\beta +\gamma , \delta , -\alpha +\beta +\delta , -\alpha +\gamma +\delta , 2 \beta -\eta , \beta +\gamma -\eta , \beta +\delta -\eta , -\alpha +\gamma +\eta \}$.

• 3. (c) When $i_{2} = 1$ and $i_{3} = 1$, we need $0 \not \in \{-\alpha + \beta , -\alpha + \delta , -\alpha + \eta \}$.

By simple but tedious case analysis, one can prove the following lemma.

Lemma 1

If $\boldsymbol{\varDelta }$ is soundness-friendly, then it is also ASE-friendly.

Proof

(a) Here, $-\alpha + 2 \delta \ne \delta$ (i.e., $\delta \ne \alpha$) follows from the fact that $Y^{\beta + \delta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$. Moreover, $-\alpha + 2 \delta \ne \alpha$ and $\delta \ne \alpha$ follow since $\alpha \ne \delta$, $-\alpha + 2 \delta \ne \beta$ follows since $Y^{2 \delta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$, $\delta \ne \beta$ follows since $Y^{2 \beta }, Y^{2 \delta } \in \mathsf {Crit}$, $-\alpha + 2 \delta \ne -\alpha + \beta + \delta$ follows since $\beta \ne \delta$, $\delta \ne -\alpha + \beta + \delta$ follows since $\alpha \ne \delta$, $-\alpha + 2 \delta \ne \eta$ follows from $Y^{2 \delta } \in \mathsf {Crit}$ and $Y^{\alpha + \eta } \in \overline{\mathsf {Crit}}$, $\delta \ne \eta$ follows from $Y^{\gamma + \delta }, Y^{\gamma + \eta } \in \mathsf {Crit}$, $-\alpha + 2 \delta \ne -\alpha + \delta + \eta$ follows from $\delta \ne \eta$, $\delta \ne -\alpha + \delta + \eta$ follows form $Y^{\gamma + \eta } \in \mathsf {Crit}$ and $Y^{\alpha + \gamma } \in \overline{\mathsf {Crit}}$.

(b) Next, $\gamma \ne \beta$ follows from $Y^{2 \beta }, Y^{\beta + \gamma } \in \mathsf {Crit}$, $\gamma \ne \alpha$ follows from $Y^{\beta + \gamma } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$, $\beta \ne \alpha$ follows from $Y^{2 \beta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$, $\gamma \ne -\alpha + 2 \beta$ follows from $Y^{2 \beta } \in \mathsf {Crit}$ and $Y^{\alpha + \gamma } \in \overline{\mathsf {Crit}}$, $\beta \ne -\alpha + 2 \beta$ follows from $\alpha \ne \beta$, $\gamma \ne -\alpha + \beta + \gamma$ follows from $\alpha \ne \beta$, $\beta \ne -\alpha + \beta + \gamma$ follows from $\alpha \ne \gamma$, $\gamma \ne \delta$ follows from $Y^{\beta + \gamma }, Y^{\beta + \delta } \in \mathsf {Crit}$, $\beta \ne \delta$ is already proven, $\gamma \ne -\alpha + \beta + \delta$ follows from $Y^{\beta + \gamma } \in \mathsf {Crit}$ and $Y^{-\alpha + 2 \beta + \delta } \in \overline{\mathsf {Crit}}$, $\beta \ne -\alpha + \beta + \delta$ follows from $\alpha \ne \delta$, $\gamma \ne -\alpha + \gamma + \delta$ follows from $\alpha \ne \delta$, $\beta \ne -\alpha + \gamma + \delta$ follows from $Y^{\gamma + \delta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$, $\gamma \ne 2 \beta - \eta$ follows from $Y^{2 \beta }, Y^{\gamma + \eta } \in \mathsf {Crit}$, $\beta \ne 2 \beta - \eta$ (i.e., $\beta \ne \eta$) follows from $Y^{\beta + \gamma }, Y^{\gamma + \eta } \in \mathsf {Crit}$, $\gamma \ne \beta + \gamma - \eta$ follows from $\beta \ne \eta$, $\beta \ne \beta + \gamma - \eta$ (i.e., $\gamma \ne \eta$) follows from $Y^{\beta + \delta } \in \mathsf {Crit}$ and $Y^{\beta + \gamma + \delta - \eta } \in \overline{\mathsf {Crit}}$, $\gamma \ne \beta + \delta - \eta$ follows from $Y^{\beta + \delta }, Y^{\gamma + \eta } \in \mathsf {Crit}$, $\beta \ne \beta + \delta - \eta$ follows from $\delta \ne \eta$, $\gamma \ne -\alpha + \gamma + \eta$ follows from $Y^{\gamma + \eta } \in \mathsf {Crit}$ and $Y^{\alpha + \gamma } \in \overline{\mathsf {Crit}}$, $\beta \ne -\alpha + \gamma + \eta$ follows from $Y^{\gamma + \eta } \in \mathsf {Crit}$ and $Y^{\alpha + \beta } \in \overline{\mathsf {Crit}}$.

(c) Finally, $\alpha \ne \beta$ and $\alpha \ne \delta$ is already known, and $\alpha \ne \eta$ follows from $Y^{\gamma + \eta } \in \mathsf {Crit}$ and $Y^{\alpha + \gamma } \in \overline{\mathsf {Crit}}$.   $\square$

Theorem 2

Let $\mathcal {T}^x_{\iota }$ and $\mathcal {T}^y_{\iota }$ be as in Theorem 1. Let be a QAP instance. Let $\mathsf {S_{qap}}$ be the SNARK in Fig. 3. Assume $\boldsymbol{\varDelta }$ is soundness-friendly. Assume $u_{j} (X)$, $j \le m_{0}$, are linearly independent from each other and from other polynomials $u_{i}$ for $i > m_{0}$. $\mathsf {S_{qap}}$ is non-black-box ASE in the AGM under the $(\mathcal {T}^x_{1}, \mathcal {T}^x_{2})$-PDL and $(\mathcal {T}^y_{1}, \mathcal {T}^y_{2})$-PDL assumptions.

Proof

The ASE proof is similar to the knowledge-soundness proof. There are two main differences. First, also has to emulate to . Second, the analysis of the abort probability is different due to the larger number of critical monomials.

Hence, we refer to the proof of Theorem 1, except that the full description of in Fig. 5 contains also the emulation of simulation queries. (Obviously, there is more going on behind the scene: for example, $\mathcal {V}$ is defined differently, and $\boldsymbol{X}^*$ includes $\boldsymbol{D}, \boldsymbol{E}$, but we already explained that part.)

Fig. 5.

in the proof of Theorem 2, and the emulation of . and are defined as in Fig. 4.

The only thing left to do now is the different (more complicated) analysis of the abort probability.

Analysis of the abort probability in step (*). Assume that $\mathcal {V}(\boldsymbol{X}) = 0$, thus also $\mathcal {V}_{Y^{i_{1}} \cdots } (\boldsymbol{X}^*) = 0$ for all critical monomials (see Theorem 2). From the coefficient of $Y^{\gamma + \delta }$ of $\mathcal {V}$, we get $b_{\delta } = - a_{\gamma } / (a_{\gamma } + 1)$ and thus $a_{\gamma }, b_{\delta } \ne -1$. From the coefficients of $Y^{\gamma + \eta }$ and $Y^{2 \delta }$, and since $a_{\gamma }, b_{\delta } \ne -1$, we get $b_{\eta } = 0$ and $a_{\delta } = 0$. Up to now, the proof looks similar to that of Theorem 1. The rest of the coefficients have to be handled differently.

From the coefficients of $Y^{\beta + \delta }$ and $Y^{\beta + \gamma }$, we get

$$\begin{aligned} u_{a} (X) =&\textstyle (a_{\gamma } + 1) (u (X) + \sum _{j} \left( \sum _{k = 1}^{m_{0}} \sigma _{k j} (r_{b}s_{a 2 k}- s_{c 2 k})\right) u_{j} (X)),\\ v_{b} (X) =&\textstyle (v (X) + \sum _{j} \left( \sum _{k = 1}^{m_{0}} \sigma _{k j} (r_{b}s_{a 2 k} - s_{c 2 k})\right) v_{j} (X)) / (a_{\gamma } + 1) . \end{aligned}$$

From the coefficient of $Y^{-\alpha + 2 \delta } D_{k}$, we get $s_{a 2 k} = 0$. From the coefficients of $Y^{\gamma } E_{k}$ and $D_{k} E_{k}$, we get $s_{c 2 k} = (a_{\gamma } + 1) s_{b k} = s_{a 1 k} s_{b k}$. Thus, for all k, either (i) $s_{b k} = s_{c 2 k} = 0$ or (ii) $s_{a 1 k} = a_{\gamma } + 1 \ne 0$ and $s_{c 2 k} = (a_{\gamma } + 1) s_{b k} \ne 0$.

If the case (i) holds for all k, then the first three polynomials $\hat{V}_{Y^i}$ in Table 2 are 0 and we are back to the knowledge-soundness case. One can then follow the remaining proof of Theorem 1, and obtain knowledge-soundness and ASE. Note that then, from the coefficient of $Y^\delta D_{k}$, it follows that also $s_{a 1 k} = 0$ for all k. Thus, the adversary did not benefit from the simulation queries.

Consider the case when at least for one k, (ii) holds. From the coefficient of $Y^\delta D_{k}$ of this k, we get $0 = r_{b}s_{a 2 k} + (b_{\delta } + 1) s_{a 1 k} - s_{c 2 k} = 1 - (a_{\gamma } + 1) s_{b k}$ and thus $s_{b k} = 1 / (a_{\gamma } + 1)$. From the coefficient of $D_{k_{1}} E_{k_{2}}$ for any $k_{1} \ne k_{2}$, we get $s_{a 1 k_{1}} s_{b k_{2}} = 0$. Thus, if some $s_{a 1 k_{2}} \ne 0$, then (since we are in the case (ii)) also $s_{b k_{2}} \ne 0$, and thus $s_{a 1 k_{1}} = s_{b k_{1}} = s_{c 2 k_{1}} = 0$ for all $k_{1} \ne k_{2}$. Hence, $r_{b}s_{a 2 k_{1}} - s_{c 2 k_{1}} = 0$, and thus making the $k_{1}$th simulation query, $k_{1} \ne k_{2}$, does not help the adversary. Thus, we can assume that makes only one query, say the $k_{2}$th one, with the simulator input $\boldsymbol{\sigma } = (\sigma _{j})$.

From the coefficient of $Y^{\beta } E_{k_{2}}$, we get $s_{b k_{2}} u_{a} (X) = 0$. Since $s_{b k_{2}} \ne 0$ and $a_{\gamma } \ne -1$, $\sum _{j \le m_{0}} \left( \sigma _{j} (r_{b}s_{a 2 k_{2}} - s_{c 2 k_{2}}) + \mathbbm {z}_{j}\right) u_{j} (X) + \sum _{j > m_{0}} \tilde{\mathbbm {z}}_{j} u_{j} (X) = 0$. Since $s_{a 2 k_{2}} = 0$ and $s_{c 2 k_{2}} = 1$, $\sum _{j \le m_{0}} \left( \mathbbm {z}_{j} - \sigma _{j}\right) u_{j} (X) + \sum _{j > m_{0}} \tilde{\mathbbm {z}}_{j} u_{j} (X) = 0$. Since $u_{j} (X)$ are linearly independent for $j \le m_{0}$, it means $\mathbbm {z}_{j} = \sigma _{j}$ for all $j \le m_{0}$. Thus, made the only simulation query on the same input that she used to cheat on, and thus this corresponds to a SASE but not an ASE attack. Hence, did not succeed in an ASE attack and thus $\chi (X) = 0$.    $\square$

On Lower-Bound of [25]. Groth and Maller proved that in any SASE SNARK, the verifier has to perform two verification equations. Our result does not contradict it since we achieve ASE, a weaker property. (Similarly, the ASE SNARK of [6] has only one verification equation.)

5 Subversion-Zero Knowledge

In a subversion zero-knowledge (Sub-ZK) SNARK [1, 3, 7, 17], the goal is to obtain zero-knowledge even if the CRS creator cannot be trusted. As noted in [2], one has to use non-falsifiable assumptions to achieve Sub-ZK. Next, we show that $\mathsf {S_{qap}}$ is Sub-ZK (under the BDH-KE assumption), assuming $\boldsymbol{\varDelta }$ satisfies some additional requirements. The same argument applies in the case of all other new SNARKs. In particular, five different choices of $\boldsymbol{\varDelta }$ in Table 3 result in a Sub-ZK SNARK; this includes the setting of Eq. (11).

According to the blueprint of [1, 3, 17], one can follow the next steps to make a SNARK subversion-resistant:

• 1. Construct a public CRS verification algorithm $\mathsf {CV}$ that checks that the CRS is correct (that is, it corresponds to some trapdoor $\mathsf {td}$).

• 2. To facilitate public verification, this can mean adding new elements to the CRS. Let us denote the set of new elements by $\mathsf {crs}_{\mathsf {CV}}$. If $\mathsf {crs}_{\mathsf {CV}}$ is non-empty, then one must reprove knowledge-soundness and/or simulation-extractability, taking $\mathsf {crs}_{\mathsf {CV}}$ into account.

• 3. Under a reasonable knowledge assumption, extract $\mathsf {td}$ from the CRS.

• 4. Show how to simulate the argument by using the extracted trapdoor.

This blueprint is formalized in [3], and we refer the reader to it for a further discussion, including proof that trapdoor-extractability and ZK suffice to get Sub-ZK. Moreover, for trapdoor-extractability, it suffices to have CRS-verifiability and a strong enough extractability assumption.

Let us show that under the setting in Eq. (11) with CRS as in Eq. (12), the correctness (that is, that it corresponds to some choice of trapdoors) of the CRS of $\mathsf {S_{qap}}$ can be verified by using a public $\mathsf {CV}$ algorithm. Modelling after [1, 3], $\mathsf {CV}$ needs to check that (1) all trapdoors belong to correct domain (for example, it checks by checking that $[y]_{1} \ne [0]_{1}$), and that (2) all CRS elements $[f (\boldsymbol{x})]_{\iota }$, where f is a public rational function, are correctly computed from trapdoors $\boldsymbol{x}$. The last verification can be done step by step, starting from simpler (for example, lower-degree) functions and then using the already verified values as helpers to verify more complex functions.

We present the CRS verification algorithm $\mathsf {CV}$ for $\mathsf {S_{qap}}$ in Fig. 6. Note that here we assume $u_{j} (X) = \sum u_{j i} X^i$, $v_{j} (X) = \sum v_{j i} X^i$, and $w_{j} (X) = \sum w_{j i} X^i$. It is easy (though tedious) to check that $\mathsf {CV}$ suffices to check that the CRS of $\mathsf {S_{qap}}$ has been correctly generated but for the following two exceptions:

Fig. 6.

The CRS verification algorithm $\mathsf {CV}$ in $\mathsf {S_{qap}}$. elements are guaranteed to be in the CRS if $\alpha = 0$. equalities and the integer exponents in comments depend on the concrete of $\boldsymbol{\varDelta }$ (namely, Eq. (11))

• 1. The elements are not guaranteed to be in the CRS unless $\boldsymbol{\varDelta }$ is well-chosen. A simple way of solving this problem is to set $\alpha \leftarrow 0$. This is not too restrictive, since 12 out of 14 $\boldsymbol{\varDelta }$-s in Table 3 have $\alpha = 0$.

• 2. One must verify that, for some $\iota$ such that $[y^\kappa ]_{\iota }$ is in the CRS, $y^\kappa$ is correctly computed, where $\kappa \in \{\beta , \gamma , \delta , \eta \}$. (Recall that $\alpha = 0$.) This involves adding a small number of pairing equations of type $[y^i]_{1} \bullet [y^j]_{2} = [y^k]_{2} \bullet [y^\ell ]_{2}$, such that each equation introduces exactly one new degree (either i, j, k or $\ell$) and reuses three degrees that are already “verified”. For example, in the first equation $i, j, k \in \{0, 1\}$. In this case, one can use pairings to establish the correctness of $y^\ell$ for $\ell \in \{-1, 0, 1, 2\}$. This means we need to put additional restrictions on $\boldsymbol{\varDelta }$.

Lemma 2

From the 14 settings of $\boldsymbol{\varDelta }$ in Table 2, the five ones marked with $\checkmark$ are CRS-verifiable.

Proof

Intuitively, we just need to describe how we (manually) found which of the choices of $\boldsymbol{\varDelta }$ from Table 3 satisfy both above restrictions. As already mentioned, the first restriction is straightforward to satisfy. Now, assuming that $\alpha = 0$, consider two cases of $\ell$ from the first pairing equation in the second restriction:

• 1. $\ell = -1$. In the second pairing equation, then (say) $i, j, k \in \{-1, 0, 1\}$. In this case, one can establish the correctness of $y^\ell$ for $\ell \in [-3, 3]$.

  To solve this, we look at the possible $\boldsymbol{\varDelta }$-s in Table 3, such that $\alpha = 0$ and one of $\beta , \gamma , \delta , \eta$ is equal to either $-1$ or 2. This only weeds out one additional possibility (namely, $\boldsymbol{\varDelta } = (0, -3, 5, 7, 1)$).

  In the case one of $\beta , \gamma , \delta , \eta$ is equal to $-1$, we will look at the cases when one of the three other values $\kappa \in \{\beta , \gamma , \delta , \eta \}$ belongs to $[-3, 3]$. This leaves still several possibilities, $\boldsymbol{\varDelta } \in \{(0, -1, 6, -4, 1), (0, -1, 7, -4, 1), (0, -1, 7, -5, 1), \ldots \}$. However, in only one case, $\boldsymbol{\varDelta } = (0, 3, -5, -7, -1)$, it is possible to verify all 5 values $y^\kappa$ for $\kappa \in \{\alpha , \beta , \gamma , \delta , \eta \}$: namely, by checking that (say) $[y^\eta ]_{1} \bullet [y]_{2} = [1]_{1} \bullet [1]_{1}$, $[y^\eta ]_{1} \bullet [y^\beta ]_{2} = [y]_{1} \bullet [y]_{1}$, $[y^\gamma ]_{2} \bullet [y^\beta ]_{1} = [y^\eta ]_{1} \bullet [y^\eta ]_{1}$, and $[y^\delta ]_{2} \bullet [y]_{1} = [y^\gamma ]_{1} \bullet [y^\eta ]_{1}$.

• 2. $\ell = 2$. Then, in the second equation, one can establish the correctness of $y^\ell$ for $\ell \in [-2, 3]$. W.l.o.g., we assume that $\ell \ne -1$ (otherwise we are back to the previous case). Thus, after two verification equations, we have the following cases left: $\boldsymbol{\varDelta } \in \{(0, -2, -3, 7, 2), (-2, 6, 7, 2), (2, -6, -7, 2), (2, 3, -7, -2)\}$.

  A simple inspection establishes that in all the three cases, where both $-2$ and 2 are present, one has an efficient CRS-verification algorithm. For example, one can take $\boldsymbol{\varDelta } = (-2, -3, 7, 2)$, that is, the setting in Eq. (11). Then, one has to verify that $[1]_{1} \bullet [y^\eta ]_{2} = [y]_{1} \bullet [y]_{2}$, $[y^\beta ]_{1} \bullet [y^\eta ]_{2} = [1]_{1} \bullet [1]_{2}$, $[y^\gamma ]_{1} \bullet [y]_{2} = [y^{\beta }]_{1} \bullet [1]_{2}$, and $[y^\gamma ]_{1} \bullet [y^\beta ]_{2} = [y^\eta ]_{1} \bullet [y^\eta ]_{2}$. (Those are the equations in Fig. 6.)   $\square$

For the sake of concreteness, we recommend to choose $\boldsymbol{\varDelta }$ as in Eq. (11). However, one can use any of the five checkmarked choices in Table 3.

One can significantly speed up $\mathsf {CV}$ in Fig. 6 by using batching techniques, as explained in [1, 3]. $\mathsf {CV}$ for other new SNARKs are essentially the same, modulo some simplifications due to say $w_{i} (X) = 0$ in the case of the QSP.

Trapdoor-Extractability and Sub-ZK. Trapdoor-extractability [3] means that if $\mathsf {CV}$ accepts the CRS, then one can extract the simulation trapdoor. In all new SNARKs, the simulation trapdoor is equal to $\mathsf {td}= y$ since does not use x. Clearly, in all new SNARKs, if $\mathsf {CV}$ accepts $\mathsf {crs}$, one can use the BDH-KE assumption to extract y. Thus, BDH-KE guarantees trapdoor-extractability, and the CRS-verifiability and the trapdoor-extractability together guarantee that one can extract $\mathsf {td}$. Hence, by the general result of [3], all new SNARKs are Sub-ZK, assuming that their CRS is verifiable and that the BDH-KE holds.

Corollary 1

Under the five $\checkmark$-ed settings of $\boldsymbol{\varDelta }$ in Table 2, $\mathsf {S_{qap}}$ is statistically composable Sub-ZK under the BDH-KE assumption.