Geoffroy Couteau

Helger Lipmaa

Roberto Parisella

Arne Tobias Ødegaard

Efficient NIZKs for Algebraic Sets

Keywords: Algebraic branching programs, algebraic languages, algebraic sets, NIZK, pairingbased cryptography, SPHF, zero knowledge

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Zero-knowledge arguments [GMR89] are fundamental cryptographic primitives allowing one to convince a verifier of the truth of a statement while concealing all further information. A particularly appealing type of zero-knowledge arguments, with a wide variety of applications in cryptography, are non-interactive zero-knowledge arguments (NIZKs) [BFM88] with a single flow from the prover to the verifier.

Early feasibility results from the 90's established the existence of NIZKs for all NP languages (in the common reference string model) under standard cryptographic assumptions. However, these early constructions were inefficient. In the past decades, a major effort of the cryptographic community has been directed towards obtaining efficient and conceptually simple NIZK argument systems for many languages of interest. Among the celebrated successes of this line of work are the Fiat-Shamir (FS) transform [FS87], which provides simple and efficient NIZKs but only offers heuristic security guarantees 3 , and pairing-based NIZKs such as the Groth-Sahai proof system [GS08] (and its follow-ups).

The quest for efficient and conceptually simple NIZKs. The Groth-Sahai NIZK proof system was a major breakthrough in this line of work, providing the first provably secure (under standard pairing assumptions) and reasonably efficient NIZK for a large class of languages, capturing many concrete languages of interest. This proof system initiated a wide variety of cryptographic applications, and its efficiency was refined in a sequence of works [BFI + 10,EG14,Ràf15,DGP + 19]. Unfortunately, the efficiency of Groth-Sahai proofs often remains unsatisfying (typically much worse than NIZKs obtained with Fiat-Shamir), and building an optimized Groth-Sahai proof for a specific problem is an often tedious process that requires considerable expertise. This lack of conceptual simplicity inhibits the potential for largescale deployment of this proof system. Therefore, we view it as one of the major open problems in this line of work to obtain an efficient proof system where constructing an optimized proof for a given statement does not require dedicated expertise. The Fiat-Shamir transform offers such a candidate -and as a consequence, it has seen widescale adoption in real-world protocols -but lacks a formal proof of security. The recent line of work on quasi-adaptive NIZKs [JR13,KW15,ALSZ20] offers simultaneously simple, efficient, and provably secure proof systems, but these are restricted to a small class of languages -namely, linear languages. Some recent SNARK proof systems also offer generic and efficient methods to handle a large class of languages given by their high-level description; however, they all rely on very strong knowledge-of-exponent style assumptions. The Couteau-Hartmann argument system. Very recently, Couteau and Hartmann put forth a new framework for constructing pairing based NIZKs [CH20]. At a high level, their approach compiles a specific interactive zero-knowledge proof into a NIZK (as does Fiat-Shamir), by embedding the challenge in the exponent of a group equipped with an asymmetric pairing. The CH argument system enjoys several interesting features:

-It generates compact proofs, with efficiency comparable to Fiat-Shamir arguments, with ultra-short common reference strings (a single group element); -It has a conceptually simple structure, since it compiles a well-known and simple interactive proof; -It handles a relatively large class of algebraic languages [BBC + 13,CC18], which are parameterized languages of the shape L Γ ,θ = {x : ∃w, Γ (x) • w = θ(x)}, where x is the input, w is the witness, Γ and θ are affine maps, such that x and θ(x) are vectors and Γ (x) is a matrix. We call (θ, Γ ) the matrix description of the language L. Since any NP language can be embedded into an algebraic language4 , this gives a proof system for all of NP. These features make the CH argument system a competitive alternative to Fiat-Shamir and Groth-Sahai in settings where efficiency and conceptual simplicity are desirable while maintaining provable security under a plausible, albeit new, assumption over pairing groups. In a sense, Couteau-Hartmann achieves a sweet spot between efficiency, generality, and underlying assumption. Limitations of the CH argument system. The CH transformation offers attractive efficiency features, but its core advantage is (arguably) its conceptual simplicity. As many previous works pointed out (see e.g. [KZM + 15]), what "real-world" protocol designers need is a method that can easily take a high-level description of a language, and "automatically" generate a NIZK for this language without going through a tedious and complex process requiring dedicated expertise. Ideally, both the process of generating the NIZK description from the high-level language and the NIZK itself should be efficient.

With this in mind, CH provides an important step in the right direction, where producing the NIZK for any algebraic language is a straightforward generic transformation applied to its matrix description. However, it falls short of fully achieving the desired goal for two reasons.

First, it does not entirely remove the need for dedicated expertise from the NIZK construction; rather, it pushes the complexity of building the NIZK to that of finding its matrix description given a higher-level description of an algebraic language. However, it does not provide a characterization of which languages, given via a common higher-level description, are algebraic, neither does it give a method to construct their matrix description 5 .

Second, the CH-compilation produces NIZKs whose soundness reduces to an instance of the novel ExtKerMDH family of assumptions. However, the particular assumption will only be falsifiable in the much more restricted setting of witness-samplable algebraic languages, which essentially seem to capture disjunctions of linear languages. Couteau and Hartmann focused on NIZKs based on the falsifiable variant, which severely limits the class of languages captured by the framework. It is much more desirable to base the security of all NIZKs produced by this framework on a single, plausible, well-supported assumption: this would avoid protocol designers the hurdle of precisely assessing the security of the specific flavor of the ExtKerMDH assumption their particular instance requires.

Our Contribution

We overcome the main limitations of the CH argument system. Our new approach, which significantly departs from the CH methodology, allows us to produce compact NIZKs for a variety of languages, with several appealing features. A general framework. We provide a generic method to compute, for several important families of languages, a different matrix description of the languages. We then construct a NIZK. We implicitly use the CH-compiler but in a way, different from [CH20]. We focus on the important set-ting of commit-and-prove NIZK argument systems [Lip16,KOS18,Kiy20], i.e. languages of the form {Com(x 1 ), . . . , Com(x n ) | R(x 1 , . . . , x n )}, where R is some efficiently computable relation. Our method allows us to automatically obtain a compact matrix description for many types of high-level relations. New NIZKs: improved efficiency or generality. As a first byproduct, we obtain improved NIZKs for some important statements, such as set membership (see Table 1) or the language of commitments to points on an elliptic curve6 , as well as new NIZKs for very general classes of statements, such as R1CS, arithmetic constraint satisfaction systems (and thus for NP). A weaker unified assumption. As the second byproduct of our formal approach, we manage to base all NIZKs in our framework on a slightly weaker form of the extended Kernel Diffie-Hellman assumption, which we call the CED (family of) assumption(s) (for Computational Extended Determinant assumption). This turns out to have an important consequence: we show that all instances of our assumption can be based on a single plausible gap assumption, which states that solving the kernel Diffie-Hellman assumption in a group G 2 (a well-known search assumption implied in particular by DDH) remains hard, even given a CDH oracle in a different group G 1 . On top of it, several of our NIZKs (like the one for Boolean Circuit-SAT) are based on a falsifiable CED assumption, while we also show that a slight modification of the NIZK for arithmetic circuits can be also based on a falsifiable variant of CED. New SPHFs. Eventually, as another byproduct of our methodology, we obtain constructions of Smooth Projective Hash Functions (SPHFs) [GL03] for new languages (SPHFs were the original motivation for introducing the notion of algebraic language, and [BBC + 13] gives a generic construction of SPHFs given the matrix description of an algebraic language), including languages describable by efficient algebraic branching programs.

Efficiency, Generality, and Security of our NIZKs

The argument of Couteau and Hartmann [CH20] improves over (even optimized variants of) the standard Groth-Sahai approach on essentially all known algebraic languages. Couteau and Hartmann illustrated this by providing shorter proofs for linear languages (Diffie-Hellman tuples, membership in a linear subspace) and OR proofs (and more generally, membership in t out of n possibly different linear languages), two settings with numerous important applications (to structure-preserving signatures, tightly-secure simulation-sound NIZKs, tightly-mCCA-secure cryptosystems, ring signatures...). Our framework builds upon the Couteau-Hartmann framework, provides a clean mathematical approach to overcoming its main downside (which is that the matrix description of "algebraic languages" must be manually found), and significantly generalizes it. Our framework enjoys most of the benefits of the Couteau-Hartmann framework, such as its ultra-short common random string (a single random group element).

Efficiency. Our framework shines especially as soon as the target language becomes slightly too complex to directly "see" from its description an appropriate and compatible matrix description C of the language; then, we get significant efficiency improvements. We illustrate this on a natural and useful example: set membership proofs for ElGamal ciphertext over G 1 (i.e., the language of ElGamal encryptions of m ∈ S for some public set S of size d), see Table 1. It depicts the complexity of optimized Groth-Sahai proofs, the generic Couteau-Hartmann compilation of Maurer's protocol (denoted CHM) by using the language parameters (Γ , θ) provided in [CH20], CHM NIZK for (Γ , θ) automatically derived in the current paper from the matrix description C, and our new NIZK. On the other hand, our modular approach provides significantly shorter proofs. Taking e.g. d = 5, we get a proof about 25% shorter compared to Groth-Sahai. Our approach also significantly improves in terms of computational efficiency. Moreover, since in our approach, we need to only encrypt the data in a single group, as opposed in two groups in the case of (asymmetric-pairing-based) Groth-Sahai, we have three times shorter commitments. In Section 8.2, we also discuss the case of multi-dimensional set membership proofs (where, depending on the structure of the set, our framework can lead to even more significant improvements).

Generality. Our framework also goes way beyond the class of languages naturally handled by Couteau-Hartmann. In particular, we show that our framework directly encompasses arithmetic constraint satisfaction systems (aCSPs), i.e., collections of functions F 1 , . . . , F τ (called constraints) such that each

d|G 1 | + (3d + 2)|G 2 | - - CHM NIZK + [CH20] (Γ , θ), Lemma 10 (3d -1)|G 1 | + (3d -2)|G 2 | (7d -4)e 1 + (3d -1)e 2 9d -2 New solutions CHM NIZK + new Γ , θ, Lemma 8 2d|G 1 | + (2d -1)|G 2 | (5d -3)e 1 + 4de 2 7d -1 New NIZK, Lemma 7 2d|G 1 | + (2d -1)|G 2 | ≤ 3de 1 + (4d -2)e 2 7d -1
function F i depends on at most q of its input locations. 7 In particular, this efficiently captures arithmetic circuits, hence all NP languages.8

Rank-1 constraints systems (R1CS) are well-known to be powerful, since they capture compactly many languages of interest [GGPR13]. They have been widely used in the construction of SNARKs. aCSPs directly extend these simple constraints to arbitrary low-degree polynomial relations. Moving away from R1CS to more expressive constraint systems can potentially be very useful: in many applications of NIZKs with complex languages, an important work is dedicated to finding the "best" R1CS to represent the language. The increased flexibility of being allowed to handle more general constraints can typically allow to achieve a significantly more efficient solution. While systematically revisiting existing works and demonstrating that their R1CS system could be improved using aCSPs would be out of the scope of this paper, we point out that this generalization approach was successfully applied in the past: the work of [HKR19] described a method to go beyond R1CS in "Bulletproof style" random-oracle-based NIZKs (this setting is incomparable to ours, as we focus on NIZKs in the standard model). They show how to handle general quadratic constraints, and demonstrate that this leads to efficiency improvements over Bulletproof on aggregate range proofs. Since aCSPs are even more general, handling any lowdegree polynomials, we expect that this representation could lead to significant optimizations for many applications of NIZKs that rely on R1CS representations. However, we are aware of no previous randomoracle-less NIZKs that can handle aCSPs natively.

Furthermore, even in scenarios where R1CS does indeed provide the best possible representation, our framework leads to proofs more compact than Groth-Sahai. We illustrate this on Table 2 for the case of general boolean circuits. Here, the standard GOS approach [GOS06] reduces checking each gate of the circuit to checking R1CS equations. When comparing the cost obtained with our framework to the cost achieved by a Groth-Sahai proof (using the optimized variant of [GSW09]), we find that our framework leads to three times smaller commitments, 20% shorter argument, and almost a factor two reduction in computation.

On the non-falsifiability of our assumption. When the algebraic branching program representation of the relation is multivariate, the corresponding matrix description may lead to a NIZK under a non-falsifiable assumption. This might appear at first sight to significantly restrict the interest of our framework: while our NIZKs are typically more efficient than Groth-Sahai, they are usually larger than SNARKs since they grow linearly with (the algebraic branching program representation of) the relation, while SNARKs have size independent of both the relation and the witness. Hence, if we allow non-falsifiable assumptions, wouldn't SNARKs provide a better solution?

We discuss this apparent issue in Section 10. First, we identify a large class of important cases where the underlying assumption becomes falsifiable; this includes Boolean circuits (and thus NP). Second, we provide a general approach to transform any NIZK from our framework into NIZKs under a falsifiable assumption, by replacing the underlying commitment scheme by a DLIN-based encryption scheme and double-encrypting certain values. This comes at the cost of increasing the commitment and argument size. Third, we argue that the gap assumption [OP01] underlying our framework is, despite its nonfalsifiability, a very natural and plausible assumption; see Section 10 for more details. In particular, gap assumptions are generally recognized as much more desirable than knowledge of exponent assumptions. In essence, our assumption says that uncovering structural weaknesses in a group G 1 does not necessarily imply the existence of structural weaknesses in another group G 2 ; in particular, this assumption trivially holds in the generic bilinear group model (where a CDH oracle in G 1 provides no useful information for breaking any assumption in G 2 ).

Overall, we view our framework as providing a desirable middle ground between Groth-Sahai (which leads to less efficient NIZKs, but under the standard SXDH assumption) and SNARKs (which lead to more efficient NIZKs in general but require highly non-standard knowledge of exponent assumptions).

Technical Overview

Intuitive overview. At a high level, the Couteau-Hartmann methodology compiles a Σ-protocol for languages of the form {x : ∃w, Γ (x) • w = θ(x)}, where (Γ , θ) are linear maps, into a NIZK. This leaves open, however, the tasks of characterizing which languages admit such a representation, finding such a representation, and when multiple representations are possible optimizing the choice of the representation. We provide a blueprint for these tasks.

We focus on commit-and-prove languages, a large and useful class of languages. At the heart of our techniques is a general method to convert a set of low-degree polynomial equations F i (X) into a set of "optimized" matrices C i (X) such that det(C i (X)) = F i (X) with a specific additional structure. We call this matrix a quasideterminental (QDR) representation of the polynomial. Then, we directly construct a compact NIZK proof system for a QDR, using a variant of the Couteau-Hartmann methodology. We prove that the resulting proof system is sound under a CED assumption. Whenever F i has a polynomial number of roots (e.g., univariate), the corresponding CED assumption is always falsifiable.

Constructing a QDR from a polynomial is a non-trivial task that highly depends on the representation of F i . We provide a general framework to construct such QDRs from the algebraic branching program (ABP [Nis91]) representation of F i ; hence, our framework is especially suited whenever the polynomials have a compact ABP representation. ABP is a powerful model of computation, capturing in particular all log-depth circuits, boolean branching programs, boolean formulas, logspace circuits, and many more.

Background. The rest of the technical overview requires understanding of some minimal background from algebraic geometry, see [CLO15] for more. Let F = Z p and X = (X 1 , . . . , X ν ). For a set F of polynomials in F[X], let A(F) := {χ ∈ F ν : f (χ) = 0 for all f ∈ F } be the algebraic set defined by F. A subset A ⊆ F ν is an algebraic set if A = A(F) for some F. Given a subset A of F ν , let I(A) be the ideal of all polynomial functions vanishing on A, I(A) := {f ∈ F[X] : f (χ) for all χ ∈ A}. Since each ideal of F[X] is finitely generated [CLO15], then so is I(A), and thus I(A) = F 1 , . . . , F τ for some F i . I is principal if it is generated by a single polynomial. All univariate ideals are principal. For an ideal I with generating set {F i }, A(I) := A({F i }). We also define Z(F ) := A({F }).

Commit-and-prove NIZKs for algebraic sets. For the sake of concreteness, we focus on commit-andprove languages where the underlying commitment scheme is the ElGamal encryption scheme; it is easy to extend this approach to any additively homomorphic and perfectly binding algebraic commitment scheme. Let pk be an Elgamal public key and let A be an algebraic set. We provide a general methodology of constructing a NIZK argument for the language

L pk,A = {[ct] 1 : ∃χ such that Dec([ct] 1 ) = [χ] 1 ∧ χ ∈ A}
of Elgamal-encryptions of elements of A. We define L pk,F := L pk,Z(F ) when we are working with a single polynomial. Assuming I(A) = F 1 , . . . , F τ , we prove that χ ∈ A by proving that F i (χ) = 0 for each F i . The resulting argument system is efficient (probabilistic polynomial-time), assuming that there is (i) an efficient algorithm (to be run only once) that finds a small generating set (F 1 , . . . , F τ ) for I(A) where τ = poly(λ), and (ii) an efficient NIZK argument system to show that F i (χ) = 0 for each F i . Note that the NIZK for showing that F i (χ) = 0 for each i is a simple conjunction of NIZKs for showing for each i that F i (χ) = 0. Now, i is a non-cryptographic problem from computational commutative algebra. The classical Buchberger-Möller algorithm [MB82] can find efficiently a finite Gröbner basis {F i } for all algebraic sets A that have a finite Gröbner basis. Other methods exist, and we will only mention a few. Most importantly, one can relate i to finding efficient arithmetic circuits and arithmetic constraint satisfaction systems (aCSPs), see Section 8.1.9 The main technical contribution of our work (on top of the general framework) is to propose an efficient solution to ii.

Constructing a compact proof system for F (χ) = 0. Here, we follow the next blueprint: we construct (iii) a small matrix C(X) (that satisfies some additional properties) of affine maps, such that det(C(X)) = F (X), and (iv) an efficient NIZK argument system for showing that det(C(χ)) = 0 for committed χ.

To solve iv, we build upon the new computational extended determinant assumption (CED). The CED assumption is a relaxation of the ExtKerMDH assumption from [CH20], which itself is a natural generalization of the Kernel Diffie-Hellman assumption. At a high level, CED says that given a matrix in a group G 2 , it is hard to find an extension of this matrix over G 2 , together with a large enough set of linearly independent vectors in G 1 in the kernel of the extended matrix (where (G 1 , G 2 ) are groups equipped with an asymmetric pairing). While CED is not falsifiable in general, it can be reduced to a natural gap assumption. The latter reduction does not work with the ExtKerMDH assumption.

Our reduction to the CED assumption proceeds by identifying the matrix C, returned by the CED adversary, with the matrix C(X) from iii. Intuitively, we construct a reduction that, knowing the Elgamal secret key sk, extracts [(γ C)(χ)] 1 , where [χ] 1 = Dec sk ([ct] 1 ), such that C(χ) has full rank iff the soundness adversary cheated, i.e., F (χ) = 0. In that case, the reduction can obviously break the CED assumption.

To ensure that the NIZK argument can be constructed, we require that C satisfies two additional properties. Briefly, (1) C(X) is a matrix of affine maps, (to ensure that the matrix is computable from the statement) and (2) the first column of C(χ) is in the linear span of the remaining columns of the matrix for any χ ∈ Z(F ) (a technical condition which ensures that an honest prover can compute the argument). We say that then C(X) is a quasideterminantal representation (QDR) of F . We also give some conditions which make it easier to check whether a given matrix is a QDR of F .

Building NIZKs from QDRs. Assuming C(X) is a QDR of F , we propose a linear-algebraic NIZK argument Π nizk for showing that x ∈ L pk,F . We prove that Π nizk is sound under a CED assumption. Importantly, CED is falsifiable if A = A(F ) has a polynomial number of elements. Otherwise, CED is in general non-falsifiable (except in some relevant cases, see Section 10), but belongs to the class of "inefficient-challenger" assumptions (usually considered more realistic than knowledge assumptions, see [Pas13]). Furthermore, CED can be reduced to a single, natural gap assumption: the hardness of breaking DDH in a group G 2 given a CDH oracle in a different group G 1 . We refer to 10.2 for more details.

Constructing QDRs. The remaining, highly non-trivial, problem is to construct a QDR of F , such that the constructed NIZK argument is efficient. In the rest of the paper, we study this problem.

First, we propose a general framework to construct NIZK arguments for L pk,F where F (χ) can be computed by an efficient algebraic branching program. Let Π be an ABP that computes F , with the node set V and the edge set E, and let = |V | -1. Given the methodology of [IK00,IK02], one can represent Π as an × matrix IK(X), such that det(IK(X)) is equal to the output of the ABP. We show that such IK(X) is a QDR. Thus, we obtain an efficient computationally-sound NIZK for L pk,F under a CED assumption.

Applications. We consider several natural applications of our framework. Univariate polynomials. Given a univariate polynomial F (X) = (X -ξ i ) of degree-d, for different roots ξ i , we construct a simple matrix C(X). The resulting NIZK argument is about 30% shorter and 20% more computationally efficient than the set membership proof that stems from [CH20, Section C]; see the comparison in Table 1. Commitments to points on an elliptic curve. We construct a NIZK argument to prove that the committed point (X, Y ) belongs to the given elliptic curve Y 2 = X 3 + aX + b. Such NIZK proofs are popular in cryptocurrency applications, [BCTV14]. The construction of C(X, Y ) is motivated by a classical algebraic-geometric (possibility) result that for any homogeneous cubic surface F (X, Y, Z), there exists a 3 × 3 matrix of affine maps that has F (X, Y, Z) as its determinant [Dic21,Bea00]. OR proofs. In Section 6.2, we look at the special case of OR proofs and study three instantiations of our general protocol to OR arguments. We discuss the advantages and downsides of each. Non-Principal Ideals. Importantly, in Section 8, we capture the very general scenario where I(A) has a "nice-looking" generating set (F 1 , . . . , F τ ) (i.e. τ is small and each polynomial has a small degree). Some cryptographically important examples include arithmetic circuits, R1CS, Boolean circuits, and arithmetic constraint satisfaction systems. Thus, we obtain efficient NIZKs for NP.

Preliminaries

For a matrix A ∈ Z n×n p and i ∈ [1, n], let C (i,1) be the submatrix obtained from C by removing the ith row and the first column.

Cryptography. A bilinear group generator

Pgen(1 λ ) returns p = (p, G 1 , G 2 , G T , ê, [1] 1 , [1] 2 ), where G 1 , G 2 , and G T are three additive cyclic groups of prime order p, [1] ι is a generator of G ι for ι ∈ {1, 2, T } with [1] T = ê([1] 1 , [1] 2 ), and ê : G 1 × G 2 → G T is
a non-degenerate efficiently computable bilinear pairing. We require the bilinear pairing to be Type-3 [GPS08], that is, we assume that there is no efficient isomorphism between G 1 and G 2 . We use the additive implicit notation of [EHK + 13], that is, we write

[a] ι to denote a[1] ι for ι ∈ {1, 2, T }. We denote ê([a] 1 , [b] 2 ) by [a] 1 • [b] 2 . Thus, [a] 1 • [b] 2 = [ab] T .
We freely use the bracket notation together with matrix notation; for example, if

AB = C then [A] 1 • [B] 2 = [C] T . We also assume that [A] 2 • [B] 1 := ([B] 1 • [A] 2 ) = [AB] T . Let P ν := {[a 0 ] 1 + ν i=0 [a i ] 1 X i : a i ∈ Z p for i ∈ [0, ν]} ⊂ G 1 [X]
be the set of linear multivariate polynomials over G 1 in ν variables.

Algebraic languages [CC18,CH20] are parameterized languages of the shape L Γ ,θ = {x : ∃w, Γ (x)•w = θ(x)}, where x is the input, w is the witness, Γ and θ are affine maps, such that x and θ(x) are vectors, and Γ (x) is a matrix. One can construct Gennaro-Lindell smooth projective hash functions (GL-SPHFs [GL03,BBC + 13,Ben16]) for all algebraic languages.

Let k ∈ {1, 2, . . .} be a small parameter related to the matrix distribution. In the case of asymmetric pairings, usually k = 1. Let D k be a probability distribution over Z ×k p , where > k. We denote D k+1,k by D k . We use the matrix distribution, L 1 , defined as the distribution over matrices ( 1 a ), where a ←$ Z p . In the Elgamal encryption scheme [ElG84], the public key is pk = [1, sk] 1 , and Enc pk (m; r) =

(r[1] 1 m[1] 1 + r[sk] 1 ). To decrypt, one computes [m] 1 = Dec sk ([c] 1 ) ← -sk[c 1 ] 1 + [c 2 ] 1 . In what fol- lows, we denote [c] 1 = Enc(m; r) for a fixed public key pk = 1 sk 1 . Elgamal's IND-CPA security is based on L 1 -KerMDH, that is, DDH.
The following Extended Kernel Diffie-Hellman assumption ExtKerMDH [CH20] generalizes the wellknown KerMDH assumption [MRV16]. (Appendix A.1 defines KerMDH.) We also define in parallel a new, slightly weaker version of this assumption, CED (computational extended determinant).

Definition 1 (D k -( -1)-ExtKerMDH). Let , k ∈ N, and D k be a matrix distribution. The D k -( -1)-ExtKerMDH assumption holds in G ι relative to Pgen, if for all PPT adversaries A, the following probability is negligible:

Pr p ← Pgen(1 λ ), [D] ι ←$ D k , ([γ C] 3-ι , [δ] ι ) ← A(p, [D] ι ) : δ ∈ Z ( -1)×k p ∧ γ ∈ Z ×k p ∧ C ∈ Z × p ∧ (γ C) D δ = 0 ∧ rk(γ C) ≥ .
We define D k -( -1)-CED analogously, except that we change the condition rk(γ C) ≥ to rk(C) ≥ .

CED is weaker than ExtKerMDH since a successful adversary has to satisfy a stronger condition (rk(C) ≥ instead of rk(γ C) ≥ ). (See Appendix A.3 for a reduction.) CED suffices for the security of all NIZK arguments of the current paper. Moreover, in Section 10.2, we reduce CED to a gap assumption. It seems that ExtKerMDH cannot be reduced to the same assumption. Finally, CED is a natural assumption since we always care about rk(C) and not rk(γ C) ≥ . Despite the general definition, in the rest of the paper (following [CH20]), we will be only concerned with the case k = 1 and D k = L 1 . NIZK Arguments. An adaptive NIZK Π for a family of language distribution {D p } p consists of five probabilistic algorithms: (1) Pgen(1 λ ): generates public parameters p that fix a distribution D p .

(2) kgen(p): generates a CRS crs and a trapdoor td. For simplicity of notation, we assume that any group parameters are implicitly included in the CRS. We often denote the sequence "p ← Pgen(1 λ ); (crs, td) ← kgen(p)" by (p, crs, td) ← kgen(1 λ ). (3) P(crs, lpar, x, w): given a language description lpar ∈ D p and a statement x with witness w, outputs a proof π for x ∈ L lpar . (4) V(crs, lpar, x, π). On input of a CRS, a language description lpar ∈ D p , a statement and a proof, accepts or rejects the proof. ( 5) Sim(crs, td, lpar, x). Given a CRS, the trapdoor td, lpar ∈ D p , and a statement x, outputs a simulated proof for the statement x ∈ L lpar .

Note that the CRS does not depend on the language distribution or language parameters, i.e. we define fully adaptive NIZKs for language distributions. The following properties need to hold for a NIZK argument.

A proof system Π for {D p } p is perfectly complete, if

Pr V(crs, lpar, x, π) = 1 | (p, crs, td) ←$ K crs (1 λ ); lpar ∈ Supp(D p ); (x, w) ∈ R lpar ; π ←$ P(crs, lpar, x, w) = 1 A proof system Π for {D p } p is computationally sound, if for every efficient A, Pr V(crs, lpar, x, π) = 1 (p, crs, td) ←$ K crs (1 λ ); ∧x / ∈ L lpar lpar ∈ Supp(D p ); (x, π) ← A(crs, lpar) ≈ 0
with the probability taken over K crs . Π for {D p } p is perfectly zero-knowledge, if for all λ, all (p, crs, td) ∈ Supp(K crs (1 λ )), all lpar ∈ Supp(D p ) and all (x, w) ∈ R lpar , the distributions P(crs, lpar, x, w) and Sim(crs, td, lpar, x) are identical.

Σ-Protocols.

A Σ-protocol [CDS94] is a public-coin, three-move interactive proof between a prover P and a verifier V for a relation R, where the prover sends an initial message a, the verifier responds with a random e ←$ Z p and the prover concludes with a message z. Lastly, the verifier outputs 1, if it accepts and 0 otherwise. In this work we are concerned with three properties of a Σ-protocol: completeness, optimal soundness and honest-verifier zero-knowledge. CH compilation. Couteau and Hartmann [CH20] compile Σ-protocols to NIZKs in the CRS model for algebraic languages by letting [e] 2 be the CRS. The basic Couteau and Hartmann compilation is for a Σ-protocol, inspired by [Mau09], for algebraic languages. We will describe it in Section 9.

Quasideterminantal Representations

Next, we define quasideterminantal representations (QDRs) C(X) of a polynomial F (X). We prove a technical lemma in Section 3.1 which shows how one can check whether a concrete matrix C(X) is a QDR of F . We use this definition in Section 4, where, given a QDR C(X), we define the NIZK argument for the associated language L pk,F (defined in Eq. ( 1)), and prove its security.

We first define the class of languages we are interested in. Initially, we are interested in the case where A = A({F }) for a single polynomial F . Fix p ← Pgen(1 λ ). For a fixed Elgamal public key pk, let lpar := (pk, F ). (Implicitly, lpar also contains p.)

Let [ct] 1 = Enc([χ] 1 ; r) = (Enc([χ i ] 1 ; r i )) i . We use freely the notation F (Dec([ct] 1 )) = F ([χ] 1 ) = [F (χ)] 1 .
In Section 4, we describe a general technique that results both in efficient NIZK arguments for languages

L pk,F = {[ct] 1 : ∃χ such that Dec([ct] 1 ) = [χ] 1 ∧ χ ∈ Z(F )} . (1)
For example, if F (X) = X 2 -X, then L pk,F corresponds to the language of all Elgamal encryptions of Boolean values under the fixed public key pk. Intuition. To motivate the definition of QDRs, we first explain the intuition behind the new NIZK argument. Recall from Definition 1 that an adversary breaks the

L 1 -( -1)-CED assumption if, given [D] 2 = [ 1 e ] 2 ←$ L 1 (i.e., e ←$ Z p ), he returns ([γ C] 1 ∈ G ×( +1) 1 , [δ] 2 ∈ G ( -1)×1 2
), such that rk(C) ≥ and γ + C( e δ ) = 0.

(2)

Following [CH20], in our arguments [e] 2 (i.e., [D] 2 ) is given in the CRS and [δ] 2 is chosen by the prover. More precisely, the prover sends Enc([γ C] 1 ) and [δ] 2 (together with some elements that make it possible to verify that Eq. ( 2) holds using encrypted values) to the verifier.

The matrix C must have full rank whenever the prover cheats, i.e. F (χ) = 0. We achieve this by requiring that det(C(X)) = F (X). Then, rk(C) = d.

We guarantee that C is efficiently computable by requiring that C(X) is a matrix of affine maps, and

[C] 1 = [C(χ)] 1 for [χ] 1 = Dec([ct] 1
). This also minimizes communication since each element of Enc([C(χ)] 1 ) can be recomputed from Enc([χ] 1 ) by using the homomorphic properties of Elgamal.

On the other hand, assume that the prover is not honest (i.e., det(C(χ)) = F (χ) = 0) but managed to compute Enc([γ] 1 ) and [δ] 2 accepted by the verifier. Assume that the reduction knows sk (the language trapdoor). Then, the reduction obtains [χ] 1 by decryption and recomputes [C(χ)] 1 . Since det(C(χ)) = 0 but the verifier accepts (i.e., Eq. ( 2)), then one can break the CED assumption by returning [(γ C)(χ)] 1 and [δ] 2 .

Definition

We now define quasideterminantal representations (QDRs) C(X) of polynomial F . QDRs are related to the well-known notion of determinantal representation from algebraic geometry, see Appendix B.1 for a discussion.

Definition 2 (Quasideterminantal Representation (QDR)). Let F (X) ∈ Z p [X] be a ν-variate polynomial. Let ≥ 1 be an integer. A matrix C(X) = (C ij (X)) ∈ Z p [X] × is a QDR of F , if the following requirements hold. Here, C(X) = (h T )(X), where h(X) is a column vector. Affine map: For each i and j, C ij (X) = ν k=1 P kij X k + Q ij , for public P kij , Q ij ∈ Z p , is an affine map. F -rank: det(C(X)) = F (X). First column dependence: For any χ ∈ Z(F ), h(χ) ∈ colspace(T (χ)). The quasideterminantal complexity qdc(F ) of F is the smallest QDR size of F . (Clearly, qdc(F ) ≥ deg(F ).) For example, C(X) = 0 X X-1 1-X is a QDR of F (X) = X(X -1).
The first column dependence property follows since 0 χ-1 = χ 1-χ w iff (χ, w) = (0, -1) or (χ, w) = (1, 0), i.e., χ ∈ Z(F ). On the other hand, C(X) = X 0 0 X-1 is not a QDR (of the same F ) since ( χ 0 ) = 0 χ-1 w iff (χ, w) = (0, 0). The first column dependence property is nicely connected to a computational requirement we need for our NIZK. However, it can be difficult to check whether a given matrix satisfies this condition. We now give two alternative conditions that imply the first column dependence property, and which are easier to check.

Lemma 1. Suppose a matrix C satisfies the affine map and F -rank properties. If it in addition satisfies one of the following properties, it also satisfies the first column dependence property.

(1) High right rank: For any χ ∈ Z ν p , rk(T (χ)) = -1.

(2) Invertible right-submatrix: there exists i, s.t. det(C (i,1) (χ)) = 0 for any χ.

Proof. (1). Consider any

χ ∈ Z(F ). By the F -rank property, det(C(χ)) = 0 and thus rk(C(χ)) ≤ -1. Suppose h(χ) ∈ colspace(T (χ)). Then rk(C(χ)) > rk(T (χ)). By the high right rank property, -1 ≥ rk(C(χ)) > rk(T (χ)) = -1, which is a contradiction. Thus, h(χ) ∈ colspace(T (χ)).
(2). From the invertible right-submatrix property, rk(C (i,1) (χ)) = -1, and thus rk(T (χ)) = -1.

E.g., any matrix C(X) that contains non-zero elements on its upper 1-diagonal and only 0's above the upper 1-diagonal is automatically a QDR of F (X) := det(C(X)). See Sections 5 and 6 for more.

Corollaries

The affine map property is needed since we use a homomorphic cryptosystem which makes it possible to compute Enc(

[C ij (χ)] 1 ) = ν k=1 P kij Enc([χ k ] 1 )+Q ij Enc([1] 1 ) given only Enc([χ] 1
). The F -rank property follows directly from the definition of CED. The first column dependence property, guarantees that the QDR C(X) satisfies the following two properties, required later: Efficient prover: There exist two PPT algorithms that we later explicitly use in the new NIZK argument (see Fig. 2) for L pk,F . First, comp 1 (p, χ, C(X)), that computes [γ] 1 and a state st. Second, comp 2 (st, [e] 2 ), that computes [δ] 2 . We require that if

comp 1 (p, χ, C(X)): Write C(χ) = (h T )(χ); y ←$ Z -1 p ; γ ← T (χ)y; st ← (p, χ, C(X); y); return ([γ]1, st); comp 2 (st, ψ(e)): Write C(χ) = (h T )(χ); Compute w such that T (χ)w = h(χ); ψ(δ) ← -(wψ(e) + ψ(y)); return ψ(δ);
F (χ) = 0, then ([γ] 1 , [δ] 2 ) satisfy Eq.
(2). We denote the sequential process

([γ] 1 , st) ← comp 1 (p, χ, C(X)), [δ] 2 ← comp 2 (st, [e] 2 ) by ([γ] 1 , [δ] 2 ) ← comp(p, [e] 2 , χ, C(X)). Zero-knowledge: For ([γ] 1 , [δ] 2 ) ← comp(p, [e] 2 , χ, C(X)), δ is uniformly random. This requirement
is needed for the zero-knowledge property of the resulting NIZK argument. To be able to construct an efficient Σ-protocol for L pk,F , we need to replace the efficient prover assumption with the following assumption. Efficient prover over integers: as the "efficient prover" requirement, but one uses e everywhere instead of [e] 2 , and δ instead of [δ] 2 . In all our instantiations, the two variations of comp are related as follows: comp(p, [e] 2 , χ, C(X)) is the same as comp(p, e, χ, C(X)) but applies an additional [•] 2 to some of the variables.

Remark 1. We will explicitly need the independence of [γ] 1 from [e] 2 for Σ-protocols and thus for CHcompilation. It is not a priori clear if it is needed for NIZK arguments in general. However, if γ = f (e) for some non-constant affine map f , then one cannot efficiently compute [γ] 1 given only [e] 2 , since we rely on type-III pairings and those two values belong to different source groups. Thus, independence of [γ] 1 from [e] 2 seems inherent in the case of type-III pairings.

Lemma 2. Assume F is as in Definition 2 and that C(X) is a QDR of F . Then (1) C has the efficientprover property. (2) C has the zero-knowledge property.

Proof. Recalling C(X) = (h T )(X), we rewrite Eq. (2) as γ + h(X)e + T (X)δ = 0 .

(3)

Assume C(X) is a QDR of F . From the first column dependence property, we get that for any χ ∈ Z(F ), there exists a w, such that T (χ)w = h(χ). Thus for such χ, Eq. (3) holds iff γ + T (χ)(we + δ) = γ + T (χ)we + T (χ)δ = 0. This gives rise to the following algorithm to compute γ and δ. In comp 1 , one samples y ←$ Z -1 p , and outputs γ ← T (χ)y. In comp 2 , one solves T (χ)w = h(χ) for w, and sets δ ← -(we+y). Clearly, γ and δ satisfy Eq. ( 2), and γ is computed independently of e. Thus, the efficient prover property holds. Since y is uniformly random, so is δ = -(we + y). Hence, the zero-knowledge property is satisfied. We depict the algorithms in Fig. 1.

Finally, we show that any matrix which satisfies the efficient prover property as well as the affine map and F -rank properties must satisfy the first column dependence property. Thus, the latter property is actually needed. Lemma 3. Let C(X) be a matrix that satisfies the affine map, F -rank and efficient prover properties. Then C satisfies the first column dependence property.

Proof. Fix p, χ, and C(X) = (h T )(X), and let comp i be any (potentially inefficient) algorithms that output

([γ] 1 , [δ] 2 ), such that [γ] 1 does not depend on e. Consider any ([γ] 1 , st) ← comp 1 (p, χ, C(X)).
For any e and the given st, let [δ e ] 2 ← comp 2 (st; [e] 2 ). Suppose that γ does not depend on e. Fix any e = e . Since Eq. ( 2) and thus Eq. ( 3) holds for both e (and thus δ = δ e ) and e (and thus δ = δ e ), h(χ)(e-e )+T (χ)(δ e -δ e ) = 0. Thus, h(χ) = T (χ)((δ e -δ e )/(e -e)), and thus h(χ) ∈ colspace(T (χ)).

kgen(p, lpar): e ←$ Z p ; return (crs, td) ← ([e] 2 , e) ;

P(crs, lpar, x = [ct] 1 , w = (χ, r)): ([γ] 1 , [δ] 2 ) ← comp(p, [e] 2 , χ, C(X)); ←$ Z p ; [ct γ ] 1 ← Enc([γ] 1 ; ) ∈ G ×2 1 ; [z] 2 ← [1] 2 + ( ν k=1 r k P k ) [ e δ ] 2 ∈ G 2 . Return π ← ([ct γ ] 1 , [δ, z] 2 ) ∈ G 2 1 × G 2 -1 2 . V(crs, lpar, x = [ct] 1 , π): check [ct γ ] 1 •[1] 2 + ν k=1 ([ct k ] 1 • P k [ e δ ] 2 ) = ? [0, 1] 1 •(-Q [ e δ ] 2 )+pk•[z] 2 . Sim(crs, td, lpar, x = [ct] 1 ): δ ←$ Z -1 p ; z ←$ Z p ; [ct γ ] 1 ← Enc(-Q( e δ )[1] 1 ; z) - ν k=1 [ct k ] 1 • P k ( e δ ); Return π ← ([ct γ ] 1 , [δ, z] 2 ) ∈ G 2 1 × G 2 -1 2 .
Fig. 2. The new NIZK argument Π nizk for L pk,F .

Argument for Algebraic Set of Principal Ideal

Fix p ← Pgen(1 λ ) and define D p := {lpar = (pk, F )}, where (1) pk is an Elgamal public key for encrypting in G 1 , and (2) F is a polynomial with qdc(F ) = poly(λ), i.e., there exists a poly(λ)-size QDR C(X) of F . (In Sections 5 and 6, we will show that such QDRs exist for many F -s.) Before going on, recall that

C ij (X) = ν k=1 P kij X k + Q ij for public P kij and Q ij .
To simplify notation, we will use vector/matrix format, by writing

C(X) = ν k=1 P k X k + Q. As always, we denote Enc([a] 1 ; r) := (Enc([a i ] 1 ; r i )) i . We often omit χ in notation like [C(χ)] 1 , and just write [C] 1 .

Protocol Description

Let L pk,F be defined as in Eq. ( 1). The new Σ-protocol and NIZK argument for L pk,F are based on the same underlying idea. Since the new NIZK is a CH-compilation of the Σ-protocol, it suffices to describe intuition behind the NIZK.

In the new NIZK argument (see Fig. 2), P uses comp 1 to compute [γ] 1 (together with state st), encrypts [γ] 1 by using fresh randomness , and then uses comp 2 (given crs = [e] 2 ) to compute [δ] 2 . If P is honest, then by the definition of QDRs of F , Eq. (2) holds, i.e., γ + C(χ)( e δ ) = 0. The latter is equivalent to γ + ( k P k χ k )( e δ ) = -Q( e δ ). V needs to be able to check that the last equation holds, while given only an encryption of [γ] 1 . To help V to do that, P sends a vector of randomizers [z] 2 to V as helper elements that help to "cancel out" the randomizers used by the prover to encrypt [γ] 1 and [χ] 1 .

The new NIZK argument is given in Fig. 2.

Efficiency

Next, we estimate of the efficiency of the NIZK argument. Note that if we use the comp algorithm given in Fig. 1, we see that the algorithm computes w and y such that

[δ] 2 = -(w[e] 2 + y[1] 2 ). This lets us write [ e δ ] 2 = 1 -w [e] 2 + 0 -y [1] 2 . This allows us to compute [z] 2 as ( ν k=1 r k P k ) 1 -w [e] 2 + ( + ν k=1 r k P k ) 0 -y [1]
2 , which can be done with 2 exponentiations in G 2 . This leads to the following lemma. Its proof follows by direct observation.

T P (C) + T Q (C)) • e 2 + 2(2 + ν) • p, (3) the communication is 2 elements of G 1 and 2 -1 elements of G 2 .
For the argument to be efficient, we need comp to be as efficient (according to Section 3.1, it must be efficient to solve the system T (χ)w = h(χ) for w, where C(X) = (h T )(X)), and the matrices P k and Q to be sparse.

In Section 5, we propose a way to construct C(X) that satisfies these restrictions for any F (X) that can be computed by a polynomial-size ABP. In Section 6, we study other interesting cases.

The estimate in Lemma 4 is often over-conservative. For example, let δ = ( e δ ). If P kij1 = P kij2 =: P for j 1 = j 2 , then the verifier has to perform one exponentiation P ([δ j1 ] 2 + [δ j2 ] 2 ) instead of two. The same holds when Q ij1 = Q ij2 for some j 1 = j 2 . Moreover, when the exponent is a small constant (in the extreme case, 1 or -1), then one does not have to perform a full-exponentiation.

Security of the NIZK Argument

Theorem 1. Let {D p } p be the family of language distributions, where D p = {lpar = (pk, F )} as before.

Here, F (X) is a ν-variate polynomial of degree d, where ν, d ∈ poly(λ). Let C(X) ∈ Z p [X] × be a QDR of F . The NIZK argument Π nizk for {D p } p from Fig. 2 is perfectly complete and perfectly zero-knowledge. It is computationally (adaptive) sound under the L 1 -( -1)-CED assumption in G 2 relative to Pgen.

Proof. Completeness: To see that the NIZK argument is complete, transform the verification equation as follows:

[ct γ ] 1 • [1] 2 + ν k=1 ([ct k ] 1 • P k [ e δ ] 2 ) = ? [0, 1] 1 • (-Q [ e δ ] 2 ) + pk • [z] 2 ⇐⇒ [ct γ ] 1 + ν k=1 ([ct k ] 1 • P k ( e δ )) = ? Enc([-Q( e δ )] 1 ; z) ⇐⇒ Enc([γ] 1 ; ) + ν k=1 (Enc([χ k ] 1 ; r k ) • P k ( e δ )) = ? Enc([-Q( e δ )] 1 ; z) ⇐⇒ Enc([γ + C(χ)( e δ )] 1 ; + ( ν k=1 r k P k )( e δ ) -z) = ? Enc([0] 1 ; 0)
which holds since the prover is honest and due to the definition of z.

Perfect zero-knowledge: Fix any λ, (p, td) ∈ Supp(K crs (1 λ )) and compute crs = [td] 2 . Then fix lpar ∈ Supp(D p ) and (x, w) ∈ R lpar . In the honest prover's algorithm, since is uniformly random, then also z is uniformly random. By the zero-knowledge property (see Section 3.2), δ output by an honest prover is uniformly random. On the other hand, Sim (see Fig. 2) also samples uniformly random δ and z. Finally, in both the prover's and simulator's case, [ct γ ] 1 is the unique value that makes the verifier accept the argument π. Hence, the distributions of the prover and the simulator are perfectly indistinguishable.

Computational soundness. Let A be a soundness adversary that, for honestly generated crs and any lpar ∈ Supp(D p ) (including C), breaks Π nizk in time τ and with probability ε. We construct the following Assume that A returns an accepting input-argument pair [δ] 2 to the CED challenger. Since A is successful, the verification equation in Fig. 2 holds, and thus also the following "decryption" of the verification equation holds:

(x = [ct] 1 , π), such that x ∈ L lpar , i.e., [χ] 1 ← Dec([ct] 1 ) is such that F (χ) = 0. B uses sk to decrypt [ct] 1 to [χ] 1 and [ct γ ] 1 to [γ] 1 . B recomputes [C(χ)] 1 ← P k [χ k ] 1 + Q. B returns [γ C(χ)] 1 and
[γ] 1 • [1] 2 + ν k=1 ([χ k ] 1 • P k [ e δ ] 2 ) = [1] 1 • (-Q [ e δ ] 2
). Thus, γ + C(χ)( e δ ) = 0, i.e., Eq. ( 2) holds. Since det(C(χ)) = F (χ) = 0, C has full rank. Thus, B breaks CED.

Efficient Instantiation Based on ABP

In this section we construct QDRs, that we denote by IK(X), for any polynomial F that can be efficiently computed by algebraic branching programs (ABPs, [Nis91,BG99]). This results in NIZKs for the class of languages L pk,F , where F is only restricted to have a small ABP. However, in many cases, the resulting matrix IK(X) is not optimal, and this will be seen in Section 7.1. Thus, following sections consider alternative construction techniques of such matrices.

Preliminaries: Algebraic Branching Programs

A branching program is defined by a directed acyclic graph (V, E), two special vertices s, t ∈ V , and a labeling function φ. An algebraic branching program (ABP, [Nis91,BG99]) over a finite field F p computes a function F : F n p → F p . Here, φ assigns to each edge in E a fixed affine (possibly, constant) function in input variables, and F (X) is the sum over all s -t paths (i.e., paths from s to t) of the product of all the values along the path. Algebraic branching programs capture a large class of functions, including in particular all log-depth circuits, boolean branching programs, boolean formulas, logspace circuits, and many more. For some type of computations, they are known to provide a relatively compact representation, which makes them especially useful. See [IK00,IK02,IW14] and the references therein.

Ishai and Kushilevitz [IK00,IK02] related ABPs to matrix determinants as follows.

Proposition 1. [IK02, Lemma 1] Given an ABP abp = (V, E, s, t, φ) computing F : F ν p → F p , we can efficiently (and deterministically) compute a function IK(χ) mapping an input χ ∈ F ν p to a matrix from F × p , where = |V | -1, such that: 1. det(IK(χ)) = F (χ), 2. each entry of IK(χ) is an affine map in a single variable χ i , 3. IK(χ) contains only -1's in the upper 1-diagonal (the diagonal above the main diagonal) and 0's above the upper 1-diagonal. Specifically, IK is obtained by transposing the matrix you get by removing the column corresponding to s and the row corresponding to t in the matrix adj(X) -I, where adj(X) is the adjacency matrix for abp.

Note that the matrix IK is transposed compared to what is found in [IK02, Lemma 1], to ensure consistency with the notation from the CED assumption.

NIZK for Algebraic Branching Programs

Lemma 5. Let abp = (V, E, s, t, φ) be an ABP that computes a ν-variate polynomial F (X). Then IK(X) is a QDR of F with = |V | -1.

Proof. Items 1 and 2 of Proposition 1 state directly that the affine map and reducibility properties of Definition 2 hold. From 3 of Proposition 1, it follows that IK(X) ( ,1) is an upper triangular matrix where the diagonal which only consists of -1's. Clearly, det(IK(χ) ( ,1) ) = 0 for any χ; thus, it follows from Lemma 1 that the first column dependence property is also satisfied. The claim = |V |-1 is obvious.

In particular, qdc(F ) ≤ |V | -1. Efficiency of comp. We next specialize the general comp i algorithms given in Fig. 1 to ABP. For this, we just have to write down how to efficiently do the next two steps: (1) Compute γ = T (χ)y. Due to the shape of IK(χ) and thus of T (χ), one can clearly compute γ as

γ i ← i-1 j=1 T ij (χ)y j-1 -y i for each i ∈ [1, ].
(2) Solve T (χ)w = h(χ) for w. Let T * be the matrix obtained from T (χ) by omitting its last row, and similarly let h * be the vector obtained from h(χ) by omitting its last element. One finds w by solving T * w = h * by forward substitution, as follows: Consider an algebraic set A ∈ Z p of size poly(λ), generated by τ univariate polynomials F 1 , . . . , F τ ∈ Z p [X]. As before, we aim to prove that an Elgamal-encrypted χ satisfies χ ∈ A, i.e., F i (χ) = 0 for all i. In the univariate case, all ideals are principal [CLO15, Section 1.5], and thus any ideal can be written as I = F for some F . Thus, A = A(F ) for F ← gcd(F 1 , . . . , F τ ) [CLO15, Section 1.5].

w i ← i-1 j=1 T ij (χ)w j -h i (χ) for each i ∈ [1, -1]. Lemma 6. Let N (v)
Moreover, I(A(F )) = I(F red ) [CLO15, Section 1.5], where F red has the same roots as F but all with multiplicity one. That is, if F (X) = (X -ξ i ) bi , for b i ≥ 1 and mutually different ξ i , then

F red = s a1 • • • ad-1 t X -ξ1 X -ξ2 X -ξd-1 X -ξd IK path (X) = X-ξ1 -1 0 ... 0 0 X-ξ2 -1 ... 0 ... ... ... ... ... 0 0 0 ... -1 0 0 0 ... X-ξ d Fig. 3. The ABP abp d path (X, ξ) for F (X) = d i=1 (X -ξi) and IK path (X)
kgen(p, lpar): e ←$ Z p ; return (crs, td) ← ([e] 2 , e) ; (X -ξ i ). This reduced polynomial F red can be efficiently computed as F red = F/ gcd(F, F ), [CLO15, Section 1.5]. Since we are constructiong NIZKs for algebraic sets, in this section, we will assume that F (X) = F red (X) = (X -ξ i ) for mutually different roots ξ i . (This will be the case if we assume A = {ξ i } for polynomially many ξ i .) Thus, it suffices to prove that F (χ) = 0, where F is a reduced polynomial. As before, for efficiency reasons, we assume that F has degree poly(λ).

P(crs, lpar, x = [ct] 1 , w = (χ, r)): ([γ] 1 , [δ] 2 ) ← comp(p, [e] 2 , χ, C(X)); ←$ Z d p ; [ct γ ] 1 ← Enc([γ] 1 ; ) ∈ G d×2 1 ; [z] 2 ← [1] 2 + r [ e δ ] 2 ∈ G d 2 ; return π ← ([ct γ ] 1 , [δ, z] 2 ). V(crs, lpar, x = [ct] 1 , π): check [ct γ ] 1 • [1] 2 + [ct] 1 • [ e δ ] 2 + [0, 1] 1 • Q [ e δ ] 2 = ? pk • [z] 2 . Sim(crs, td, lpar, x = [ct] 1 ): δ ←$ Z d-1 p ; z ←$ Z d p ; [ct γ ] 1 ← Enc(-Q( e δ )[1] 1 ; z) -[ct] 1 • ( e δ ); return π ← ([ct γ ] 1 , [δ, z] 2 ).
We now apply the ABP-based protocol to a univariate reduced polynomial F . We depict the ABP abp d path (X, ξ) in Fig. 3. The ABP consists of a single path of length d with edges labelled by values X -ξ i . Clearly, abp d path (X, ξ) computes F (X). The corresponding matrix IK path (X) is also given in Fig. 3. Fig. 4 depicts the resulting set-membership NIZK argument that X ∈ {ξ i }.

Lemma 7. Let F (X) be a univariate reduced polynomial. The ABP-based NIZK argument for L pk,F has prover's computation of at most 3d exponentiations in G 1 and 4d -2 exponentiations in G 2 , verifier's computation of 7d -1 pairings and at most d exponentiations in G 2 , and communication of 2d elements of G 1 and 2d -1 elements of G 2 .

Proof. Prover: First, we write down the concrete formulas for the comp algorithm from Fig. 1.

1. Computation of γ = T (χ)y: one sets

γ 1 ← -y 1 , γ i ← (χ -ξ i )y i-1 -y i for i ∈ [2, d -1], and
γ d ← (χ -ξ d )y d-1 . (d -1 field operations.)
[γ] 1 can then be computed by using at most d exponentiations in G 1 . However, if either (a) χ = ξ d or (b) χ -ξ i is small for all i, then d -1 exponentiations suffice. 2. Solving T (χ)w = h(χ) for w:

w i ← - i j=1 (χ -ξ j ) for i ∈ [1, d -1].
This allows us compute [δ] 2 in the following way: Define [a i ] 2 := w i [e] 2 . We can recursively compute

[a i ] 2 as [a 1 ] 2 = (χ -ξ 1 )[e] 2 and [a i ] 2 = (χ -ξ i )[a i-1 ] 2 ,
and so computing each [a i ] 2 requires at most 1 exponentiation. Note that if χ = ξ j , then [a j ] 2 = [0] 2 and thus requires no exponentiations. Further, each [a i ] 2 = [0] 2 for each i ≥ j, which then also do not require exponentiations. We finally compute

[δ i ] 2 = [a i ] 2 + [y i ] 2 ,
which gives us a total of at most 2d -2 exponentiations in G 2 , and we only achieve this bound if χ = ξ d , Since field operations are cheap, comp is dominated by at most d exponentiations in G 1 to compute [γ] 1 and 2d -2 exponentiations in G 2 (up to d -2 of which can have a small exponent χ -ξ i ) to compute [δ] 2 . In addition, the prover performs 2d exponentiations in G 1 to compute [ct γ ] 1 and 2d exponentiations in G 2 to compute [z] 2 . Thus, the prover performs 3d (3d -

1 if χ = ξ d ) in G 1 and 4d -2 exponentiations in G 2 . Verifier: We first note that Q [ e δ ] 2 = -ξ • [ e δ ] 2 -[ δ 0 ] 2 ∈ G d 2 . Thus, [ct] 1 • [ e δ ] 2 + [0, 1] 1 • Q [ e δ ] 2 = [ct] 1 •[ e δ ] 2 -[0, 1] 1 •(ξ •[ e δ ] 2 +[ δ 0 ] 2 ) = [κ] T -[0, 1] 1 •[ δ 0 ] 2 , where [κ i ] T = ([ct] 1 -ξ i • [0, 1] 1 )•[( e δ ) i ] 2 . Thus, Q [ e δ ]
2 can be computed in 3d -1 pairings. Thus, the verifier's total computation is 7d -1 pairings. Note that the verifier executes at most d exponentiations; however, this number is smaller if the exponents are small. Moreover, one can usually precompute all values

[ξ i ] 1 . X X 2 s F (X) Y X X Y X a b -Y IK(X, Y ) = X -1 0 0 0 X -1 0 Y 0 0 -1 b a X -Y Fig. 5. ABP example for F (X, Y ) = X 3 + aX + b -Y 2 .
Communication: 2d group elements to transfer the ciphertexts [ct γ ] 1 , d -1 group elements to transfer [δ] 2 , and d group elements to transfer the randomizers [z] 2 , 4d -1 group elements in total.

Special Case: OR Arguments

In an OR argument, the language is L pk,X(X-1) , that we will just denote by L {0,1} , assuming that pk is understood from the context. The case of OR arguments is of particular interest because of its wide applications in many different scenarios. Indeed, one of the most direct applications of [CH20] is a new OR proof with the argument consisting of 7 group elements. Due to the importance of L {0,1} , in Appendix C.1, we will detail three example NIZK arguments that are all based on CED-matrices. The first argument is based on abp 2 path , and the other two arguments are based on known Σ-protocols from the literature. Interestingly, the third example is not based on ABPs; the added discussion clarifies some benefits of using the ABP-based approach.

Elliptic Curve Points

In Fig. 5, we depict an ABP and IK(X, Y ) for the bivariate function F (X, Y ) = X 3 + aX + b -Y 2 (i.e., one checks if (X, Y ) belongs to the elliptic curve Y 2 = X 3 + aX + b). In Section 7.1, we will propose a non-ABP-based QDR for the same task. ABPs for hyperelliptic curves Y 2 + H(X)Y = f (X) (where deg(H) ≤ g and deg f = 2g + 1) of genus g can be constructed analogously.

NIZK arguments that committed (X, Y ) belongs to the curve are interesting in practice since one often needs to prove in zero-knowledge that a verifier of some pairing-based protocol accepts. Such a situation was studied in [BCTV14], who proposed to use cycles of elliptic curves, such that the number of points on one curve is equal to the size of the field of definition of the next, in a cyclic way. Using the NIZK, resulting from the example of the current subsection, one can use a bilinear group with group order p to prove that the encrypted coordinates belong to an elliptic curve where the finite field has size p. Different normal form. Motivated by [PSV12], we also consider the following less common normal form for an elliptic curve, F (X, Y ) = (X + aY )(X + bY )(X + cY ) -X, for mutually different a, b, c.

Then, one can construct the following ABP-based 3 × 3 QDR:

X+aY -1 0 0 X+bY -1 -X 0 X+cY
.

On Bivariate Case

Dickson [Dic21] proved that for any degree-d bivariate polynomial F (X), there exists a d×d matrix C(X) of affine maps that has F (X) as its determinant. Plaumann et al.

[PSV12] described efficient algorithms for finding C(X) for some families of polynomials F ; in their case, C(X) is usually symmetric and can satisfy some other additional requirement like semidefiniteness. Since the ABP-based approach often blow ups the dimension of the matrix, we will next use the results of [Dic21,PSV12] to construct a d × d matrix C(X). However, the resulting matrix is usually not a QDR, which results in additional complications. We provide several concrete examples in the case F (X, Y ) describes an elliptic curve. Plaumann et al.

[PSV12] provided also examples for the case d ∈ {4, 5}, noting however that finding a determinantal representation of F becomes very time-consuming for d ≥ 5. In Appendix D.3, we will provide an example for d = 5. We refer to [PSV12] for algorithms and general discussion.

Optimized Solutions for Elliptic Curves

Let F (X, Y ) = X 3 + aX + b -Y 2 be a polynomial that describes an elliptic curve. In Section 6.3, we described a small ABP for checking that (X, Y ) ∈ E(Z p ), where E(Z p ) : F (X, Y ) = 0. However, this resulted in a 4 × 4 matrix IK(X, Y ). Next, we construct 3 × 3 matrices, of correct determinant, for two different choices of F . In general, there are several inequivalent linear symmetric determinantal representations of F , [PSV12]. In both cases, we chose the matrix by inspection.

Case F (X, Y ) = X 3 + aX + b -Y 2 for a = 0. In Appendix D.1, we show that in case there exists a 3 × 3 determinantal representation that is not a QDR, and discuss the possible issues that arise when one tries to use our NIZK argument in such a case. Case F (X, Y ) = X 3 + b -Y 2 . We will tackle this case in Appendix D.2.

Handling Non-Principal Ideals

Next, we extend the new framework to constructing a NIZK argument that an Elgamal-encrypted χ satisfies χ ∈ A for any algebraic set A = A(I). Namely, assume that I(A) has a known generating set (F 1 , . . . , F τ ) for some τ . We prove that χ ∈ A by proving that F i (χ) = 0 for each F i . Thus, D p = {(pk, A)}, where I(A) = F 1 , . . . , F τ and each F i has qdc(F i ) = poly(λ).

The argument system can be implemented in polynomial time and space, assuming that (1) we know a generating set with small τ = poly(λ) and with small-degree polynomials, (2) for each F i , we know a small QDR C i (X) of F i , and (3) we can construct an efficient NIZK argument system for showing that det(C i (X)) = 0. The previous sections already tackled the last two issues. In this section, we study issue (1). However, the issues are related. In particular, steps (2) and ( 3) are most efficient for specific type of polynomials F i , and when solving (1), we have to take this into account.

NIZK for NP

Next, we use the described methodology to implement arithmetic circuits, and then extend it to R1CS (a linear-algebraic version of QAP [GGPR13]) and aCSPs (arithmetic constraint satisfaction systems), i.e, constraint systems where each constraint is a small-degree constant that depends on some small number of inputs. We also show how to directly use our techniques to implement the Groth-Sahai-Ostrovsky constraint system [GOS06] that have efficient reductions to corresponding circuits. Interestingly, this seems to result in the first known pairing-based (random-oracle-less) NIZK for general aCSPs; although see [Sze20] for a recent use of aCSPs to construct SNARKs. Arithmetic circuits. Let C be an arithmetic circuit over Z p , with n gates (including input gates) and m wires. We construct an algebraic set A C = (χ 1 , . . . , χ n ) ∈ Z n p , such that χ ∈ A C iff C(χ) = 0, as follows. First, χ corresponds to the vector of wire values. As in the case of QAP [GGPR13], we assume that each gate is a weighted multiplication gate that computes F i : ( j u ij χ ij )( j v ij χ ij ) → χ i for public u ij , v ij , and i j , where for the sake of efficiency, the sum is taken over a constant number of values.

1. First, each χ i corresponds to the value of the output wire of ith gate, with χ j , j ≤ m 0 corresponding to the inputs of the circuit. We also assume that the last few wire values correspond to the output values of the circuit. 2. Second, for each gate i > m 0 , we introduce the polynomial

F i (χ) = χ i -( u ij χ ij )( v ij χ ij ).
Then A C = {(χ 1 , . . . , χ m ) : F i (χ) = 0 for all i > m 0 }. To construct a NIZK for showing χ ∈ A C , we do as before: (1) We let the prover Elgamal-encrypt χ. (2) We show that F i (χ) = 0 for all i by using the NIZK argument from Section 4. Note that each polynomial in this case is quadratic, and thus one can

construct a 2 × 2 QDR C(χ) = uij χi j -1 -χi vij χi j .
According to [GS08], the Groth-Sahai proof for this task has commitment length (2m+1

)(|G 1 |+|G 2 |) and argument length (2m + 2n + 2)(|G 1 | + |G 2 |). The new NIZK has commitment length 2m|G 1 | and argument length n(4|G 1 | + 3|G 2 |). Assuming m ≈ n and |G 2 | = 2|G 1 |,
the new NIZK has 3 times shorter commitments/encrypts and 20% shorter proofs. The new NIZK has approximately 1.5-2 times smaller prover's and verifier's computation. Since the computation in [GS08] can probably be optimized, we have not included complete comparison. Extension: R1CS. In R1CS (rank-

1 constraint system [GGPR13]), one has n constraints ( u ij χ i )( v ij χ i ) =
w ij χ i in m variables χ i , for arbitrary public matrices U = (u ij ), V = (v ij ), and W = (w ij ). There is clearly a simple reduction from arithmetic circuits to R1CS. The described solution for arithmetic circuits can be used to construct a NIZK argument system for R1CS, by defining

F i (χ) = ( u ij χ i )( v ij χ i ) -w ij χ i and C(χ) = uij χi j -1 - wij χi j vij χi j .
V comp. Groth-Sahai [GSW09] 4(|G 1 | + |G 2 |) 2(m + 1)(|G 1 | + |G 2 |) (6m + 2n + 2)(|G 1 | + |G 2 |) (12m + 4n + 4)(e 1 + e 2 ) 16(2m + n)p New, Section 8.1 |G 2 | 2m • |G 1 | (m + n)(4|G 1 | + 3|G 2 |) (m + n)(5e 1 + 4e 2 ) 13(m + n)p
Extension: Arithmetic Constraint Satisfaction Problems (aCSPs). Fix F = Z q . Recall that for a q ≥ 1, a q-aCSP instance F over F is a collection of functions F 1 , . . . , F τ (called constraints) such that each function F i depends on at most q of its input locations. That is, for every j ∈ [1, τ ] there exist i 1 , . . . , i q ∈ [1, n] and f : F q → F such that F j (χ) = f (χ i1 , . . . , χ iq ) for every χ ∈ F n . Then F is satisfiable if F j (χ) = 0 for each j.

One can extend R1CS to q-aCSP for small constant q, assuming that F j are (small-degree) polynomials for which one can construct poly-size QDRs. Intuitively, F is the generating set for some polynomial ideal I = I(A), and thus the examples of this subsection fall under our general methodology. One can possibly use some general techniques (see Section 8.2 for some examples) to minimize the generating sets so as to obtain more efficient NIZKs.

Specialization: Boolean Circuits. By using techniques from [GOS06], one can construct a NIZK for any Boolean circuit that, w.l.o.g., consists of only NAND gates. Intuitively, one does this by showing that each wire value is Boolean, and then showing that each NAND gate is followed correctly. The latter can be shown by showing that a certain linear combination of the input and output wires of the NAND gate is Boolean. Thus, here one only uses polynomials of type f i (χ) = A(χ) 2 -A(χ), where A(χ) = a ij χ j for some coefficients a ij .

In Table 2, we compare the resulting NIZK with the optimized Groth-Sahai proof for Boolean circuits by Ghadafi et al.

Various Examples

Next, we give very generic background on generating sets and after that, we give some examples of the cases when it pays off directly to work with aCSPs (and not just arithmetic circuits) and then use the described methodology to construct the NIZK. We emphasize that one does not need a Gröbner basis and thus sometimes there exist smaller generating sets. In fact, there exist many alternative methods for constructing efficient aCSPs not directly related to generating sets at all; and the Gröbner basis technique is just one of them -albeit one that is strongly related to our general emphasis on polynomial ideals. As we see from the examples, the efficiency of NIZK depends on a delicate balance between the size of the generating set and the degree of the polynomials in that set. Really, it follows from Lemma 4 that if the generating set contains polynomials F i for which QDRs have sizes i , then the resulting NIZK has communication complexity

(2 i )(|G 1 | + |G 2 |) -τ |G 2 |.
Basic Background on Generating Sets. Generating sets of an ideal can have vastly different cardinality. For example, Z is generated by either {1} or by the set of all primes. Since a Gröbner basis [Buc65] is, in particular, a generating set, one convenient way of finding a generating set is by using a Gröbner basis algorithm; however, such algorithms assume that one already knows a generating set. Fortunately, the Buchberger-Möller algorithm [MB82] (as say implemented by CoCoA 10 ) can compute a Gröbner basis for I(A), given any finite set A. Worst-Case Multi-Dimensional Set-Membership Proof. We performed an exhaustive computer search to come up with an example of a 3-dimensional set of five points that has the least efficient NIZK argument in our framework. One of the examples we found11 is A = {(2, 5, 1), (2, 4, 2), (2, 5, 3), (1, 2, 4), (3, 1, 5)}. In this case, we found a reduced degree-lexicographic Gröbner basis (y -z -2)(y + z -6), 1 18 (6x(3y -5) -37y + (z -4)z + 68),

1 9 9x 2 -33x + y -(z -4)z + 22 , 1 3 (-12x + 5y + z(z(3z -23) + 53) -34)
that consists of three quadratic and one cubic polynomials. Clearly, here, each degree-d polynomial has an optimal-size d × d QDR. In the only non-trivial case (the cubic polynomial), one can use the matrix

C4(x, y, z) = z 1 0 53/3 23/3-z -4 x-5y/12+17/6 0 -z .
Thus, one can construct a NIZK argument with communication of 2(2 + 2 + 2 + 3) = 18 elements of G 1 and 18 -4 = 14 elements of G 2 . Since, usually, elements of G 2 are twice as long as elements of G 1 , it means that, in the worst case, such a NIZK argument will only be 4.6 times longer than a single OR proof. This is also the upper bound on the NIZK communication according to our exhaustive search, further discussion would be outside the scope of the current paper.

The most efficient known alternative seems to add (structure-preserving) signatures (SPSs) of 5 points to the CRS, letting the prover encrypt a signature of the chosen point, and then proving that the encrypted value is a valid signature of some point. (See, e.g., [RKP09].) This alternative has both a much larger CRS and worse concrete complexity compared to our NIZK argument. Moreover, it assumes that the underlying signature scheme is unforgeable. Range proofs. In Appendix C.2, we will show how to use our techniques to construct range proofs, i.e., proofs that the committed value χ belongs to some interval [0, N ]. Couteau and Hartmann's approach can be used to propose range proofs of efficiency Θ(log N ) by using the binary decomposition of χ. In Appendix C.2, we note that the use of the NIZK from Section 6.1 helps us to obtain a NIZK with better verifier's computation.

Back to Algebraic Languages

The well-known methodology of diverse vector spaces (DVSs, [BBC + 13,Ben16]) has been used to successfully create efficient smooth projective hash functions (SPHFs) for algebraic languages. Moreover, by now several constructions of NIZKs based on such SPHFs are known, [ABP15,CH20]. For all such constructions, the first step is to construct language parameters Γ and θ (see Section 2). Unfortunately, existing constructions of the language parameters are all somewhat ad hoc.

Next, we improve on the situation by proposing a methodology to construct (Γ , θ) for any L pk,A , where A is any algebraic set for which Section 8 results in an efficient NIZK. We start the process from a QDR C i of F i , where F 1 , . . . , F τ is some generating set of I(A), and output concrete parameters (Γ , θ). The problem of constructing such C i was already tackled in the current paper, with many examples (including the case when C i is based on an ABP). As the end result, we construct explicit language parameters (Γ , θ) for a variety of languages where no such small parameters were known before. Moreover, even in the simple case of univariate polynomials, where previous solutions were known [BBC + 13,CH20], the new parameters are smaller than before.

We consider various NIZKs that one can construct for given (Γ , θ). For every fixed (Γ , θ), the NIZK from Section 4 is more efficient than the QA-NIZK of [ABP15] and usually more efficient than the CHM NIZK of [CH20]. Finally, we briefly discuss resulting GL-SPHFs [GL03] based on the new language parameters. Preliminaries. We describe the CHM (Couteau-Hartmann-Maurer) Σ-protocol and the resulting NIZK in Appendix F.1. There, we will also state the efficiency of their construction as a function of (Γ , θ). We also restate Theorem 18 from [CH20] about the security of the CHM NIZK.

On Algebraic Languages for Elgamal Ciphertexts

Next, we derive language parameters Γ and θ for an arbitrary L pk,F , such that θ(x) ∈ colspace Γ (x) iff x ∈ L pk,F . In the case where I(A) = F 1 , . . . , F τ is not a principal ideal, one can then "concatenate" all τ parameters Γ (x) and θ(x).

We start the derivation from the equation T (χ)w = h(χ) in Fig. 1. To simplify notation, let E(χ; r) := Enc([χ] 1 ; r) ∈ G 2 1 be a transposed ciphertext. Let E(T (χ)) (resp., E(h(χ))) denote an element-wise (transposed) encryption of T (χ) (resp., h(χ)), where χ i is encrypted by using randomizer r i (that is, χ i is "replaced" by [ct i ] 1 ) and constants are encrypted by using the randomizer 0. We define [Γ (x)] 1 and [θ(x)] 1 as follows:

[Γ (x)]1 = (E(T (χ)) E(0 d×d ; I d )) ∈ G 2d×(2d-1) 2 , [θ(x)]1 = E(h(χ)) ∈ G 2d 2 . (4) Thus, [Γ ] 1 w * = [θ] 1 is an "encrypted" version of T (χ)w = h(χ)
, where [Γ ] 1 contains additional columns and w * contains additional rows (compared to w) to take into account the randomizers used to encrypt

χ i . Note that E(C(χ)) = E( P k χ k + Q; P k r k ).
Example 1. Let F (X) = (X -0)(X -1), and thus d = 2. Recall that then C(χ) = χ -1 0 χ-1 and thus

T (χ) = -1 χ-1 and h(χ) = ( χ 0 ). Since Enc([0] 1 ; 1) = [1, sk] 1 and Enc([0] 1 ; 0) = [0, 0] 1 , Eq. (4) results in [Γ ]1 = E(-1; 0) E(0; 1) E(0; 0) E(χ -1; r) E(0; 0) E(0; 1) =     0 1 0 -1 sk 0 ct1 0 1 ct2 -1 0 sk     1 ∈ G 4×3 1 , [θ]1 = ct 1 ct 2 0 0 1 . A variation of this [Γ , θ] 1 was given in [BBC + 13,CH20]. To motivate Theorem 2, note that w * 1 = w = -χ is a solution of T (χ)w * 1 = h(χ). Setting ŵ := (w * 2 w * 3 ) = r 1 -w * 1 = r 1 χ results in Γ w * -θ = (0 0 0 -χ(χ -1)) , which is equal to 0 4 iff χ ∈ {0, 1}. Theorem 2. L pk,F = L Γ ,θ .
Proof.

(1) Assume x = Enc(χ) ∈ L pk,F . By the first column dependence property of Definition 2, there exists w such that T (χ)w = h(χ), i.e., C(

= 0. To show that x ∈ L Γ ,θ , we need to construct w * such that θ = Γ w * . First, we set w * i ← w i for i ≤ d -1. This guarantees that Dec([θ] 1 ) = Dec([Γ ] 1 )w * . Next, we have to set the remaining coefficients of w * i so that also the randomizers in

(E(T ) E(0 d×d ; I d ))w * = E(h) match. Denoting ŵ = (w * d , . . . , w * 2d-1 ) , this is achieved by setting ŵ ← ( P k r k ) 1 -w . Really, then (E(T ) E(0 d×d ; I d ))w * -E(h(χ)) =E(C)( -1 w ) + E(0 d×d ; I d ) ŵ =E(C; P k r k )( -1 w ) + E(0 d ; ŵ) =E(0 d ; ( P k r k )( -1 w ) + ( P k r k ) 1 -w ) =E(0 d ; 0 d ) .
(2) Assume that x = Enc(χ) ∈ L Γ ,θ , and thus [θ] 1 ∈ colspace([Γ ] 1 ). Let w * be such that θ = Γ w * . After entry-wise decrypting, we get

Γ * = (T (χ) 0)w * = h(χ). Let w = (w * 1 , . . . , w * d ) . Hence, T (χ)w = h(χ), which means that C(χ)( -1 w ) = 0. If x ∈ L pk,F then det(C(χ)) = 0. Since -1 is non-zero, this is a contradiction.
In Appendix F.2, we will give two more (lengthy) examples to illustrate how w * is chosen. Handling Non-Principal Ideals. Assume I(A) has a generating set (F 1 , . . . , F τ ) for τ > 1, and that for each F i , we have constructed the language parameter Γ i , θ i . We can then construct the language parameter for L pk,A by using the well-known concatenation operation, setting Γ = On the Couteau-Hartmann Disjunction. In Appendix F.3, we describe the Couteau-Hartmann disjunction that results in Γ of size (3d -1) × (3d -2) and compare it to Eq. ( 4). For the sake of completeness, we also reprove the efficiency of the CHM NIZK from [CH20].

Efficiency of Set-Membership NIZKs: Comparisons

In Table 1 we give a concrete efficiency comparison in the case of set-membership. This is motivated by the fact that this is probably the most complex language for which [CH20] provides a concrete NIZK with which we can compare our results. Because of the still large dimensions of Γ , using the CHM Σ-protocol as in [CH20] for L Γ ,θ = L pk,F has quite a big overhead. Thus, the NIZK in Lemma 7 is quite a bit more efficient. However, it compares favorably to [CH20]. In the following lemma, we state its efficiency.

Lemma 8. Let F be a univariate degree-d polynomial and let C(X) be the abp path -based QDR of F from Section 6.1. Let [Γ ] 1 be constructed as in Eq. (4). Then, the CHM NIZK argument requires (5d -3)e 1 + 4de 2 from the prover, 7d -1 pairings from the verifier, and 4d -1 group elements.

Proof. In this proof, we use the notation of Lemma 4. Note that T Γ = {|(i, j)| : T ij = 0} + {|(i, j)| s.t. j > 1 : P kij = 0 for some k} + 2 • and T θ = {|(i, j)| : h ij = 0} + {|i| : P ki1 = 0 for some k}. For a general C, the efficiency estimate follows from Proposition 2 and the above formulas for T Γ and T θ . Hence, we only give concrete estimates for the case of univariate F .

The prover can compute [Γ (x)] 1 r in T Γ = 5d -3 exponentiations in G 1 , and

[d] 2 in 2n = 2 • 2d = 4d exponentiations in G 2 . The verifier executes T Γ = 5d -3 pairings to compute [Γ ] 1 • [d] 2 , T θ = 2 pairings to compute [θ(x)] 1 • [e] 2 , and n = 2d pairings to compute [a] 1 • [1] 2 , in total 7d -1 pairings.
Note that the computation of the language parameters Γ , θ induces some cost. However, this computation is usually done once in advance. It is also not expensive, both in the case of the new NIZK and the CHM NIZK [CH20] requiring one to compute [ξ i ] 1 for each root ξ i .

GL-SPHFs for Algebraic Sets

We give an example of GL-SPHFs (Gennaro-Lindell smooth projective hash functions, [GL03]) based on new lpar = (Γ , θ). We refer the reader to [CS02,BBC + 13,Ben16] for a formal definition of GL-SPHFs. Briefly, recall that an SPHF is defined for a language parameter lpar and associated language L lpar . A SPHF consists of an algorithm hashkg(lpar) to generate the private hashing key hk, an algorithm projkg(lpar, hk) to generate a public projection key hp from hk, and two different hashing algorithms: hash(lpar, hk, x) that constructs an hash H, given the input x and hk, and projhash(lpar, hp, x, w) that constructs a projection hash pH, given the input x and its witness w. It is required that (1) H = pH when x ∈ L lpar , and that (2) H looks random when x ∈ L lpar , given (lpar, hp, x).

In the GL-SPHFs [GL03], lpar and the projection key hp can depend on x, while in other types of SPHFs, x is only chosen after lpar and hp are fixed. In the "DVS-based" constructions of SPHFs of [BBC + 13], one starts with

[Γ ] 1 ∈ G n×t 1 and [θ] 1 ∈ G n
1 that may or may not depend on x = [Γ ] 1 w. One samples a random hk = α ←$ Z n p , and sets hp ← α [Γ ] 1 . For x = [Γ ] 1 w, one computes pH = projhash(lpar, hp, x, w) ← hp • w and H = hash(lpar, hk, x) ← hk • x.

For any A(I) for which the NIZK of Section 4 is efficient, one can also construct an efficient SPHF by constructing Γ and θ as in Eq. (4). In Appendix F.4, we will describe a GL-SPHF for the language of elliptic curve points.

On Falsifiability of CED

In the current paper, we significantly expand the class of languages for which the Couteau-Hartmann framework allows for the construction of efficient NIZKs. However, for many of these languages, the underlying variant of the CED assumption is not falsifiable in the sense of Naor [Nao03]. At first sight, even though the Couteau-Hartmann framework leads to particularly compact NIZKs, relying on a nonfalsifiable assumption seems to limit the interest of the result severely: if one is willing to rely on nonfalsifiable in the first place, then there are countless pairing-based SNARGs and SNARKs which will achieve much more compact proofs [Gro10,Lip12,GGPR13] (albeit the prover cost will be much higher in general).

Next, we discuss the falsifiability of the CED assumption. In Section 10.1, we study the falsifiable CED case, by clarifying for which languages there exist (algebraic) polynomial-time algorithms to check F (χ) = 0. In particular, we point out that for many examples of the current paper, the CED assumption is already falsifiable. After that, we concentrate on the cases when this is not so.

In Section 10.2, we show that despite their unfalsifiability, CED assumptions are fundamentally different in nature from knowledge-of-exponent assumptions (which underlie the security of existing SNARK candidates [Gro10,Lip12,GGPR13]). We will prove that CED assumptions are implied by a new but natural gap assumption [OP01] that KerMDH stays secure in G 2 even given a CDH oracle in G 1 .

In Section 10.3, we modify our NIZKs to make the CED assumption falsifiable by letting the prover additionally encrypt input elements in G 2 . If the polynomial F is quadratic, then the soundness reduction can use them to check whether the prover's inputs belong to the language or not, thus making CED falsifiable. Since each gate of an arithmetic circuit is a quadratic polynomial, one can construct a NIZK for arithmetic circuits under a falsifiable assumption. The reason why we do not start with this solution is the added cost. First, the additional elements make the argument longer. Second, as probably expected, one cannot use Elgamal but has to use the less efficient DLIN cryptosystem [BBS04].

Thus, if CED is falsifiable, then one can use an Elgamal-based solution. Otherwise, one has a securityefficiency tradeoff: one can either rely on a non-falsifiable gap-assumption or use a slightly less efficient DLIN-based falsifiable NIZK.

On Languages for Which CED Is Falsifiable

The CED assumption is falsifiable if there exists an efficient verification algorithm V f , such that given an arbitrary ciphertext tuple x = [ct 1 , . . . , ct ν ] 1 and an sk-dependent trapdoor T, V f (p, pk, x, T) can efficiently check whether Dec sk ([ct 1 , . . . , ct ν ] 1 ) ∈ L pk,F . As in the rest of the paper, we take T = sk. Thus, given a ciphertext tuple [ct] 1 , V f can use sk to decrypt it and obtain the plaintext

[χ] 1 . V f then forms the QDR [C(χ)] 1 from [χ] 1 . If F (χ) = 0 (that is, x ∈ L pk,F ), then [C(χ)] 1 has full rank.
Otherwise, it has rank < . Thus, if F (X) is such that it is possible to check efficiently whether F (χ) = 0, given [χ] 1 , we can construct an efficient falsifiability check V f . (Note that this approach is different from Couteau-Hartmann, who required T to be a matrix.)

First, if |A| = poly(λ), then V f just checks if [χ] 1 is equal to [a]
1 for any a ∈ A. Thus, the NIZK for the univariate case in Section 6.1 and the NIZK for boolean circuits in Section 8.1 rely on a falsifiable CED assumption. (This assumes that all polynomials have degree poly(λ), and the circuits are polynomialsize.) In general, the NIZK in the case of non-principal ideal, Section 8, is based on falsifiable CED iff A(I) has polynomial size.

The outliers are the cases of principal ideals of multivariate polynomials (since then |A(I)| can be exponential as in the set of points (X, Y ) on an elliptic curve) and some instances of non-principal ideals where |A(I)| is super-polynomial. In the latter case, we can clarify the situation further. Namely, given a generating set F 1 , . . . , F τ , by Bézout's theorem, A(I) has at most size deg 1). Thus, constant-size set-membership arguments in Section 8.2 or aCSPs for constant-size arithmetic circuits in Section 8.1 are based on falsifiable CED. However, range proofs and superconstant-size arithmetic circuits are based on non-falsifiable CED.

F i . Assuming each deg F i is poly(λ), deg F i is super-polynomial if τ = ω(
The super-polynomial size of A(I) does not mean that efficient V f does not exist. E.g., assume F j (X) = i (X i -s j ) for each j. The ideal F j , for a single j, has exponential size. However, given [χ] 1 , one can check if F j (χ) = 0 by checking if χ i = s j for some j. This can be generalized to the case F j is a product of affine multivariate polynomials a ik X k + b ik . Clearly, F (χ) = 0 iff one of its affine factors is equal to 0. So, V f can check if there exists an i such that

a ik [χ k ] 1 + b ik [1] 1 = [0] 1 .
Generalizing this, one can efficiently establish whether [C] 1 is full-rank if the Leibniz formula for the determinant, det(C) = σ∈Sn (sgn(σ) n i=1 C i,σi ), contains only one non-zero addend. On the other hand, since V f has only access to [χ] 1 , there is not much hope that the CED assumption is falsifiable if F is a product of irreducible polynomials, such that at least one of them has a total degree greater than one, unless we add some additional, carefully chosen, elements to the proof for this purpose. In the general case, this is not efficient, but the number of additional needed elements might not be prohibitive for some applications.

Finally, the falsifiability of CED depends only on the polynomial F and not on the specific C. One could find two different CED-matrices C i for F , such that the first one results in a more efficient NIZK argument, but the second one has a specific structure enabling one to construct efficient V f .

CED as a Gap Assumption

We show that CED follows from a new gap assumption, which states that given p ← Pgen(1 λ ), even if one finds some structural properties in G 1 that allows breaking CDH over this group, this does in general not guarantee an efficient algorithm for solving KerMDH [MRV16] over the other group G 2 . More formally:

Definition 3. Assume that the (exponential-time) oracle O([x, y] 1 ) outputs [xy] 1 . D -1,k -CDH G1 ⇒ KerMDH G2 holds relative to Pgen, if ∀ PPT A, Theorem 3. Let -1, k ∈ N. If the D k -CDH G1 ⇒KerMDH G2 assumption holds relative to Pgen, then D k -( -1)-CED holds in G 1 relative to Pgen.
Proof (of Theorem 3). Let A be an CED adversary, as in Definition 1, that succeeds with a non-negligible probability ε A . We construct the following CDH G1 ⇒KerMDH G2 adversary B.

B receives p ← Pgen(1 λ ) and [D] 2 ← D k , and feeds them to A. Assume A is successful. B obtains Note that in particular, this re-proves the result of [CH20] that CED is secure in the generic bilinear group model (since a CDH oracle in G 1 does not help to break any assumption in G 2 in the generic bilinear group model).

([γ C] 1 , [δ] 2 ) ← A(p, [D] 2 ), where γ ∈ Z ×k p , C ∈ Z × p , and δ ∈ Z ( -1)×k p . Write (γ C) = X L X R v L v R , where X R ∈ Z ( -1)×( -1) p and say v L ∈ Z 1×(k+1) p . Since A is successful, we get rk(C) ≥ and thus X R is invertible. Next, A's winning condition (γ C) D δ = 0 rewrites to X L • D + X R • δ = 0 , v L • D + v R • δ = 0 , which gives, when X R is invertible, D c = 0, where c ← (u L -u R • X -1 R • X L ) ∈ Z k+1 p .

DLIN-Based NIZK Based on Falsifiable CED

While constructing a Sub-ZK QA-NIZK, [ALSZ20] had to check efficiently if C is invertible, given only [C] 1 . We will next study whether we can apply their technique. It is not straightforward to apply it since their case is somewhat different: there, C is a k × k (in particular, k ∈ {1, 2}) public matrix sampled from D k and then given as a part of the CRS. In our case, C can have an arbitrary poly(λ) dimension, and it is reconstructed from the input to the NIZK argument.

To explain the technique of [ALSZ20], consider the case

[C] 1 ∈ G 2×2 1
.

[ALSZ20] added to the CRS certain additional elements in G 2 (namely, [C 11 , C 12 ] 2 ), such that it became possible to check publicly (by using pairings) whether det C = 0 by checking whether

[C 11 ] 1 •[1] 2 = [1] 1 •[C 11 ] 2 , [C 12 ] 1 •[1] 2 = [1] 1 •[C 12 ] 2 , and [C 22 ] 1 • [C 11 ] 2 = [C 21 ] 1 • [C 12 ] 2 .
One cost of publishing the additional elements in [ALSZ20] was that it changed the assumption they used from KerMDH to the less standard SKerMDH assumption [GHR15]. As we see next, we have to use the DLIN cryptosystem [BBS04] instead of the Elgamal cryptosystem. However, as a result, we will obtain a NIZK for any F , computable by a poly-size arithmetic circuit, sound under a falsifiable CED assumption. Another benefit of it is to demonstrate that our framework is not restricted to Elgamal encryptions.

Next, we show how to construct a NIZK, based on a falsifiable CED assumption, for the polynomial F (X, Y ) = X 2 -Y . We ask the prover to also encrypt X in G 2 . In the soundness reduction, a CEDadversary uses the latter, after decryption, to check whether

[X] 1 •[X] 2 = [Y ] 1 •[1] 2 . We must ensure that the verifier only accepts the proof if [X] 2 is correct, i.e., [X] 1 •[1] 2 = [1] 1 •[X] 2 .
Since Elgamal is not secure given symmetric pairings, we cannot use the secret key or the same randomness in both groups. Hence, we use the DLIN encryption scheme (see Appendix A.2 for its definition). Given sk = (sk 1 , sk 2 ) and

pk ι = [1, sk 1 , sk 2 ] ι , we define lpar := (pk 1 , pk 2 , F ). Then, L lpar := {([ct 1 , ct 2 ] 1 , [ct 1 ] 2 )}, where [ct 1 ] ι = Enc ι (X; r 1 , r 2 ) = [r 1 sk 1 , r 2 sk 2 , X + r 1 + r 2 ] ι and [ct 2 ] 1 = Enc 1 (Y ; r 3 , r 4 ) = [r 3 sk 1 , r 4 sk 2 , Y + r 3 + r 4 ] 1 . We prove that [ct 1 , ct 2 ] 1 are encryptions of X and Y such that X 2 = Y , by using the QDR C(X, Y ) = X -1 -Y X .
The use of the DLIN encryption scheme just affects the efficiency and the communication size of the protocol. In addition, one can check that [ct 1 ] 1 and [ct 1 ] 2 encrypt the same X in two different groups by checking that

[ct 1 ] 1 • [1] 2 = [1] 1 • [ct 1 ] 2 .
Since the DLIN encryption is doubly-homomorphic like Elgamal, then the argument of Section 4.1 stays essentially the same, with Elgamal encryptions replaced by DLIN encryptions, and the dimensions of randomizers and ciphertexts increasing slightly. In the soundness proof, given that the prover also outputs Enc 2 (X; r 1 , r 2 ), the constructed CED adversary obtains plaintexts [X, Y ] 1 , [Z] 2 and, then can efficiently verify if the statement X 2 = Y holds.

Combining this idea with the rest of our framework, we can construct a NIZK for any language of DLIN-encryptions for any F , based on a falsifiable CED assumption. This is since one can check that F = 0 by checking that an arithmetic circuit evaluates to 0, and each gate of an arithmetic circuit evaluates a quadratic function. For example, to prove that Y 2 = X 3 + aX + b, one can encrypt Y , Y , X, X , and X , and then prove that Y = Y 2 , X = X 2 , X = XX , and Y = X + aX + b. Acknowledgment. Geoffroy Couteau was partially supported by the ANR SCENE.

Table 3. The efficiency of new NIZK arguments for L {0,1} . The communication is given as (g1, g2, z), where gι is the number of Gι elements (ι = 1 in the Σ-protocols) and z is the number of Zp elements. The computation is given as (e1, e2, p), where eι is the number of exponentiations in Gι and p is the number of pairings. Proof. Let A be an adversary that breaks D k -( -1)-CED with probability ε. We construct the following adversary B that breaks D k -( -1)-ExtKerMDH:

Scheme |crs| |π|

P comp V comp Assumpt. Π ∨ simple , Π ∨ cg , Π ∨ cds (0, 1, 0) (4,
B(p, [D] ι ) ([γ C]3-ι, [δ]ι) ← A(p, [D]ι); return ([γ C]3-ι, [δ]ι);
If A succeeds, then by Definition 1, (γ C) D δ = 0 and rk(γ) ≥ . However, if rk(γ) ≥ then also clearly rk(γ C) ≥ . Thus, B succeeds with probability ≥ ε.

B More on Section 3

B.1 Determinantal Representations

The following problem is well-studied in algebraic geometry, [Har92,Dol10]. Given a homogeneous polynomial f (X 0 , . . . , X n ) of degree-d find a d × d matrix C(X) = (L ij (X)) with affine maps as its entries such that f (X) = det(L ij (X)) .

The resulting equation det(C(X)) = F (X) is known as F 's determinantal representation.

More generally, one considers × matrices C(X) with the same property. In this case, the determinantal complexity dc(F ) of the polynomial F is the minimal size of any determinantal representation of F . Clearly, dc(F ) ≥ deg(F ).

All plane curves and cubic surfaces have determinantal complexity equal to their degree, [Dic21]. Dickson [Dic21] also proved a general theorem about the impossibility of determinantal representations of size deg(F ) for general polynomials F . See [Dic21,Bea00] for more information. Moreover, efficient algorithms for finding determinantal representations, if they exist, have only been proposed lately [PSV12]; see also Section 8.

QDRs, as defined in Definition 2, additionally have the first column dependence property, which is not required for determinantal representations. Not every determinantal relation is a QDR (see Section 7 for some examples) and thus it is plausible that in general, qdc(F ) > dc(F ).

C More on Section 6

C.1 On OR Proofs Π ∨ simple and Π ∨ cg . The NIZK argument Π ∨ simple (see Fig. 7) for L {0,1} follows from the approach in Section 6.1, by using abp 2 path . On the other hand, Π ∨ cg (see Fig. 7) follows from the approach in Section 6.1, given the ABP in Fig. 6 (right). It is based roughly on the Chaidos-Groth Σ-protocol from [CG15], which itself is based on checking whether X • X = X. We depict the ABPs and corresponding matrices IK(X) in in Fig. 6. The correctness of both arguments follows from the fact that the solution of T (χ)w = h(χ) is w = -χ. (5, 5) 13 (4, 3) d = 3

(5.05, 5.05) 12.62 (3.79, 3.15)

A N = {x : 0 ≤ x ≤ N } results in an inefficient NIZK argument, since GS(A N ) = { N i=0 (x -i)} contains a polynomial F of linear-in-N degree N +1. (Since F is univariate, one can use the solution of Section 6.1 in this case.)

One can instead use a different generating set of smaller-degree polynomials. Assuming N = 2 η -1, a well-known idea in range proofs is to extend x to binary digits x i , and to prove separately that each x i is Boolean. In the case N + 1 is not a power of two, one can use an idea from [LAN03]. Namely, let b j := (N + 2 j )/2 j+1 , where j ∈ [0, η]. Then, χ ∈ [0, N ] iff χ = η j=0 b j χ j for some χ j ∈ {0, 1} [LAN03].

To translate this idea to our framework, we introduce additional indeterminates and write A N = {(x, x 0 , . . . , x η ) : x = η j=0 b j x j ∧ (b j ∈ {0, 1} for all j)}. Note that in the terms of algebraic geometry, A N is a variety in the affine space Z η+2 p , such that A N is its projection to the affine space Z p . Clearly, GB(A N ) = {X 2 η -X η , . . . , X 2 0 -X 0 , X -η j=0 b j X j } is a (lexicographic) Gröbner basis for A N that consists of one linear and η quadratic polynomials. Thus, the resulting NIZK argument has communication complexity Θ(η) = Θ(log N ). A similar trick is useful in also other settings.

We can base range proofs on d-ary digits, for d ≥ 2, using an ABP-based univariate NIZK to show that each X j ∈ {0, . . . , d -1}. One has to execute log d N basic NIZK proofs. The resulting range proof has complexities depicted in Table 4. (The complexities are such due to the fact that in this case, all values χ -ξ i are small.) In particular, the verifier's computation (which is the most important measure in many applications) is minimized when d = 3.

As in the case of the multi-dimensional set-membership proof, an alternative is to use signature-based solutions [RKP09,DGP + 19] that offer somewhat better proof size Θ(N/ log N )(|G 1 | + |G 2 |). However, also here these solutions have a longer CRS size and require that the underlying signature scheme is unforgeable. We leave it as an open question how to combine the protocols of the current paper with signatures. as+XY /(sY + X 2 ) if sY + X 2 = 0 .

D More on

Since Y 2 = X 3 + aX + b, one can use formulas like X 3 + b = Y 2 -aX to modify the expressions. In particular, the three given expressions for w are equivalent if the three denominators sX + Y = -det(C (1,1) ), sY + X 2 = -det(C (2,1) ), and aX + b = a det(C (3,1) ) are all non-zero. Solving F (X, Y ) = 0 and det(C (i,1) ) = 0 gives that the ith expression for w holds except in either 3, 4, or 2 points. Since there is only one point (X, Y ) = (-b/a, bs/a) where all F (X, Y ) = 0 and det(C (i,1) ) = 0 hold, it means one can compute w in all but a single point.

Thus, we can construct a NIZK argument, with = 3, assuming that there exists a square root of -b/a modulo p. Moreover, it cannot be applied in the special case (X, Y ) = (-b/a, bs/a). Thus, strictly speaking, the resulting NIZK is not for L pk,F but for a different language, and this outlines the need of QDRs. However, the resulting argument could be still interesting in the case when in the honest case, (X, Y ) has some restrictions.

D.2 Elliptic Curve Points

, Case F (X, Y ) = X 3 + b -Y 2
Consider the following less common normal form for an elliptic curve, F (X, Y ) = (X + aY )(X + bY )(X + cY ) -X, for mutually different a, b, c; w.l.o.g., let b = 0. By inspection, we found the following matrix:

C (X, Y ) = X 0 -1 Y +s X+s 1 -sX+Y +s 2 Y X
, where s = b 1/3 (assuming b has a cubic root). Then,

w ←          Y /(s+X)+1 -X if s + X = 0 , (s 2 -sX+X 2 +Y )/Y -X if Y = 0 , -s 2 +2sX+(X-1)Y -sX 2 +b+Y (X-Y ) /(X(s + X) -Y ) if X(s + X) -Y = 0 .
None of these formulas succeeds if all F (X, Y ) = s + X = Y = X(s + X) -Y = 0, which can only happen if (X, Y ) = (-s, 0).

D.3 Fifth-Degree Example

Next, we give a fifth-degree example directly from [PSV12]:

F (X, Y ) =X 5 + 3X 4 Y -2X 4 -5X 3 Y 2 -12X 3 -15X 2 Y 3 + 10X 2 Y 2 -28X 2 Y + 14X 2 + 4XY 4 -6XY 2 -12XY + 26X + 12Y 5 -8Y 4 -32Y 3 + 16Y 2 + 48Y -24 ,
and

C(X, Y ) =   X+Y 0 0 0 0 0 X+2Y 0 0 0 0 0 X-Y 0 0 0 0 0 X-2Y 0 0 0 0 0 X+3Y -2   +
0 2 1 0 0 2 0 0 0 1 1 0 0 2 1 0 0 2 0 -1 0 1 1 -1 0 .

As noted in [PSV12], this is just one of 33280 possible solutions for the latter (integer) matrix. In this case, one can write 5 different formulas for χ 1 , depending on which submatrix C (I,1) (X, Y ) has a nonzero determinant. One can check that there are four points for which all these submatrices have a zero determinant.

Note that there is no obvious small-dimensional ABP-based solution in this case.

E More on Section 8

E.1 Another Multi-Dimensional Set-Membership Proof

To demonstrate that one does not always need a set-membership proof of the worst-case size, we will next work out an example for the following set A = {(2, 1, 2), (1, 4, 2), (3, 1, 3), (1, 2, 3)} ⊂ Z 3 p . By using CoCoA, we found the following lexicographic Gröbner basis GB lex (I) = (z -3)(z -2), (y -1)(y + 2z -8), x + 1 3 (5y -8)z -3y + 3 of size 3. (The corresponding degreelexicographic and degree-reverse-lexicographic Gröbner bases have size 6.) By following our methodology, to show that χ ∈ A, we show that F i (χ) = 0 for each F i ∈ GB lex (I). More precisely:

F.2 More Examples

To simplify parsing, we have omitted the use of bracket notation in examples, writing say 0 instead of [0] 1 .

Example 2. Let F (X) = 4 i=1 (X -ξ i ). Then In this case, w 1 = -(χ -ξ 1 ), w 2 = -(χ -ξ 1 )(χ -ξ 2 ), w 3 = -(χ -ξ 1 )(χ -ξ 2 )(χ -ξ 3 ), and ŵ = r 1 -w = r(1 χ -ξ 1 (χ -ξ 1 )(χ -ξ 2 ) (χ -ξ 1 )(χ -ξ 2 )(χ -ξ 3 )).

Example 3 (Elliptic curve.). Let F (X, Y ) = X 3 + aX + b -Y 2 and C(X, Y ) = X -1 0 0 0 X -1 0 Y 0 0 -1 b a X -Y be as in Fig. 5. Then for [ct 1 ] 1 = Enc(χ 1 ; r 1 ) and [ct 2 ] 1 = Enc(χ 2 ; r 2 ),

Fig. 1 .

 1 Fig. 1. comp i algorithms assuming h(χ) ∈ colspace(T (χ)). Here, ψ = id in the case of the Σ-protocol, and ψ = [•]2 in the case of the NIZK argument.

Lemma 4 .

 4 Consider Π nizk with QDR C. Define T P (C) := |{(i, j) : ∃k, P kij = 0}|, and T Q (C) := |{(i, j) : Q ij = 0}|. Let c be the time needed to run comp, e ι is the time of an exponentiation in G ι , and p is the time of a pairing. Then (1) the prover's computation is dominated by c + 2 • e 1 + 2 • e 2 , (2) the verifier's computation is dominated by (

  L 1 -( -1)-CED adversary B. (See Definition 1 for the definition of CED.) The CED challenger creates p ← Pgen(1 λ ), [D] 2 = [ 1 e ] 2 ←$ L 1 and sends (p, [D] 2 ) to B. B runs (crs, td) ← K crs (p). B runs the setup algorithm of Elgamal to compute a random secret key sk and public key pk from the correct distribution. B fixes any F such that lpar = (pk, F ) ∈ Supp(D p ), and sends crs = [e] 2 and lpar to A. Let C be a fixed poly(λ)-size QDR of F .

  be the neighbourhood of a node v in the underlying ABP. Assuming C(X) = IK(X), the computational complexity of comp is dominated by 2(|E| -|N (s)|) -|N (t)| field multiplications, exponentiations in G 1 , and 2( -1) exponentiations in G 2 . Proof. Clearly, computing γ requires at most |E|-|N (s)| field multiplications, and computing w requires at most |E| -|N (s)| -|N (t)| field multiplications. Finally, in the case of the NIZK argument, computing [γ] 1 requires exponentiations in G 1 , and computing [δ] 2 requires 2( -1) exponentations in G 2 . 6 Applications 6.1 Univariate F (Set-Membership Proof )

Fig. 4 .

 4 Fig. 4. The NIZK argument for L pk,F , where F (X) is a monic univariate polynomial with qdc(F ) = d.

  [GSW09]. Here, m is the number of wires and n is the number of gates. In the case of the AES circuit described in [GSW09], m = 33880 and n = 34136. Assuming |G 2 | = 2|G 1 | and e 2 = 2e 1 , we get that the NIZK of [GSW09] has commitment length 203283|G 1 |, argument length 814662|G 1 |, prover's computation 1629324e 1 , and verifier's computation 1630336p. The new NIZK has commitment length 67760|G 1 |, argument length 680160|G 1 |, and prover's computation 884208e 1 , and verifier's computation 884208p. Hence, the new NIZK has 3 times shorter commitments, 20% shorter arguments, and 1.84 times smaller prover's and verifier's computation.

  Since 12 rk(C) ≥ , we get c = 0. Using Gaussian elimination, one can compute c by an arithmetic circuit over Z p . Thus, B can compute [c] 1 from [γ C] 1 with the help of O that allows it to multiply exponents over G 1 . B returns [c] 1 to the challenger. Clearly, B breaks KerMDH with probability ε A .

  on CED and ExtKerMDH Lemma 9. Let , k, and D k be as in Definition 1. If D k -( -1)-ExtKerMDH holds, then D k -( -1)-CED holds.

  Section 7 D.1 Elliptic Curve Points, Case F (X, Y ) = X 3 + aX + b -Y 2 for a = 0By inspection, we found the following 3 × 3 matrix, where 13 s = -b/a: C(X, Y ) = F (X, Y ). However, C is not a QDR. We will explain next what does it mean in the concrete case.Solving Eq. (2) together with F (X, Y ) = 0 gives us the following formulas to replace into Fig.1depending on which minor of C is non-zero: -sX) /(aX + b) if b + aX = 0 ,

  -SPHF for Elliptic Curve PointsLet A = {(X, Y ) : Y 2 = X 3 +aX +b} as in Section 6.3. Then, one can use lpar= (Γ , θ) from Example 3 to define hk ←$ Z 8 p , hp ← α [Γ ] 1 = α 3 ct 11 + α 4 ct 12 + aα 8 -α 2 , α 7 ct 11 + α 8 ct 12 -α 4 , -α 7 ct 21 -α 8 ct 22 -α 6 , α 1 + α 2 sk, α 3 + α 4 sk, α 5 + α 6 sk, α 7 + α 8 sk ,and, in the casex ∈ L lpar , pH = H = [α Γ w] 1 =    χ1 (-α3ct11 -aα8 + α4χ1 + α2) -χ1 (α7χ1ct11 + ct12 (α8χ1 + α4)) + χ2 (α7ct21 + α8ct22 + α6) + r1 (α1 + χ1 (α3 + χ1 (α7 + α8sk) + α4sk) + α2sk) +r2 (α5 -χ2 (α7 + α8sk) + α6sk)

Table 1 .

 1 Comparison of set-membership proofs, i..e., NIZKs for L pk,F , where F (X) is univariate, as in Lemmas 7, 8 and 10. The verifier's computation is given in pairings. The Groth-Sahai computation figures are not published and based on our own estimation; hence, we have omitted the computation cost. Note that |G2| = 2|G1| in common settings. In CHM and new NIZK, |crs| = |G2|.

	Argument

Table 2 .

 2 Comparison of falsifiable NIZKs for Boolean circuit satisfiability: the Groth-Sahai proof, as optimized by Ghadafi et al. [GSW09], and the new NIZK from Section 8.1. Here, |Gι| is the length of one element from Gι

	Protocol	|crs|	|com|	|π|	P comp.

Table 4 .

 4 Complexities in the range proof. Every entry should be multiplied by log 2 N . P comp in (e 1 , e 2 ) V comp in p Comm. in (|G 1 |, |G 2 |)

	General	( 3d-1 log 2 d , 3d-1 log 2 d )	7d-1 log 2 d	( 2d log 2 d , (2d-1) log 2 d )
	d = 2 (also [CH20])

The classical approach to do so for circuit satisfiability uses algebraic commitments to all values on the wire of the circuit; then the statement "all committed values are consistent and the output is 1" is an algebraic language.

While we can always embed any language in an algebraic language, this can be inefficient; the CH proof system is efficient when the language is "natively" algebraic.

NIZKs for this type of languages have recently found important applications in blockchain applications, such as the zcash cryptocurrency, see [KZM+ 15] and https://z.cash/technology/jubjub/.

That is, for every j ∈ [1, τ ] there exist i1, . . . , iq ∈ [1, n] and f : F q → F such that ∀χ ∈ F n , Fj(χ) = f (χi 1 , . . . , χi q ). Then F is satisfiable if ∀j, Fj(χ) = 0.

Technically, one could always take aCSPs, write them as a circuit satisfiability problem, and embed that into an agebraic language to capture it with the Couteau-Hartmann framework; the point of our framework is that, by capturing this powerful model directly, we can obtain much better efficiency on aCSPs.

There are ample examples of sets A that have small generating sets (and even small Gröbner bases), which can be found using a variety of standard tricks and methods (e.g. increasing the dimension of the affine space from some F n to F n , n > n, such that the new n -n "helper variables" make it possible to construct a small Gröbner basis that consists of only small-degree polynomials). We will use such tricks in some of our illustrations and applications.

http://cocoa.dima.unige.it/

In the case of many other sets, the NIZK will be much more efficient. We will provide one concrete example in Appendix E.1.

Pr p ← Pgen(1 λ ); D ←$ D -1,k ; [c]3-ι ← A O (p, [D]ι) : D c = 0 k ∧ c = 0 -1 ≈ λ 0 .

Note that this is the point where we need to use CED instead of ExtKerMDH since we cannot deduce c = 0 from rk(γ C) ≥ .

Hence, this assumes that there exists a square root of -b/a modulo p, i.e., that there exists c such that ac 2 = -b, which is true for (p + 1)/2 values of b. If b is not one of those values, one can by inspection find a different matrix. Alternatively, one can use the ABP-based solution from Section 6.3.

A More on Section 2

A.1 Matrix Assumptions

The following assumptions are, while relatively recently formalized, very standard. In particular, MDDH generalizes DDH and KerMDH generalizes CDH. See [EHK + 13,GHR15,MRV16] for more discussion.

Let ι ∈ {1, 2}. D ,k -MDDH Gι (Matrix Decisional Diffie-Hellman, [EHK + 13]) holds relative to Pgen, if ∀ PPT A, Adv mddh A,Pgen,Gι,D ,k (λ

According to Lemma 4 of [MRV16], in a bilinear group, if D ,k -MDDH holds then also D ,k -KerMDH holds. According to Lemma 1 of [GHR15], if D ,k -KerMDH holds in generic symmetric bilinear groups then D ,k -SKerMDH holds in generic asymmetric bilinear groups.

A.2 DLIN Encryption

The DLIN cryptosystem [BBS04] is less efficient, with the ciphertext consisting of 3 group elements instead of 2. However, the DLIN cryptosystem remains secure in the case of symmetric pairings. Its IND-CPA security is based on

Fig. 6. The matrices for the ABP-based simple (ABP abp 2 path (X, {0, 1}), left) and the ABP-based Chaidos-Groth (right) argument for f (X) = X 2 -X = X(X -1) and the corresponding matrices.

kgen(p, lpar): e ←$ Z p ; return (crs, td) ← ([e] 2 , e) ; P(crs, lpar, x, w): As seen from Fig. 7, in both Π ∨ simple and Π ∨ cg , the prover's computation is dominated by

The verifier's computation is dominated by 13 pairings. In the case of Π ∨ simple , this follows from

From the outset, the famous Cramer-Damgård-Schoenmakers (CDS) Σ-protocol from [CDS94] looks quite different. The idea behind CDS is that to prove that χ ∈ {0, 1}, one follows the prover's algorithm in the true branch (resulting in transcript (a χ , e χ , z χ )) and the simulator's algorithm in the other branch (resulting in transcript (a 3-χ , e 3-χ , z 3-χ )). To make sure that at least one branch is correctly computed, the prover chooses e i such that e 1 + e 2 = e, where e is the verifier's second message. Couteau and Hartmann [CH20] described a CH-compilation of the CDS protocol.

Somewhat unexpectedly, one can use our generic framework also here, by defining the QDR C cds (X) = 0 X X-1 1-X . However, C cds (X) does not belong to the class of matrices considered by Ishai and Kushilevitz, [IK00,IK02] and thus not correspond to an ABP.

In Fig. 7, we also depict the new NIZK argument Π ∨ cds that applies Figs. 1 and 2 to C cds (X). The property of CDS that the simulated branch depends on χ carries over since one samples γ 2-χ ←$ Z p and sets γ 1-χ ← 0; i.e., the index i of the non-random γ i depends on χ. Intuitively, the prover simulates the branch 2 -χ. The reason behind it is that det(

As a small optimization, [z] 2 can computed as follows: (1)

In both cases, the prover spends 3 exponentiations in G 2 . Thus, the prover's computation is dominated by 5e 1 + 4e 2 .

To see the verifier accepts note that here

δ-e 2 can be computed in 5 pairings. In total, the verifier executes 13 pairings.

C.2 Range Proof

The following example both has a long cryptographic pedigree and can be used to simply explain how to expand our framework. In a range proof, the task is to prove that the encrypted value belongs to a fixed range [0, N ]. Many range proofs have been proposed in the cryptographic literature, [Bou00,LAN03,Lip03,CCs08,RKP09,CLs10,CLZ12,DGP + 19], due to their many applications and non-trivial constructions. It is possible that the Couteau-Hartmann compilation works directly with some of the existing Σ-protocol-based range proofs like [LAN03]. We will next show how to use our framework to obtain a proof with Θ(log N ) communication. Write η = log 2 N . In this case, just setting -We show that (z -3)(z -2) = 0, by using

3x-8z+9 5z-9 . Thus, one needs 3 NIZK arguments for quadratic polynomials ( = 2). By Lemma 4, the NIZK argument for A has thus communication of 3

As in all examples in Section 8.2, we used Gröbner-basis techniques to find a small aPCS for A. Clearly, any arithmetic circuit for checking that χ ∈ A has size larger than 3. In particular, in this concrete case, it seems that one needs to use the full power of aPCS.

An alternative generating set, that is not a Gröbner basis, is GS(I) = {(x-1)(y -1), (x-3)(y -2)(z -2), (x -2)(y -4)(z -3)} of size 3. While GS is tidier, the argument for GS(A) is slightly less efficient since two of the polynomials are cubic. Thus, here, one can construct three QDRs of size 2, 3, and 3. The resulting NIZK has communication of

F More on Section 9

F.1 CHM NIZK

We describe the CHM (Couteau-Hartmann-Maurer) Σ-protocol and the resulting NIZK, see Fig. 8. For further reference, we state the following results. We refer to Appendix A and [CH20] for unexplained notions and notation.

Proposition 2 (Efficiency of the CHM Σ-Protocol and CH Compilation).

In the CHM Σ-protocol, the prover executes T γ ≤ nt exponentiations and the verifier executes T Γ + T θ + n ≤ nt + n exponentiations; the communication is n group elements and t + 1 integers. In the compiled protocol, the prover executes T γ ≤ nt exponentiations in G 1 and 2n exponentiations in G 2 , and the verifier executes

Proposition 3 (Couteau-Hartmann). Consider the NIZK argument Π C Σ , described in Fig. 8, for any algebraic language distribution D lpar outputting pairs lpar = [Γ , θ] 1 ∈ P n×t ν × P n ν . 1. It is sound under the L 1 -t-CED assumption in G 2 relative to Pgen. 2. If the language distribution is witness-sampleable with trapdoors T lpar ∈ Z n×n p , then Π C Σ is sound under the falsifiable L 1 -t-CED assumption in G 2 relative to Pgen.

If the language distribution is

.

Clearly,

where ( * ) holds iff F (χ) = 0.

F.3 CHM NIZK based on Couteau-Hartmann Disjunction

On the Couteau-Hartmann Disjunction. In Appendix F.3, we describe the Couteau-Hartmann disjunction that results in Γ of size (3d -1) × (3d -2) and compare it to Eq. ( 4).

In Appendix C of [CH20], the authors describe a method of constructing the parameters [Γ ] 1 and [θ] 1 of L Γ ,θ for the disjunction of two algebraic languages L Γ i,θi , i ∈ {0, 1}. That is, x ∈ L Γ ,θ iff L Γ i,θi for at least one i. Briefly, they define

Thus, a disjunction from matrices

In the honest case, a valid witness is either (w 0 , -1, 0, 0) or (0, 0, w 1 , -1) , where w i is a valid witness corresponding to the ith disjunct.

We will demonstrate how it differs from our parametrization for the two examples given above. First, when F (X) = X -ξ and thus

, with w = r. Applying the disjunction of Eq. ( 6) to it for two different values of ξ i and ciphertexts [ct i ] 1 , i ∈ {1, 2}, we get (omitting the bracket notation)

, with w = (r 1 , -1, 0, 0) or w = (0, 0, r 2 , -1) . This should be compared with 4×3 matrix Γ of [BBC + 13] (see also Example 1). Going one step forward, for d = 4, the Couteau-Hartmann disjunction results in a matrix of size (2 • 5 + 1) × (2 • 4 + 2) = 11 × 10, which should compared with the matrix Γ of Example 2 that has size 8 × 7. In the general case d = 2 c for some c ≥ 1, the resulting matrix has dimensions (3d -1) × (3d -2) .

As noted before, the new solution results in matrices of size 2d × (2d -1).

Efficiency. For the sake of completeness, we reprove the following lemma, also given in [CH20]. Note that cw has zero elements which means that the computation of [d] 2 by the prover is more efficient than by the general result Proposition 2.

Lemma 10. Let d = 2 c , and assume in recursion Γ 0 and Γ 1 always have equal dimensions. The CH compiled NIZK argument, as in Fig. 8, corresponding to Γ of this subsection as in Eq. (6), requires (7d -4)e 1 + (3d -1)e 2 from the prover, (9d -2)p from the verifier, and the communication is On top of this, the prover computes [d] 2 ← [e] 2 w + r[1] 2 . If d = 1 then this can be executed in 2 exponentiations. At each recursion step, w will still have one non-small element and r will have dimension 3d -2. Thus, this takes 1 + (3d -2) = 3d -1 exponentiations in G 2 .

Verifier's computation. Since Γ has 6d -2 non-zero elements, the verifier has to execute 6d -2 pairings to compute