Alonso González

Carla Ràfols

Shorter Pairing-based Arguments under Standard Assumptions

HAL is

Introduction

This paper deals with the problem of constructing non-interactive publicly verifiable arguments of knowledge under falsifiable assumptions to prove that a circuit φ is correctly evaluated in two different settings.

In one such possible setting, all of the input of the circuit φ is known. In this case, the argument does not need to be zero-knowledge and can leak partial information. This is the typical situation in verifiable computation in which a resource-limited device delegates a costly computation to a more powerful machine.

Another important setting requires the input and output to be partially or totally hidden and the argument to be zero-knowledge. This is interesting from a theoretical perspective as CircuitSat is usually taken to be the standard NP complete problem. On the practical side, often the best way to prove a large, complicated statement in zero-knowledge is to encode it as a circuit and prove that it is satisfiable. Further, CircuitSat is considered a sort of benchmark to evaluate the efficiency of zero-knowledge proofs.

Succinct Non-Interactive Arguments of Knowledge or SNARKs in bilinear groups have been a phenomenal success in both of these scenarios [START_REF] Groth | Short pairing-based non-interactive zero-knowledge arguments[END_REF][START_REF] Lipmaa | Progression-free sets and sublinear pairing-based non-interactive zeroknowledge arguments[END_REF]8,[START_REF] Danezis | Square span programs with applications to succinct NIZK arguments[END_REF]16]. These arguments are succinct, more specifically, they are constant size, that is, not dependent on the circuit size, and extremely efficient also concretely (3 group elements in the best constructions [16]). They are also very fast to verify, which is a very interesting feature in practice, as in many scenarios verification is performed many times. However, these constructions still suffer from some problems, like long trusted parameters, heavy computation for the prover and reliance on non-falsifiable computational assumptions. Further, it is a well-known fact that the latter is unavoidable for succinct arguments in the non-interactive setting [11].

Non-falsifiable assumptions offer great efficiency at the price of less understood security guarantees. The problem is that it is not possible to efficiently check if the adversary effectively breaks the assumption, which results in nonexplicit security reductions [START_REF] Naor | On cryptographic assumptions and challenges (invited talk)[END_REF] which inherently do not allow to choose concrete security parameters meaningfully. Therefore, it is interesting to construct arguments with properties similar to SNARKs (short proof size, fast verification) for correct circuit evaluation that avoid falsifiable assumptions.

When the input of the circuit is public, SNARKs can be used to prove that the circuit is correctly evaluated while avoiding falsifiable assumptions. Indeed, since it is possible to check if a prover breaks soundness (as the input is public), the tautological assumption "the scheme is sound" is already falsifiable. For the case where at least some part of the input is secret, the same trivial solution can be used if the prover additionally commits to the input with some commitment which is extractable under falsifiable assumptions. 3 However, these trivial solutions require circuit dependent assumptions.

The goal of this paper is to design efficient constructions both in terms of proof size and verification complexity from milder (falsifiable, circuit independent) assumptions.

Our Results

We construct an argument for proving that an arithmetic circuit φ : Z n p → Z n p is correctly evaluated. We give two instantiations, the first one with proof size (3d + 2)G 1 + (d + 2)G 2 group elements and where verification requires 4d + 6 parings and O(n + n + d) exponentiations, for d the depth of the circuit. We give a less efficient scheme where both proof size and verification cost are approximately the double of the first construction, more concretely, the proof size is (6d + 3)G 1 + (2d + 3)G 2 group elements and the verification requires 8d + 9 pairings.

For the first construction, we need to rely on the knowledge soundness of QA-NIZK arguments of membership in linear spaces, which has only been proven in the generic group model [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF]. The second argument is fully based on falsifiable assumptions. The first one is an assumption that falls into the Matrix Decisional Diffie-Hellman assumption framework of Escala et al. [4] extended in asymmetric groups, where the challenge matrix is given in both groups. The size of the matrix depends on q, for q being the maximum number of multiplicative gates with the same multiplicative depth in the circuit. The second assumption is also a q-type assumption and similar to the q-SFrac Assumption of [12].

For boolean circuits, the argument can be made zero-knowledge and the resulting proof has size O((n -n pub ) + d), where n pub is the number of public inputs, while verification remains the same.

Our Techniques

Circuit Satisfiability can be represented as a set of quadratic and linear equations. It would seem that it suffices to find aggregated proofs of satisfiability of these equations to get sublinear proofs in the number of wires circuit wires. For instance, a natural strategy would be to commit to wires with shrinking commitments and use any constant-size QA-NIZK argument of membership in linear spaces (e.g. [26]) to give an aggregated proof that the affine constraints hold and use "aggregated" variants of GS Proofs [19] such as [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF][START_REF] Daza | Shorter quadratic QA-NIZK proofs[END_REF] for the quadratic constraints.

The reason why this approach fails is that when using shrinking commitments it is unclear what are the guarantees provided by QA-NIZK arguments since they are not proofs of knowledge (w.r.t. general PPT adversaries and not generic ones). Similarly, the arguments for quadratic equations are commit-and-prove schemes which require binding commitments to the solution of the equation. Knowledge Transfer Arguments. Our solution is to divide the set of constraints into d sets of quadratic and affine constraints, one per multiplicative level of the circuit. Namely, if φ : Z n p → Z n p is an arithmetic circuit of depth d, we express correct evaluation at level i as the following system:

-(quadratic constraints) c ij = a ij b ij for j = 1, . . . , n i . -(affine constraints) a ij , b ij are affine combinations of output wires of previous levels, that is a ij , b ij , c ij represent
, respectively, the left, right and output of the jth gate at level i. Our technical innovation is to eliminate the need for binding commitments to the wires at all levels of the circuit by "transferring" knowledge of the input to lower levels. More specifically, given adversarially chosen shrinking commitments L i (resp. R i , O i ) to all the left (resp. right, output) wires at level i, we first give a constantsize argument with constant-time verification which proves:

If (a i , b i , L i , R i , O i ) is such that L i , R i open to a i , b i then O i opens to c i = a i • b i .
We think of this building block as a "quadratic knowledge transfer argument", as it shows that if an adversary knows an opening for left and right wires, it also knows an opening of the output wires at the next level. This property is formalized as a promise problem because the verifier of the argument never checks that L i , R i open to a i , b i (otherwise the verification of the argument would be linear in the witness). Using a quadratic arithmetic program encoding [8] of the quadratic constraints we prove soundness under a certain q-assumption.

With this building block, the problem of constructing the argument is reduced to arguing that left and right wires are correctly assigned, i.e. proving that affine constraints are satisfied. We build a "linear knowledge transfer" argument with constant proof size and verification time showing that:

Given an opening of the commitments to the output wires O 1 , . . . , O i which is consistent with L 1 , . . . , L i and R 1 , . . . , R i then it is also consistent with L i+1 and R i+1 .

Correct evaluation of the circuit can be easily proven by combining these two building blocks. Since the input of the circuit is public and the shrinking commitments we use are deterministic, a consistent assignment O 1 , L 1 , R 1 , . . . , O d , L d , R d of the circuit wires is known by the reduction in the proof of soundness. A successful soundness adversary must output another assignment which disagrees with it starting from some level i. If the adversary outputs as part of its proof

L 1 , . . . , L i , R 1 , . . . , R i , O 1 , . . . , O i-1 , O * i , with O * i = O i ,
the reduction knows openings of L i , R i and it can break the soundness of the quadratic knowledge transfer argument. On the other hand, if it sends L 1 , . . . ,

L * i , R 1 , . . . , R * i , O 1 , . . . , O i-1 , where either L * i = L i or R * i = R i ,
then it knows valid openings of O j until level i -1 and it can break the soundness of the "linear knowledge transfer" argument.

To construct the linear knowledge transfer argument, we use QA-NIZK arguments of membership in linear spaces [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF][START_REF] Jutla | Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces[END_REF][START_REF] Libert | Short group signatures via structure-preserving signatures: Standard model security from simple assumptions[END_REF]26,[START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF]. Although soundness of these arguments can be proven under standard assumptions, it turns out that traditional soundness is not what we need in this setting. Indeed, to see this, suppose we want to prove that two shrinking, deterministic commitments open to the same value. Let M, N be the commitment keys. If C 1 = Mw and C 2 = Nw are commitments to the same value, obviously

C 1 C 2 ∈ Im M N . (1)
Let π a QA-NIZK proof of membership in linear spaces for [START_REF] Danezis | Square span programs with applications to succinct NIZK arguments[END_REF]. In our linear knowledge transfer argument, π should convince the verifier that:

"If C 1 = Mw for some known w, and π verifies, then C 2 = Nw."

The problem is that for any w such that C 1 = Mw = Mw , an adversary can set C 2 = Nw and compute π honestly with w . In other words, the adversary can "switch witnesses" without breaking the soundness of the QA-NIZK argument. So standard soundness does not help to argue that the left and right wires are consistently evaluated with lower levels of the circuit.

On the other hand, the "witness switching attack" is easy to rule out, as it requires the attacker to know two openings for C 1 , but this breaks the binding property of the first commitment. However, because the commitment is shrinking we do not know how to extract w to get a reduction to the binding property unless we use the knowledge soundness property of the QA-NIZK Argument as proven (in the generic group model) in [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF].

Soundness of the Linear Argument under Standard Assumptions. One of our main technical contributions is to show that such witness switching attacks are not possible under a certain decisional assumption in bilinear groups. To get back to our example, our first observation is that, using the linear properties of the QA-NIZK arguments of membership in linear spaces, a break of the knowledge transfer property can be turned into a proof of membership π † for a vector of the form ( 0 C ), where C = C 2 -Nw = 0. The crs of the QA-NIZK argument system is of the form A, B = M K 1 + N K 2 , KA, for some matrix A and a random matrices K 1 , K 2 . A proof for (C 1 , C 2 ) must be of the form C 1 K 1 + C 2 K 2 (unless one solves some computationally hard problem). Intuitively, is not easy to construct π † since it must be of the form π † = C K 2 and hence an adversary must somehow find an element in the kernel of M (which is in general a hard problem, otherwise the commitment is not binding) in order to eliminate any dependence on K 1 in B. However, in the security proof it is not clear how to extract such element in the kernel of M, which is of the same size of w, only from C and π † , which are of constant size. To bypass this problem, we assume that a stronger decisional assumption related to M holds, namely that it is hard to decide membership in the image of M (a type of Matrix Diffie-Hellman assumption [4]). Specifically, we assume that M K 1 is pseudo-random and, using this decisional assumption, we can jump to game where K 2 is information theoretically hidden and then there is an exponentially low probability of computing π † = C K 2 . To do this, we need to find a way around the problem that there is still some information about K 1 which is leaked trough the crs of QA-NIZK arguments of [26] as KA = K1A K2A , where A is either a (k + 1) × k matrix for general linear spaces or a k × k matrix when the linear spaces are generated by witness samplable distributions. To solve this, we use the fact that, information theoretically, part of K 1 is never leaked through KA when A is a (k + 1) × k matrix. We leave it as an open question to achieve a similar result when A is a k × k to exploit witness samplability.

Zero-Knowledge. In all our subarguments the verification equations are pairing product equations, so they can be made zero-knowledge with Groth-Sahai proofs [19]. However, our proof uses in a fundamental way that the input of the verification is public. Therefore, this only works when the commitment to the input is extractable. The resulting scheme is not practical as this is only possible with bit-by-bit commitments to the input. However, it can be easily extended to boolean circuits with a proof size of O(n -n pub + n + d) group elements (where n pub is the size of the public input), which is an interesting improvement over state-of-the-art, as all constructions in the crs model under falsifiable assumptions are linear in the circuit size (see [18] and concrete improvements thereof, mainly [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF]).

Previous Work.

NIZK from Falsifiable Assumptions. Groth, Ostrovsky, and Sahai constructed a NIZK proof system boolean CircuitSat only from falsifiable assumptions. The size of the proof depends asymptotically on n + m, where n is the size of the input and m is the number of gates [START_REF] Groth | Non-interactive zaps and new techniques for NIZK[END_REF], while the verifier's running time is proportional to the size of the circuit. The construction can be extended to arithmetic circuits using [19]. Several concrete improvements can be done with recent results in the QA-NIZK setting [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF][START_REF] Jutla | Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces[END_REF][START_REF] Libert | Short group signatures via structure-preserving signatures: Standard model security from simple assumptions[END_REF]26,[START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF] but we are not aware of any asymptotic improvements.

Gentry et al.

[10] constructed a NIZK proof of size n + poly(λ), which is essentially optimal when considering proofs (rather than arguments). They use what they called hybrid fully homomorphic encryption, which is a combination of symmetric encryption and fully homomorphic encryption (FHE) [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. While this shows that it is theoretically possible to build proofs of size independent of the circuit size under standard assumptions, they need to give NIZK proofs for correct key generation of FHE keys and correct evaluations of the FHE encryption algorithm and decryption algorithms. 4 These NIZK proofs, in general, need to represent the statements as boolean circuits and therefore they are of lower practical interest. Furthermore, the verifier needs to homomorphically evaluate the circuit using the FHE scheme and then its runtime is proportional to the circuit size.

Verifiable Computation. Kalai et al. [START_REF] Kalai | On publicly verifiable delegation from standard assumptions[END_REF], based on [START_REF] Goldwasser | Delegating computation: interactive proofs for muggles[END_REF] and the sum-check protocol of Lund et al. [START_REF] Lund | Algebraic methods for interactive proof systems[END_REF], constructed the first publicly verifiable non-interactive delegation scheme for boolean circuits from a simple constant size assumption in bilinear groups. Their crs is circuit dependent but they made it universal using a crs for the universal circuit. 5 . The verifier's runtime is O((n + d)polylog(s)), and the communication complexity is O(d • polylog(s)), where s is the size of the circuit, and in most other parameters it is far from being efficient (crs size, prover complexity).

As explained in [START_REF] Kalai | On publicly verifiable delegation from standard assumptions[END_REF] there's a vast literature on verifiable computation (apart from the already mentioned) which can be roughly classified into a) designated verifier schemes [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF][START_REF] Kalai | How to delegate computations: the power of no-signaling proofs[END_REF], b) schemes under very strong assumptions: "knowledge of exponent" type (e.g. [8,[START_REF] Parno | Pinocchio: Nearly practical verifiable computation[END_REF]), generic or algebraic group model (e.g. [16,31]), assumptions related to obfuscation, or homomorphic encryption [34] or c) interactive arguments [START_REF] Goldwasser | Delegating computation: interactive proofs for muggles[END_REF]. Note that all these constructions are incomparable to ours as long as they either rely on arguably stronger assumptions (b) or are in a different model (a and c).

Preliminaries

Given some distribution D we denote by x ← D the process of sampling x according to D. For a finite set S, x ← S denotes an element sampled from the uniform distribution over S.

Bilinear Groups. Let G be some probabilistic polynomial time algorithm which on input 1 λ , where λ is the security parameter, returns the group key which is the description of an asymmetric bilinear group gk = (p, G 1 , G 2 , G T , e, P 1 , P 2 ), where G 1 , G 2 and G T are groups of prime order p, the elements P 1 , P 2 are generators of G 1 , G 2 respectively, e : G 1 × G 2 → G T is an efficiently computable, non-degenerate bilinear map, and there is no efficiently computable isomorphism between G 1 and G 2 .

Elements in G γ , are denoted implicitly as [a] γ = aP γ , where γ ∈ {1, 2, T } and P T = e(P 1 , P 2 ). With this notation, e([a] 1 , [b] 2 ) = [ab] T . Vectors and matrices are denoted in boldface. Given a matrix T = (t i,j ), [T] γ is the natural embedding of T in G γ , that is, the matrix whose (i, j)th entry is t i,j P γ . We denote by |G γ | the bit-size of the elements of G γ .

I n refers to the identity matrix in Z n×n p , 0 m×n to the all-zero matrix in Z m×n p (simply I and 0, respectively, if n and m are clear from the context).

Lagrangian Pedersen Commitments. Given an arbitrary set R = {r 1 , . . . , r m } ⊂ Z p , we define the jth Lagrange interpolation polynomial as:

λ j (X) = =j (X -r ) (r j -r ) .
It is a well known fact that given a set of values x j , j = 1, . . . , m, P (X) = m j=1 x j λ j (X) is the unique polynomial of degree at most m -1 such that P (r j ) = x j . The Lagrangian Pedersen commitment in G γ for some γ ∈ {1, 2} to a vector x ∈ Z m p is defined as

Com ck (x) = m i=1 x j [λ j (s)] γ = [P (s)] γ ,
where the commitment key is ck = ([λ 1 (s)] γ , . . . , [λ m (s)] γ ), for s ← Z p . It is computationally binding under the m-DLog assumption.

We also consider vectors of Lagrangian Pedersen commitments defined as

[P (s)] γ = m i=1 x i [λ i (s)] γ ∈ G ks γ
, where s ∈ Z ks p for some k s ∈ N and λ i (s) is just (λ i (s 1 ), . . . , λ i (s ks )) . ). For a matrix distribution D k , we denote as D k the distribution of the first k rows of the matrices sampled according to D k .

Assumption 1 Let D ,k be a matrix distribution and gk ← G(1 λ ). For all non-uniform PPT adversaries A and relative to gk

← G(1 λ ), A ← D ,k , w ← Z k p , [z] γ ← G γ and the coin tosses of adversary A, 1. the Matrix Decisional Diffie-Hellman Assumption in G γ (D k -MDDH γ ) holds if |Pr[A(gk, [A] γ , [Aw] γ ) = 1] -Pr[A(gk, [A] γ , [z] γ ) = 1]| ≤ negl(λ), 2. the Split Matrix Decisional Diffie-Hellman Assumption in G γ (D k -SMDDH γ ) holds if |Pr[A(gk, [A] 1 , [A] 2 , [Aw] γ ) = 1] -Pr[A(gk, [A] 1 , [A] 2 , [z] γ ) = 1]| ≤ negl(λ).
Two examples of interesting distributions are the following:

L k : A =    s1 0 ... 0 0 s2 ... 0 . . . . . . . . . . . . 0 0 ... s k 1 1 ... 1    LG R,k : A =    λ R 1 (s1) λ R 1 (s2) ... λ R 1 (s k ) λ R 2 (s1) λ R 2 (s2) ... λ R 2 (s k ) . . . . . . . . . . . . λ R (s1) λ R (s2) ... λ R (s k )    ,
where

s i ← Z p and R = {r 1 , . . . , r N } ⊂ Z p .
The assumption associated to the first distribution is the k-Lin family. The assumption associated to the second one is new to this paper and is the (R, k)-Lagrangian Assumption. In our construction, we will use the LG R,2 -SMDDH 1 assumption (for N the maximum number of gates of the same multiplicative depth). In the full version of this work we argue about the generic hardness of the LG R,k -MDDH γ assumption in (symmetric) k-linear groups for k = 1 and k = 2, which implies the generic hardness of LG R,2 -SMDDH 1 in asymmetric bilinear groups. We note that for all interesting distributions D k , we can assume that the D k -MDDH Assumption is generically hard in k-linear groups and in particular, that every k × k minor is invertible with overwhelming probability.

The Kernel Diffie-Hellman Assumption [32] says one cannot find a non-zero vector in one of the groups which is in the co-kernel of A. We also use a generalization in bilinear groups which says one cannot find a pair of vectors in

G k+1 1 × G k+1 2
such that the difference of the vector of their discrete logarithms is in the co-kernel of A. Assumption 2 Let D ,k be a matrix distribution. For all non-uniform PPT adversaries A and relative to gk

← G(1 λ ), A ← D ,k , w ← Z k p , [z] γ ← G γ and the coin tosses of adversary A, 1. the Find-Rep Assumption holds if Pr r ← A(gk, [A] 1 , [A] 2 ) : r T A = 0 = negl(λ), 2. the Kernel Matrix Diffie-Hellman Assumption holds in G γ [32] if Pr [r] 3-γ ← A(gk, [A] γ ) : r A = 0 = negl(λ),

the Split Kernel Matrix Diffie-Hellman Assumption [14] holds if

Pr [r] 1 , [s] 2 ← A(gk, [A] 1 , [A] 2 ) : r = s ∧ r A = s A = negl(λ).
The Find-Rep Assumption for the LG R, ,k MDH Assumption is equivalent to solving k instances of the q-Dlog Assumption in both groups, in which the adversary receives q powers of s i , i = 1, . . . , k in both groups and computes s i ∈ Z p . This follows from the observation that if r is a solution of the Find-Rep problem, it can be associated to a polynomial which is 0 in s i for all i = 1, . . . , k and its factorization allows to compute s i .

We note that the Split Decisional and Split Kernel MDH Assumptions are generically hard in asymmetric bilinear groups for all distributions for which the non split variant is hard in symmetric bilinear groups whenever k ≥ 2.

Finally, we introduce an assumption which is similar to the q-SFrac Assumption considered in [12], but in the source group.

Assumption 3 (R-RSDH Assumption) Let R be an arbitrary set of integers of cardinal q. The R-Rational Strong Diffie-Hellman Assumption holds in G 1 if the following probability is negligible in λ:

Pr e([z] 1 , [1] 2 ) = e([w] 1 , [t(s)] 2 ) z = 0 gk ← G(1 λ ); ([z] 1 , [w] 1 ) ← A gk, R, [s i ] 1,2 q-1 i=1 , [s q ] 2
, where t(s) = r∈R (s -r), and the probability is taken over gk ← G(1 λ ), s ← Z p and the coin tosses of adversary A.

It is important to note that it is possible to check if an adversary has succeeded in breaking the assumption, since the value [t(s)] 2 can be constructed as a linear combination of {[s i ] 2 } q i=1 given R. The intuition why the assumption is generically hard is as follows. Since [z] 1 , [w] 1 are given in the group G 1 , the adversary must construct them as a linear combinations of all elements it has received in G 1 , which are (

[1] 1 , [s] 1 , . . . , [s q-1 ] 1 ).
On the other hand, the adversary can only win if z/t(s) = w, but the adversary can only find a non-trivial solution generically if z is constructed as a (non-zero) multiple of t(X) = r∈R (X -r) evaluated at s. But this is not possible because in G 1 it only receives powers of s of degree at most q -1 and t(X) is of degree q.

Arithmetic Circuits

Arithmetic circuits are acyclic directed graphs where the edges are called wires and the vertices are called gates. Gates with in-degree 0 are labeled by variables X i , i = 1, . . . , n or with a constant field element, the rest of the gates are either labeled with × and are referred to as multiplication gates or with + and are called addition gates. In this work we consider only fan-in 2 multiplication gates and the circuit is defined over a field Z p , where p is the order of some cryptographically useful bilinear group. Each circuit computes a function φ : Z n p → Z n p . Let G be the set of multiplicative gates of the circuit excluding multiplicationby-constant gates. We denote by m the cardinal of this set. For simplicity and without loss of generality, we may assume all outputs of the circuit to be the output of some multiplication gate.

For our construction of Sect. 5, we partition the set G of multiplicative gates of the circuit into different levels. More precisely, we define {G i } d i=1 , where G i , for i = 1, . . . , d , is the set of gates G ∈ G such that the maximum of gates in G evaluated in any path from the input of the circuit to an input of G is i -1. The minimal such d for which the partition exists is the multiplicative depth of the circuit, which we always denote by d. Further, we define G 0 to be the set of n 0 variable inputs. If G ∈ G i , we say that G has multiplicative depth i. Let n i be the cardinal of G i . With this notation, a circuit computes a function φ : Z n0 p → Z n d p , i.e. n = n 0 , n = n d and the number of multiplication gates is d i=1 n i . We now consider an encoding of circuit satisfiability where the variables are divided according to their multiplicative depth. For each gate in G i , i ∈ {1, . . . , d} the circuit is correctly evaluated if the output of the gate is the product of two multivariate polynomials of degree 1 where the variables are outputs of gates of less multiplicative depth, that is, the output of gates in G j , for some j, 0 ≤ j ≤ i -1.

Lemma 1. Let φ : Z n0 p → Z n d
p , be a circuit of multiplicative depth d and with m gates. For i ∈ {1, . . . , d}, define n i as the number multiplication gates at level i. There exist

a) variables C ij , i = 0, . . . , d, j = 1, . . . , n i , b) variables A ij , B ij , i = 1, . . . , d, j = 1, . . . , n i , b) constants f ij , g ij , f ijk , g ijk ∈ Z p , i = 1, . . . , d, k = 0, . . . , i-1, j = 1, . . . , n i , = 1, . . . , n k
such that, for every (x 1 , . . . , x n0 ) ∈ Z n0 p , if we set C 0j = x j , for all j = 1, . . . , n 0 , then φ(x 1 , . . . , x n0 ) = (y 1 , . . . , y n d ) and for each i ∈ {1, . . . , d}, A ij , B ij , C ij are evaluated respectively to the left, the right and the output wires of the jth gate at level i, if and only if the following equations are satisfied:

1. (Quadratic Constraints). For each i = 1, . . . , d, if j = 1, . . . , n i : C ij = A ij B ij . 2. (Affine Constraints) A ij = f ij + i-1 k=0 n k =1 f ijk C k and B ij = g ij + i-1 k=0 n k =1 g ijk C k . 3. (Correct Output) C dj = y j , j = 1, . . . , n d .
Given an arithmetic circuit φ : Z n0 p → Z n d p , we can define the witness for correct evaluation of φ(x) = y as a tuple (a, b, c), where a = (a 1 , . . . , a d ), b = (b 1 , . . . , b d ), c = (c 0 , . . . , c d ), s i = (s i1 , . . . , s ini ) for any s ∈ {a, b, c}. The tuple is an an assignment to A ij , B ij and C ij which satisfies the equations described in Lemma 1.

Using standard techniques due to [8], quadratic constraints can be written as a polynomial divisibility problem.

Lemma 2. (QAP for the Hadamard Product) Let (a i , b i , c i ) ∈ (Z ni p ) 3 , n i ∈ N. Let R = {r 1 , . . . , r N } ⊂ Z p be a set of elements of Z p for some N ≥ n i and let λ i (X) = j =i X -r j r i -r j . Define p i (X) =   ni j=1 a ij λ j (X)     ni j=1 b ij λ j (X)   -   ni j=1 c ij λ j (X)   .
Then,

c i = a i • b i if and only if p i (X) = h i (X)t(X), where t(X) = r∈R (X -r) and h i (X) ∈ Z p [X] is a polynomial of degree at most N -2. Proof. By definition, p i (r j ) = a ij b ij -c ij , so p i (X) is divisible by t(X) if and only if a ij b ij -c ij = 0 for all j = 1, . . . , n i .
On the other hand, for each i, affine constraints can be written also as polynomial relations. That is, for any set R = {r 1 , . . . , r N } such that N ≥ n i , there exist families of polynomials

V = {v i , v ik }, W = {w i , w ik } of degree N -1 such that (a, b, c) is a valid witness if and only if ni j=1 a ij λ j (X) = v i (X) + i-1 k=0 n k =1 c kl v ik (X) and ni j=1 b ij λ j (X) = w i (X)+ i-1 k=0 n k =1 c kl w ik (X). It suffices to define v i (X) = ni j=1 f ij λ j (X), v ik (X) = ni j=1 f ijk λ j (X), w i (X) = ni j=1 g ij λ j (X), w ik (X) = ni j=1 g ijk λ j (X).
The proof follows by evaluating the equations in the points r j ∈ R.

Arguments of Knowledge Transfer

In this section we construct what we informally name "knowledge transfer argument" for both linear and quadratic equations. The name captures the idea that these arguments ensure that if a valid opening is known for some committed value, then an opening is also known for another commitment and this second opening is a certain quadratic or linear function of the original opening.

Formally, the prover needs to prove membership in a language L of the form (w, C, D), where w is the opening of a shrinking commitment C. The statement is that "if C opens to w, then D opens to F (w)". Since typically there is an exponential number of possible openings of C, the language would not make sense without w, i.e. the statement "there exists an opening w of C such that D opens to F (w)" would most probably be always true.

K(gk, R): Sample s ← Z * p ; Output crs = gk, { λ 1 (s)] γ , . . . , [λ m (s)] γ γ∈{1,2} , [s i ] 1 i∈{1,...,m-2} , [t(s)] 2 . P(crs, a, b): (X) = m i=1 a i λ i (X); r(X) = m i=1 b i λ i (X); o(X) = m i=1 c i λ i (X); h(X) = ( (X)r(X) -o(X))/t(X); [L] 1 = [ (s)] 1 ; [R] 2 = [r(s)] 2 ; [O] 1 = [o(s)] 1 ; [H] 1 = [h(s)] 1 ; Output [H] 1 . V(crs, a, b, [L] 1 , [R] 2 , [O] 1 , [H] 1 ): Check if: e([L] 1 , [R] 2 ) -e([O] 1 , [1] 2 ) = e([H] 1 , [t(s)] 2 )
; output 1 in this case and 0 otherwise. Deciding membership in L can be done efficiently with a number of operations which is proportional to the size of the statement. Our verifier, however, does not use w for verification (i.e. it never checks that w is a valid opening of C) and does only a constant number of public key operations (ignoring the need to read w as part of the statement). When using these subarguments in the full argument for correct circuit evaluation, the verifier never reads w but w is uniquely determined by the context. This is formalized as a promise problem defined by a language of good instances L Y ES and of bad instances L N O . Completeness guarantees that proofs are accepted for all instances of L Y ES , while soundness guarantees that no argument will be accepted for instances of L N O . The promise is that "w is an opening of C" and nothing is claimed when x / ∈ (L Y ES ∪ L N O ) (i.e. when the promise does not hold). A formal definition of QA-NIZK for promise problems can be found in the full version of this work.

Argument for Hadamard Products

Let m ∈ N. We give an argument for the promise problems defined by languages

L quad Y ES , L quad N O ,
L quad Y ES = (a, b, [L] 1 , [R] 2 , [O] 1 ) : c = a • b and [L] 1 = [Λ] 1 a, [R] 2 = [Λ] 2 b, [O] 1 = [Λ] 1 c , L quad N O =    (a, b, [L] 1 , [R] 2 , [O] 1 ) : c = a • b, [L] 1 = [Λ] 1 a and [R] 2 = [Λ] 2 b, but [O] 1 = [Λ] 1 c    .
Perfect completeness. The argument described in Fig. 1 has perfect completeness as the values

[L] 1 , [O] 1 can be computed from {[λ i (s)] 1 . . . , [λ m (s)] 1 }, and [R] 2 from {[λ i (s)] 2 . . . , [λ m (s)] 2 }.
Further, by definition, the polynomial (X)r(X) -o(X) takes the value a i b i -c i = 0 at point r i ∈ R. Therefore, (X)r(X) -o(X) is divisible by t(X), so h(X) is well defined. Further, the degree of H is at most m -2 (since (X)r(X) has degree 2m -2 and t(X) has degree m) and thus [H] 1 can be computed from [s] 1 , . . . , [s m-2 ] 1 .

Computational Soundness. We argue that if A produces an accepting proof for (a, b, c,

[L] 1 , [R] 2 , [O] 1 ) ∈ L quad N O
then we can construct an adversary B against the (R, m)-Rational Strong Diffie-Hellman Assumption. Given a challenge gk,

[s i ] 1 m-1 i=1 , [s i ] 2 m i=1
, adversary B can simulate the common reference string perfectly because λ i (X) is a polynomial whose coefficients in Z p depend only on R of degree at most m -1. Therefore,

[λ i (s)] 1 , [λ i (s)] 2 can be computed from {s i } m-1
i=1 in both the source groups. On the other hand, t(X) is a polynomial with coefficients in Z p which depend only on R of degree at most m.

So [t(s)] 2 can be computed in G 2 given {[s i ] 2 } m i=1 . Adversary A outputs (a, b, c, [L] 1 , [R] 2 , [O † ] 1 , [H † ] 1 ) which is accepted by the verifier and (a, b, c, [L] 1 , [R] 2 , [O † ] 1 ) ∈ L quad
N O , which in particular means that, for L = (s), R = r(s), the equation

e([L] 1 , [R] 2 ) -e([O † ] 1 , [1] 2 ) = e([H † ] 1 , [t(s)] 2 ) (2)
holds but O † = O(s).
Since adversary B received a, b as part of A's output, it can run the honest prover algorithm and obtain O, H which satisfy that

e([L] 1 , [R] 2 ) -e([O] 1 , [1] 2 ) = e([H] 1 , [t(s)] 2 ) (3)
and O = O(s). Subtracting equations ( 2) and (3), we get e([

O † -O] 1 , [1] 2 ) = e([H † - H] 1 , [t(s)] 2 ). Therefore, ([O † -O] 1 , [H † -H] 1
) is a solution to the (R, m)-Rational Strong Diffie-Hellman Assumption.

We note that the verification algorithm never uses (a, b) which are part of the statement. When using the scheme as a building block, we omit (a, b) from the input of the verifier of the quadratic relations.

Argument for Linear Languages

Let gk be a bilinear group of order p and

1 , 2 , n ∈ N and [M] 1 ∈ G 1 ×n 1 , [N] 1 ∈ G 2 ×n 1
be some matrices sampled from some distributions M, N . We give two arguments for the promise problem defined by languages L lin Y ES , L lin N O , which are parameterized by gk, [M] 1 , [N] 1 and are defined as:

L lin Y ES = {(w, [u] 1 , [v] 1 ) : [u] 1 = [M] 1 w, [v] 1 = [N] 1 w} L lin N O = {(w, [u] 1 , [v] 1 ) : [u] 1 = [M] 1 w, [v] 1 = [N] 1 w}.
The arguments are simply the QA-NIZK Arguments of membership in linear spaces for general and witness samplable distributions as presented by Kiltz and Wee [26] (which generalize previous constructions [START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF][START_REF] Jutla | Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces[END_REF]). Both arguments are very similar and can be easily written in a unified way. The idea is to use the arguments to prove that there exists a witness w such that

K(gk, [M] 1 , [N] 1 ):// M ∈ Z 1×n p , N ∈ Z 2×n p K 1 ← Z 1 ×k p ; K 2 ← Z 2×k p ; K = K 1 K 2 ; Sample A ← D k ; [B] 1 = [M K 1 + N K 2 ] 1 ; C 1 = K 1 A; C 2 = K 2 A; C = KA return crs = (gk, [B] 1 , [A] 2 , [C] 2 ). P(crs, [u] 1 , [v] 1 , w): return [π] 1 = w [B] 1 ; V(crs, [u] 1 , [v] 1 , [π] 1 ): Check if: e([π] 1 , [A] 2 ) = e([u ] 1 , [C 1 ] 2 ) + e([v ] 1 , [C 2 ] 2 )
u v = M N w.
Intuitively, assuming that it is hard to find non-trivial (w, w

) such that [u] 1 = [M] 1 w = [M] 1 w , this would prove that [v] 1 = [N] 1 w.
However, finding a security proof is not simple.

For witness samplable distributions, we only know a proof in the generic group model. The proof is a trivial consequence of the knowledge soundness property of QA-NIZK arguments which has already been used in previous works [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF]. It has a proof size of k group elements when instantiated for the k-Lin Assumption.

Our main technical contribution is to prove soundness for the promise problem for general distributions (not necessarily witness samplable) assuming the hardness of the decisional problem for the distribution associated to matrix M (the M -MDDH Assumption). It has a proof size of k + 1 group elements when instantiated for the k-Lin Assumption.

In Figure [START_REF] Daza | Shorter quadratic QA-NIZK proofs[END_REF] we describe the QA-NIZK argument of membership in linear spaces for witness samplable and general distributions (the only difference between these two cases is the definition of Dk ), as presented in [26]. The difference with the original presentation in [26] is that we separate the key K in blocks K 1 , K 2 associated to M, N, which will be convenient for the proof. Perfect completeness, perfect zero-knowledge and computational soundness under any D k -KerMDH Assumption is proven [26].

Soundness of Lin Dk , w.r.t. the language L lin N O , is a direct consequence of Lemma 3. Lemma 3. For any adversary A and for any N ∈ Z 2×n p , let

K * (gk, [M] 1 , [N] 1 ): // M ∈ Z 1 ×n p , N ∈ Z 2 ×n p Sample A ← D k ; C 1 ← Z 1×k p ; C 2 ← Z 2×k p ; C = C 1 C 2 ; K 1,2 ← Z 1 p ; K 2,2 ← Z 2 p ; K 2,1 = (C 2 -K 2,2 A)A -1 ∈ Z 2 ×k p ; [z] 1 = [M ] 1 K 1,2 ; [B] 1 = ([M C 1 A -1 -zAA -1 + N K 2,1 ] 1 , [z] 1 + [N ] 1 K 2,2 ); return crs = (gk, [B] 1 , [A] 2 , [C] 2 ).
A = Pr   v = 0 π = v K 2 M ← M; N ← N ; crs ← K(gk, [M] 1 , [N] 1 ); ([v] 1 , [π] 1 ) ← A(crs, [M] 1 , [N] 1 )   . 1. When D k = D k and M is witness samplable, if A is generic there exists a PPT adversary B such that A ≤ Adv M -FindRep (B) + negl(λ). 2. When D k = D k , there exists a PPT adversary B such that A ≤ Adv M -MDDH (B)+ 1/p,
where M is the distribution which results from sampling matrices from M and transposing them.

Proof. (Lemma 3.1.) The proof is a direct consequence of the fact that scheme from Fig. 2 is an argument of knowledge in the generic group model, as proven by Fauzi et al. [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF]Theorem 2]. Indeed, if this is the case there exists an extractor which given A outputs a witness w * such that ( 0 v ) = ( M N ) w * . Since v = 0, then w * = 0 and w * ∈ Z n p is an element in the kernel of M , which breaks the M -FindRep assumption 6 .

Proof. (Lemma 3.2). The proof follows from the indistinguishability of the following games

Game 0 : This game runs the adversary as in Lemma 3. Game 1 : This game is exactly as Game 0 but the crs is computed using algorithm K * , as defined in figure 3, and the winning condition is

v = 0 and π = (v (C 2 -K 2,2 A)A -1 , v K 2,2 ).
Game 2 : This game is exactly as Game 1 but z ← Z n p .

We now prove some Lemmas which show that the games are indistinguishable. Lemmas 4 and 5 show that the adversary has essentially the same advantage of winning in any game. Lemma 6 says that the adversary has negligible probability of winning in Game 2 . Lemma 3.2 follows from the composition of lemmas 4, 5 and 6.

Lemma 4. For any (unbounded) algorithm A we have Pr[Game

1 (A) = 1] = Pr[Game 0 (A) = 1]. Proof. If we define K 1,1 = (C 1 -K 1,2 A)A -1 and K = K 1 K 2 = K 1,1 K 1,2 K 2,1 K 2,2 ,
we observe that the output of K * is well formed and the winning condition is the same as in the previous game, since

[B] 1 = ([M C 1 A -1 -zAA -1 + N K 2,1 ] 1 , [z] 1 + [N ] 1 K 2,2 ) = ([M K 1,1 +N K 2,1 ] 1 , [M K 1,2 +N K 2,2 ] 1 ) = [M K 1 +N K 2 ] 1 , and
KA = (C 1 -K 1,2 A)A -1 K 1,2 (C 2 -K 2,2 A)A -1 K 2,2 A A = C 1 -K 1,2 A + K 1,2 A C 2 -K 2,2 A + K 2,2 A = C,
and by definition π = (v (C 2 -K 2,2 A)A -1 , v K 2,2 ) = (v K 2,1 , v K 2,2 ) = v K 2 .
Therefore we just need to argue that the distribution of K is the same in both games. But this is an immediate consequence of the fact that for every value of (C, K 1,1 , K 2,1 ) there exists a unique value of (K 1,2 , K 2,2 ) which is compatible with

C = KA. Indeed, C = KA ⇐⇒ C i = K i,1 A + K i,2 A, i = 1, 2 ⇐⇒ (C i -K i,2 A)A -1 = K i,1 , i = 1, 2.
Lemma 5. For any PPT algorithm A there exists a PPT algorithm B such that

| Pr[Game 1 (A) = 1] -Pr[Game 0 (A) = 1]| ≤ Adv M-MDDH (B).
Proof. We construct an adversary B that receives the challenge (

[M ] 1 , [z * ] 1 ), where z * is either M r, r ← Z 1 p , or z * ← Z n p . B computes the crs running K * (gk, [M] 1 , [N] 1 ) but replaces [z] 1 with [z * ] 1 ,

and then runs A as in game

Game 1 . It follows that Pr[B([M ] 1 , [z * ] 1 ) = 1|z * = M r] = Pr[Game 1 (A) = 1] and Pr[B([M * ] 1 , [z * ] 1 ) = 1|z * ← Z n p ] = Pr[Game 2 (A) = 1
] and the lemma follows.

Lemma 6. For any (unbounded) algorithm

A, Pr[Game 2 (A) = 1] ≤ 1/p.
Proof. We will show that, conditioned on A, C, B, M, N, the matrix K 2,2 is uniformly distributed. Since it holds that BA = (M , N )C, we get that the first k columns of B, namely B 1 , are completely determined by B 2 , the last column of B. Indeed

(B 1 , B 2 )A = (M , N )C ⇐⇒ B 1 = ((M , N )C -B 2 A)A -1 .
Hence, conditioning in A, C, B 2 , M, N doesn't alter the probability. We have that B 2 = z + N K 2,2 , which consists of n equations on n + 2 variables. It follows that there are 2 free variables. Then K 2,2 is uniformly distributed and hence completely hidden to the adversary. Note that

π = v K 2 =⇒ π 2 = v K 2,2 ,
where π 2 is the last element of π. Given that v = 0, the last equation only holds with probability 1/p and so A's probability of winning.

The knowledge transfer property is a direct consequence of Lemma 3.

Theorem 1. For any adversary A against the soundness of Lin with respect to L lin N O , it holds that:

1. When D k = D k , M is witness samplable, if A is generic then there exists a PPT adversary B such that A ≤ Adv M -FindRep (B) + negl(λ). 2. When D k = D k , there exist adversaries B 1 and B 2 such that Adv Lin (A) ≤ Adv D k -KerMDH (B 1 ) + Adv M -MDDH (B 2 ) + 1/p.
Proof. Both for the witness samplable and the general case, given an adversary that produces a valid proof for a statement in L lin N O , successful attacks can be divided in two categories.

Type I: In this attack [π]

1 = [u ] 1 K 1 + [v ] 1 K 2 . Type II: In this type of attack [π] 1 = [u ] 1 K 1 + [v ] 1 K 2 .
Type I attacks are not possible for witness samplable distributions, because proofs are unique, i.e. there is only one value of π which can satisfy the verification equation. Type I attacks are computationally infeasible for general distributions. Indeed, we construct an adversary B 1 against the D k -KerMDH assumption. 7 The adversary B 1 receives a challenge [A] 2 and then runs the soundness experiment for A itself. When A outputs (

[u] 1 , [v] 1 , [π] 1 ), B 1 out- puts [π † ] 1 = [π] 1 -[u ] 1 K 1 -[v ] 1 K 2 = 0. Since [π] 1 is accepted by the verifier we get that e([π] 1 , [A] 2 ) = e([u ] 1 , [C 1 ] 2 ) + e([v ] 1 , [C 2 ] 2 ) and then π † A = πA -u K 1 A -v K 2 A = πA -u C 1 -v C 2 = 0.
We conclude that the success probability of a type I attack is bounded by Adv D k -KerMDH (B 1 ).

For type II attacks, for both types of distributions, since

[π] 1 = [u ] 1 K 1 + [v] 1 K 2 is a valid proof for [u]1 [v]1
, then, by linearity of the verification equation,

π † = π -w B is a valid proof for 0 [v † ]1 = [u]1-[M]1w [v]1-[N]1w
. Since v = Nw, we conclude that an attacker of type II can be turned into an attacker B 2 for Lemma 3.

"knowledge transfer" is because these arguments will ensure that, if the prover knows a witness for the circuit evaluation up to level i which is also a valid opening up to level i of a set of shrinking commitments to the corresponding wires, it also knows a valid opening to the commitments of the wires at level i + 1.

Since the input of the circuit is public, the idea is that these arguments allow to "transfer" the knowledge of the witness for correct evaluation (a consistent assignment to all wires) to lower levels of the circuit. Any adversary against soundness needs to break the "chain" of consistent evaluations at some point and thus, break the soundness of one of the two subarguments. This technique allows us to avoid using binding commitments to the wires at each level, while still being able to define what it means to break soundness. Intuitively, the difficulty we have to circumvent is to reason about whether the openings of shrinking commitments satisfy a certain equation without assuming that the adversary is generic, as there are many possible such openings.

The reason why we use two arguments is natural given characterization of circuits given in Sect. 3. The variables A ij (resp. B ij , C ij ) describe correct assignments to the j-th left (resp. right, output) wire at level i. We use the quadratic knowledge transfer property to ensure that a certain value O i is a valid (deterministic, not hiding) commitment to all the outputs at level i if L i-1 and R i-1 are valid commitments (i.e. consistent with the input) to all the right and left wires at the previous level. On the other hand, we encode the affine constraints as membership in linear spaces and use the linear knowledge transfer argument to ensure that L i , R i are valid commitments to all left and right wires at level i if O j for j = 1, . . . , i -1 are valid commitments to the previous levels.

Throughout this section, R φ represents a relation R φ = {(gk, x, y) : φ(x) = y} where gk is an asymmetric bilinear group of order p and φ : Z n0 p → Z n d p as described in Sect. 3 and N = max i=1,...,d n i is the maximum number of multiplicative gates of same multiplicative depth. The construction is parameterized by a value k s , following the dicussion in Sect. 4.2 on the security properties of the linear knowledge transfer argument.

This section is organized as follows: we first show how to encode affine constraints as membership in linear spaces, then we present the description of our argument in terms of the two subarguments and give the (sketched) proof of security, and finally we discuss its efficiency.

Encoding Affine Constraints as Membership in Linear Spaces

We translate the affine constraints described in the circuit encoding of Sect. 3 as membership of (

[O] 1 , [L] 1 , [R] 2 ) in a linear subspace of G n+(2d-1)ks 1 × G dks 2 .
We write in matrix form the expression of (

x, [O] 1 , [L] 1 , [R]
2 ) in terms of the internal wires of the circuit, following Sect. 3. The commitments to the output values

[O] 1 should satisfy that [O i ] 1 = [Λ i ] 1 c i , where Λ i = (λ 1 (s), . . . , λ ni (s))
and λ j (X) is the jth Lagrangian polynomial for some R = {r 1 , . . . , r N } ⊂ Z p and the input x = c 0 is public. These constraints can be expressed in matrix form in equation (4):

         x O 1 O 2 O 3 . . . O d-1          =          I 0 0 0 . . . 0 0 Λ 1 0 0 . . . 0 0 0 Λ 2 0 . . . 0 0 0 0 Λ 3 0 . . . . . . . . . . . . 0 0 0 0 . . . Λ d-1                   c 0 c 1 c 2 c 3 . . . c d-1          (4)
We denote the matrix on the right hand side of (4) as M, so this equation reads

( x O ) = Mc.
On the other hand, the constraints satisfied by the left wires in terms of the output wires of previous levels can be written in matrix form as shown in equation ( 5):

       L 1 L 2 L 3 . . . L d        =        F 1,0 0 0 . . . 0 F 2,0 F 2,1 0 . . . 0 F 3,0 F 3,1 F 3,2 . . . 0 . . . . . . . . . . . . . . . F d,0 F d,1 F d,2 . . . F d,d-1               c 0 c 1 c 2 . . . c d-1        +        L1 L2 L3 . . . Ld        , (5)
that is, for each i,

L i = i-1 k=0 F i,k c k + Li , where F i,k = n k j=1 f ijk1 λ j (s), n k j=1 f ijk2 λ j (s), . . . n k j=1 f ijkn k λ j (s) = v ik1 (s), v ik2 (s), . . . v ikn k (s) (6)
and Li = ni j=1 f ij λ j (s) = v i (s), for the constants which are defined in Lemma 1. We denote the matrix on the right hand side of equation [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF] as N, so this equation reads L = Nc + L. The constraints satisfied by the right wires in terms of the output wires of previous levels can be written in a similar form as shown in equation [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF]:

       R 1 R 2 R 3 . . . R d        =        G 1,0 0 0 . . . 0 G 2,0 G 2,1 0 . . . 0 G 3,0 G 3,1 G 3,2 . . . 0 . . . . . . . . . . . . . . . G d,0 G d,1 G d,2 . . . G d,d-1               c 0 c 1 c 2 . . . c d-1        +        R1 R2 R3 . . . Rd        , (7)
that is, for each i,

R i = i-1 k=0 G i,k c k + Ri , where G i,k = n k j=1 g ijk1 λ j (s), n k j=1 g ijk2 λ j (s), . . . n k j=1 g ijkn k λ j (s) = w ik1 (s), w ik2 (s), . . . w ikn k (s) , (8)
and Ri = ni j=1 g ij λ j (s) = w i (s). We denote the matrix on the right hand side of equation [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF] as P, so this equation reads R = Pz + R.

With the notation defined, satisfaction of the affine constraints can be written as

[O ]1 [L]1-[ L]1 [R]2-[ R]2 ∈ Im [M]1 [N]1 [P]2 , where [O ] 1 = [x]1 [O]1 .
That is, the linear constraints are satisfied if a certain vector is in a subspace generated by some matrix which depends on the circuit.

New Argument

In this section we describe our construction for proving correct evaluation of an arithmetic circuit.

Setup(R φ ): Pick s ← Z ks p . Generate crs φ = (crs φ,1 , . . . , crs φ,ks ), where crs φ,i ← Quad.K(gk, {[s j i ] 1 } N -1 j=1 , {[s j i ] 2 } N j=1
) is the crs for the quadratic knowledge transfer argument defined in Fig. 1. Express affine constraints (equations 4), [START_REF] Fauzi | An efficient pairing-based shuffle argument[END_REF], and ( 7)) which define circuit satisfiability as membership in the image of ([M ] 1 , [N ] 1 , [P ] 2 ) as explained in Sect. 5.1. Generate a crs for the bilateral linear knowledge transfer argument defined in Fig. 4 for

([M ] 1 , [N ] 1 , [P ] 2 ) .
Prove(crs, (x, y, a, b, c) ∈ R φ ): Given the input x, the output y, and (a, b, c) a valid assignment to left, right and output wires as described in Lemma 1, the prover proceeds as follows:

1. For each i ∈ {1, . . . , d}, commit to a i , c i in G ks 1 and to b i in G ks 2 as:

[L i ] 1 = ni j=1 a ij [λ j (s)] 1 = [Λ i ] 1 a i , [R i ] 2 = ni j=1 b i,j [λ j (s)] 2 = [Λ i ] 2 b i , [O i ] 1 = ni j=1 c ij [λ j (s)] 1 = [Λ i ] 1 c i .
2. (Quadratic Constraints) For each i ∈ {1, . . . , d}, and each j ∈ {1, . . . , k s }, compute a proof Π quad i,j that the vector a i •b i , which is the componentwise product of the openings of

[L ij ] 1 , [R ij ] 2 , is an opening of [O ij ] 1 . 3. (Linear Constraints) Compute a proof Π lin that [L i ] 1 and [R i ] 2 are com-
mitments to the correct evaluation of all the left and right wires at level i, for all i ∈ {1, . . . , d}, that is, that they satisfy the affine linear constraints which relate them to the outputs of gates at levels j = 0, . . . , i -

1. 4. Output (C = ([L] 1 , [R] 2 , [O] 1
), Π quad , Π lin ) as the proof, where Π quad = {Π quad i,j

: i = 1, . . . , d, j = 1, . . . , k s }. Verify(crs, (x, y), (C, Π quad , Π lin )): Output 1 if the following two checks are successful and 0 otherwise:

1. Verify Π quad , Π lin . 2. Check that [O d ] 1 = n d j=1 [λ j (s)] 1 y j .
Security. Perfect completeness is obvious, because if (x, y, a, b, c) is a valid witness for satisfiability, then it satisfies both linear and quadratic constraints because of the characterization of Sect. 3 and the definition of M, N, P presented in Sect. 5.1.

Let A be an adversary against the soundness of the scheme. We construct an adversary B 1 against the quadratic knowledge transfer argument, B 2,0 , . . . , B 2,d-1 against the linear knowledge transfer argument.

Adversary B 1 receives the common reference string of the quadratic subargument, which includes (gk, [s i ] 1

N -1 i=1 , [s i ] 2 N i=1
) and samples α j ← Z * p , j = 2, . . . , k s . It defines s = s 1 , s j = α j s j and computes the crs of the quadratic argument for s j , j = 1, . . . , k s from the received values. It then creates the common reference string of the full argument in the natural way, by defining the matrices M, N, P from the crs of the quadratic subargument and sampling the rest of the secret key. When it receives an accepting proof (C = (

[L] 1 , [R] 2 , [O] 1
), Π quad , Π lin ) from adversary A for some statement (x, y), adversary B 1 computes the full witness for correct evaluation (a, b, c) from x. The adversary searches for indexes i, j such that [L ij ] 1 and [R ij ] 2 are commitments to a i and b i but [O ij ] 1 is not a valid commitment to a i • b i , and it aborts if these indexes do not exist. From α j , adversary A computes µ = (µ 1 , . . . , µ ni ) ∈ Z ni p such that λ (s j )µ = λ (s) and ν ∈ Z p such that νt(s j ) = t(s). It returns

(a i • µ, b i • µ, [L ij ] 1 , [R ij ] 2 , [O ij ] 1 ), as an instance of L quad N O together with an accepting proof [νH ij ] 1 .
Adversary B 2,i , i = 0, . . . , d -1 receives a common reference string of the linear subargument for the language associated to the first i + 1, (i + 2), (i + 2) blocks of rows and the first i j=0 n i columns of M, N, P, respectively. That is, M i , N i are defined as:

M i =   I 0 Λ1 . . . 0 Λi   , N i =   F1,0 0 ... 0
, [O 1 ] 1 , . . . , [O i ], [L 1 ] 1 -[ L1 ], [L i+1 ] 1 -[ Li+1 ], [R 1 ] 2 - [ R1 ] 2 , . . . , [R i+1 ] 2 -[ Ri+1 ]
2 ) together with its corresponding proof, which adversary B 2,i can compute from the proof given by adversary A and the secret values it sampled to extend the crs of the subargument to the full crs (this is possible using the linearity of the proof, full details are in the full version of this work.

For every successful adversary A at least one of the adversaries B 1 , B 2,0 , . . . , B 2,d-1 does not abort. This is because if the statement is false there must be some point in the "chain" where either

[L i ] 1 , [R i ] 2 are honestly computed but [O i ] 1 is not, or [O i ] 1 is honestly computed but [L i+1 ] or [R i+1 ] is not.
The linear knowledge transfer argument is based on the L 2 -KerMDH and the M i -SMDDH G1 assumptions. The latter reduces to the LR R,ks -SMDDH and the SXDH assumptions as proven in the full version of this work. Based on this proof, we can state the following Theorem.

Theorem 2. Let (gk, φ : Z n0 p → Z n d p , R) be a bilinear group of order p, an arithmetic circuit and a set of Z p of cardinal N = max i=1,...,d n i . For any adversary A against the soundness of the argument defined above there exist adversaries B 1 , B 2 , B 3 , B 4 such that:

Adv snd (A) ≤Adv R-RSDH (B 1 ) + dAdv L2-SKerMDH (B 2 ) + dk s Adv LG R,ks -SMDDH G 1 (B 3 )+ d min(N -k s , d) log k s Adv SXDH (B 4 ) + d(1 + k s ) p .
Note that k s ≤ 2 and then the largest security lost factor is d min(N -k s , d) ≤ d • N , which is arguably of the order of the circuit size.

Efficiency

In the most efficient instantiation, the proof size is (3d + 2)|G 1 | + (d + 2)|G 2 | and naive verification requires to compute 3d pairings for the quadratic relations and 2(n 0 + 3d + 4) for the linear part, n d exponentiations in G 1 for the output. Using the "bilinear batching" techniques of Herold et al. [21] the number of pairings can be reduced to n 0 + 3d + 4 for the linear part. Since the input is known in Z p , n 0 pairings in this part can be replaced by n 0 exponentiations in G T . Finally, using standard batching techniques [START_REF] Ferrara | Practical short signature batch verification[END_REF], the number of pairings for the quadratic part can be reduced to d + 2. As a result the total number of pairings required for verification is 4d + 6, plus n 0 exponentiations in G T and O(n 0 + d + n d ) exponentiations in the source group.

In the instantiation which is secure in the standard model, the proof size is (6d + 3)|G 1 | + (2d + 3)|G 2 | and naive verification requires to compute 6d pairings for the quadratic relations and 2(n 0 + 6d + 6) for the linear part, and using the same batching techniques the number of pairings required for verification is 8d + 9.

Adding Zero-Knowledge

In this section we argue how to add zero-knowledge to the argument for correct arithmetic circuit evaluation of Sect. 5.2. The same discussion applies for the argument for boolean circuit satisfiability discussed in Sect. 6.1 for boolean circuits.

We have to distinguish two different situations. In the first one the input is public, and we can easily modify our proof so that it reveals nothing about the internal evaluation steps. When the input or part of the input must be secret, which is the most useful case, the circuit input cannot be part of the verifier's input, at least not in the clear. A natural idea is to let the prover commit to it. The problem is that our "knowledge transfer" idea requires the reduction in the soundness proof to know this secret input, which means that the commitment to the input must be extractable so that we can efficiently extend it to a vector of correct evaluations (a, b, c). Even in a QA-NIZK setting where we can efficiently open the commitments, they are only F -extractable [START_REF] Escala | Fine-tuning Groth-Sahai proofs[END_REF] (under falsifiable assumptions), which means that we can only extract in the source groups but not in Z p . This leaves us only with a couple of solutions, all of them unsatisfactory.

One of them is to commit to inputs bitwise and prove that this is done correctly. This is not acceptable in terms of concrete efficiency for arithmetic circuits, but it is a practical approach for boolean circuits.

The second one is to use a commitment to the input which is extractable under knowledge assumptions. Of course, then our construction is no longer secure under falsifiable assumptions, but it is interesting that it indicates a tradeoff in SNARK constructions: longer proof size and verification costs (Θ(d) group elements/ pairings, respectively) but weaker assumptions (only the input needs to be extracted and not the full witness).

In any case, we leave for future work to explore the possibilities of this or other mixed approaches. We now give the technical details on how to add zeroknowledge to our argument for correct circuit evaluation, distinguishing the two aforementioned situations.

Adding Zero-knowledge to Correct Evaluation of Middle Wires. This step is straightforward. The argument is changed so that [L] 1 , [R] 2 , [O] 1 are not given in the clear, but instead the prover gives GS commitments [START_REF] Groth | Efficient noninteractive proof systems for bilinear groups[END_REF] to each of its components. For the quadratic argument, it gives a GS Proof that the verification equation is satisfied, that is, for each i it proves in zk that the pairing product equation:

e([L i ] 1 , [R i ] 2 ) -e([O i ] 1 , [1] 2 ) = e([H i ] 1 , [T ] 2 ) is satisfied, where [L i ] 1 , [R i ] 2 , [O i ] 1 , [H i ] 1 are hidden committed values.
For the linear argument, it suffices to give a GS proof of satisfiability of the verification equation in Fig. 4. In its most efficient instantiation, the verification equation in Fig. 4 consists of 2 pairing product equations and hence the GS proof consists of 8 elements of each group.

An alternative, more efficient approach (which requires only 2|G 1 | + 2|G 2 | group elements) for the linear argument proves that the vectors of committed elements are in a certain linear (bilateral) space. The idea is quite simple but a little cumbersome, so we explain it in the full version of this work.

Adding this zero-knowledge layer in the intermediate wires is not too costly. The total size of the proof is 4d|G 1 | + 2d|G 2 | for the commitments to the wires, 4d|G 1 | + 4d|G 2 | for the GS proofs of quadratic equation, 2|G 1 | + 2|G 2 | for the linear constraints part. Verification requires 26 pairings for each GS verification equation and 2(n 0 +3d+4) for the linear proof. First, one can observe that in fact since the input is known in Z p , the n 0 pairings can be replaced by exponentiations in G T . Second, using the "bilinear batching" techniques of [21] this is reduced to 7d + 3d + 4. Finally, using traditional batching techniques [START_REF] Ferrara | Practical short signature batch verification[END_REF], the cost of verifying all the to GS equations can be reduced to d + 6, resulting in a total cost of 4d + 10 pairings (and O(n 0 + d) exponentiations).

Hiding the input and output. Finally, we discuss how to use our results in a scenario where not only the middle values of the wires should be hidden but also the input and the output. In this case the prover commits to the input x using an extractable commitment (using one of the options described above). For instance, c x can be just the concatenation of GS commitments to the inputs provided the prover submits also a proof of knowledge of their opening (giving additional bitwise commitments and a proof that c x is of the right form, a proof of knowledge in the ROM) or a commitment of knowledge under extractable assumptions). In all these cases, c x can be written as

[c x ] 1 = [E] 1 x + [V] 1 s (or,
if it has components in both source groups in G 1 , G 2 in a similar way except that the matrices E and V will also have component in different groups).

The only difference in this case is that in the first n 0 rows of M we replace the identity matrix by the matrix E and we add columns of the form E, 0 .

The output is never given in the clear but the commitment to [O d ] 1 is a perfectly binding commitment to it.

Boolean Circuits

We extend our results to any boolean circuit φ : {0, 1} n0 → {0, 1} n d . The gates of φ are assumed to have fan-in two but otherwise they can be of any type (excluding non-interesting or trivial gate types). The construction relies on the characterization of these gates as quadratic functions of the inputs. We list below the 10 gate types allowed for the circuit φ, along with its expression as a quadratic function. The list of gates is taken from [START_REF] Danezis | Square span programs with applications to succinct NIZK arguments[END_REF], which observe that the last remaining 6 gate types depend mostly on one input and are not used often. AND(a, b, c): ab = c NAND(a, b, c):

1 -ab = c OR(a, b, c): 1 -(1 -a)(1 -b) = c NOR(a, b, c): (1 -a)(1 -b) = c XOR(a, b, c): b(1 -a) + a(1 -b) = c XNOR(a, b, c): 1 -a(1 -b) -b(1 -a) = c G 1 (a, b, c) = (c = a ∧ b): (1 -a)b = c G 2 (a, b, c) = (c = a ∧ b): 1 -(1 -a)b = c G 3 (a, b, c) = (c = a ∧ b): a(1 -b) = c G 4 (a, b, c) = (c = a ∧ b): 1 -a(1 -b) = c.
From this characterization we slice the circuit into several quadratic and affine constraints similar to the arithmetic case. As before, we partition the set of gates G of a given circuit φ into different subsets G i according to the depth, n i is cardinal of the gates at level i and we assume that gates at each level are ordered in some way and they are denoted as G i1 , . . . , G ini .

For each level i, we define variables C ij , j = 1, . . . , n i which will encode the output of gate j at level i. The gate G ij will be correctly evaluated if

C ij = G ij (A ij , B ij ), where A ij = C k L L and B ij = C k R R for some indexes 0 ≤ k L , k R < i, 1 ≤ L ≤ n k L and 1 ≤ R ≤ n k R ,
which depend on i, j and which are specified by the circuit description. That is, the left wire of G ij should be the output of the L th gate at level k L and the right wire the output of the R th gate at level k R . Lemma 7. Let φ : {0, 1} n0 → {0, 1} n d , be a circuit of multiplicative depth d with n i gates at level i. There exist

a) variables C ij , i = 0, . . . , d, j = 1, . . . , n i , b) variables A ij , B ij , i = 1, . . . , d, j = 1, . . . , n i , c) constants f ijk , g ijk ∈ {0, 1}, i = 1, . . . , d, k = 0, . . . , i -1, j = 1, . . . , n i , = 1, . . . , n k , d) constants β ij , γ ij , ij , δ ij ∈ Z p , i = 1, . . . , d, j = 1, . . . , n i , which depend on the type of gate G ij ,
such that, for every (x 1 , . . . , x n0 ) ∈ {0, 1} n0 , if we set C 0,j = x j , for all j = 1, . . . , n 0 , then φ(x) = y and A ij , C ij are evaluated to the left and output of the jth gate at level i if and only if the following equations are satisfied:

1. (Quadratic constraints). For each i = 1, . . . , d, for all j = 1, . . . , n i ,

C ij = A ij B ij + A ij β ij + B ij γ ij + ij , (9) 2.

(Affine constraints)

A ij = i-1 k=0 n k =1 f ijk C k and B ij = i-1 k=0 n k =1 g ijk C k . 3. ( Correct
Output) For all j = 1, . . . , n d , C dj = y j . Proof. For the (i, j)th circuit gate, a description of the circuit φ specifies the gate type and indexes (k i,j,L , i,j,L ) which indicate the left and right wire. Therefore, from the quadratic expression of boolean gates for boolean circuit satisfiability, correct evaluation of G ij is expressed as: C ij = C k i,j,L , i,j,L C k i,j,R , i,j,R α ij + C k i,j,L , i,j,L β ij + C k i,j,R , i,j,R γij + ij , for some α ij , β ij , γij , ij ∈ Z which depend on the gate type. This can be rewritten as an equation over Z p as: C ij = C k i,j,L , i,j,L (C k i,j,R , i,j,R α ij )+C k i,j,L , i,j,L β ij +(C k i,j,R , i,j,R α ij )(α -1 ij γij )+ ij .

(10) For any (i, j) we define the constant f ijk and g ijk to be 0 everywhere except for f ijk i,j,L i,j,L = 1 and g ijk i,j,R i,j,R = α ij . Therefore, if

A ij = i-1 k=0 n k =1 f ijk C k = C k i,j,L , i,j,L and B ij = i-1 k=0 n k =1 g ijk C k = C k i,j,
R , i,j,R and equation (10) which expresses correct evaluation of gate (i, j) can be rewritten as:

C ij = A ij B ij + A ij β ij + B ij γ ij + ij , (11)
where γ ij = α -1 ij γij . Obviously, this implies that if c 0,j = x j , and the linear constraints are satisfied, then the rest of the output wires are also consistent with x j and we conclude that c n d ,j is the output corresponding to this input. Therefore, if c n d ,j = y j , we can conclude that φ(x) = y.

To achieve succinct ness, quadratic equations which encode correct gate evaluation are represented as a divisibility relation with the usual polynomial aggregation technique.

Lemma 8. Let R ⊂ Z p be a set of cardinal N and let λ j (X) be the associated Lagrangian polynomials and t(X) the polynomial whose roots are the elements of R. Let φ : {0, 1} n0 → {0, 1} n d , be any circuit such that N = max i=1,...,d n i . There exist some unique polynomials u L,i (X), u R,i (X), u 0,i (X) of degree at most N -1 which are efficiently computable from the circuit description and such that for any tuple

(a i , b i , c i ) ∈ ({0, 1} ni ) 3 , if i (X) = ni j=1 a j λ j (X), r i (X) = ni j=1 b j λ j (X), o i (X) = ni j=1 c j λ j (X),
it holds that a i , vecc i are consistent assignments to the left and output values of gates at level i if and only if t(X) divides p i (X), where p i (X) = i (X)r i (X) + i (X)u L,i (X) + r(X)u R,i (X) + u 0,i (X) -o i (X).

Proof. The proof is a direct consequence of Lemma 7. Indeed, it suffices to define u L,i (X), u R,i (X), u 0,i (X) to take the values u L,i (r j ) = β ij , u R,i (r j ) = γ ij and u 0,i (r j ) = ij for j = 1, . . . , n i and 0 for j = n i + 1, . . . , N . Therefore,

p i (r j ) = a ij b ij + a ij β ij + b ij γ ij + ij -c ij .
This proves that if equation (11) is satisfied then p i (X) is divisible by t(X), since it is 0 in all of its roots. Finally, the polynomials u L,i (X), u R,i (X), u 0,i (X) can be efficiently computed from the circuit description, as they depend only on N and the type of each gate.

A New Argument for Correct Boolean Circuit Evaluation

From Lemma 7, we can design an argument for boolean circuit satisfiability based on weaker assumptions, similar as in Sect. 5. The argument is based on a quadratic and a linear "knowledge transfer" subarguments. The linear argument is identical to the arithmetic case. For the quadratic argument, now the prover needs to show (aggregating the proof at each level i for j = 1, . . . , n i ) that the quadratic equations

C ij = A ij B ij + A ij β ij + B ij γ ij + ij
are satisfied, whereas before the equations were C ij = A ij B ij . However, the security proof is almost identical to the arithmetic case.

Indeed, the verification equation of the quadratic argument is adapted to the new equation type, i.e. For each level i = 1, . . . , d, and each j = 1, . . . , k s given commitments

[L ij ] 1 , [R ij ] 2 , [O ij ] 1 ,
and some value [H i,j ] 1 the quadratic argument checks if

e([L ij ] 1 , [R ij ] 2 )+e([L ij ] 1 , [u L,i (s j )] 2 )+e([u R,i (s j )] 1 , [R ij ] 2 )+e([u 0,i (s j )] 1 , [1] 2 ) -e([O ij ] 1 , [1] 2 ) = e([H ij ] 1 , [T ] 2 ),
where u L,i (X), u R,i (X), u 0,i (X) are the polynomials associated to the gate constants at level i. To prove soundness, given an opening of [L ij ] 1 and [R ij ] 2 which is not consistent with [O ij ], it suffices to compute [O ij ] 1 , [H ij ] 1 consistent with these openings and subtract the two verification equations to find a solution to the R-Rational Strong Diffie-Hellman Assumption.

Zero-Knowledge. The argument can be made zero-knowledge for the middle wires by proving with the GS proof system that the argument for correct circuit evaluation is satisfied, as discussed in Sect. 5.4 for the arithmetic case. The input can also be hidden provided it is encrypted with an extractable commitment. In the boolean case this can be done in a relatively efficient way, for example under the DDH Assyumption with GS commitments. The cost of giving the committed secret inputs and a proof that they open to {0, 1} using the GS proof system is (6(n 0 -n pub ), 6(n 0 -n pub )) group elements. It can be reduced to (2(n 0 -n pub ) + 10, 10) group elements under standard assumptions using the results of González and Ràfols [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF], but at the price of having a crs quadratic in n 0 and to (2n 0 +4, 6) with a linear crs under a non-standard (falsifiable) (n 0 -n pub )assumption similar to the q-Target Strong Diffie-Hellman Assumption using the results of Daza et al. [START_REF] Daza | Shorter quadratic QA-NIZK proofs[END_REF].

2. 1

 1 Cryptographic Assumptions Definition 1. Let k ∈ N. We call D ,k (resp. D k ) a matrix distribution if it outputs in PPT time, with overwhelming probability matrices in Z ×k p (resp. in Z (k+1)×k p

Fig. 1 .

 1 Fig. 1. Our argument for componentwise product. λi(X) is the ith Lagrange polynomial associated to R, a set of Zp of cardinal m, t(X) is the polynomial which has as roots all the elements of R. Both a and b are m-dimensional vectors in Zp.

  which are parameterized by m ∈ N and a Lagrangian Pedersen commitment key ck = ([Λ] 1 , [Λ] 2 ) and are defined as

Fig. 2 .

 2 Fig. 2. The Lin D k argument for proving membership in linear spaces. The matrix A is either sampled from a distribution D k = D k or from a distribution D k = D k , such that the D k -KerMDH assumption holds. In the latter case k = k + 1 while in former case k = k.

Fig. 3 .

 3 Fig. 3. The modified crs generation algorithm used in Lemma 3.

  and P i is defined similarly. Using the linear properties of the crs, B 2,i computes the common reference string of the full argument. 8 When it receives an accepting proof(C = ([L] 1 , [R] 2 , [O] 1 )} di=1 , Π quad , Π lin ) from adversary A for some statement (x, y), adversary B 2,i computes the full witness (a, b, c).It then checks if [O 1 ] 1 , . . . , [O i ] 1 are commitments to c 1 , . . . , c i but either [L i+1 ] 1 or [R i+1 ] 2 arenot valid commitments to a i or b i . If this is not the case, it aborts. Else it outputs (c 1 , . . . , c i

	F2,0	F2,1 ...	0	
	. . . Fi+1,0 Fi+1,1 ... Fi+1,i . . . . . . . . .	 ,

Essentially the only such commitment known is bit to bit encryption, e.g. Groth-Sahai commitments to bits.

Note that using the celebrated recent results ofPeikert and Shiehian [36] this scheme can be based solely on the LWE assumption.

There's the technicality that a verifier running in time sub-linear in the circuit size can not even read the circuit, which is part of the input of the universal circuit. For this reason, they restricted the circuits to be to log space uniform boolean cicuits

For the distribution M used in Sect. 5 this assumption is equivalent to the q-DLog assumption.

This part of the proof follows essentially the same lines of the first constant-size QA-NIZK arguments for linear spaces of Libert et al.[START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] which were later simplified and generalized byKiltz and Wee [26].

We can assume w.l.o.g. that the crs for the linear knowledge transfer associated to Mi, Ni, Pi includes {[sj]1,2} N -1 j=1 , [s N j ], as this does not compromise security.

This author was supported in part by the French ANR ALAMBIC project (ANR-16-CE39-0006). The research leading to this article was supported by a Marie Curie "UPF Fellows" Postdoctoral Grant and by Project RTI2018-102112-B-I00 (AEI/FEDER,UE)

Extension to SMDDH Assumptions

In Sect. 5 the crs needs to publish M in both groups, i.e.

In that case we can't reduce the knowledge transfer to a MDDH assumption but only to a SMDDH assumption. Note that this implies that we need to prove Lemma 3 even when the adversary is given [M] 1 , [M] 2 . But this is not a problem, since we can build an adversary for Lemma 5 against the M -SMDDH assumption. Similarly, we can prove Theorem 1 holds, even when the adversary is given

, assuming the hardness of the M -SMDDH assumption.

Extension to Bilateral Linear Languages

In Sect. 5 we need a QA-NIZK argument for bilateral linear spaces [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF], which are linear spaces splitted between G 1 and G 2 . In [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF], a QA-NIZK argument for such languages is given, which is very close to the argument of membership in (unilateral) linear spaces of [26]. In Figure (4) we describe the QA-NIZK argument of [START_REF] González | QA-NIZK arguments in asymmetric groups: New tools and new constructions[END_REF] adapted to matrices with 3 blocks. The proof of the knowledge transfer property is essentially the same as in the unilateral case and can be found in the full version of this work.

A New Argument for Correct Arithmetic Circuit Evaluation

In this section we describe our construction for proving correct evaluation of an arithmetic circuit. It makes use of two subarguments: a quadratic and a linear "knowledge transfer" subarguments. The reason why we use the term