Dario Fiore

Anca Nitulescu

David Pointcheval

Boosting Verifiable Computation on Encrypted Data

We consider the setting in which an untrusted server stores a collection of data and is asked to compute a function over it. In this scenario, we aim for solutions where the untrusted server does not learn information about the data and is prevented from cheating. This problem is addressed by verifiable and private delegation of computation, proposed by Gennaro, Gentry and Parno (CRYPTO'10), a notion that is close to both the active areas of homomorphic encryption and verifiable computation (VC). However, in spite of the efficiency advances in the respective areas, VC protocols that guarantee privacy of the inputs are still expensive. The only exception is a protocol by Fiore, Gennaro and Pastro (CCS'14) that supports arithmetic circuits of degree at most 2. In this paper we propose new efficient protocols for VC on encrypted data that improve over the state of the art solution of Fiore et al. in multiple aspects. First, we can support computations of degree higher than 2. Second, we achieve public delegatability and public verifiability whereas Fiore et al. need the same secret key to encode inputs and verify outputs. Third, we achieve a new property that guarantees that verifiers can be convinced about the correctness of the outputs without learning information on the inputs. The key tool to obtain our new protocols is a new SNARK that can efficiently handle computations over a quotient polynomial ring, such as the one used by Ring-LWE somewhat homomorphic encryption schemes. This SNARK in turn relies on a new commit-and-prove SNARK for proving evaluations on the same point of several committed polynomials. We propose a construction of this scheme under an extractability assumption over bilinear groups in the random oracle model.

Introduction

Due to the ubiquity of the Internet and the advent of cloud computing, it is increasingly common for users to exchange and receive information processed on remote machines. Online storage services are already widely available on the Internet, and allow users to store, access and share their data from anywhere and from multiple devices. This phenomenon includes not only storage: it is more and more common to rely on computation performed on third party machines.

While this shift in the computing trend brings several benefits, new security challenges also emerge. These challenges are related to a main question: what happens if the remote machine is not trusted? In this work we are particularly concerned with two security problems in this space. First, we would like to ensure that the untrusted machine can perform the computation without learning the private data of the users. Second, we would like to enable the receivers of computation results to efficiently check that such results are correct. Both problems are in the scope of two important research lines in cryptography.

Privacy-Preserving Computation. The first problem is related to fully homomorphic encryption (FHE) [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF][START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. While for a long time it was only known how to construct homomorphic encryption schemes supporting a single operation (e.g., only addition [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] or multiplication [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]), Gentry's breakthrough showed the first FHE scheme that enables computing any function on encrypted data. If Gentry's first FHE was mostly a feasibility result, research in this area has progressed significantly giving rise to many new FHE schemes (e.g., [SV10, BV11, BGV12, GSW13, DM15, CGGI16, CGGI17]) that are efficient and see their first practical applications.

Ensuring Correctness of Computation. The second problem is related to verifiable computation (VC) [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF] and related notions such as interactive proofs [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems (extended abstract)[END_REF], probabilistically checkable proofs [START_REF] Arora | Probabilistic checking of proofs; A new characterization of NP[END_REF] and succinct arguments [START_REF] Kilian | A note on efficient zero-knowledge proofs and arguments[END_REF]. Briefly speaking, these are protocols that enable a powerful prover to convince a verifier that a statement (e.g., correctness of a computation, y " f pxq) is true in such a way that the verifier can run with fewer resources, e.g., faster than re-executing the function. Similarly to FHE, also in this research area, results have been confined to theory for long time. However, several recent works have shown a change in this trend, and today we have several VC protocols that are efficient and have been experimented in practical scenarios, see e.g., [GKR08, CMT12, GGPR13, PHGR13, BCG `13, Gro16, ZGK `17, WJB `17, AHIV17, WTs `18, BCG `18, BBC `18, BCR `19, MBKM19, CFQ19, XZZ `19].

Ensuring Correctness of Privacy-Preserving Computation

In spite of the research mentioned above, the problem of ensuring both the correctness and the privacy of computation performed on untrusted machines has received much less attention in the literature. There are three main works that considered explicitly this problem.

The first one is the seminal paper of Gennaro et al. [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF] who introduced the notion of non-interactive verifiable computation. In [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF] they indeed show how to combine garbled circuits and FHE in order to build a VC scheme for arbitrary functions that also preserves the privacy of the computation's inputs and outputs against the computing machine.

The second work is that of Goldwasser et al. [GKP `13] that shows how to use their succinct single-key functional encryption scheme in order to build a VC protocol that preserves the privacy of the inputs (but not of the outputs).

Both these two solutions [GGP10, GKP `13] are however not very satisfactory in terms of efficiency. The main issue in the construction of [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF] is that they need the full power of FHE to perform homomorphic evaluations of garbled circuits. Some of the efficiency issues in [GKP `13] include the use of several instances of an attribute-based encryption that must support an expressive class of predicates (at NC1 circuits), and an inherent design limitation (due to following the approach of [START_REF] Parno | How to delegate and verify in public: Verifiable computation from attribute-based encryption[END_REF]) by which their scheme supports functions with a single bit of output (which in practical scenarios like computing on large integers would require multiple instances of their protocol).

A third work that considered the problem of ensuring correctness of privacy-preserving computation is the one of Fiore et al. [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] who proposed a solution that combines an FHE and a VC scheme. The idea of their generic construction is rather simple and consists into using a VC in order to prove that the homomorphic evaluation on ciphertexts has been done correctly. As discussed in [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF], even this solution may encounter efficiency limits. This is due to the fact that the VC scheme must be executed on a computation that, due to the FHE ciphertext expansion, is of much larger representation than the computation that would be executed on plain text. Motivated by this issue, [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] also proposed an efficient solution that, for the case of quadratic functions, can avoid this issue. The efficient construction in [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] overcomes the problem of ciphertext expansion in two ways: (1) they consider homomorphic encryption schemes working in the Ring-LWE setting in which ciphertexts are represented by polynomials in a given polynomial ring; (2) they develop, as the VC building block, an homomorphic MAC scheme especially tailored to handle messages that are polynomials in which the prover execution can be independent of the degree of such polynomials. However, for reasons that we will detail later (see Section 3), their technique is inherently bound to computations of multiplicative depth 1. Also, by using an homomorphic MAC as VC, verification requires a secret key, the same secret key used to encode the inputs. This limits the applicability of these solutions to scenarios where users and verifiers are either the same entity or they share a secret key.

Our Contributions

We propose a new protocol for verifiable computation on encrypted data that improves on the state-of-the-art solution of Fiore et al. [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] in multiple aspects. Notably, we can support HE computations of multiplicative depth larger than 1. Second, we achieve public verifiability whereas [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] is only privately verifiable. Finally, our scheme has an additional property that guarantees that verifiers may be convinced of outputs correctness without learning information on the original inputs. This latter property is particularly relevant in the publicly verifiable setting where the users who encrypt the data and the verifiers are distinct entities. Technically, we achieve this property because our protocol allows for re-randomizing the encrypted results, which was not possible in [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] that only considered deterministic HE evaluations.

Our key tool to obtain this result is a new SNARK that can efficiently handle computations that are arithmetic circuits f over a quotient polynomial ring R q :" Z q rXs{xRpXqy (exactly like the popular choice for many Ring-LWE schemes) in which the prover's costs have a minimal dependence on the degree d of RpXq. Specifically, let f be the circuit over R q and f be the corresponding circuit over Z q (i.e., the one that would be computed on plaintexts where additions and multiplications in R q are replaced by the corresponding operations in Z q ). Then, whereas a naive application of [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF]'s generic solution would incur a cost for proof generation at least Opd ¨| f |q where | f | is f 's circuit size, our scheme lets proof generation be doable in time Opd ¨n `| f |q where n is f 's input size. We stress that here we are considering the cost of proof generation, after having performed the HE computation; or in other words we consider the cost of generating the proof once the witness is available. To see how this efficiency feature concretely improves, consider for example an f that is a multivariate polynomial of degree c ě 2 by which | f | can be n c , and consider that for Ring-LWE security the degree d can be a rather large integer (e.g., d « 8000). Then removing the multiplicative factor d ¨| f | can significantly speed up the prover's costs. Let us also notice that the factor d ¨n is unavoidable as the prover must read the input.

Our SNARK for arithmetic circuits over polynomial rings is built in a modular way using two building blocks: a commit-and-prove SNARK for arithmetic circuits (AC-Π), and a commitand-prove SNARK for multiple polynomial evaluations (MUniEv-Π).

To instantiate AC-Π, we can use any commit-and-prove SNARK for arithmetic circuits that supports the same commitment key as our scheme MUniEv-Π. Given the recent result of Campanelli et al. [START_REF] Campanelli | LegoSNARK: Modular design and composition of succinct zero-knowledge proofs[END_REF], MUniEv-Π can be instantiated with a variety of schemes including the efficient commit-and-prove variant of Groth16 [START_REF] Groth | On the size of pairing-based non-interactive arguments[END_REF] proposed in [START_REF] Campanelli | LegoSNARK: Modular design and composition of succinct zero-knowledge proofs[END_REF].

For scheme MUniEv-Π, we propose a construction based on the Strong Diffie-Hellman and Power Knowledge of Exponent (PKE) assumptions in bilinear groups, in the random oracle model. We believe this scheme can also have other applications. Slightly more in detail, MUniEv-Π allows one to prove the following statement: given a commitment C to degree-d polynomials tP j pXqu j , a commitment C 1 to a vector of Z q -elements tp j u j , and a public point k, show that p j " P j pkq for all j " 1 to . In comparison to using an existing general-purpose commit-and-prove SNARK for arithmetic circuits (e.g., LegoGroth16 from [CFQ19]), our scheme MUniEv-Π has slightly smaller proofs and proving time at least three times faster (cf. Section 7.3 for more details).

Finally, we note that our scheme MUniEv-Π is in turn constructed from a SNARK BivPE-Π for the partial evaluation of a committed bivariate polynomial, i.e., given commitments C and C 1 to P pX, Y q and QpY q respectively, prove that QpY q " P pk, Y q for some public point k. We construct BivPE-Π by extending the univariate polynomial commitment techniques of Kate et al. [START_REF] Kate | Constant-size commitments to polynomials and their applications[END_REF]. It is worth mentioning that other works [START_REF] Papamanthou | Signatures of correct computation[END_REF]ZGK `17] extended [START_REF] Kate | Constant-size commitments to polynomials and their applications[END_REF] to support the evaluation of multivariate polynomials, which include bivariate ones. However, the main difference (crucial for our application) is that we can support partial evaluations in one variable while keeping the result polynomial also committed.

Organization

In Section 2 we introduce notation and basic cryptographic definitions. Section 3 describes our SNARK for arithmetic computations in quotient polynomial rings. In Section 4 we show how to combine our SNARK from Section 3 together with Ring-LWE-based HE schemes in order to build a verifiable computation scheme with input and output privacy, and also how to achieve the new property of preserving privacy of the inputs from the verifier. In Section 5 we state the computational assumptions needed by our schemes, and we present the BivPoly.Com commitment. In Section 6 we build our SNARK BivPE-Π for bivariate polynomials partial evaluation and then in Section 7 we show how turn it into an efficient MUniEv-Π for the simultaneous evaluation of many univariate polynomials. In Section 8 we prove the security of our scheme BivPE-Π.

Notation and Definitions

Notation. Let λ P N be the computational security parameter. We say that a function is negligible in λ, and we denote it by negl, if it is a f pλq " opλ ´cq for every fixed constant c. We also say that a probability is overwhelming in λ if it is 1 ´negl. When sampling uniformly at random the value a from the set S, we employ the notation a Ð$ S. When sampling the value a from the probabilistic algorithm M, we employ the notation a Ð M. We use :" to denote assignment. We consider NP binary relations R between statements u and witnesses w.

An adversary is denoted by A and is assumed to be probabilistic Turing machines that run in polynomial time, i.e., PPT. For two PPT machines A, B, with the writing pA}Bqpxq we denote the execution of A followed by the execution of B on the same input x and with the same random coins.

Commitment Schemes

For completeness, we recall the definition of a knowledge commitment scheme: Definition 1 (Non-Interactive Commitment). A non-interactive commitment scheme is a tuple of algorithms Com " pComGen, Com, ComVer, OpenVerq: ComGenp1 λ q Ñ ck: Generates a commitment public key ck. It specifies a message space M ck , a randomness (opening) space R ck , and a commitment space C ck . This algorithm is run by a trusted or distributed authority; Compck, mq Ñ pc, oq: Outputs a commitment c and an opening information o. Given a message m P M ck , the sender picks a randomness o P R ck and computes the commitment pc, oq. ComVerpck, cq Ñ 0{1: Checks whether c is a well-formed commitment. If so, it outputs 1, otherwise it outputs 0; OpenVerpck, c, m, oq Ñ 0{1: Outputs 1 if the value m P M ck is the committed message in the commitment c and 0 if pm, o, cq does not correspond to a valid pair opening-commitment.

We say Com " pComGen, Com, ComVer, OpenVerq is a secure commitment scheme if it satisfies the following properties:

Correctness. Let ck Ð ComGenp1 λ q. Any commitment of m P M ck honestly generated pc, oq Ð Compck, mq is successfully verified by ComVerpck, cq and by OpenVerpck, c, m, oq. Hiding. It is statistically hard, for any adversary A, to generate two messages m 0 , m 1 P M ck such that A can distinguish between their corresponding commitments c 0 and c 1 where pc 0 , o 0 q Ð Compck, m 0 q and pc 1 , o 1 q Ð Compck, m 1 q. Binding. It is computationally hard, for any adversary A, to come up with a collision pc, m 0 , o 0 , m 1 , o 1 q, such that o 0 and o 1 are valid opening values for two different pre-images m 0 ‰ m 1 for c. For any adversary A, the following probability is negligible

Pr » - OpenVerpck, c, m 0 , o 0 q " 1 ck Ð ComGenp1 λ q ^OpenVerpck, c, m 1 , o 1 q " 1 pc, pm 0 , o 0 q, pm 1 , o 1 qq Ð Apckq ^m0 ‰ m 1 fi fl .
Knowledge Binding [START_REF] Buldas | Knowledge-binding commitments with applications in time-stamping[END_REF]. For every adversary A that produces a valid commitment c associated to a message that verifies, i.e. such that ComVerpck, cq " 1, there is an extractor Ext A that is able to output a pre-image m and a valid opening o of c, with overwhelming probability:

Pr » - ck Ð ComGenp1 λ q OpenVerpck, c, m, oq " 1 pc; pm, oqq Ð pA}Ext A qpckq ComVerpck, cq " 1 fi fl " 1 ´neglpλq.
For the sake of simplicity, throughout this work, we will omit the commitment key ck from the input of the algorithms, and with a slight abuse of notation, we will adopt the writing Compmq Ñ pc, oq.

SNARKs -Succinct Non-Interactive Arguments of Knowledge

We recall the definition of (zero-knowledge) succinct non-interactive arguments of knowledge (zk-SNARKs).

Definition 2 (SNARK for NP). A SNARK is defined by three algorithms, Π.Genp1 λ , Rq Ñ crs: on input a security parameter λ P N and a NP relation R, the generation algorithm outputs a common reference string crs; Π.Provepcrs, u, wq Ñ π: given a prover reference string crs, an instance u and a witness w s.t.

pu, wq P R, this algorithm produces a proof π; Π.Verpcrs, u, πq Ñ b: on input a verification state crs, an instance u, and a proof π, the verifier algorithm outputs b " 0 (reject) or b " 1 (accept); satisfying completeness, succinctness, knowledge-soundness as described below:

Correctness. For all valid statement pu, wq P R, Pr " Verpcrs, u, πq " 0 crs Ð Π.Genp1 λ , Rq ^pu, wq P R π Ð Provepcrs, u, wq

 " neglpλq;
Succintness. The size of the proof is linear in the security parameter λ, i.e. independent of the size of the computation or the witness; Knowledge-Soundness [START_REF] Bellare | On defining proofs of knowledge[END_REF]. A non-interactive proof system Π is knowledge-sound for the class Z of auxiliary input generators if for any PPT adversary A KS there exists an extractor Ext A such that:

Pr " Verpcrs, u, πq " 1 crs Ð Π.Genp1 λ , Rq, aux Ð Zpcrsq ^Rpu, wq " 0 ppu, πq; wq Ð pA KS }Ext A qpcrs, auxq  " neglpλq.

Zero Knowledge. A Π protocol is a (statistical) zero-knowledge for a relation R if there exists a stateful interactive polynomial-size simulator Sim " pSim crs , Sim Prove q such that for all stateful interactive distinguishers D, for every large enough security parameter λ P N, every auxiliary input aux, the two probabilities are negligibly close:

Prrpu, wq P R ^Dpπq " 1 pcrsq Ð Genp1 λ q, pu, wq Ð Dpcrs, auxq, π Ð Provepcrs, u, wqs;

Prrpu, wq P R ^Dpπq " 1 pcrs, trapq Ð Sim crs p1 λ q, pu, wq Ð Dpcrs, auxq, π Ð Sim Prove pcrs, trap, u, auxqs.

Commit and Prove SNARKs. Let Rpu, wq be an NP relation where w " ptx i u i , ωq. A commit-and-prove SNARK (CaP-SNARK) for commitment scheme Com and relation Rpu, wq is a SNARK for the "commit-and-prove relation" R ck pu ˚, w ˚q where u ˚" pu, tc i u i q, w ˚" ptx i u i , to i u i , ωq and that holds iff Rpu, ptx i u i , ωqq holds and OpenVerpc i , m i , o i q " 1 for all i. We adopt the syntax for CaP-SNARK used in [CFQ19]: Π.Genpck, Rq Ñ crs: on input a relation-independent commitment key ck and a NP relation R, it generates the crs; Π.Provepcrs, pu, tc i u i q, ptx i u i , to i u i , ωqq Ñ π: outputs a proof; Π.Verpcrs, pu, tc i u i q, πq Ñ b: rejects or accepts the proof.

Proof Systems for Arithmetic Function Evaluation over Quotient Polynomial Rings

In this section we describe our commit-and-prove SNARK for arithmetic computations in quotient polynomial rings.

Let R be the quotient ring Z{xRpXqy for some polynomial R P ZrXs of degree d. For a prime q " d we define F " Z q a finite field and R q " R{qR. We want to construct a succinct non-interactive zero-knowledge argument system for some relation R f of correct evaluation of an arithmetic function f p¨q : R q n Ñ R q taking n P N inputs in the quotient ring R q " R{qR. The function f to be evaluated on polynomials tP j u n j"1 in the quotient ring R q is considered to be public.

Let MPoly-Com " pMPoly.ComGen, MPoly.Com, MPoly.ComVer, MPoly.OpenVerq be a linearly homomorphic commitment scheme for (many) univariate polynomials, i.e., the message space M consists in vectors of n ď polynomials of degree d ď ν, for some integer bounds , ν chosen in MPoly.ComGen. In Section 7 we show an efficient instantiation of such a scheme in bilinear groups.

We describe a Commit-and-Prove SNARK, Rq-Π, for commitment scheme MPoly-Com and for the following relation R ck f :" tpu " pC, P q; w " ptP j u n j"1 , ρ, T qq : MPoly.OpenVerpC, tP j u, ρq " 1 ^P " f pP j q ´T Ru The relation R ck f implicitly contains two bounds , ν on, respectively, the number of inputs of f and the degree d f of f as an arithmetic circuit.

In a nutshell, given a compact commitment C and a public polynomial P P R q , our Rq-Π scheme allows to prove that C opens to some polynomials P j P R @j " 1 . . . n such that P is the result of evaluating the function f on tP j u j , evaluation done in the polynomial ring R q .

High-Level Description of our Rq-Π SNARK. We build our Rq-Π scheme as a combination of the following building blocks:

-MUniEv-Π " pMUniEv-Π.Gen, MUniEv-Π.Prove, MUniEv-Π.Verq: a CaP-SNARK for the simultaneous evaluation of n univariate polynomials tP j u n j"1 in a point k, where tP j u are committed with MPoly-Com. Proposing efficient constructions of MPoly-Com and MUniEv-Π are key technical contributions of this paper; these are detailed in Section 7.

-AC-Π " pAC-Π.Gen, AC-Π.Prove, AC-Π.Verq: a CaP-SNARK for arithmetic circuits over Z q where inputs and outputs are committed (as a vector of degree-0 polynomials) with the MPoly-Com scheme.

Various instantiations of AC-Π compatible with our pairing-based MPoly-Com commitment can be obtained by using for example the compiler recently proposed in [START_REF] Campanelli | LegoSNARK: Modular design and composition of succinct zero-knowledge proofs[END_REF];1 a particularly efficient one is a commit-and-prove variant of [START_REF] Groth | On the size of pairing-based non-interactive arguments[END_REF].

The two building blocks above are used as follows.

The prover, knowing a quotient polynomial T P Z q rXs such that f ppP j q j q " P `T R, starts by computing a commitment C T to T P Z q rXs (which may have degree higher than that of R).

Next, the key idea is that instead of directly proving that P " f ppP j q j q´T R for the committed polynomials tP j u and T (that would require to work with a large arithmetic circuits f ), we use the homomorphic properties of the polynomial ring Z q rXs to "compress the computation". Namely, to prove P " f ppP j q j q ´T R, we evaluate all the polynomials in a random point k and then prove the relation on the resulting scalars, using the fact that: f pP j pkqq ´RpkqT pkq " pf pP j q ´RT qpkq " P pkq.

where f : Z n q Ñ Z q is an arithmetic circuit that is the same as f except that every addition (resp. multiplication) in R q is replaced by an addition (resp. multiplication) in Z q .

This idea is similar to the homomorphic hash function defined by Fiore et al. [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF]. In [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF], they let this idea work by evaluating the polynomials "in the exponent", i.e., they publish a set of group elements g k i , and then they compute homomorphically over these encodings to get g P pkq .

This technique however hits two problems: first, they cannot deal with reductions modulo RpXq, and second, to compute homomorphically a multiplication on these encodings, they have to "consume" a pairing, and thus only degree-2 computations can be supported.

In our case, we solve these issues by exploiting the power of the commit and prove paradigm in order to obtain, for every evaluation, a fresh random k. Then, having k P Z q allows us to support higher-degree computations as well as to deal with modular reductions.

To proceed with the protocol, the prover thus needs to get a random point k, not of its choice and independent of the values committed in C T and C and of the statement P . This is possible by using a random oracle Hash to obtain a value k on which it evaluates the polynomials tP j pkq " p j u n j"1 , Rpkq " r, P pkq " p and T pkq " t 1 . Next, the prover compactly commits to the respective evaluations of the polynomials pT, tP j u n j"1 q as pC 1 , ρ 1 q. At this point the prover will use:

1. the MUniEv-Π scheme to prove that C 1 is a commitment to a vector of n`1 scalars pt, tp j u n j"1 q that are the results of evaluating in point k a vector of n `1 polynomials pT, tP j u n j"1 q that are committed in C T ˆC; Remark 3. We consider linearly homomorphic commitment schemes MPoly-Com and we commit in C T and C to vectors of n `1 ď polynomials pC T , τ q Ð MPoly.CompT, 0, 0 . . . 0q and pC, ρq Ð MPoly.Comp0, tP j u n j"1 q with an appropriate number of 0's, i.e., pT, tP j uq " pT, t0uq `p0, tP j uq, such that computing C T ˆC results in a commitment pC T ˆC, τ `ρq Ð MPoly.CompT, tP j u n j"1 q to the concatenation of T , tP j u.

2. the AC-Π scheme to prove that p " P pkq " f ppp j q j q ´rt 1 , and that t 1 , tp j u n j"1 are openings of C 1 . More formally, the algorithms of the protocol are described in Figure 1. A detailed intuition of the functionalities of each algorithm follows.

3.1 Formal Description of Our Rq-Π Scheme.

We construct a commit-and-prove SNARK scheme Rq-Π " pGen, Prove, Verq for any relation R ck f with respect to some bounds , ν on the cardinality of tP j u j and on the degree d f of f . Rq-Π.Genpck, R ck f q Ñ crs 1: crsC Ð MUniEv-Π.Genpck, R eval q, crs 1 Ð AC-Π.Genpck, Rf q 2: return crs :" pcrsC , crs 1 q Rq-Π.Provepcrs, x, wq 1: pC, P q :" x, ptPju n j"1 , ρ, T q :" w 2: pCT , τ q Ð MPoly.CompT q 3: k Ð HashpC, P, CT q 4: p " P pkq, r " Rpkq, 5: t 1 " T pkq, pj " Pjpkq 6: pC 1 , ρ 1 q Ð MPoly.Compt 1 , tpjuq 7: uC :" pCT ˆC, C 1 , kq 8: πC Ð MUniEv-Π.ProvepcrsC , uC , wC q, 9: π 1 Ð AC-Π.Provepcrs 1 , u 1 " pC 1 , p, rq, w 1 q 10: returns π " pCT , C 1 , πC , π 1 q Rq-Π.Verpcrs, x " pC, P q, πq 1: π :" pCT , C 1 , πC , π 1 q 2: k Ð HashpC, P, CT q 3: p :" P pkq, r :" Rpkq 4: uC :" pCT ˆC, C 1 , kq 5: u 1 :" pC 1 , p, rq 6: bC Ð MUniEv-Π.VerpcrsC , uC , πC q 7: b 1 Ð AC-Π.Verpcrs 1 , u 1 , π 1 q 8: return pbC ^b1 q " 1.

Fig. 1. Our SNARK Rq-Π for Evaluations over Polynomial Rings

Relations for MUniEv-Π and AC-Π. We define the intermediate statements R eval , Rf to be proven using the two SNARKs, MUniEv-Π and AC-Π: R eval : We first define the relation for simultaneous evaluation of multiple polynomials on a point k, to be supported by MUniEv-Π. The prover has to convince the verifier that for a given point k (that in our case is random, but part of the statement) and two commitments C T ˆC and C 1 , it knows the corresponding opening values pT, tP j u j , τ `ρq and pt 1 , tp j u j , ρ 1 q such that P j pkq " p j for all j, and T pkq " t 1 .

More formally, MUniEv-Π.Prove takes as input a statement u C " pC T ˆC, C 1 , kq, and a witness w C " ppT, tP j uq, pt 1 , tp j uq, τ `ρ, ρ 1 q, and R eval holds for pu C , w C q iff: R eval :" tpu C , w C q :@j, p j " P j pkq ^t1 " T pkq ^pC 1 , ρ 1 q " MPoly.Compt 1 , tp j uq ^pC T ˆC, τ `ρq " MPoly.CompT, tP j u j qu.

Rf : We define the relation for correct computation of f , to be supported by AC-Π. The prover has to convince the verifier that an equality holds for some scalar values t 1 , tp j u, p, r P Z q . The inputs p, r are known by the verifier (they are public) and t 1 , tp j u are given implicitly in a committed form pC 1 , ρ 1 q " MPoly.Compt 1 , tp j uq. More formally, given a statement u 1 " pC 1 , p, rq and a witness w 1 " pρ 1 , t 1 , tp j uq for the computation p " f pp j q ´rt 1 and for the opening of C 1 , the relation is defined as follows:

Rf :" tpu 1 , w 1 q : p " f pp j q `rt 1 ^pC 1 , ρ 1 q " MPoly.Compt 1 , tp j uqu.

CRS Generation. The setup algorithm Rq-Π.Genpck, R ck f q, given a commitment key ck Ð MPoly.ComGenp1 λ q that supports commitments up to different polynomials P j P R q (all of degrees ď d) and one commitment to a polynomial T P Z q rXs of higher degree (up to ν)2 and the NP relation R ck f including the bound parameters , ν, outputs a crs enabling the proof and verification of a function f of degree d f ă ν over a set of polynomials tP j u n j"1 of cardinality n ď .

First it runs the generation algorithm for MUniEv-Π and computes a part of the setup, crs C Ð MUniEv-Π.Genpck, R eval q.

Then it generates a common reference string for AC-Π that will be used for proving computations of f : crs 1 Ð AC-Π.Genpck, Rf q. As an observation, AC-Π assumes commitments to vectors of scalars; these can be done with MPoly-Com, by seeing them as vectors of degree-0 polynomials.

Prover. Given a reference string crs, statement u " pC, P q and witness w " ptP j u n j"1 , ρ, T q where P is a public polynomial, C is a compact commitment to polynomials tP j u n j"1 P R q with opening ρ, and T P Z q rXs is a quotient polynomial, the prover algorithm produces a proof π that f ppP j q j q " P `T R as follows:

-The prover commits to T " ř ν i"0 T i X i : pC T , τ q Ð MPoly.CompT q. -The prover then runs k Ð HashpC, P, C T q to obtain a random value k.

-The prover evaluates the polynomials in k : tP j pkq " p j u n j"1 , Rpkq " r, P pkq " p and T pkq " t.

-The prover commits the respective evaluations t 1 , tp j u n j"1 as pC 1 , ρ 1 q Ð MPoly.Compck, t 1 , tp j u n j"1 q. -The prover runs the algorithm for MUniEv-Π to prove that the opening values t 1 , tp j u of the commitment C 1 are evaluation in k of the polynomials T, tP j u, committed in C T ˆC :

π C Ð MUniEv-Π.Provepcrs C , u C , w C q
where u C " pC T ˆC, C 1 , kq, w C " ppT, tP j uq, pt 1 , tp j uq, τ `ρ, ρ 1 q.

-It then runs the proving algorithm of AC-Π for proving the evaluation of f on scalars with a witness w 1 for the computation p " f pp j q ´rt and for the opening of C 1 :

π 1 Ð AC-Πpcrs 1 , u 1 " pC 1 , p, rq, w 1 q.
-The prover eventually outputs π " pC T , C 1 , π C , π 1 q.

Verifier. The algorithm Ver on input a statement u " pC, P q and a proof π :" pC T , C 1 , π C , π 1 q recomputes the randomness k by running k Ð HashpC, P, C T q. Then the Verifier has only to evaluate the known polynomials P, R in k obtaining p :" P pkq, r :" Rpkq. Once it has all the elements to redefine the two statements u C :" pC T ˆC, C 1 , kq and u 1 :" pC 1 , p, rq for the proofs π C and π 1 it runs the corresponding verification algorithms of these two SNARKs, MUniEv-Π.Ver and AC-Π.Ver to check the proofs and outputs the conjunction of the two answers.

Security Analysis

About the above construction, we can state the following security result.

Theorem 4. Assuming that AC-Π and MUniEv-Π are secure commit-and-prove arguments of knowledge, the new construction Rq-Π described above satisfies completeness, succinctness, zero-knowledge and knowledge-soundness.

Proof. Before diving in the technicalities of the security proof, we provide a short intuition for the knowledge soundness property. The proof consists of two main steps: First, we rely on the knowledge-soundness of the two SNARKs to show that for any adversary creating an accepting proof there is a knowledge extractor that, with all but negligible probability, returns witnesses that correctly satisfy the two relations R eval , Rf mentioned previously. Second, the only remaining possibility is that the polynomial V " P ˚´f pP j q `T R is nonzero. However, V pkq " 0 and this holds for a random point k sampled by the random oracle independently of V , which can happen only with probability degpV q{q which is negligible.

Correctness. We aim to prove that under the hypothesis that the commitment pC, ρq on tP j u j open correctly and the two SNARKs are secure, the previous protocol is correct, proving the evaluation of f on polynomials P j in the ring R q . Correctness of the protocol follows from the correctness of MUniEv-Π and AC-Π schemes. If the prover follows the protocol as expected, the commitments C T , C 1 are correctly computed, the two proofs π C , π 1 are generated honestly, then from the correctness of the two SNARK the verification algorithm accepts with overwhelming probability.

Knowledge Extractor. First we build for any PPT adversary A against the SNARK a knowledge-extractor Ext A that runs on the same input as the adversary A. Moreover, whenever A outputs px " pC, P q, πq where π is a proof that verifies, the extractor Ext A produces a corresponding witness w " ptP j u n j"1 , ρq. To this end, we should show that from any A we can define two adversaries M.A and Π.A for the MUniEv-Π and AC-Π schemes respectively. These adversaries are simply defined: First, from the input crs, aux of adversary A, we can redefine their own crs's and auxiliary information.

M.A just takes the crs C and redefines the remaining elements as aux C . Π.A proceeds similarly, partitions the elements in crs as follows: pcrs 1 , aux 1 q. Next, both M.A and Π.A execute A, get its output π " pC T , C 1 , π C , π 1 q and return as respective outputs the subpart π C and π 1 of the proof π.

By the knowledge soundness of the two schemes MUniEv-Π and AC-Π we can deduce that there exist respective extractors M.Ext and Π.Ext that output the respective witnesses w C " pT, tP j u, t 1 , tp j u, ρ, τ, ρ 1 q and w 1 .

From these two extractors we define Ext A by keeping only parts of the witnesses: w :" ptP j u, ρq. Finally, by the knowledge soundness of MUniEv-Π and AC-Π schemes, we have that for an accepting proof π C , respectively π 1 , the extractors M.Ext and Π.Ext return a wrong witness w C , w 1 with negligible probability, and consequently, the same holds also for Ext A .

Remark 5. Notice that we require in the knowledge soundness Theorem 2 the extractor Ext A to take the same input as the adversary A. In our specific case, A is an adversary with black-box acces to a random oracle Hash. We may consider the slightly different knowledge soundness definition for oracle SNARKs (OSNARKs) from [START_REF] Fiore | On the (in)security of SNARKs in the presence of oracles[END_REF]. Fortunately, in the same work, the authors show a positive result on the existence of such OSNARKs for (pseudo)random oracles, based on classical SNARKs that are assumed to satisfy proof of knowledge with respect to randomly-distributed auxiliary input. This way we can deal with black-box access to Hash, as such hash function can be simulated with a random string as auxiliary input.

Soundness. Above we have basically shown that for every A there exists an extractor Ext A that with all but negligible probability returns a witness such that the two statements are valid. In particular, the knowledge soundness of the MUniEv-Π gives us that the values t 1 , tp i u are correct evaluations in point k of the polynomials T, tP j u n j"1 , while the knowledge soundness of CaP ´Π gives us that p ˚´f pp j q `t1 r " 0. The only remaining possible case, in which the adversary A would be successful in cheating is if the polynomial V " P ˚´f pP j q `T R is not zero. However, p ˚´f pp j q `t1 r " 0 means that V pkq " 0.

Based on our choice of q " d and the random choice of k P Z q we can argue that PrrV pkq " 0s " negl.

Indeed, the probability that the random point k generated by the random oracle Hash, after (and thus independently) of the values C, P, C T , to be a root of the non-zero polynomial V is degpV q{q which is negligible, since the degrees of the polynomials are assumed to be bounded by polypλq.This shows that V must be the zero polynomial.

Zero-Knowledge. We have to construct a simulator Sim " pSim crs , Sim Prove q as in the Theorem 2, using the zero-knowledge simulators of the underlying SNARKs: pSim crs C , Sim MUniEv-Π.Prove q, pSim crs 1 , Sim Π q as follows:

Sim crs is the same as Gen, but for the two specific crs C and crs 1 that are generating by running respectevely pcrs C , trap C q Ð Sim crs C p1 λ q and pcrs 1 , trap 1 q Ð Sim crs 1 p1 λ q for the two zero-knowledge SNARKs.

Provepcrs, x, wq 1: pC, P q :" x, ptPiu n i"1 , ρ, T q :" w 2: pCT , τ q Ð MPoly.CompT q 3: k Ð HashpC, P, CT q 4: p " P pkq, r " Rpkq, 5: t 1 " T pkq, pi " Pipkq 6: pC 1 , ρ 1 q Ð MPoly.Compt 1 , tpiuq 7: uC :" pCT , C, C 1 , kq 8: πC Ð MUniEv-Π.ProvepcrsC , uC , wC q, 9: π 1 Ð AC-Π.Provepcrs 1 , u 1 " pC 1 , p, rq, w 1 q 10: returns π " pCT , C 1 , πC , π 1 q Sim Prove pcrs, xq 1: pC, P q :" x 2: pC0, τ q Ð MPoly.Comp0q 3: k Ð HashpC, P, C0q 4: p " P pkq, r " Rpkq, 5: t ˚" 0, p i " 0 6: pC ˚, ρ 1 q Ð MPoly.Compt ˚, tp i uq 7: uC :" pC0}C, C ˚, kq 8: πC Ð Sim MUniEv-Π.Prove pcrsC , trap C , uC q, 9: π 1 Ð Sim Π pcrs 1 , trap 1 , u 1 " pC ˚, p, rqq 10: returns π " pC0, C ˚, πC , π 1 q Fig. 2. A Simulator for the Zero-Knowledge.

Then, Sim Prove is able to generate a simulated proof for any commitment C and any polynomial P P R q by committing any T ˚P Z q rXs (we can use T ˚:" 0) and then using the simulators for the zero-knowledge of the two underlying SNARKs. We proceed with a sequence of games in order to show the indistinguishability of the simulation.

Hybrid 0. This is the real protocol, described in Figure 2, where proof π is generated by Prove algorithm. Hybrid 1. In this game, we still use the witness of the evaluation, w " ptP i u n i"1 , ρq, and we generate pC T , τ q Ð MPoly.Compck, T q as in step 2 of the real protocol, but in order to generate the proof π, we run instead the zero-knowledge simulators for the two SNARKs, pSim crs C , Sim MUniEv-Π.Prove q and pSim crs 1 , Sim Π q. Based on the fact that MUniEv-Π and AC-Π are zero-knowledge schemes, the two games are perfectly indistinguishable. Hybrid 2. The Sim Prove algorithm described in Figure 2 outputs the proof. Based on the perfectly hiding property of the commitment scheme MPoly-Com the values C 0 and C T as well as C ˚and C 1 in the two hybrids are indistinguishable.

[ \

Applications to Computing on Encrypted Data

In this section we detail on how we can use our scheme Rq-Π for computations over polynomial rings to build a VC scheme with input and output privacy.

Verifiable Computation

Here we recall the notion of verifiable computation from [START_REF] Gennaro | Non-interactive verifiable computing: Outsourcing computation to untrusted workers[END_REF]. We adapt the definitions to fit the setting (that is in the scope of our construction) where we have public verifiability and public delegatability [START_REF] Parno | How to delegate and verify in public: Verifiable computation from attribute-based encryption[END_REF], as well as privacy of the inputs and outputs. A VC scheme VC " pKeyGen, ProbGen, Compute, Verify, Decodeq consists of the following algorithms:

KeyGenp1 λ , f q Ñ pP K f , SK f q: Given the security parameter, the key generation algorithm outputs a public key and a matching secret key for the function f . ProbGen P K f pxq Ñ pσ x , τ x q: The problem generation algorithm uses the public key P K f to encode the input x into a public value σ x , to be given to the computing party, and a public value τ x to be given to the verifier. Compute P K f pσ x q Ñ σ y : Given the public key P K f and the encoded input, the compute algorithm returns an encoded version of the function's output. Verify P K f pτ x , σ y q Ñ acc: Given the public key P K f for function f , and the public verifier information τ x , the verification algorithm accepts (output acc " 1) or rejects (output acc " 0) an output encoding σ y .

Decode SK f pσ y q Ñ y: Given the secret key SK f for function f , and an output encoding σ y , the decoding algorithm outputs a value y.

The correctness of a VC scheme is the obvious property: if one runs Compute on an honestly generated input encoding of x, then the output must verify and its decoding should be y " f pxq.

For security, intuitively we want to say that an adversary that receives the public parameters for a function f and an encoding of an input x cannot create an encoding that passes verification and decodes to y 1 ‰ f pxq. More formally, we say that a publicly verifiable computation scheme VC is secure for a function f , if for any PPT adversary A, we have that PrrExp P ubV erif A rVC, f, λs " 1s " neglpλq, where the experiment Exp P ubV erif is described below. The input privacy notion intuitively says that no information about the inputs is leaked. This is defined using a typical indistinguishability experiment. Note that input privacy implies also output privacy. More formally, we say that a publicly verifiable (and publicly delegatable) VC scheme VC is private for a function f , if for any PPT adversary A, we have that PrrExp P riv A rVC, f, λs " 1s ď 1 2 `neglpλq, where the experiment Exp P riv is described below.

Experiment

Exp P ubV erif A rVC, f, λs pP K, SKq Ð KeyGenp1 λ , f q; x Ð ApP K f q; pσ x , τ x q Ð ProbGen P K f pxq; σy Ð ApP K f , σ x , τ x q; â cc Ð Verify P K f pτ x , σy q ŷ Ð Decode SK f pσ y q If â cc " 1 and ŷ ‰ f pxq, output '1', else '0'; Experiment Exp P riv A rVC, f, λs b Ð t0, 1u; pP K f , SK f q Ð KeyGenp1 λ , f q; px 0 , x 1 q Ð ApP K f q pσ b , τ b q Ð ProbGen P K f px b q; b Ð ApP K f , σ b q If b " b, output '1', else '0'

Our VC Scheme

We describe our VC scheme below. The construction is essentially an instantiation of the generic solution of Fiore et al. [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF] when using an homomorphic encryption scheme whose homomorphic evaluation algorithm fits our relation R f . This can be obtained by using HE schemes in the Ring-LWE setting where the ciphertext space works over the same ring R q supported by our Rq-Π construction, and where the evaluation algorithm does not involve modulus switches and rounding operations. An example of such a scheme is the one of Brakerski and Vaikunthanatan [START_REF] Brakerski | Fully homomorphic encryption from ring-LWE and security for key dependent messages[END_REF].

Let MPoly-Com " pMPoly.ComGen, MPoly.ComVer, MPoly.OpenVerq be a polynomial commitment scheme, Rq-Π " pRq-Π.Gen, Rq-Π.Prove, Rq-Π.Verq be a CaP zk-SNARK for polynomial rings computation, and let HE " pHE.KeyGen, HE.Enc, HE.Eval, HE.Decq be a homomorphic encryption scheme in the Ring-LWE setting. Then our VC scheme works as follows:

KeyGenp1 λ , f q Ñ pP K f , SK f q:
-Run ppk, skq Ð HE.KeyGenpλq to generate a key pair for HE.

-Run crs Ð Rq-Π.Genpck, R ck f q to generate the common reference string of Rq-Π for the relation R ck f . -Set P K f " ppk, crs, f q and SK f " psk, crsq. ProbGen P K f pxq Ñ pσ x , τ x q:

-Parse x " tx i u n i"1 and compute ciphertexts P i Ð HE.Encppk, x i q -Compute the commitment pC, ρq " MPoly.ComptP i uq and define σ x " pC, tP i u, ρq and τ x " C. Compute P K f pσ x q Ñ σ y :

-Parse σ x " pC, tP i u, ρq; -Compute the result ciphertext P Ð HE.Evalppk, f , tP i uq " f ptP i uq.

-Run π Ð Rq-Π.Provepcrs, pC, P q, ptP i u, ρqq.

-Define σ y " pP, πq Verify P K f pτ x , σ y q Ñ acc: output b Ð Rq-Π.Verpcrs, pC, P q, πq. Decode SK f pτ x , σ y q Ñ y: Decrypt y " HE.Decpsk, P q.

Following the general result in [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF], the scheme satisfies correctness, security and privacy. In particular, privacy relies on the semantic security of HE, and security on the soundness of the SNARK.

Preserving Privacy of the Inputs Against the Verifier

The VC scheme described in the previous section works when the homomorphic computation P Ð f ptP i uq on the ciphertexts is deterministic. This can raise the issue that the result ciphertext P may reveal information on the plaintexts tx i u underlying tP i u (e.g., in lattice-based schemes such information may be inferred by looking at the distribution of the noise recovered as P 's decryption time).

It would be therefore interesting to capture the setting where one wants to hide information on the x i 's even from the decryptor. Such a property would turn useful in scenarios where the data encryptor and decryptor are different entities. As an example, consider the case of users that store medical data x on a cloud server which computes some query f on behalf of an analyst, who however is not entitled to learn more than f pxq.

In this section, we provide a formal definition of this property, that we call context-hiding, and then describe how our scheme from the previous section can be extended to achieve this additional property.

Defining Context-Hiding. Informally, this property says that output encodings σ y , as well as the input verification tokens τ x , do not reveal any information on the input x. Notably this should hold even against the holders of the secret key SK f . We formalize this definition in a zero-knowledge style, requiring the existence of simulator algorithms that, without knowing the input, should generate pτ x , σ y q that look like the real ones. More precisely, a VC scheme is context-hiding for a function f if there exist simulator algorithms S 1 , S 2 such that:

the keys pP K f , SK f q and pP K 1 f , SK 1 f q are statistically indistinguishable, where pP K f , SK f q Ð KeyGenp1 λ , f q and pP K f , SK f , tdq Ð S 1 p1 λ , f q; for any input x, the following distributions are negligibly close

pP K f , SK f , σ x , τ x , σ y q « pP K f , SK f , σ x , τ 1 x , σ 1 y q
where pP K f , SK f , tdq Ð S 1 p1 λ , f q, pσ x , τ x q Ð ProbGen P K f pxq, σ y Ð Compute P K f pσ x q, and pσ 1 y , τ 1 x q Ð S 2 ptd, SK f , f pxqq. Our Context-Hiding Secure VC scheme. Before describing the scheme in detail, let us provide some intuition.

The first observation is that for the HE scheme this problem can be solved by adding to the result P an encryption of 0, P 0 , whose noise can statically hide that in P (a so called noise flooding technique). However if we do this change in our VC scheme we have two issues: (1) the computation is not deterministic anymore; (2) the prover may create a bogus encryption of 0, not of the correct distribution, in order to make decryption fail. We can solve these issues by using the fact that, as underlying tool for verifiability, we are using a SNARK that can handle deterministic computations. In particular, we can do the following.

For (2) we add to the public key s honestly generated encryptions of 0 tP i u s i"1 , and then ask the untrusted party to compute the result as P 1 " P `P 0 with P 0 " ř n i"1 b i ¨P i , for uniformly random bits b i . By choosing appropriately the noise parameters in the P i 's and by taking s « λ, based on the leftover hash lemma, P 0 can statistically hide the noise in P .

Formally, adding such a randomization at the end of computing a function f guarantees leveled circuit privacy. In a nutshell, a somewhat-FHE HE is leveled circuit private if there exists a simulator algorithm HE.S such that HE.Sppk, d, f pxqq « HE.Evalppk, f, HE.Encpxqq are statistically close. Here the input d taken by the simulator represents information on the depth of f .

For (1), we simply consider proving a slightly different relation, that is: R f :" tpu " pC, P 1 , tP i u s i"1 q; w " ptP j u n j"1 , T, ρ, b 1 , . . . , b s qq : pC, ρq " MPoly.ComptP j uq ^@i P rss b i P t0, 1u P

1 " f pP j q `s ÿ i"1 b i P i ´T R u
To use our scheme Rq-Π on the above relation, we can do the following. Given a function f : R q n Ñ R q , define the function f 1 : R q n`s ˆZs q Ñ R q that takes n `2s inputs such that

f 1 px 1 , . . . , x n , o 1 , . . . , o s , b 1 , . . . , b s q " f px 1 , . . . , x n q `s ÿ i"1 b i ¨oi .
Then we use our Rq-Π on the following relation R 1 f :" tpu " pC 1 , P 1 q; w " ptP j u n j"1 , tP i u s i"1 , tb i u s i"1 , T, ρ 1 qq : pC 1 , ρ 1 q " MPoly.ComptP j u, tP i u, tb i uq ^@i P rssb i P t0, 1u

P 1 " f 1 pP j , tP i u, tb i uq ´T R u where C 1 " C ˆC˚ˆC b and ρ 1 " ρ `ρ˚`ρ b .
It can be seen that R 1 f matches the format R f 1 (for the function f 1 and a larger set of inputs) of relations supported by our Rq-Π scheme. One change however is that the commitment C 1 cannot be created directly by ProbGen as it contains elements that depend on a specific computation. We can solve this problem by using the homomorphic property of the commitment scheme: namely we assume that at key generation a commitment pC ˚, ρ ˚q " MPoly.ComptP i uq is created and made public, and that the prover creates a similar commitment pC b , ρ b q " MPoly.Comptb i uq to the random coefficients. Then C 1 can be obtained as C ¨C˚¨C b and its opening is ρ 1 " ρ `ρ˚`ρ b . A more precise description of the protocol is given below.

KeyGenp1 λ , f q Ñ pP K f , SK f q:
-Run ppk, skq Ð HE.KeyGenpλq to generate the key pair for HE.

-Run crs Ð Rq-Π.Genpck, R f 1 q to generate the Rq-Π crs for the relation R f 1 .

-For i " 1 to s: P i Ð HE.Encppk, 0q and compute a commitment pC ˚, ρ ˚q " MPoly.ComptP i uq.

-Set P K f " ppk, tP i u s i"1 , C ˚, ρ ˚, crs, f q and SK P " psk, crsq. ProbGen P K f pxq Ñ pσ x , τ x q: this is the same as in the previous section. Compute P K f pσ x q Ñ σ y : parsing σ x " pC, tP i u, ρq, do the following:

-Sample b 1 , . . . , b s Ð$ t0, 1u uniformly at random, and compute a commitment pC b , ρ b q " MPoly.Comptb i uq (thinking of each b i as a degree-0 polynomial). -Compute the result ciphertext P 1 Ð f ptP i uq `řs i"1 b i P i . -Run π Ð Rq-Π.Provepcrs, pC ˆC˚ˆC b , P 1 q, ptP i u, tP i u, tb i u, ρ, ρ ˚, ρ b qq. -Define σ y " pP 1 , C b , πq Verify P K f pτ x , σ y q Ñ acc: output b Ð Rq-Π.Verpcrs, pC ˆC˚ˆC b , P q, πq. Decode SK f pτ x , σ y q Ñ y: Decrypt y " HE.Decpsk, P 1 q. Theorem 6. If HE is semantically secure and circuit private, and Rq-Π is knowledge sound and zero-knowledge, then the VC described above is correct, secure, private and context-hiding.

Proof (Sketch). The proof of the result is rather simple. Below we provide a proof sketch. First, notice that based on the correctness of Rq-Π and that of HE, we obtain correctness of our protocol.

The security follows from the knowledge soundness of the SNARK. The only detail to mention is that we also rely on the correctness of the HE scheme in order to make sure that, for honestly generated ciphertexts tP i u of tx i u, and tP i u for 0, and for binary coefficients tb i u, the ciphertext P 1 Ð f ptP i uq `řs i"1 b i P i decrypts to f pxq. Finally, we can prove context-hiding via a simple hybrid argument based on the privacy property of the HE scheme and the zero-knowledge of our SNARK. We define the VC simulators as follows. S 1 proceeds exactly as KeyGen except that it runs the SNARK simulator pcrs, tdq Ð Sim crs pR f 1 , λq instead of Gen, and set its trapdoor to be td. S 2 ptd, SK f , yq first sets τ 1

x " C where C is created as a commitment to some dummy input. Next, it creates C b as another commitment to a dummy value, and computes P 1 as an encryption of y using HE.Sppk, d, yq (where d is information on the depth of f ), and finally it invokes the SNARK simulator π Ð Sim Prove pcrs, pCˆC ˚ˆC b , P 1 qq. Then S 2 outputs τ 1

x and σ 1 y " pP 1 , C b , πq. The indistinguishability of the keys is immediate from the zero-knowledge of the SNARK. For the second property, we can define an hybrid simulator S 1 that, with knowledge of σ x , runs as S 2 but creates P 1 as in Compute. It is easy to see that the output of S 1 is indistinguishable from that of S 2 by the property of HE.Hide, also by the hiding of the commitment and by the zeroknowledge of the SNARK we obtain that the values pτ 1

x , σ 1 y q generated by S 1 are indistinguishable from the ones generated using ProbGen and Compute.

Bivariate Polynomial Commitment

Our final goal is to build an efficient instantiation of the MUniEv-Π scheme for the evaluation on the same point of many univariate polynomials committed with MPoly-Com. This is the key tool for our Rq-Π scheme for computations over polynomial rings presented in Section 3.

We construct MPoly-Com and MUniEv-Π starting from a commitment scheme BivPoly.Com for bivariate polynomials and a commit-and-prove argument BivPE-Π for the partial evaluation, in one variable, of a committed bivariate polynomial.

In this section we recall bilinear pairings and the computational assumptions needed by our schemes, and then we present the BivPoly.Com commitment scheme. The construction of the BivPE-Π commit-and-prove SNARK is described in Section 6, while their conversion into MPoly-Com and MUniEv-Π appears in Section 7.

Computational Assumptions

Security of our constructions rely on various computational assumptions. We state here our assumptions over bilinear groups. Some of them are standard q-type assumptions in the frame of DLog-hard groups and others are extractable (non-falsifiable) assumptions, a class of assumptions inherent to the security of SNARKs as shown in [START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF].

Bilinear Groups. Let the generator G input a security parameter λ and output a description of a bilinear group gk :" pq, G, G, G T , eq Ð$ Gp1 λ q such that q is a λ-bit prime; -G, G, G T are cyclic groups of order q; -e : G ˆG Ñ G T is a bilinear asymetric map (pairing), which means that @a, b P Z q : epg a , g b q " epg, gq ab ; if g and g generate G and G respectively, then epg, gq generates G T ; membership in G, G, G T can be efficiently decided, group operations and the pairing e are efficiently computable, generators are efficiently sampleable, and the descriptions of the groups and group elements each have size Opλq bits.

The d-Strong Diffie-Hellman Assumption (d ´SDH). The Strong Diffie-Hellman assumption [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF] says that given pg, g s , . . . , g s d q it is infeasible to compute y " g 1 s´r for a chosen r P Z q . In our applications, a few more group elements Σ are given as input to the adversary: Assumption 1 (d ´SDH) The d-Strong Diffie-Hellman assumption holds relative to a bilinear group gk if for all PPT adversaries A we have, on the probability space gk Ð Gp1 λ q, Σ Ð ppg, g s , . . . g s d q; pg, g s qq, g Ð$ G, g Ð$ G, and s Ð$ Z q :

Adv d´sdh A pλq :" Pr " pr, yq Ð Apgk, Σq ^y " g

1 s´r ı " neglpλq.
An adaptation of the proof in Boneh and Boyen [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF] shows that our variant of the d ´SDH assumption holds in the generic bilinear group model.

Knowledge of Exponent Assumptions. The knowledge of exponent (KEA) assumption introduced by Damgard [Dam92] says that given g, g α in a group G it is infeasible to create c, ĉ so ĉ " c α without knowing a so c " g a and ĉ " pg α q a . d-Power Knowledge of Exponent Assumption (d ´PKE) is another long-standing extractable assumption. It says that given tg, g s , g s 2 , . . . , g s d , ĝ, ĝs , ĝs 2 , . . . , ĝs d u with ĝ " g α , it is infeasible to create c, ĉ where ĉ " c α without knowing a 0 , a 1 , . . . a d that satisfy c " ś d i"0 pg s i q a i .

The pd, q-Bivariate PKE Assumption (pd, q ´BPKE). We introduce a bivariate power knowledge of exponent assumption that is a simple extension of the popular d ´PKE assumption. The pd, q-Bivariate Power Knowledge of Exponent Assumption for a bilinear group gk, noted by pd, q ´BPKE is a hybrid between PKE assumption for d different powers of s and powers of t and KEA assumption for input ph, ĥ :" h α q P G 2 . It takes the two basis pg, ĝ :" g α q, ph, ĥ :" h α q and all the powers tg s i t j , ĝs i t j u d, i,j"0 and claims that it is infeasible to create c, ĉ such that ĉ " c α without knowing δ, ta ij u d, i,j"0 , that satisfy c " h δ ś d, i,j"0 pg s i t j q a ij . More formally:

Assumption 2 (pd, q ´BPKE) The pd, q ´BPKE assumption holds relative to a bilinear group gk for the class Z of auxiliary input generators if, for every aux P Z and PPT adversary A, there exists a PPT extractor Ext such that, on the probability space gk Ð Gp1 λ q, Σ Ð pg, tg s i t j u d, i,j"0 , tĝ s i t j u d, i,j"0 ; ph, ĥ, h s q; pg, ĝ, g s qq, aux Ð Zpgk, Σq, g, h Ð$ G, g Ð$ G, α, s, t Ð$ Z q , ĝ :" g α , ĥ :" h α , and ĝ :" g α : Adv d´pke A pλq :" Pr « pc, ĉ; δ, ta ij u d, i,j"0 q Ð pA}Extqpgk, Σ; auxq epĉ, gq " epc, g α q ^c ‰ h δ ś d, i,j"0 pg s i t j q a ij ff " neglpλq.

Knowledge Commitment for Bivariate Polynomials

Based on an efficient construction of a polynomial commitment scheme proposed by [START_REF] Kate | Constant-size commitments to polynomials and their applications[END_REF] we further construct a knowledge commitment scheme for bivariate polynomials that is perfectly hiding and computationally binding. This will later allow us to use commitments in a CaP-SNARK BivPE-Π for polynomial partial evaluation. The commitment scheme BivPoly.Com " pBiv.ComGen, Biv.Com, Biv.ComVer, Biv.OpenVerq consists of four algorithms as described in Figure 3 and it is specialized for (bivariate) polynomials P P Z q rX, Y s: the message space M ck is defined by polynomials in Z q rX, Y s of degree in X bounded by a value d and degree in Y bounded by some value .

Remark 7. The Biv.ComGen algorithm computes two extra values g 1 :" g s , h 1 :" h s to be added to ck (step 4). Although these elements are not used by the commitment scheme, they are useful to construct our Commit and Prove SNARK for partial evaluations of polynomials committed with BivPoly.Com. In other words, used as a stand alone commitment scheme, BivPoly.Com may have a slightly shorter commitment key ck (by removing step 4 from Biv.ComGen).

Biv.ComGenp1 λ , d, q Ñ ck 1: gk Ð Gp1 λ q, g, h Ð$ G, g Ð$ G, α, s, t Ð$ Zq 2: ĝ :" g α , ĥ :" h α , ĝ :" g α 3: gij :" g s i t j , ĝij :" ĝs i t j @ i ă d, j ă 4: g1 :" g s , h1 :" h s 5: return ck " tgk, pgijq d, i,j"0 , pĝijq d, i,j"0 ; ph, ĥq; pg, ĝq; pg1, h1qu

Biv.Compck, P q Ñ pC, ρq Security of the Commitment BivPoly.Com. We call BivPoly.Com a knowledge commitment, since the prover cannot make a valid commitment without "knowing" the committed values. We will rely on the pd, q ´BPKE assumption for extracting the committed polynomials. We can state the following theorem on the security of BivPoly.Com: Theorem 8. The commitment scheme BivPoly.Com is perfectly hiding and computationally binding assuming the d ´SDH assumption holds in G. Moreover, assuming pd, q ´BPKE, the scheme is knowledge binding.

1: P :" ř d, i,j"0 aijX i Y j 2: ρ Ð$ Zq 3: c " h ρ ś d, i"0,j"0 g a ij ij 4: ĉ " ĥρ ś d, i"0,j"0 ĝa ij ij 5: C Ð pc
Proof. We thus prove the required properties: Perfect Hiding: Since C " pc, ĉq " pg δ , ĝδ q in G 2 for some δ P Z q , we have that c and ĉ are uniformly distributed elements of G 2 with the property ĉ " c α , independently of the committed values a i .

Computational Binding: Assume that there exists a non-uniform probabilistic time adversary A that creates two valid openings pA " ř d, i,j"0 a ij X i Y j , ρq and pB " ř d, i,j"0 b ij X i Y j , τ q of the same commitment C " pc, ĉq, i.e., h ρ g Aps,tq " h τ g Bps,tq .

By the homomorphic property of the commitment scheme we have zpρ ´τ q `Aps, tq ´Bps, tq " 0 mod q, for some z such that h " g z . We distinguish the following cases, with specific non-zero polynomials for which s or t are roots:

1. Either the two randomness are the same ρ ´τ " 0, leading to Aps, tq ´Bps, tq " 0. We reduce the case to the d ´SDH assumption for s or the ´SDH assumption for t in the following two sub-cases: (a) If ř i p ř j pa ij ´bij qt j qX i is the zero polynomial, meaning that all the coefficients ř j pa ij bij qt j are zero @i P t0, . . . du. Since polynomials A and B are different, there exist a ĩ P t0, . . . du so that t is a root of the polynomial ř j pa ĩj ´bĩj qY j . (b) If there exists at least one index i 0 , such that ř j pa i 0 j ´bi 0 j qt j ‰ 0, then we have that s is a root of the polynomial defined by fixing t: ř i p ř j pa ij ´bij qt j qX i . 2. The two randomness ρ ‰ τ , then we construct an algorithm that breaks the DLog instance pg, h " g z q.

We now conclude that with non-zero polynomials such that s or t is a root we break the d ´SDH assumption for s or the ´SDH assumption for t, and then we explain how we break discrete logarithm in the latter case:

1. We will study separately the two sub-cases, one reduction to d ´SDH assumption for s, and another one for ´SDH assumption for t.

(a) Consider an adversary A against the commitment scheme that breaks the binding with non-negligible probability ε. The probability of A producing a pair A, B satisfying the first case, sub-case (a) is at least ε{4. We show how to construct an algorithm B SDH 1 against ´SDH assumption for t that calls the adversary A. The adversary B SDH 1 using its challenge σ " pg, g s , . . . , g s d , pg, g s qq picks random scalars α, t Ð$ Z q and computes a commitment key ck for A:

ck " tgk, pg ij q d, i,j"0 , pĝ ij q d, i,j"0 ; ph, ĥq; pg, ĝqu. Consider that A outputs C " pc, ĉq, two scalars ρ " τ and two polynomials A and B that both pairs pρ, Aq and pτ, Bq are valid openings. This means we have that Aps, tq´Bps, tq seen as a polynomial in s, t equals to 0. Knowing that for some index ĩ, we have ř j pa ĩj ´bĩj qt j " 0, the adversary B SDH 1 is able to compute g 1 t in the following way: Consider c j 0 " a ĩj 0 ´bĩj 0 the first non-zero coefficient of the polynomial ř j pa ĩj ´bĩj qY j . We have that g c j 0 t j 0 " g ´tj 0 Qptq , so g 1 t " g ´Qptq c j 0 for some polynomial QpY q of degree ă ´cj 0 . B SDH 1 is then able to solve the d ´SDH instance. (b) For the second case, the adversary B SDH 2 against d ´SDH assumption for s runs an adversary A that outputs a second-type (b) forgery. In the same manner, the adversary B SDH 2 using its challenge picks random scalars α, t Ð$ Z q and computes a commitment key ck for A. We show how to construct an algorithm B SDH 2 against d ´SDH assumption for s that calls the adversary A. The adversary B SDH 2 using its challenge σ " pg, g s , . . . , g s d , pg, g s qq picks random scalars α, t Ð$ Z q and computes a commitment key ck for A: ck " gk, pg ij q d, i,j"0 , pĝ ij q d, i,j"0 ; ph, ĥq; pg, ĝq ( .

In a similar way as in the previous case, with the non-zero polynomial for which s is a root, B SDH 2 is able to compute g 1{s and solve the d ´SDH instance. 2. For this case we construct an algorithm B that uses A to efficiently solve a DLog instance.

Given a DLog instance pg, h " g z q, the algorithm B chooses α, s, t Ð$ Z q , sets ĝ :" g α , ĥ :" h α and presents ck " gk, pg ij q d, i,j"0 , pĝ ij q d, i,j"0 ; ph, ĥq; pg, ĝq ( .

to A.

Since this ck has the same distribution as a real common reference string there is a overwhelming probability for adversary A to return two valid openings for the same commitment C. Consider that A outputs C " pc, ĉq, two scalars ρ, τ and two polynomials A and B that both pairs are valid openings. Therefore, we have that g zpρ´τ q`Aps,tq´Bps,tq " 1 which implies zpρ´τ q`Aps, tq´Bps, tq " 0.

B is then able to compute the discrete logarithm value z " Bps,tq´Aps,tq ρ´τ . It is easy to see that the success probability of B solving the DLog instance is a small constant inferior to the advantage of A in breaking the binding property of the commitment scheme.

Knowledge Commitment:

The existence of a non-uniform probabilistic polynomial time knowledge extractor Ext that extract the contents of the knowledge commitment made by a non-uniform probabilistic polynomial time committer A that outputs a valid pair pc, ĉq follows directly from the pd, q ´BPKE assumption.

BivPE-Π.Genpck, R ck q Ñ crs :" ck BivPE-Π.Provepcrs, u, wq 1: pC, C 1 , kq :" u, pP, Q, ρ, ρ 1 q :" w 2: W :" `P ´Q˘{ pX ´kq 3: pD, ωq Ð Biv.CompW q 4: g :" h1{h k , x, y Ð$ Zq 5: U :" eph x gy , gq 6: e Ð Hashpu, D, Uq 7: σ " x ´pρ 1 ´ρqe mod q 8: τ " y ´ωe mod q 9: return π :" pD, e, σ, τ q BivPE-Π.Verpcrs, u, πq Ñ b 1: pC, C 1 , kq :" u, pD, e, σ, τ q :" π 2: pc, ĉq :" C, pc 1 , ĉ1 q :" C 1 , pd, dq :" D 3: b1 Ð Biv.ComVerpCq 4: b2 Ð Biv.ComVerpC 1 q 5: b3 Ð Biv.ComVerpDq 6: A " epd, g1{g k q ¨epc{c 1 , gq ´1 7: U :" eph σ gτ , gqA e , s.t. g :" h1{h k 8: b4 Ð pe " Hashpu, D, Uqq 9: return pb1 ^b2 ^b3 ^b4q In this section we show how to construct a commit-and-prove SNARK BivPE-Π for the partial evaluation in a single variable of bivariate polynomials.

Relations for Bivariate Polynomial Partial Evaluation

The relation R for partial evaluation of bivariate polynomials is defined over tuples pk, P pX, Y q, QpY qq P Z q ˆZq rX, Y s ˆZq rY s as follows R :" tpk, P pX, Y q, QpY qq : QpY q " P pk, Y qu.

The scheme we propose in this section is a Commit-and-Prove (CaP) SNARK for the above R where P P Z q rX, Y s and Q P Z q rY s are committed in C and C 1 respectively using BivPoly.Com.

3

Namely, following the definition from Section 2.2, BivPE-Π is a zk-SNARK for the following commit-and-prove relation R ck :" tpu " pC, C 1 , kq; w " pP, Q, ρ, ρ 1 qq :

(1) pC, ρq " Biv.CompP q ^pC 1 , ρ 1 q " Biv.CompQq ^QpY q " P pk, Y qu.

Our BivPE-Π Scheme for Bivariate Polynomial Evaluation

We aim to build an efficient commit-and-prove SNARK, BivPE-Π, dedicated to partial evaluation for bivariate polynomials P P Z q rX, Y s in X " k P Z q . Our scheme is based on an algebraic property of polynomials. We remark that pX ´kq perfectly divides the polynomial P pX, Y q ´P pk, Y q for k P Z q .

BivPE-Π works for an (R-independent) bivariate polynomial commitment scheme BivPoly.Com " pBiv.ComGen, Biv.Com, Biv.ComVer, Biv.OpenVerq, as detailed in Figure 4, and has to satisfy completeness, succinctness, zero-knowledge and knowledge-soundness.

Description of Our BivPE-Π Protocol. Let BivPoly.Com be a bi-variate polynomial knowledge commitment scheme. We construct a zero-knowledge SNARK scheme for any relation R ck with respect to some bounds d, on the degrees in X and in Y of the polynomials P P Z q rX, Y s supported by BivPoly.Com. Our protocol is formally depicted in Figure 4.

CRS generation. The setup algorithm outputs a crs enabling the proof and verification of statements for the associated relation R ck defined in Eq. (1).

We remark that Gen algorithm is just using the same public information (commitment key) ck from the BivPoly.Com scheme.

Prover. Given crs, the statement u " pC, C 1 , kq (two commitments C, C 1 and an evaluation point k) and the witness w " pP, Q, ρ, ρ 1 q (the corresponding polynomials P P Z q rX, Y s, Q P Z q rY s and their randomness ρ, ρ 1 ), the prover proceeds to compute a proof π that P pk, Y q " QpY q, pC, ρq " Biv.CompP q, and pC 1 , ρ 1 q " Biv.CompQq in two steps:

Step 1. (From 1 to 3 in the Prove algorithm from Figure 4.) The prover computes a witness to the correct (partial) evaluation in k P Z q of the polynomial P P Z q rX, Y s as P pk, Y q " Q P Z q rY s. The witness of this evaluation is a polynomial W P Z q rX, Y s defined as the quotient W :" P pX,Y q´QpY q

X´k

. This is a well-defined polynomial in Z q rX, Y s if and only if P pk, Y q " Q P Z q rY s. The element of the proof π that enables checking this algebraic property over the polynomials P and Q will be a commitment pD " pd, dq, ωq to the polynomial W , where ω Ð$ Z q is a fresh randomness.

Remark 9. To this point, the verifier should be convinced that the polynomial Q is the good evaluation in k of P , only by checking the corresponding polynomial equation evaluated in a random hidden point ps, tq : W ps, tqps ´kq " P pk, tq ´Qptq. This can be translated in terms of commitments pC, ρqpC 1 , ρ 1 q, pD, ωq to P, Q, W as a pairing check: epd, g 1 {g k q ¨epc{c 1 , gq ´1 " eph ps´tqω´pρ´ρ 1 q , gq where C " pc, ĉq, C 1 " pc 1 , ĉ1 q, D " pd, dq.

Because of the hiding property, the verifier does not have access to the openings of the commitments, as it does not know the randomness ρ, ρ 1 , ω.

We therefore need the prover to provide something more together with the commitment D. The prover needs to compute an extra proof of knowledge of the randomnesses ω used to create this comitment and of the correct relation to satisfy with respect to the randomness ρ, ρ 1 of the statement commitments C, C 1 such that the pairing expression cancels the respective terms h pρ´ρ 1 q and h ps´tqω . This is easily solved by building a Schnorr proof of knowledge of the exponents ω, pρ 1 ´ρq that appear in A " eph ps´kqω´pρ´ρ 1 q , gq " eph pρ 1 ´ρq h ps´kqω , gq. If we define g :" h 1 {h k " h s´k , then this proof is a classical Schnorr proof for the public value A " eph ρ 1 ´ρ gω , gq " eph, gq ρ 1 ´ρ ¨epg, gq ω in the target group G. But we will show we can make it more efficient.

Step 2. (From 4 to 7 in the Prove algorithm from Figure 4.) This step consists in this noninteractive Schnorr proof associated to the value A " eph ρ 1 ´ρ gω , gq:

-Choose x, y P Z q , -Define U " eph x gy , gq, this corresponds to the first round in the interactive Schnorr proof protocol, where the prover sends its commitment. -Sample the challenge to the Schnorr proof by running the random oracle (hash function) on input the statement to be proven and the commitment U: e Ð Hashpu, D, Uq, -Compute the answers σ " x ´pρ 1 ´ρqe mod q and τ " y ´ωe mod q. The values sent as Schnorr proof are three scalars e, σ, τ , where e is the output of the hash function Hashpu, D, Uq and does not depend on the size of U P G T . After the two described steps, the prover algorithm outputs π :" pD, e, σ, τ q.

Verifier. First, the verifier parses the received statement and proof (steps 1 and 2 in the Ver algorithm from Figure 4), then it makes sure the commitments C, C 1 , D are well-formed (steps 3 to 5 in the Ver algorithm from Figure 4) by running the Biv.ComVer algorithm. If this is not the case, we discard the proof π. To verify the proof π, one needs the polynomial equation W pX, Y qpX ´kq " P pk, Y q ´QpY q to hold for some secret evaluation points ps, tq. We can rewrite this equation in terms of pairings applied to the commitments pC, C 1 , Dq: epd, g 1 {g k q ¨epc{c 1 , gq ´1. If the polynomials W, P, Q evaluated in the secret points s, t satisfy the equation W ps, tqps´kq " P pk, tq´Qptq, then all the exponents in base g cancel out in the pairing expression. It is not the case for the exponents in base h which correspond to the randomness used in the commitments. The important remark is that if D is correct, the remaining value A " epd, g 1 {g k q ¨epc{c 1 , gq ´1 can be written only in terms of the 3 randomness ρ, ρ 1 , ω used to commit to P, Q, W :

A " eph ps´kqω h pρ 1 ´ρq , gq " eph ρ 1 ´ρ gω , gq.

This can be checked by the usual verification procedure of the Schnorr proof transmitted in π, i.e. the values pe, σ, τ q: Compute A " epd, g 1 {g k q ¨epc{c 1 , gq ´1 and U " eph σ gτ , gq ¨Ae then run the Hash function to check whether e " Hashpu, D, Uq.

Security of BivPE-Π. The security of our scheme is captured in the following theorem whose proof is elaborated in Section 8:

Theorem 10. Assuming both the d ´SDH and pd, q ´BPKE assumptions hold in the bilinear group gk, the protocol CaP-BivPE-Π is a zero-knowledge Succinct Non-Interactive Argument of Knowledge in the random oracle model.

Random Oracle Model. We point out that in the case one is not interested in hiding the committed bivariate polynomial P and its partial evaluation Q, then it is possible to define a simplified version of our scheme that does not need the Schnorr-style proof and thus is secure without random oracles. This protocol is the same as CaP-BivPE-Π except that one would set ω " ρ " ρ 1 " 0 (so the commitments are no longer hiding); this way the evaluation proof can be just the commitment D and it can be verified with the pairing check epd, g 1 {g k q " epc{c 1 , gq.

7 CaP-SNARK for Simultaneous Evaluations

In this section we show how we can use our BivPE-Π scheme for the partial evaluation of one bivariate polynomial on a point k in order to prove the evaluation of many univariate polynomials on the same point k. The resulting scheme MUniEv-Π can be used in the protocol presented in Section 4 for verifiable computation using HE on Ring-LWE. More precisely, we show how to use our BivPoly.Com and BivPE-Π to define a commitment scheme and a compact proof system dedicated to multi-polynomials evaluation in the same random point k: given a single compact knowledge commitment C for a set of univariate polynomials tP j pXqu j P Z q rXs and a public evaluation point k P Z q , we want to prove that some values tp j u j committed in C 1 are indeed evaluations of the committed polynomials in this point k.

Commitment for Multiple Univariate Polynomials

We describe below, MPoly-Com, our new knowledge commitment for a set of univariate polynomials. It is obtained in a straightforward way from BivPoly.Com. It is defined as follows, where for simplicity we consider `1 committed univariate polynomials P j " ř d i"0 p ij X i for all 0 ď j ď , 0 ď i ď d:

MPoly.ComGenp1 λ , d, q Ñ ck: Given some degree bound d and some maximal bound `1 on the cardinal of the polynomial set to be committed, it runs ck Ð Biv.ComGenp1 λ , d, q, where d, are the bounds on the degrees on X and Y of the bivariate polynomials in Z q rX, Y s. MPoly.Compck, tP j u 0ďjď q Ñ pC, ρq: Given a set tP j u of `1 polynomials in Z q rXs, with coefficients tp ij u iďd,jď i,j"0 we can define the bivariate polynomial P " ř d, i,j"0 p ij X i Y j and run pC, ρq Ð Biv.Compck, P q; MPoly.ComVerpck, C " pc, ĉqq Ñ 0{1: Runs b Ð Biv.ComVerpck, C " pc, ĉqq; MPoly.OpenVerpck, C, tP j u 0ďjď , ρq Ñ tP j u j : Runs P Ð Biv.OpenVerpck, C, P, ρq where P is parsed as ř d, i,j"0 p ij X i Y j . then output 1, else output 0 (reject).

We state the following theorem. Its proof simply follows from the way we encode multiple polynomials into a bivariate one.

Theorem 11. This commitment scheme MPoly-Com is perfectly hiding, computationally binding, and knowledge binding assuming the scheme BivPoly.Com also is so.

Proof. Let us show these three properties from the initial BivPoly.Com commitment.

Perfect hiding: Since C " pc, ĉq in G 2 is generated by Biv.Com algorithm, and BivPoly.Com is hiding, we have that MPoly-Com is perfectly hiding as well.

Computational binding: Assume that there exists a non-uniform probabilistic time adversary A that given a commitment C " pc, ĉq creates two valid openings ptA j u j , ρq, ptB j u j , τ q, where all A j , B j P Z q rXs. Then we create an adversary B against the binding of BivPoly.Com that runs A and outputs the pair of polynomials in Z q rX, Y s as follows A :" ř j"0 A j Y j and B :" ř j"0 B j Y j . We have that pA, ρq and pB, ρq are two valid openings for the commitment C. This breaks the binding property of BivPoly.Com.

Knowledge binding: This property follows directly from the knowledge binding of BivPoly.Com scheme.

Succinct Proof of Multiple Evaluations in a Point k

The construction of an efficient MUniEv-Π dedicated to multiple uni-variate polynomial evaluations in some common point k follows as well from the BivPE-Π scheme we built for partial evaluations. More precisely, for some parameters d, and some given knowledge commitments C, C 1 for polynomials of maximal degree d, tP j u 0ďjď P Z q rXs and scalars tp j u 0ďjď P Z q and a public evaluation point k P Z q , we want to prove that p j is the evaluation P j pkq for any 0 ď j ď .

Description of Our CaP MUniEv-Π Protocol. We now describe our protocol for proving multiple uni-variate polynomial evaluations in some common point k, where the j index is always considered as 0 ď j ď , and thus for `1 polynomials: MUniEv-Π.Genp1 λ , R uni q Ñ crs: On input a security parameter λ P N and a NP relation R uni :" tpu " ptP j u j , kq; w " tp j uq : P j pkq " p j u, define the associated relation R bi :" tpu " pP pX, Y q, kq; w " QpY qq : QpY q " P pk, Y qu where P pX, Y q :" ř j"0 P j Y j , QpY q :" ř j"0 p j Y j . Output the common reference string by running crs Ð Genpck, R bi q; MUniEv-Π.Provepcrs, u " pC, C 1 , kq, w " ptP j u j , tp j u j , ρ, ρ 1 q: Given crs, the instance u and the witness w, the prover defines new bi-variate polynomials P pX, Y q :" ř j"0 P j Y j , QpY q :" ř j"0 p j Y j and compute the proof π for those: π Ð Provepcrs, u " pC, C 1 , kq, w " pP, Q, ρ, ρ 1 q. Output π :" pD, e, σ, τ q; MUniEv-Π.Verpcrs, u, πq Ñ b: Same algorithm as for partial-evaluation BivPE-Π.

Remark 12. The commitment D to the bivariate polynomial W P Z q rX, Y s that appears in the proof can be seen as a commitment to a vector of univariate polynomials tW j u j using the MPoly-Com as follows: Write W j " ř d i"0 w ij X i , then running MPoly.Compck, tW j u j q gives the same output pD, ωq as running Biv.Compck, W q. Theorem 13. Assuming the BivPE-Π is a public coin argument of knowledge of openings of C and C 1 to some polynomials P P Z q rX, Y s, Q P Z q rY s such that P pk, Y q " QpY q, then MUniEv-Π is a public coin argument of knowledge of openings of C and C 1 to a set of polynomials tP j u j P Z q rXs and a set of scalars tp j u j P Z q such that P j pkq " p j @0 ď j ă .

Proof. We prove the required properties:

Correctness. Follows from the BivPE-Π correctness.

Knowledge Soundness. We first build a knowledge-extractor. This knowledge extractor directly follows from Theorem 14 and an extended extractor can be defined as in Theorem 15. For any adversary B against BivPE-Π, there exists an aggregated machine B ˚that outputs the same as B together with a extended witness wit " pP, ρ, Q, ρ 1 , W, ωq.

From the output of this extended machine B ˚we can further extract tP j :" ř d i"0 p ij X i u j , tp j :" q j u j , W j :" ř d i"0 w ij X i u j just by reading the respective coefficients p ij , q j , w ij from the bivariate polynomials P " ř d, i,j"0 p ij X i Y j , Q " ř j"0 q j Y j , and W " ř d, i,j"0 w ij X i Y j . Therefore, for any adversary A against the MUniEv-Π protocol, there exists an extended machine A ˚that runs the aggregate machine B ˚under its output and further returns the same statement and proof as A toghether with an extended witness wit " ptP j u j , ρ, tp j u j , ρ 1 , tW j u, ω; δ, γq, where P j , W j P Z q rXs, p j P Z q are the openings of the commitments pC, C 1 , Dq under randomness ρ, ρ 1 , ω and δ, γ are such that A " epd, g 1 {g k q ¨epc{c 1 , gq ´1 " eph δ gγ , gq.

Soundness. We reduce the soundness of MUniEv-Π to the soundness of BivPE-Π. Suppose there exists an adversary A against the soundness of MUniEv-Π, with the corresponding associated extended machine A ˚that outputs a cheating proof π ˚that passes the verification check with non-negligible probability. We then build an efficient adversary B against BivPE-Π that runs the machine A ˚to break the protocol with non-negligible probability.

B runs A ˚that outputs the corresponding tuple proof-statement-witness u " pC, C 1 , kq, π

˚"
pD, e, σ, τ q, wit " ptP j u j , ρ, tp j u j , ρ 1 , tW j u, ω; δ, γq. Then, we can define some corresponding bivariate polynomials as follows and build an extractor for B: We have the corresponding polynomials P P Z q rX, Y s and Q P Z q rY s defined from the univariate polynomials extracted above: P pX, Y q :" ř j"0 P j pXqY j , QpY q :" ř j"0 p j Y j . We know by our assumption that in the output of A ˚there exists at least one j 0 P t0, . . . u such that P j 0 pkq ‰ p j 0 . Then it follows that the previous defined P and Q do not satisfy the required statement: P pk, Y q ‰ QpY q, wich breaks the soundness of the BivPE-Π.

[ \

Efficiency and Comparison

We summarize the performance of our scheme MUniEv-Π in terms of prover and verification time and proof size. The proof consists of 2 elements from the group G and 3 elements of Z q . Generating a proof for polynomials of degree d requires a total of 2 d exponentiations in G in order to compute the commitment D, and Op d log dq operations in Z q in order to compute the polynomial W pX, Y q using polynomial division.4 Verifying a proof requires 5 pairings, and the following number of exponentiations: 6 in G, 1 in G and 1 in G T . 5We compare MUniEv-Π against a solution based on a general-purpose SNARK restricted to proving multiple polynomial evaluations in a commit-and-prove fashion. For the latter, we choose the LegoGroth16 scheme from [START_REF] Campanelli | LegoSNARK: Modular design and composition of succinct zero-knowledge proofs[END_REF], which makes the SNARK of [START_REF] Groth | On the size of pairing-based non-interactive arguments[END_REF] (which is currently among the most efficient SNARKs) to efficiently work with committed inputs, and that achieves the following efficiency. The proof consists of 4 elements of G and 1 element of G. Let m and n be the size and degree of the QAP modeling the evaluation of polynomials of degree d, and note that m, n ě d. Proof generation requires 2m `n ` d ` and m exponentiations in G and G respectively, as well as Opn log nq operations in Z q for a polynomial division. Verification requires 7 pairings.

The analysis above shows that our scheme MUniEv-Π has slightly smaller proofs and, more notably, has faster proof generation. Considering that m, n ě d and that G operations are at least twice slower than in G, our prover is at least 3 times faster.

Provepcrs, u, wq 1: W :" pP ´Qq{pX ´kq 2: pD, ωq Ð Biv.CompW q 3: x, y Ð$ Zq 4: U :" eph x gy , gq 5: e Ð Hashpu, D, Uq 6: σ " x ´pρ 1 ´ρqe 7: τ " y ´ωe 8: π :" pD, e, σ, τ q Sim Prove pcrs, u " pC, C 1 , kqq 1: W ˚:" 0 P ZqrX, Y s 2: pD ˚" pd, dq, ωq Ð Biv.CompW ˚q 3: e, x, y, k Ð$ Zq, A " epd, g1{g k qepc{c 1 , gq ´1 4: U ˚" eph x gy , gqA e 5: If Hashpu, D ˚, U ˚q P Query, abort Else, Hashpu, D ˚, U ˚q :" e 6: σ :" x 7: τ :" y 8: π :" pD ˚, e, σ, τ q Fig. 5. A Simulator for the Zero-Knowledge.

Security Analysis of our CaP BivPE-Π

In what follows we prove the main security result of our paper, Theorem 10.

Correctness. Correctness of our protocol can be proved by direct verification: if the commitments C, C 1 , D are honestly generated, the checks the Ver algorithm does all pass through. We consider C " h ρ g P ps,tq , C 1 " h ρ 1 g p , D " h ω g W psq , where Q " P pk, Y q and W pX, Y q " P pX,Y q´P pk,Y q px´kq . We have that U :" eph x gy , gq and the verifier computes U from u and π as follows:

U " eph σ gτ , gq ¨Ae " eph σ gτ , gq ¨epd, g 1 {g k q e ¨epc{c 1 , gq ´e " eph σ gτ , gq ¨eph ω g W psq , g s´k q e ¨eph ρ´ρ 1 g P ps,tq´p , gq ´e " eph σ gτ , gq ¨eph, gq eps´kqω ¨epg, gq eps´kqW psq ¨eph, gq epρ 1 ´ρq ¨epg, gq ´epP ps,tq´pq " eph σ gτ , gq ¨eph, gq eps´kqω`epρ 1 ´ρq " eph σ gτ , gq ¨eph epρ 1 ´ρq geω , gq " eph x gy , gq.

Zero-Knowledge. We consider the case of a honest verifier Ver to prove zero-knowledge of our scheme, as we use the Fiat-Shamir heuristic to convert it into a non-interactive proof [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF]. We thus have to construct a simulator Sim " pSim crs , Sim Prove q, where Sim crs is the same as Gen algorithm and outputs pcrs, trap :"Kq. Sim Prove is able to generate a simulated proof for any commitments C, C 1 and any k by committing any W ˚(we can use W ˚:" 0) and then simulating the Schnorr's proof. We proceed with a sequence of games in order to show the indistinguishability of the simulation.

Hybrid 0. This is the real protocol, described in Figure 5, where proof π is generated by Prove algorithm.

Hybrid 1. In this game, we use the witness of the evaluation, w " pP, Q, ρ, ρ 1 q, and we generate W P Z q rX, Y s as in step 1 of the real protocol, but in order to generate the proof π, we run instead the zero-knowledge simulator of the Schnorr proof (as in the lines 4 to 8 in Sim Prove procedure). Based on the fact that x, y are picked uniformly at random, U is uniformly random as well and the probability that the value pu, D, Uq had already been queried to the Hash oracle is q h {q, where q h is the number of queries asked to the oracle and q is the order of the group. It follows that the probability of this simulator to be distinguishable from the real proof algorithm is as well negligible.

Hybrid 2. The Sim Prove algorithm described in Figure 5 outputs the proof. Based on the perfectly hiding property of the commitment scheme the values D ˚and D in the two hybrids 1 and 2 are indistinguishable. Knowledge Soundness. Before going into the technical details of the proof, we provide some intuition about its strategy. The polynomial commitment scheme BivPoly.Com requires the prover Prove to exhibit two values pc, ĉq, that are the same encoding of coefficients of a polynomial P pX, Y q in the exponent, but with respect to different bases. The reason that we require the prover to duplicate its effort w.r.t. α is so that the simulator in the security proof can extract representations of pc, ĉq as a polynomial P pX, Y q, under the pd, q ´BPKE assumption.

Suppose an adversary A manages to forge a SNARK of a false statement that nonetheless passes the verification test. The intuition behind the proof is to use the adversary A and the fact that the commitment scheme BivPoly.Com is extractable to be able to solve the d ´SDH assumption for d " degpP q in X. There is a similar complementary case that allows this adversary to solve the d ´SDH assumption for d " degpP q in Y (actually in our notations).

To proceed to proving Theorem 10, we first need two preliminary lemmas:

Lemma 14 (Global Extractor). Assume that BivPoly.Com is an extractable commitment scheme with perfect hiding and computational binding properties and that pd, q´BPKE assumption holds in the bilinear group gk. For any PPT adversary A KS agains the knowledge soundness of BivPE-Π that has non-negligeable probability of success in breaking the scheme, there exists an extractor Ext such that:

Pr » - - - - - crs Ð BivPE-Π.Genp1 λ , Rq, z Ð Zpcrsq C " Biv.CompP, ρq
ppu, πq; witq Ð pA KS }Ext ˚qpcrs, zq ^C1 " Biv.CompQ, ρ 1 q u :" pC, C 1 , kq, π :" pD, U, σ, τ q ^D " Biv.CompW, ωq wit :" pP, ρ, Q, ρ 1 , W, ωq BivPE-Π.Verpcrs, u, πq " 1 fi ffi ffi ffi ffi fl " " 1 ´neglpλq.

Proof. We show the existence of an extractor Ext ˚that will output the polynomials P pX, Y q, QpY q, W ˚pX, Y q and the randomness ρ, ρ 1 , ω corresponding to the commitments C, C 1 , D, with overwhelming probability.

Let A KS be an adversary that breaks the KS of the protocol BivPE-Π with overwhelming probability, meaning it outputs a false proof that passes the verifier checks. Consider now the adversary B BPKE that takes as input σ Ð pg, tg s i t j u d, i,j"0 , tĝ s i t j u d, i,j"0 ; ph, ĥ, h s q; pg, g α , g s qq and runs the adversary A KS against the scheme. B BPKE can provide a valid CRS to A KS by using its inputs:

crs " tgk, pg ij q d, i,j"0 , pĝ ij q d, i,j"0 ; ph, ĥ, h 1 q; pg, g α , g 1 qu.

The statement u, corresponding to π Ð A KS pcrsq, contains the values C :" pc, ĉq, C 1 :" pc 1 , ĉ1 q that verify epc, ĝq " epĉ, gq and epc 1 , ĝq " epĉ 1 , gq. The same holds for the value D provided in the proof π " pD, e, σ, τ q, i.e. epd, ĝq " ep d, gq.

Provided that for any adversary B BPKE that outputs valid commitment pair pc, ĉq, there exists an extractor that returns the corresponding witness (the opening). We run the extractor Ext B associated to B BPKE for each of the inputs C " pc, ĉq, C 1 " pc 1 , ĉ1 q, D " pd, dq. This returns the description of polynomials P pX, Y q, QpY q, W ˚pX, Y q and some scalars ρ, ρ 1 , ω. Note that the existence and efficacy of Ext B is guaranteed by the pd, q ´BPKE assumption. We will then define a general extractor Ext ˚associated to the adversary A KS by running Ext B on the same input. We call this global algorithm composed of the adversary A KS and the general extractor Ext ˚, machine M :" A KS ||Ext ˚.

[ \ Lemma 15 (Extended Adversary Machine). Assume that pd, q ´BPKE assumption holds in the bilinear group gk and that Schnorr proof used in the BivPE-Π protocol is sound. For any PPT adversary A KS against the knowledge soundness of the scheme BivPE-Π that outputs u " pC, C 1 , kq, π " pD, e, σ, τ q, where C, C 1 , D are well-formed commitments under BivPoly.Com and the proof π verifies, i.e. Verpcrs, u, πq, there exists a machine, extended adversary A ˚that outputs the same as A KS together with an extended witness wit " pP, ρ, Q, ρ 1 , W, ω, δ, γq, where P, W P Z q rX, Y s, Q P Z q rY s are the openings of the commitments pC, C 1 , Dq under randomness ρ, ρ 1 , ω and δ, γ are such that A " epd, g 1 {g k q ¨epc{c 1 , gq ´1 " eph δ gγ , gq.

Proof. We use the previous defined machine M from Theorem 14 and the rewinding technique [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF] for proving the soundness of the Schnorr's proof to extract the scalars δ, γ such that A " eph δ gγ , gq: Consider the game between the challenger and the machine M against the soundness of the Schnorr's proof. The challenger runs M by fixing the values pC, C 1 , Dq and changing the oracle definition to get a fork with e 1 Ð HashpU, D, Uq ‰ e. The forger M will output two distinct forgeries corresponding to the same random oracle query, but for two distinct answers of the random oracle, e and e 1 . The Forking Lemma shows that by rewinding the adversary Opq h {εq times, where q h is the maximal number of random oracle queries of the machine M and ε its success probability, then one finds two such forgeries pσ, τ q, pσ 1 , τ 1 q with constant probability, which enables to compute the values δ, γ such that A " eph δ gγ , gq.

Using the existence of Ext ˚extractor and of the algorithm that rewinds the machine M in order to obtain the output δ, γ as described before, we can define an aggregate machine A corresponding to the concatenation of both. This machine A ˚takes the same input as A KS and outputs the witness corresponding to the commitment openings pP, ρq, pQ, ρ 1 q, pW, ωq and two scalars δ, γ satisfying A " eph δ gγ , gq.

[ \ Knowledge Soundness. We now have all the tools to prove the soundness in two steps.

Step 1. First we show that for every PPT adversary A KS against the soundness of the protocol, there exists an extractor Ext A that runs on the same input and random coins as A KS and outputs a witness. Defining the extractor Ext A is straightforward from the Theorem 14 by running the Ext ˚and keeping just the values pP, ρ, Q, ρ 1 q from its output.

Assuming the existence of an adversary A KS and extractor Ext A that has a non-negligible success probability in winning the soundness game against the protocol BivPE-Π, we now show that we can either solve the discrete logarithm problem, or break the d ´SDH assumption.

Step 2. Suppose the machine A ˚associated to A KS defined in the Theorem 15 is able to output a cheating pair statement-proof u " pC, C 1 , kq, π " pD, e, σ, τ q and a witness wit " pρ, ρ 1 , ω, P, Q ˚, W ˚, pδ, γqq such that it passes verification checks, but the extracted values P P Z q rX, Y s, Q ˚P Z q rY s are not satisfying the expected relation Q ˚pY q " P pk, Y q.

For simplicity, we will call ∆ " ρ 1 ´ρ. Assuming that the commitment scheme is binding, then one of the following scenarios must hold:

1. The polynomials extracted do not satisfy the correct relation not even when evaluated in s: W ˚ps, tq ‰ P ps,tq´Q ˚ptq s´k . This type of forgery can be reduced to the DLog problem for pg, hq P G, in the case 1 below (see Theorem 16); 2. The polynomial W ˚P Z q rX, Y s committed in D does not satisfy the correct relation with respect to the other extracted values P, Q ˚, but still evaluated in s, t we have that W ˚ps, tq " P ps,tq´Q ˚ptq s´k . We reduce the case to the d ´SDH assumption, in the case 2 below (see Theorem 17).

[ \ Lemma 16 (Case 1). Consider the adversarial machine A ˚associated to A KS defined by the Theorem 15 that outputs some values u " pk, C, C 1 , D, e, σ, τ q and pρ, P, ρ 1 , Q ˚, ω, W ˚, δ, γq, such that P pk, Y q ‰ Q ˚pY q, where P, W ˚P Z q rX, Y s, Q ˚P Z q rY s and pP, ρq, pQ ˚, ρ 1 q, pW ˚, ωq are the openings of the commitments pC, C 1 , Dq and pδ, γq satisfy A :" eph ω g W ˚ps,tq , g 1 {g k q ëph ´∆g P ps,tq´Q ˚ptq , gq ´1 " eph δ gγ , gq. Given that the verification check outputs 1 for π, there is a negligible probability that the values k, P, Q ˚, W ˚are such that W ˚ps, tq ‰ P ps,tq´Q ˚ptq ps´kq under DLog assumption with respect to the group G.

Proof. Let B DLog be an adversary that gets the challenge pg, hq P G and simulates the crs to A by picking α, s P Z p and computing the missing elements. We define g :" h s´k , and we denote δ, γ, the two outputs of A ˚such that A " eph δ gγ , gq. Assuming the binding of the commitment scheme, the check in the verification step of the scheme gives us: eph ps´kqω g ps´kqW ˚ps,tq , gq ëph ρ´ρ 1 g P ps,tq´Q ˚ptq , gq ´1 " eph δ gγ q. By the non-degeneracy of the pairing map, it must be that h δ`ps´kqγ´∆´ps´kqω " g ps´kqW ˚ps,tq´P ps,tq`Q ˚ptq .

Since ps ´kqW ˚ps, tq ´P ps, tq `Q˚p tq ‰ 0, we can extract the discrete logarithm of h in basis g.

[ \ Lemma 17 (Case 2). Consider the adversarial machine A ˚associated to A KS defined by the Theorem 15 that outputs some values u " pk, C, C 1 , D, e, σ, τ q and pρ, P, ρ 1 , Q ˚, ω, W ˚, δ, γq, such that P pk, Y q ‰ Q ˚pY q, where P, W ˚P Z q rX, Y s, Q ˚P Z q rY s and pP, ρq, pQ ˚, ρ 1 q, pW ˚, ωq are the openings of the commitments pC, C 1 , Dq and pδ, γq satisfy A :" eph ω g W ˚ps,tq , g 1 {g k q ëph ´∆g P ps,tq´Q ˚ptq , gq ´1 " eph δ gγ , gq. Given that the verification check outputs 1 for π, there is a negligible probability that the values k, P, Q ˚, W ˚satisfy W ˚ps, tq " P ps,tq´Q ˚ptq ps´kq under d 1 ´SDH assumption with respect to the bilinear group gk, where d 1 " maxtd, u.

Proof. Consider the adversary B SDH against d 1 ´SDH assumption, having as auxiliary input z " pk, ∆, ω, δ, γq. Using its challenge pg, g s , . . . , g s d , ĝs , . . . , ĝs d ; h, h s , ĥ; pg, g s qq it picks random scalars α, t Ð$ Z q and computes g ij :" g s i t j , g ij :" g s i t j for i " 0, . . . , d and j " 0, . . . , , ĝ :" g α , and computes a commitment key ck " gk, pg ij q d, i,j"0 , pĝ ij q d, i,j"0 ; ph, ĥq; pg, ĝq ( . It further sends the following crs corresponding to the relation R ck to A ˚: crs " ck, ph 1 , g 1 q, Hashp¨, ¨, ¨q( . Note that h 1 and g 1 are in the initial challenge.

From the output of the aggregated machine A ˚, B SDH gets the values u " pk, C, C 1 , D, e, σ, τ q and pρ, P, ρ 1 , Q ˚, ω, W ˚, δ, γq. The verification check of the Schnorr proof implies A " epd, g 1 {g k q ¨epc{c 1 , gq ´1 " eph ω g W ˚ps,tq , g s´k q ¨eph ´∆g P ps,tq´Q ˚ptq , gq ´1 " eph ∆ h ps´kqω , gq ¨epg ´pP ps,tq´Q ˚ptqq g ps´kqW ˚ps,tq , gq " eph ∆ gω , gq.

The outputs δ, γ from the extended adversary machine are such that A " eph δ gγ , gq (from the soundness of the Schnorr's proof). This, together with the previous equation leads to the conclusion eph δ gγ , gq " eph ∆ gω , gq and so eph ∆´δ gω´γ , gq " 1. The adversary B SDH is able to produce a solution to the equation ps ´kqpω ´γq `∆ ´δ " 0 mod q and though to find s " k `δ´∆ ω´γ mod q, unless γ " ω and δ " ∆. In the former case, from the value s, one can easily break any SDH problem. In the latter case, the two writings for A, and the non-degeneracy of the pairing map lead to g ps´kqW ˚ps,tq´P ps,tq`Q ˚ptq " 1.

Using P P Z q rX, Y s, compute QpY q :" P pk, Y q and define the polyomial W " P pX,Y q´QpY q pX´kq P Z q rX, Y s. We have also that g ps´kqW ps,tq " g P ps,tq´Qptq , then B d 1 ´SDH computes g Qptq´Q ˚ptq " g ps´kqpW ˚ps,tq´W ps,tqq . Define the polynomial in Z q rX, Y s : W 1 pX, Y q " pX ´Y qpW pX, Y q Ẃ ˚pX, Y qq ´QpY q `Q˚p Y q, we have that g W 1 ps,tq " 1. This splits in two cases:

1. If W 1 pX, tq " ř i p ř j w 1 ij t j qX i is the zero polynomial in X, meaning that all the coefficients wi " ř j w 1 ij t j are zero @i P t0, ¨¨¨, du, then by choosing an index i 0 P t0, . . . du with a non-zero element w 1 i 0 j (unless W 1 " 0 which contradicts the hypothesis of the Lemma) we have that t is a root of the polynomial ř j w 1 i 0 j Y j . 2. If there exists at least one index ĩ, such that wı " ř j w 1 ĩj t j ‰ 0, then we have that s is a root of the polynomial defined by fixing t: W 1 pX, tq " ř i wi X i . If the first case happens with non-negligible probability, algorithm B SDH 1 receives an ´SDH instance in t, and choosing s, can complete the input for the aggregate machine A ˚. Knowing that ř j w 1 i 0 j t j " 0, the adversary B SDH 1 is able to compute g 1 t in the following way: Consider w 1 i 0 j 0 the first non-zero coefficient of the polynomial ř j w 1 i 0 j Y j : g w 1 i 0 j 0 t j 0 " g t j 0 `1W 2 ptq for some polynomial W 2 of lower degree, and so g w 1 i 0 j 0 " g tW 2 ptq , or equivalently g 1{t " pg W 2 ptq q 1{w 1 i 0 j 0 . B SDH 1 is then able to solve the ´SDH problem, as g W 2 ptq can be computed from the initial instance.

If the second case happens with non-negligible probability, the algorithm B SDH 2 receives a d ´SDH instance in s, and can complete it as an input for A ˚by choosing t. Doing as above, with a polynomial that has s as a root, it can compute g 1{s . This solves the ´SDH instance. [ \

Fig. 4 .

 4 Fig. 4. Our CaP-SNARK for Bivariate Polynomial Partial Evaluation

In particular, relevant to our work is the compiler that shows that commit-and-prove SNARKs for Pedersen-like commitments can be made compatible with one another.

The commitment key ck can have some special property for optimization, for example, it may consist of two keys, one for committing to polynomials Pj P Rq of degrees ď d and another longer key to commit to polynomials T P ZqrXs of degree ν.

Note that, although Q is a uni-variate polynomial in Y , it can also be seen as a bivariate polynomial.

Note that W can be computed by aggregating the results of polynomial divisions of degree d.

The numbers are obtained by observing that the six pairings for Biv.ComVer can be batched resulting into 2 pairings and 4 exponentiations in G.

Acknowledgments

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud). The first author has been partially supported by the Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), CRYPTOEPIC (ref. EUR2019-103816), and SECURITAS (ref. RED2018-102321-T), by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339), and by a research gift from Protocol Labs.