Rinocchio: SNARKs for Ring Arithmetic

Chaya Ganesh¹, Anca Nitulescu², and Eduardo Soria-Vazquez³

¹ Indian Institute of Science, India.

² Protocol Labs, USA.

³?? Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE. chaya@iisc.ac.in, anca.nitulescu@protocol.ai, eduardo.soria-vazquez@tii.ae

Abstract. Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive ecient verication of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be eciently represented as either Boolean or arithmetic circuits over nite elds. For most constructions, the choice of the prime eld Fp is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work we overcome such restrictions and enable verifying computations over rings. We construct the rst designated-verier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements such that their pairwise dierences are invertible. Our contribution is threefold: We rst introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring. Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT 2013), we design SNARKs over rings in a modular way. We generalize pre-existent assumptions employed in eld-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it is amenable to dierent settings. Finally, we propose two applications for our k SNARKs. In the rst one, we instantiate our construction for the Galois Ring GR(2*;d*), i.e. the degree-d Galois extension of Z₂k. This allows us to naturally prove statements about circuits over e.g. Z₂₆₄, which closely matches real-life computer architectures such as standard CPUs. Our second application is veriable computation over encrypted data, specically for evaluations of Ring-LWEbased homomorphic encryption schemes.

$$ \mathbb{F}_{p} $$

$$ \mathbb{Z}_{2}k, $$

$$ G R(2^{k},d) $$

$$ \mathbb{Z}_{2^{664}} $$

^?? Work done while at Department of Computer Science, Aarhus University, Aarhus, Denmark.

Table of Contents

Rinocchio: SNARKs for Ring Arithmetic 1 Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez

1 Introduction 3 1.1 SNARKs for Computation over Rings 4 1.2 Our Contributions 5 1.3 Comparison with Related Work 7

2 Preliminaries 8 2.1 Background in Ring Theory 10

3 Quadratic Programs over Commutative Rings 12 3.1 QRP Composition 13 3.2 Direct QRP construction 16

4 Secure Encoding Schemes over Rings 16 4.1 Secure Encodings 17

5 Designated Verifier SNARK 18 5.1 Construction from QRP 20 5.2 Security proof 21

6 Designated Verifier SNARKs for computation over $ \mathbb{Z}_{2^k} $ 25 6.1 A secure encoding for $ GR(2^k,\delta) $ 25 6.2 A simple construction 26 6.3 Soundness amplification 26

7 SNARKs for computation over Encrypted Data 27 7.1 Homomorphic Encryption schemes and their parameters 27 7.2 Secure Encodings for (Ring-)LWE ciphertexts 28 7.3 (zk-)SNARKs for Ring-LWE-based homomorphic encryption 30

A More Preliminaries 36 A.1 Verifiable Computation 36

B Assumptions on Ring Encodings 37

C QRP as an Abstraction 39

D Some useful QRPs. 39 D.1 Bit Decomposition Gate 40 D.2 Modular reduction gate 40

E Further details on SNARKs for computation over Encrypted Data 42 E.1 Further details on Torus encoding 42

F [Gro16]-Like Construction based on Linear-Only Encodings 42 F.1 Proof of Security 43

1 Introduction

Proof systems have a rich history in cryptography and theory of computation [GMW86,For87, ⁺ BGG 90]. They are now a fundamental building block in numerous cryptographic constructions such as public-key encryption [NY90], signature schemes [CS97], identication schemes [FFS87], anonymous credentials [CL01], secure voting [CF85], secure multi-party computation [GMW87] + and, more recently, in cryptocurrencies such as ZCash [BCG 14].

Succinct proofs and verication. Zero-knowledge proofs [GMR89] provide the ability to convince a verier about the truth of a statement without revealing the secrets involved. Zero-knowledge proofs are known to exist for all languages in NP [GMW86].

A non-interactive zero-knowledge proof (NIZK) [BFM88] is a proof system where the prover sends only one message to the verier, and the verier decides whether to accept or not based on its input, the message, and any public parameters. NIZKs are usually studied in the common reference string (CRS) model, where some structured string is generated in an initial setup phase and made available to everyone to prove/verify statements. A large body of work has been devoted to the design and implementation of ecient proofs for a variety of applications. For various practical scenarios, some of the crucial parameters are the amount of interaction, the proof size and how ecient is to prove or verify statements. When it comes to optimization of communication complexity in proof systems, it has been shown that statistically-sound proofs are unlikely to allow for signicant improvements in proof size. It was shown in [Wee05] that when considering proof systems for NP, statistical soundness requires the prover to communicate, roughly, as much information as the size of the witness. The search for ways to beat this bound motivated the study of computationally sound proofs.

When restricting ourselves to computational soundness, proofs can be shorter than the length of the witness [BCC88]. Computationally sound proofs are called argument systems. Many applications also require succinct verication, where the verier is able to check a nondeterministic polynomialtime computation in time that is much shorter than the time required to run the computation given the NP witness. Succinct proofs were considered by Kilian [Kil92], whose four-message construction, based on probabilistically checkable proofs (PCP), was soon after made non-interactive by Micali [Mic94] in the random oracle model. In the plain model, non-interactivity is achieved by generating a CRS during a setup phase. There has been a series of works on constructing (zero-knowledge) Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) [Gro10,Lip12, + BCCT12,BCI 13,GGPR13,PHGR13,Lip13,BCTV14,Gro16], which have very short proofs that can be veried very quickly. All these constructions are based on non-falsiable assumptions [Nao03], and the result of Gentry and Wichs [GW11] shows that in the plain model, it is unlikely that SNARGs for general NP languages exist based on falsiable assumptions. The approaches + of [GGPR13,PHGR13], which led to concretely ecient proofs were generalized in [BCI 13] under the concept of Linear PCP (LPCP). LPCPs are a form of interactive proofs where security holds under the assumption that the prover is restricted to compute only linear combinations of its inputs. These proofs can then be transformed into SNARKs by means of an extractable linear-only encryption scheme, that is, an encryption scheme where a valid new ciphertext output by the adversary is an ane combination of the encryptions that the adversary sees as input. Roughly, this \limited malleability" of the encryption scheme, will force the prover to adhere to the above restriction.

1.1 SNARKs for Computation over Rings

Despite the progress we have seen in SNARKs, all existing contructions oer eciency benets only for proving statements which can be eciently represented as very particular forms of computation. The works of [GGPR13,PHGR13,DFGK14] consider statements represented as circuit computations, either as a Boolean circuit with AND, OR and NOT gates, or as an arithmetic + circuit with addition and multiplication over a eld. The results of [BSCGT13,BCG 13] imply that random-access machine computations can be eciently reduced to circuit satisability. The + compiler of [BCG 13] gives an ecient reduction from the correctness of programs to arithmetic circuit satisability for a prime eld of suitable size. However, it is clearly interesting to consider computations over other rings, like Z₂32 and Z₂64. While this can be reduced to computation over a eld, emulating ring arithmetic in terms of nite eld operations incurs a signicant overhead [KPS18]. Computation over these rings matches models of computation in real-life programming and in computer architectures such as over CPU words. In addition, xed and oating-point arithmetic operations that frequently come up in real-world applications (for instance in approximate, rather than exact computations such as in Machine Learning [CCKP19]), are more naturally expressed in terms of operations over these rings. The work of LegoSNARK [CFQ19] partially mitigates the eciency issue of being tied to a unique, particular representation of computation. They achieve their results by seeing a computation as naturally consisting of dierent components and proposing a modular approach that uses the SNARK best suited for each component. Composition of proof gadgets is orthogonal to our work, and by extending our construction to be commit-and prove, the broader class of rings to which we can eciently apply our SNARK adds yet another tool for works in the spirit of LegoSNARK.

$$ \mathrm{B C G^{+}13} $$

$$ \mathbb{L}_{2^{32}} $$

$$ \mathbb{L}_{2^{64}} $$

Applications. Veriable computation (VC) allows a computationally weak client to outsource evaluation of a function to a powerful server. The client can then verify that the output returned by the server is indeed correct while performing less work than what is necessary for computing the function itself. SNARKs immediately give a VC scheme, where the server performs the computation and returns a SNARK proof together with the output. There has been signicant progress in the recent years in constructing protocols and implementing systems for veriable computation that leverage

• • • SNARKs [BCG 13,BCTV14,BFR 13,CFH 15]. As has been noted in prior works [PHGR13], the performance of existing constructions deteriorate for functionalities that have \bad" arithmetic circuit representations.

In order to use existing SNARK schemes, one would have to translate the statement to a statement about circuit satisfaction over a eld. This translation is expected to incur some overhead, and it is desirable that one can prove native computation. Most computer architectures, for instance, Intel x64, support primitive data-types over rings. These architectures have specially designed hardware to support fast and ecient arithmetic operations over rings. Matrix multiplication is heavily optimized for the ring Z₂64, and many native implementations compute over Z₂64 by default. Proving ring computations could also lead to building anonymous credential schemes o of standard signature schemes like RSA.

$$ \mathbb{Z}_{2^{64}} $$

$$ \mathbb{L}_{2^{64}} $$

Eciency considerations. The core problem behind eciently simulating arithmetic over Z₂k in SNARKs in which the underlying eld is Fp(for a 254-bit prime p) and k < 0: 5dlog pe is that k of minimizing the amount of times one has to compute the modular reduction x mod 2 so that correctness is preserved. This operation, which we denote as bit decomposition, can be implemented

$$ \mathbb{Z}_{2}k, $$

$$ \mathbb{F}_{p} $$

$$ ^)p $$

$$ k,<,0.5\lceil\log p\rceil $$

$$ 2^{k} $$ for circuits over F_pat the cost of m + 1 multiplication gates, where m = dlog(x_max)e and x_max denotes the maximum value x might attain [KPS18], given its position on the circuit and any known bounds on the inputs. Inputs provided in zero-knowledge can, themselves, be ensured to be k-bit k numbers at the cost of k + 1 multiplication gates. Whereas placing \reduction mod 2 " gates in a circuit could be phrased as an optimization problem, practitioners do not nd it eciently solvable in practice and often resort to heuristics [KPS18].

$$ m=\left\lceil\log(x_{m a x})\right\rceil $$

$$ \mathbb{F}_{p} $$

$$ x_{m a x} $$

$$ k+1 $$

$$ 2^{k>3} $$

In other applications, there is the somewhat converse problem that the eld F_pis not big enough to represent values in a single circuit wire. This happens, for example, if one wants to compute zkSNARKs where the statements are related to some RSA ring [DFKP16]. As each ring element then corresponds to m \words", each of them on an independent circuit wire, multiplying ring : 58 elements requires e.g. O(m¹) multiplication gates, applying Karatsuba’s method.

$$ \mathbb{F}_{p} $$

$$ O(m^{1.58}) $$

1.2 Our Contributions

Our goal is to construct a (zk)-SNARK for ring computations, thus bringing the theory of proof systems closer to practice. Along the way, we tackle new technical problems, introduce useful building blocks, such as Quadratic Ring Programs (QRPs) and secure encodings over rings. Finally, we provide two applications for our SNARKs based on the QRP characterization: Privacy-preserving veriable computation and SNARKs over Z₂k.

$$ \mathbb{Z}_{2}{}^{k} $$

Quadratic Programs over Rings. Gennaro et al. [GGPR13] introduced the notion of Quadratic Span Programs (QSP) and Quadratic Arithmetic Programs (QAP) which can be used to compactly encode computations. They show how to convert any Boolean/arithmetic circuit into a QSP/QAP.

In this spirit, we dene an analogue of a Quadratic Arithmetic Program (QAP) for arithmetic circuits over rings, called Quadratic Ring Program (QRP). QRPs \naturally" characterize computation on the underlying ring, which allows us to construct a SNARK without having to emulate the ring arithmetic inside a eld, as would be required if we were to use a QAP. Furthermore, we give an explicit way to construct QRPs for rings containing big enough exceptional + sets [BCPS18,ACD 19,DLS20], i.e. sets of elements such that their pairwise dierences are invertible. We believe the notion of a QRP could be of independent interest as a generalization of existing quadratic programs.

$$ \mathrm{A C D^{+}19} $$

Designated-verier (zk)-SNARK for ring computation. The QRP characterization allows a test for satisability of an arithmetic circuit over a ring. To construct a succinct proof, we follow the blueprint of [GGPR13,PHGR13], where the QRP test is performed in a probabilistic way. The setup produces a structured reference string that consists of linearly homomorphic encodings, on top of which the prover is expected to compute using the (secret) witness. Under knowledgetype assumptions that we extend to encodings over rings, we prove security of our designatedverier SNARK. In particular, we prove our construction secure under variants of the generalized q-PDH and d-PKE assumptions extended to encodings over rings, carefully addressing the technical challenges that arise in the new ring setting. These generalized assumptions were already stated for encodings over elds by prior works as [GGPR13,GMNO18] and gained some condence as a base to build post-quantum SNARKs. Similar to the counterpart of assumptions in the eld case, where for instance, the existence of secure bilinear groups limits the choice of the nite elds, our ring assumptions are also cautiously made and assumed to be plausible when care is taken about the particular choice of ring and encoding scheme. In AppendixBwe show that if an encryption scheme is assumed to be a linear-only extractable encoding, then that encoding satises the generalized q-PDH and q-PKE assumptions over rings. Therefore, if our assumptions turn out to not hold for a non-trivial choice of ring and encoding, that would lead to an ecient encryption scheme (the encoding) over that ring which allows for more than just linear homomorphism, potentially towards a new fully/somewhat homomorphic encryption scheme.

On more ecient constructions. We take a small detour to discuss our choice of [GGPR13, PHGR13] as our reference SNARK construction. While there has been a lot of progress since [GGPR13] with contructions that oer more properties and better eciency, these two papers constitute a crucial milestone in the SNARK landscape, upon which other constructions have been built. As our work is the rst one that builds SNARKs over general commutative rings while requiring only black-box access to the ring’s operations, we consider generalizing the foundational work as a rst step and then focus on further improving their eciency. We hope that our work sets the stage for e.g. future SNARKs over rings with very small proofs (such as [Gro16]) or SNARKs over rings with an updatable CRS, both of which we discuss below.

The state-of-the art SNARK construction of Groth16 [Gro16] is very ecient and has a proof size of three group elements. The construction is, however, in the idealized Generic Group Model (GGM). Translating the ideas behind the construction to general rings would require idealized models over rings. We can in fact construct a SNARK along the lines of the construction of Groth16 and prove security assuming that the encoding satises \linear only extractability", which roughly means that the only operations that can be performed over the encodings are ane. While a similar assumption over elds is plausible for an encoding based on exponentiation in a bilinear group (in the GGM), this turns out to be a strong assumption for encodings over rings. Since we do not know of candidate instantiations, we give the Groth-16 like construction in AppendixF. Formalising a suitable idealized model for rings and exploring candidate encodings for linear-only assumptions is an interesting avenue for research.

While there has been recent progress on reducing the degree of trust in preprocessing SNARKs

• • by constructing \updatable CRS" SNARKs [GKM 18,MBKM19,CHM 20], QAP-based SNARKs give the best concrete eciency in terms of proof size. Our characterization of ring computation as a QRP and subsequent SNARK construction inherits the need for a trusted CRS generation. This allows us to obtain better proof sizes. Moreover, in the designated-verier setting, a trusted CRS is more acceptable in practice, since if we do not need ZK, we can simply have the verier run the setup and send the CRS to the prover, and reuse the CRS to prove many statements.

Privacy-preserving veriable computation. We show how our new (zk)-SNARK can be instantiated with polynomial rings in order to obtain a Veriable Computation (VC) scheme with input and output privacy. While veriable computation is a well-studied area, the problem of ensuring both correctness and privacy of the computation performed by untrusted machines remains one of the main concerns in this setting. The works solving this problem are far from achieving practical eciency.

A natural generic construction for such schemes would be to consider a straightforward combination of SNARKs and FHE, where FHE allows computation over encrypted data and a SNARK is used to verify the integrity of the results of the computation. However, such a generic construction results in a large overhead even when used with the most performant state-of-the-art SNARKs for arithmetic circuits over nite elds to prove FHE evaluations. This is due to the limitation of having to use QAP/SSP-based SNARKs for proving computations over ciphertexts which are not natu- rally expressed as eld elements. Therefore, such solutions do not scale well when the evaluation in FHE has to be emulated by arithmetic circuits over elds, and the resulting privacy-preserving VC schemes have very poor eciency.

1.3 Comparison with Related Work

The results of [BISW17] give constructions of a designated verier Succinct Non-interactive AR- Gument (SNARG) based on vector encryption over rings under the assumption that the encryption scheme satises linear targeted malleability. The subsequent work in [BISW18] constructs a SNARG with quasi-optimal prover complexity. Even though these works use an encoding scheme over a ring to compile the information theoretic object, the statement to be proven is represented as Boolean/arithmetic circuit satisability over a eld, and the computation is still over F_p. The underlying linear PCP is essentially a QSP/QAP. Crucially, in these works the statement to be proved is an arithmetic circuit over a eld, whereas our motivation is proving statements that are represented over rings like Z₂64 or a polynomial ring Rq= Zq[Y]=(f (Y)) directly.

$$ \mathbb{F}_{p} $$

$$ \mathbb{Z}_{2^{64}} $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

• In [KPP 14], Kosba et al. generalize the notion of Quadratic Arithmetic Programs over a eld F to that of Quadratic Polynomial Programs (QPPs), which compute circuits whose wires carry values in the ring F[X]. These polynomial circuits, where the addition and multiplication operations are over F[X], are introduced with the goal of representing (multi-)sets S of elements
• over F. While the construction in [KPP 14] is limited to rings of polynomials over the same elds for which SNARKs a la [PHGR13] are secure, our work allows to build SNARKs for any ring R satisfying the property that it has a large subset such that the dierence of the elements in the subset are invertible. Furthermore, our denition of QRP also recovers the QPP formulation as an instantiation of the underlying ring R, which we show in AppendixC.

$$ \mathrm{[K P P^{+}14]} $$

$$ \mathbb{F} $$

$$ \mathbb{F}[X] $$

$$ [\mathrm{K P P^{+}14}] $$

Privacy-Preserving Veriable Computation. To our knowledge, there are four main works that consider privacy in the context of VC. The rst one is the seminal paper of Gennaro et al. [GGP10] who introduced the notion of non-interactive veriable computation and builds it from garbled + circuits and FHE. The second work is that of Goldwasser et al. [GKP 13] shows how to use a 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 of these solutions [GGP10,GKP 13] are, however not very satisfactory in terms of eciency.

$$ [\mathrm{G K P^{+}13]} $$

A third work that considered the problem of ensuring correctness of privacy-preserving computation is the one by Fiore et al. [FGP14], who proposed using a VC in order to prove that the homomorphic evaluation of FHE ciphertexts has been done correctly. [FGP14] solution is inherently bound to computations of quadratic functions because the VC scheme is instantiated using homomorphic MACs.

To overcome this, the most recent work in this area by Fiore et al. [FNP20] proposes a new protocol for veriable computation on encrypted data that supports homomorphic computations of multiplicative depth larger than 1. Towards their VC scheme, [FNP20] build a new SNARK that can eciently handle computations of arithmetic circuits over a quotient polynomial ring R_q= Z_q[Y]=(f (Y)) for a prime number q in which the prover’s costs have a minimal dependence on the degree d of f (Y). Although this seems to t the arithmetic structure for Ring-LWE schemes, it imposes many limitations due to the restriction to rings R_qwhere q is not only a prime, but it also has to match secure and ecient pairing constructions for some underlying SNARK over F_q. Another signicant impact on the performance present in the work of [FNP20] is on the

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ q $$

$$ f(Y) $$

$$ \mathcal{R}_{q} $$

$$ \mathbb{F}_{q} $$ prover eort to evaluate the circuit C over ciphertexts. In their VC scheme, a prover performs the homomorphic evaluation of the Ring-LWE HE without reduction modulo f (Y), where f (Y) is the quotient polynomial that denes R_q= Z_q[Y]=(f (Y)). Instead, it computes the circuit C over Z_q[Y], processing polynomials of high degrees, namely the initial degree d grows linearly with the multiplicative depth of the circuit. This has a signicant overhead that adds to the delegated task itself.

$$ f(Y) $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ \mathbb{Z}_{q}[Y] $$

We take a step further and propose a better VC scheme with privacy that follows the same blueprint: combining homomorphic encryption and a SNARK. The latter is, in turn, based on encoding schemes that take as input ciphertexts of a Ring-LWE-based HE. The use of our generic SNARK for computation over rings allows for better choices of group order q which improves over the approach in [FNP20]. Moreover, in our construction, the prover is not asked to come up with a dierent witness than the one obtained via the delegation task it completed. Our SNARK allows then for speed up through classical eciency optimisations in R_qsuch as Number-Theoretic Transform (NTT). Also, we provide tools to enable the application of more advanced noise reduction techniques for the Ring-LWE scheme such as modulo switching. Furthermore, our scheme is in the plain model, while [FNP20] requires a random oracle. We give a detailed comparison of our application to privacy-preserving VC with the scheme of [FNP20] in Section7.3.

$$ \mathcal{R}_{q} $$

In a recent work of [BCFK20], the authors propose a new solution to veriable computation on encrypted data. Like [FNP20], the work of [BCFK20] uses the paradigm of combining VC and HE. However, in contrast to [FNP20] that requires the HE scheme to work with very specic parameters, the solution of [BCFK20] allows a exible choice of HE parameters. The key idea of the protocol in [BCFK20] is a new homomorphic hash function for Galois rings. While we treat veriable computation on encrypted data in our work too, we note that our work is more general { we construct (zk)SNARKs for ring computations. We achieve privacy-preserving veriable computation as an application of our SNARK over suitable rings. In addition, the instantiation given in [BCFK20] uses the GKR protocol that admits class of log-space uniform circuits. Our QRP abstraction yields SNARKs for general circuit computations, albeit while making knowledge assumptions similar to analogous SNARKs for elds.

2 Preliminaries

Notation. We use to denote the security parameter. A function is said to be negligible if for all large enough values of the input, it is smaller than the inverse of any polynomial. We use negl to denote a negligible function. We use PPT to denote probabilistic polyonomial time machines.

If A is a randomized algorithm, we use y A (x) to denote that y is the output of A on x. We write x X to mean sampling a value x uniformly from the set X. By writing Ak_A() we denote the execution of A followed by the execution of_Aon the same input and with the same random coins. The output of the two are separated by a semicolon.

$$ y\gets\mathcal{A}(x) $$

$$ x \rightarrow \mathcal {X} $$

$$ \mathcal{A}\rVert\chi_{\mathcal{A}}(\sigma) $$

$$ \chi_{A} $$

Whenever we talk about a ring R, unless otherwise specied, we always mean a commutative nite ring with identity. We denote the units of such a ring as R. Finally, we write Zpk to denote k the ring of integers modulo p.

$$ R^{*} $$

$$ p^{k} $$

$$ \mathbb{Z}_{p^{k}} $$

Denition 1(SNARK). A triple of polynomial time algorithms (Setup*;Prove;*Verify) is a SNARG for an NP language L with corresponding relation R, if the following properties are satised.

1.Completeness. For all (x;w) 2R, the following holds:

$$ (x,w)\in\mathcal{R} $$

$$ \operatorname*{P r}\left(\mathsf{V e r i f y}(\mathsf{v k},x,\pi)=1\ :\ {\begin{array}{l}{(\sigma,\mathsf{v k})\leftarrow\mathsf{S e t u p}(1^{\kappa})}\ {\pi\leftarrow\mathsf{P r o v e}(\sigma,x,w)}\end{array}}\right)=1 $$

2.Knowledge Soundness . For any PPT adversary A, there exists a PPT algorithm_Asuch that the following probability is negligible in :

$$ \chi_{A} $$

$$ \operatorname*{P r}\left(\begin{matrix}{\mathsf{V e r i f y}(\mathsf{v k},\tilde{x},\tilde{\pi})=1}\ {\land\mathcal{R}(\tilde{x},w^{\prime})=0}\ \ \mathrm{(\sigma,\mathsf{v k})\leftarrow\mathsf{S e t u p}(1^{\kappa})}\ {((\tilde{x},\tilde{\pi});w^{\prime})\leftarrow\mathcal{A}|\chi_{\mathcal{A}}(\sigma)}\end{matrix}\right) $$

3.Succinctness. For any x and w, the length of the proof is given by j j = poly() polylog(jxj+ jwj).

$$ | \pi | = \operatorname {p o l y} (\kappa) \cdot \operatorname {p o l y l o g} (| x | + $$

Non-black-box Extraction. The notion of Knowledge Soundness requires the existence of an extractor that can compute a witness whenever the adversarial prover produces a valid argument. The extractor we dened above is non-black-box and gets full access to the adversary’s state, including any random coins.

Zero-Knowledge. An SNARK is zero-knowledge if it does not leak any information besides the truth of the statement.

Denition 2(zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk- SNARK)). A zk-SNARK for a relation R is a SNARK for R with the following zero-knowledge property:

{ Zero-knowledge. There exists a PPT simulator (S₁; S₂) such that S₁ outputs a simulated CRS and trapdoor; S₂ takes as input, a statement x and, and outputs a simulated proof; and, for all PPT adversaries (A₁; A₂), the following is negligible in.

$$ (\mathcal{S}{1},\mathcal{S}{2}) $$

$$ \ mathcal\ S{_1} $$

$$ \tau;S_{2} $$

$$ \tau , $$

$$ (\mathcal{A}{1},\mathcal{A}{2}) $$

$$ \ \ K\ $$

$$ \beginedaligned}{}&{{}\left|\operatorname*{P r}\left(\begin{matrix}{(x,w)\in\mathcal{R}\wedge}\ {\mathcal{A}{2}(\pi,\mathsf{s t a r e})=1}&{{}:\begin{}}&({sigma,\mathsf{s t a r e})\leftarrow\mathcal{S}{1}(1^{\kappa},\sigma)}\ \ {}\ {\pi\leftarrow\mathsf{P r o o v}(\sigma,w)}}\ end{}\ \ {}begin{}&{{} $$

Public vs Designated veriability. In a publicly veriable SNARK, there is no private verication information, i.e. vk =;. A SNARK is designated veriable if the proof can be veried only by a party knowing vk. Note that in the designated-verier case, the verier’s decision bit on a proof potentially leaks some information about vk. Thus, the same common reference string cannot be reused for multiple proofs as in publicly-veriable case. This was addressed in prior works in veriable computation [GGP10,CKV10], by either keeping the decision bit secret from the prover, or running a fresh setup every time a proof fails verication. Note that any sound scheme can tolerate O(log) bits of leakage, and assuming that the decision bit leaks only a constant number of bits of information, one would only need to run a new setup after logarithmically-many proof rejections.

Strong Soundness. Multi-statement designated-verier SNARKs are requiring soundness to hold even against a prover that makes adaptive queries to a proof verication oracle.

2.1 Background in Ring Theory

We now turn to recall some useful results from ring theory. Most of the results here provided are standard. While some of the known results for elds and euclidean domains (such as Z) carry over to the more general rings we deal with, others do not. For example, one has to be careful about the fact that the rings we consider contain zero divisors, i.e. d 2 R nf0g for which 9 q 2 R nf0g such that d q = 0.

$$ d\in R\setminus{0} $$

$$ d\cdot q=0 $$

$$ \exists\ q q\in{0} $$

Lemma 1. Let R be a nite ring. Then all non-zero elements of R are either a unit or a zero divisor.

Proof. For every a 2 R nf0g, let f_a: R!R be the map given by f_a(x) = a x. If f_ais injective, then it has to be surjective, because R is nite. Therefore, in such a case there must exist an x 2 R verifying that f_a(x) = 1. So we conclude that a is a unit.

$$ a\in R\setminus{0} $$

$$ f_{a}:R\to R $$

$$ f_{a}(x)=a\cdot x $$

$$ f_{a} $$

$$ f_{a}(x)=1 $$

$$ x\in R $$

Assume that f_a(x) is not injective. Then there exist b;c 2 R;b 6= c; such that a b = a c, and thus a (b c) = 0. In other words, a is a zero divisor.

$$ f_{a}(x) $$

$$ b,c\in R,b\neq c. $$

$$ a\cdot b=a\cdot c, $$

$$ a\cdot(b-c)=0 $$

We recall that an ideal of a ring R is an additive subgroup I R such that r x 2 I for any r 2 R;x 2 I. Through the paper, (x) will denote the ideal generated by x 2 R.

$$ I\subseteq R $$

$$ r\cdot x\in I $$

$$ r\in R,x\in I $$

$$ x\in R $$

Theorem 1. Let R be a nite commutative ring with identity and let Z(R) denote the set of all its zero divisors. Then the following are equivalent:

1. Z(R) is an ideal.

2. Z(R) is a maximal ideal.

3. R is local.

4.Every x 2 Z(R) is nilpotent.

$$ x\in Z(R) $$

Proof. (1), (2). Assume Z(R) is an ideal and it is not maximal. Then, there must exist some ideal I such that Z(R) ( I ( R. Which is absurd, as if Z(R) ( I, then I must contain a unit and hence I = R.

$$ (1)\Leftrightarrow(2) $$

$$ Z(R) $$

$$ Z(R)\subsetneq I\subsetneq R $$

$$ Z(R)\subseteq I $$

(2)) (3). Assume R contains another maximal ideal I 6= Z(R). Then either I ( Z(R), in which case it is not maximal, or otherwise it contains a unit and hence I = R.

$$ I\neq Z(R) $$

$$ I \subsetneq Z (R) $$

(3)) (1). Let M be the maximal ideal of R. In order to see that Z(R) is an ideal, let x;y be any two zero-divisors and (x); (y) the ideals they generate. Because R is local, then (x) M and (y) M. Since M is a proper ideal of R, then we have that 8r 2 R, r (x + y) 2 M and that r (x + y) cannot be a unit. Hence, by Lemma1, r (x + y) 2 Z(R).

$$ x,y $$

$$ (x)\subset M $$

$$ (y)\subset M $$

$$ \forall r \in R, r \cdot (x + y) \in M $$

$$ r\cdot(x+y) $$

$$ r\cdot(x+y)\in Z(R) $$

(1)) (4). Assume Z(R) is an ideal, and assume towards contradiction some x 2 Z(R) such i that x 6= 0 for any positive integer i. Then, as R is nite, there must exist some i > j > 0 i j j i j j such that x = x, from which we deduce that x (x 1) = 0. As x 6= 0, then it has to i j i j be that x 1 2 Z(R). Then, as we also now that x 2 Z(R) and Z(R) is an ideal, then i j ^{i j} (x 1) x = 12 Z(R). Which is absurd, as then we would have that Z(R) = R.

$$ Z(R) $$

$$ x,\in,Z(R) $$

$$ x^{i}\neq0 $$

$$ x^{i},=,x^{j} $$

$$ i,>,j,>,0 $$

$$ x^{j}\cdot\left(x^{i-j}-1\right)=0 $$

$$ x^{j}\neq0 $$

$$ x^{i-j}-1,\in,Z(R) $$

$$ x^{i-j},\in,Z(R) $$

$$ \ (mathfrak x{}^{i-j}-1)-\mathfrak{x}{}^{i-j}=-1\in\mathbb{Z}(R) $$

$$ Z(R) $$

$$ Z(R)=R $$

(4)) (1). Let Z(R) = fx₁;:::;x_mg. We will prove that Z(R) is an ideal by showing the existence of some z 2 R such that z x_j= 0 for all j 2 [m], from which follows that Z(R) is an ideal. We construct z = z^mrecursively as follows. Because x₁ is nilpotent, there exists an a₁ s.t. a1+1 a1a_1ai x = 0 but x 6= 0, so we dene z₁ = x. For i 2 [m], we dene z_i= z_{i 1}x, where a_i(which 1 1 1 i is possibly zero) is chosen such that z_i6= 0 and z_ix_i= 0. Notice that a_imust exist from the fact that x_iis nilpotent.

$$ Z(R),=,{x_{1},\ldots,x_{m}} $$

$$ (4);\Rightarrow;(1) $$

$$ Z(R) $$

$$ z\cdot x_{j}=0 $$

$$ z\in R $$

$$ j\in[m] $$

$$ z=z_{m} $$

$$ Z(R) $$

$$ x_{1}^{a_{1}+1}=0 $$

$$ x_{1} $$

$$ z_{1}=x_{1}^{a_{1}} $$

$$ x_{1}^{a_{1}}\neq0 $$

$$ a_{1} $$

$$ i\in[m] $$

$$ z_{i}=z_{i-1}\cdot x_{i}^{a_{i}} $$

$$ z_{i}\neq0 $$

$$ a_{i} $$

$$ z_{i}\cdot x_{i}=0 $$

$$ x_{i} $$

$$ a_{i} $$

Theorem 2(Chinese Remainder Theorem). Let I₁;:::;I_mbe m pairwise co-prime⁴ ideals of R, i.e. 8i 6= j;I_i+ I_j= R. Denote I = I₁ I_m. Then the following map is a ring isomorphism:

$$ I_{1},\ldots,I_{m} $$

$$ c o - p r i m e ^ {4} $$

$$ R,,i.e.,\forall i\neq j,I_{i}+I_{j}=R $$

$$ I=I_{1}\cdots I_{m} $$

$$ R/I\to R/I_{1}\times\cdots\times R/I_{m} $$

$$ r\bmod I\mapsto(r\bmod I_{1},\ldots,r\bmod I_{m}) $$

Exceptional sets. Elements which satisfy that their pairwise dierences are invertible will be fundamental in our constructions. These have received dierent names in the literature: ‘Condition + (F)’ sets in [BCPS18], ‘exceptional sequences’ in [ACD 19] and ‘exceptional sets’ in [DLS20]. We will stick with the latter denomination.

$$ (\mathrm{F})^{?} $$

$$ [\mathrm{A C A^{+}19}] $$

Denition 3. Let A = fa₁;:::;a_ng R. We say that A is an exceptional set if 8i 6= j;a_ia_j2 R . We dene the Lenstra constant of R to be the size of the biggest exceptional set in R.

$$ A=\left{a_{1},\ldots,a_{n}\right}\subset R $$

$$ i f\forall i\neq j,a_{i}{!-}!a_{j}\in R^{*} $$

We will need the following generalization of the Schwartz-Zippel lemma.

n Lemma 2. [Generalized Schwartz-Zippel Lemma [BCPS18]] Let f : R! R be an n-variate non- zero polynomial. Let A R be a nite exceptional set. Let deg(f) denote the total degree of f. Then: deg(f)

$$ f:R^{n}\to R $$

$$ A\subseteq\ R R $$

$$ \operatorname*{P r}_{\vec{a}\leftarrow A^{n}}[f(\vec{a})=0]\leq\frac{d e g(f)}{|A|} $$

Proof. We prove by induction on the number of variables n. For n = 1, let a₁ 2 A be a root of f (x). As (x a₁) is a monic polynomial, we have that f (x) = (x a₁)f₁(x), where the deg(f₁) < deg(f). Any other root a₂ 2 A has to be a root of f₁(x), as (a₂ a₁) 2 R and f (a₂) = 0. Hence, we have that f (x) = (x a₁)(x a₂)f₂(x), where the deg(f₂) < deg(f₁). By iterating this argument, we conclude that f (x) cannot have more roots in A than deg(f) and hence Pr_{a A}[f (a) = 0] (deg(f))=jAj.

$$ f(x) $$

$$ n=1 $$

$$ a_{1}\in A $$

$$ \left(x-a_{1}\right) $$

$$ f(x)=\big(x-a_{1}\big)f_{1}\big(x\big) $$

$$ d e g(f_{1})<d e g(f) $$

$$ a_{2}\in A $$

$$ f_{1}(x) $$

$$ (a_{2}!-!a_{1})\in R^{*} $$

$$ f(a_{2})=0 $$

$$ f(x)=\ x-a_{1}\big)\ x-a_{2}\big)x_{2}(x) $$

$$ d e g(f_{2})<d e g(f_{1}) $$

$$ f(x) $$

$$ d e g(f) $$

$$ \operatorname{P r}_{a\leftarrow A}[f(a)=0]\leq(d e g(f))/|A| $$

Assume now the result holds for (n 1)-variate polynomials. Given any n-variate polynomial f (~x) 2 R[x₁;:::;x_n], denote by k = deg_xn(f) the largest power of x_nappearing in any monomial of f. Then we have that: k

$$ (n-1) $$

$$ f({\vec{x}})\in R[x_{1},\ldots,x_{n}] $$

$$ k=d e g_{x_{n}}(f) $$

$$ x_{n} $$

$$ f $$

$$ f({\vec{x}})=\sum_{\ell=1}^{k}x_{n}^{\ell}\cdot g_{\ell}(x_{1},\ldots,x_{n-1}) $$

Denote by E₁ the event g_k(~a) = 0. By denition of k, we know that g_k(x₁;:::;x_{n 1}) is a non-zero polynomial, so by induction hypothesis Pr_{a A}n 1 [E₁] (deg(f) k)=jAj. Assuming :E₁ and by applying the same reasoning as for n = 1, we have that f (*a*) 2 R[x_n] has at most k roots in A, so Pr_{a A}[f (*a*) = 0j:E₁] k=jAj. We nalize by noting that (where the probability is taking over the n choice of ~a A):

$$ \mathcal{E}_{1} $$

$$ g_{k}(\vec{a})=0 $$

$$ k_{i} $$

$$ g_{k}(x_{1},\ldots,x_{n-1}) $$

$$ \operatorname*{P r}{\vec{a}\leftarrow A^{n-1}}[\mathcal{E}{1}]:\leq:(\mathrm{}{d e g}(f):-:k)/|A| $$

$$ \neg \mathcal {E} _ {1} $$

$$ f(\vec{a})\in R[x_{n}] $$

$$ \Pr_ {\vec {a} \leftarrow A} [ f (\vec {a}) = 0 | \neg \mathcal {E} _ {1} ] \leq k / | A | $$

$$ n=1 $$

$$ {\vec{a}}\gets A^{n}) $$

$$ \begin{aligned}{\operatorname*{P r}[f(\vec{a})=0]=}&{{}\operatorname*{P r}[f(\vec{a})=0|\neg\mathcal{E}{1}]\cdot\operatorname*{P r}[\neg\mathcal{E}{1}]+\operatorname*{P r}[f(\vec{a})=0|\mathcal{E}{1}]\cdot\operatorname*{P r}[\mathcal{E}{1}]}\ {\leq}&{{}\operatorname*{P r}[f(\vec{a})=0|\neg\mathcal{E}{1}]+\operatorname*{P r}[\mathcal{E}{1}]\leq\frac{d\mathrm{}{d e g}(f)-k}{|A|}+\frac{k}{|A|}}\ \end{aligned} $$

⁴ Such ideals are also denoted co-maximal by some authors.

Interpolation. Lagrange interpolation for sets of points (x_i;y_i) 2 R² can be computed, as long as all the x_iare part of the same exceptional set A R. This follows from either looking at the denition of Lagrange basis polynomials or, more formally, from the Chinese Remainder Theorem (Theorem2). As an intuition of the latter approach, the ideals (x xi) are co-prime, so there is a Q d+1 one-to-one correspondence between any polynomial p(x) 2 R[x]=I, where I = (x x_i), and i₌₁ y₁ = p(x₁);:::;y_d+1= p(x_d+1). In other words, any p(x) 2 R[x] of degree d is uniquely determined by its evaluation at d points of an exceptional set. For more details about the CRT argument, see + e.g. [ACD 19].

$$ (x_{i},y_{i})\in R^{2} $$

$$ A,\subset,R $$

$$ x_{i} $$

$$ \mathrm{o r} $$

$$ (x - x _ {i}) $$

$$ p(x)\in R[x]/I $$

$$ y_{1}=p(x_{1}),\ldots,y_{d+1}=p(x_{d+1}) $$

$$ Itextstyle=\prod_{i=1}^{d+1}(x-x_{i}) $$

$$ p(x)\in R[x] $$

$$ \mathrm{..g.[{A C D^{+}19}]} $$

Galois Rings. Galois Rings are the generalization of Galois Fields to the ring case. Informally, a k Galois Ring relates to integers modulo p in the same way a Galois Field relates to integers modulo a prime p. In the following, we provide a high level overview of their properties and arithmetic. For a more detailed introduction to Galois Rings, see [Wan03].

$$ p^{k} $$

Denition 4. A Galois Ring is a ring of the form R = Zpk [X]=(h(X)), where p is a prime, k a positive integer and h(X) 2 Zpk [X] a monic polynomial of degree d 1 such that its reduction modulo p is an irreducible polynomial in F_p[X].

$$ R=\mathbb{Z}_{p^{k}}[X]/\big(h\ X\big), $$

$$ h(X),\in,\mathbb{Z}_{p^{k}}[X] $$

$$ d\geq1 $$

$$ \mathbb{F}_{p}[X] $$

Given a base ring Z_pk, there is a unique degree d Galois extension of Z_pk, which is precisely the Galois Ring provided on the previous denition. Hence, we shall denote such Galois Ring as ^k GR(p;d). Note that Galois Rings reconcile the study of nite elds Fpd = GR(p;d) and nite rings k of the form Zpk = GR(*p;*1).

$$ \mathbb{Z}_{p}^{k} $$

$$ \mathbb{Z}_{p}{{k\ k}} $$

$$ G R(p^{k},d) $$

$$ \mathbb{F}_{p^{d}}=G R(p,d) $$

$$ \mathbb{Z}_{p^{k}}=G R(p^{k},1) $$

k Every Galois Ring R = GR(p;d) is a local ring and its unique maximal ideal is (p). Hence, by Theorem1, all the zero divisors of R are furthermore nilpotent, and they constitute the maximal ideal (p). Furthermore, we have that R=(p)=F_pd, and thus a canonical homomorphism : R ! F_pd which can be computed by ‘reducing modulo p’.

$$ R=G R(p^{k},d) $$

$$ R/(p)\cong\mathbb{F}_{p^{d}} $$

$$ \pi:R\to\mathbb{F}_{p^{d}} $$

$$ p^{\prime} $$

• k d Proposition 1([ACD 19]). The Lenstra constant of R = GR(p;d) is p.

$$ R=G R(p^{k},d);s;p^{d}. $$

k In this work, we will be particularly interested in Galois Rings of the form R = GR(2*;d*), i.e. k of characteristic 2, maximal ideal (2) and such that R=(2) = F₂d. Whenever we need to explicitly represent elements a 2 R, we will do so as it follows from Denition4. In that case, we will say that a is given in its additive representation, which consists of the residue classes

$$ R=G R(2^{k},d) $$

$$ 2^{k} $$

$$ R/(2)\cong\mathbb{F}_{2^{d}} $$

$$ a\in R $$

$$ a\equiv a_{0}+a_{1}\cdot X+\ldots+a_{d-1}\cdot X^{d-1}\mod h(X),\quad a_{i}\in\mathbb{Z}_{2^{k}}. $$

(1)

3 Quadratic Programs over Commutative Rings

We extend Quadratic Arithmetic Programs (QAPs) from working over elds, as originally introduced in [GGPR13], to also cover commutative rings with identity. This gives us a characterization for the satisability of arithmetic circuits over such rings. Throughout this section, whenever we talk about rings, we restrict ourselves to commutative rings with identity.

Denition 5(Quadratic Ring Programs (QRP)). A Quadratic Ring Program (QRP) Q over a ring R consists of three sets of polynomials, V = fv_k(x) : k 2 [0*;m*]g; W = fw_k(x) : k 2 [0*;m*]g; Y = fy_k(x) : k 2 [0*;m*]g and a target polynomial t(x), all in R[X]. Let C be an arithmetic

$$ \left(Q R P\right)Q $$

$$ \mathcal{V}\ =\ {{\upsilon_{k}(x)\ :\ k\ \in\ [0,m]}},\mathcal{W}\ =\ {{w_{k}(x)\ :\ k\ \in} $$

$$ \ [0,m]},}{\mathcal{Y}},=\left{y_{k}(x):k\in\left[0,m\right]\right} $$

circuit over R with n inputs and n⁰ outputs. We say that Q is a QRP that computes C if the following holds:

$$ n^{\prime} $$

n+n0 a₁;:::;aⁿ;a^{m n0+1};:::a^m2 R is a valid assignment to the input/output variables of C if m n n0 and only if there exist an+1*;:::;a*_{m n}0 2 R such that:

$$ a_{1},\ldots,a_{n},a_{m-n^{\prime}+1},\ldots a_{m}{\ \in\ }R^{n+n^{\prime}} $$

$$ a_{n+1},\ldots,a_{m-n^{\prime}}\in R^{m-n-n^{\prime}} $$

$$ t(x);\mathrm{}{d i v i d e s};p(x), $$

P P m m where p(x) = V (x) W (x) Y (x), V (x) = v₀(x) + akvk(x), W(x) = w₀(x) + ak Pk=1 k=1 m w_k(x) and Y (x) = y₀(x) + a_ky_k(x). k₌₁

$$ p(x)=V(x)\cdot W(x)-Y(x),\ V(x)=\big(v_{0}(x)+\textstyle\sum_{k=1}^{m}a_{k}\cdot v_{k}(x)\big),\ W(x)=\big(w_{0}(x)+\textstyle\sum_{k=1}^{m}a_{k}:. $$

$$ w_{k}(x)_{\ }^{\top} $$

$$ \textstyle(Y)=(y_{0}(x)+\sum_{k=1}^{m}a_{k}\cdot y_{k}(x)) $$

We dene the size and degree of Q to be m and deg(t(x)) respectively. Given polynomials V (x);W(x);Y (x) 2 R[X] dened as above and corresponding to a valid assignment of the in- put/output wires, we will call them a QRP solution.

$$ \ t(t(x)) $$

$$ V(x),W(x),Y(x),\in,R[X] $$

Let C be a circuit whose gates have fan-in two and fan-out one. To build a QRP, we will make use of an exceptional set A as follows. We will pick elements rg2 A for each multiplication gate g 2 C Q and dene the target polynomial as t(x) = (x r_g). The v_k(x);w_k(x) and y_k(x) polynomials g2C can be computed by interpolating over the same r_g’s (which can be done for exceptional sets) in the same way one proceeds in the QAP case [GGPR13,PHGR13] (see our more detailed explanations below). Intuitively, QRP composition when the roots of t(x) are taken from the same exceptional set A follows from the same fact polynomial interpolation does: The ideals (x r_g) are co-prime and we can thus apply the Chinese Remainder Theorem. R[X]=(t(X)) ’ R ::: R, and we have a one-to-one correspondence between p(x) mod t(x) and p(r₁);:::;p(r_deg(t(x))).

$$ r_{q}\in A $$

$$ \textstyle{t\bigl(x\bigr)=\prod_{a\in\mathcal{C}}\bigl(x-r_{g}\bigr)} $$

$$ g\in C $$

$$ v_{k}(x),w_{k}(x) $$

$$ y_{k}(x) $$

$$ {r_{g}}^{\ \ }{}} $$

$$ t(x) $$

$$ (x-r_{g}) $$

$$ R[X]/(t(X))\simeq R\times\ldots\times $$

$$ p(x) $$

$$ t(x) $$

$$ p(r_{1}),\ldots,p(r_{d e g(t(x))}) $$

In Section3.1we prove in how to build a QRP for a multiplication sub-circuit and how to compose several QRPs into a single QRP for any arithmetic circuit, in a similar spirit to GGPR [GGPR13]. In Section3.2we show how to obtain the QRP directly, rather than through composition.

3.1 QRP Composition

Theorem 3. Let C be a circuit over the ring R containing only one multiplication gate. If C has m 1 inputs and a single output, there is a QRP of size m and degree 1 that computes C.

Proof. Let t(x) = x r, r 2 A, where A is the exceptional set. Dene1(X₁;:::;Xm 1) = c₀ + P P m ^{1 m 1} c_iX_i(resp.₂(X₁;:::;X_{m 1}) = d₀+ d_iX_i) to be the linear polynomial corresponding i=1 i=1 to the left (resp. right) input wire of the only multiplication gate in C. For k 2f0*;:::;m* 1g, let v_k(x) = c_k, w_k(x) = d_k, and y_k(x) = 0. Set v_m(x) = w_m(x) = 0 and y_m(x) = 1. Then we have that:

$$ t(x)=x-r,,r\in A $$

$$ \rho_{1}(X_{1},\ldots,X_{m-1})=C_{0}+ $$

$$ \textstyle{\sum_{i=1}^{m-1}c_{i}\cdotp_{X}} $$

$$ \rho_{2}(X_{1},\ldots,X_{m-1})=d_{0}+\textstyle\sum_{i=1}^{m-1}d_{i}\cdot X_{i}) $$

$$ k \in {0, \dots , m - 1 } $$

$$ v_{k}(x)=c_{k},,w_{k}(x)=d_{k} $$

$$ y_{k}(x)=0 $$

$$ v_{m}(x)=w_{m}(x)=0 $$

$$ y_{m}(x)=1 $$

$$ \begin{aligned}{\big(v_{0}(x)+\sum_{k=1}^{m}a_{k}\cdot v_{k}(x)\big)\cdot\big(w_{0}(x)+\sum_{k=1}^{m}a_{k}\cdot w_{k}(x)\big)-\big(y_{0}(x)+\sum_{k=1}^{m}a_{k}\cdot y_{k}(x)\big)}\ {=\rho_{1}(a_{1},\ldots,a_{m-1})\cdot\rho_{2}(a_{1},\ldots,a_{m-1})-a_{m}=p(x)}\ \end{aligned} $$

m We prove that this is a QRP for C. First assume that a₁;:::;a_m2 R is a valid assignment to the input/output of C. Then p(x) = 0, which is trivially divisible by t(x). Conversely, assume that the degree-zero polynomial p(x) is divisible by the degree-one t(x). As r is a root of t(x), then so it has to be of p(x), which implies p(x) = 0.

$$ a_{1},\ldots,a_{m}\in R^{m} $$

$$ p(x)=0 $$

$$ t(x) $$

$$ p(x) $$

$$ t(x) $$

$$ p(x) $$

$$ p(x)=0 $$

Composing QRPs. Our denition of QRPs and the construction of QRP above, allow for their composition exactly as in the eld case [GGPR13]. In the following, we use the symbol both for circuit and QRP composition. Note that the composition theorem below holds for the particular QRP construction of Theorem3, and we make no claims about other constructions that satisfy the QRP denition. In particular, we are careful to pick all the roots of the target polynomials to belong to the same exceptional set A.

For i 2f1*;* 2g, let Q_ibe a QRP computing an arithmetic circuit f_i. Let I_ibe the set of indices representing all wires in fⁱand allow I₁ \I₂ to ‘stitch’ up to ‘ output wires of I₁ to the inputs of (i) (i) (i) I₂. Denote such stitched circuit as C = C₂ C₁. Express Q_ias V = fv ₍x₎ : k 2I_ig; W = k _(i) (i) (i) (_i) fw ₍x) : k 2I_ig; Y = fy ₍x₎ : k 2I_ig and target polynom_ial t ₍x₎. Then, let Q = Q₂ Q₁ k k consists of V = fv_k(x) : k 2I₁ [I₂g; W = fw_k(x) : k 2I₁ [I₂g; Y = fy_k(x) : k 2I₁ [I₂g and a target polynomial t(x) which are constructed as follows.

$$ i\in{1,2} $$

$$ Q_{i} $$

$$ f_{i} $$

$$ \ {T}{}_{i} $$

$$ \mathcal{I}{1}\cap\mathcal{I}{2} $$

$$ f_{i} $$

$$ {\underline{{T}}}_{1} $$

$$ C=C_{2}\circ C_{1} $$

$$ \ {cal T}_{2} $$

$$ Q_{i} $$

$$ \mathcal{V}^{(i)}={v_{k}^{(i)}(x):k\in\mathcal{I}_{i}},\mathcal{W}^{(i)}= $$

$$ {w_{k}^{(i)}(x):k\in\mathcal{I}{i}},\mathcal{Y}^{(i)}={y{k}^{(i)}(x):k\in\mathcal{I}_{i}} $$

$$ t^{(i)}(x) $$

$$ Q=Q_{2}\circ Q_{1} $$

$$ \mathcal{V}={v_{k}(x){\ :\ }k\in\mathcal{I}{1}\cup\mathcal{I}{2}},\mathcal{W}={w_{k}(x){\ :\ }k\in\mathcal{I}{1}\cup\mathcal{I}{2}},\mathcal{Y}={y_{k}(x){\ :\ }k\in\mathcal{I}{1}\cup\mathcal{I}{2}} $$

$$ t(x) $$

(1) (2)~ First, dene t(x) = t (x) t (x). Second, for all indices k 2 I₂ nI₁, extend the denition (1) (1) (1) of the wire polynomials in Q₁ as v (x) = w (x) = y (x) = 0. Proceed analogously for Q₂ k~ k~ k~ ^(i) (i) and k 2I₁ nI₂. For all k 2I₁ [I₂ and i 2f1*;* 2g, we can now set v_k(x) v ₍x₎ mod t ₍x), k (_i) (i) (i) (i) w_k(x) w ₍x₎ mod t ₍x₎ and y_k(x) y ₍x₎ mod t ₍x₎. Such modular equivalences can be k k satised as long as the target polynomials have no common roots, as we show in the following lemma.

$$ t(x)=t^{(1)}(x)\cdot t^{(2)}(x) $$

$$ \widetilde{k},\in,\mathcal{I}{2},\setminus,\mathcal{I}{1} $$

$$ Q_{1} $$

$$ \ \ v{{}dot{{}{\tilde{k}}}}^x{(1)}(x),=,{{dot{{}{}}{\tilde{k}}}}^{(1)}(x),=,{_{\tilde{k}}}^{(1)}(x),=,0 $$

$$ Q_{2} $$

$$ {hat k\ \in\ }{\mathcal{I}}{1}\setminus{\mathcal{I}}{2} $$

$$ k\in\mathcal{I}{1}\cup\mathcal{I}{2} $$

$$ i\in{1,2} $$

$$ v_{k}(x)\equiv,v v_{k}^{(i)}(x) $$

$$ t^{(i)}(x) $$

$$ w_{k}(x)\equiv w_{k}^{(i)}(x) $$

$$ t^{(i)}(x) $$

$$ y_{k}(x)\equiv y_{k}^{(i)}(x) $$

$$ t^{(i)}(x) $$

(1) (2) Lemma 3. Let t (x), t (x) 2 R[X] be two polynomials which have roots only on the same (1) (2) exceptional set A R and such that they have no common roots. Let I₁ = (t (x)), I₂ = (t (x)) and I = I₁ I₂. Then R[X]=I ! R[X]=I₁ R[X]=I₂.

$$ t^{(1)}(x),;{t t^{(2)}(x)},\in,R[X] $$

$$ A\subset R $$

$$ I_{1}=(t^{(1)}(x)),,I_{2}=(t^{(2)}(x)) $$

$$ I=I_{1}\cdot I_{2} $$

$$ R[X]/I\xrightarrow{\sim}R[X]/I_{1}\times R[X]/I_{2} $$

Q(i) (i) (i) d Proof. For i 2f1*;* 2g, let t ⁽x⁾ = (x r). Dene ideals I^i;ji= (x r), where 1 jⁱdⁱ. jii=1 jiji Dene S = fI_i;ji: 1 i 2*;* 1 j_idⁱg. All the ideals ⁱn S are paⁱrwise coprime. To see that, take any K; K~ 2 S and re-denote for simplicity K = (x k); K~ = (x k). As k x 2 K, we have that k k = k x + x k~ 2 K + K. Hence, as k; k are two dierent elements from the same exceptional set A R, we have that k k~ is a unit and so K + K~ = R[X].

$$ i\in{1,2} $$

$$ t^{(i)}\bigl(x\bigr)=\prod_{j_{i}=1}^{d_{i}}\bigl(x-r_{j_{i}}^{(i)}\bigr) $$

$$ 1\leq j_{i}\leq d_{i} $$

$$ I_{i,j_{i}}=(x-r_{j_{i}}^{(i)}) $$

$$ S={I_{i,j_{i}}:1\leq i\leq2,1\leq j_{i}\leq d_{i}} $$

$$ \zeta,{\ddot{K}}\in S $$

$$ K=\big(x-k\big),\tilde{K}=\big(x-\tilde{k}\big) $$

$$ k-x\in K $$

$$ \ -\tilde{k}=k!-!x!+!x!-!\tilde{k}\in!\tilde{K}!+!\tilde{K} $$

$$ k,\dot{k} $$

$$ A\subset R $$

$$ k-\dot{k} $$

$$ K+\tilde{K}=R[X] $$

Given the above, we can apply the CRT (Theorem2) three times and conclude that

$$ R[X]/I_{1}\times R[X]/I_{2}\xrightarrow{\sim}(\prod_{j_{1}=1}^{d_{1}}R[X]/I_{1,j_{1}})\times(\prod_{j_{2}=1}^{d_{2}}R[X]/I_{2,j_{2}})\xrightarrow{\sim}R[X]/I. $$

We prove that the above construction for Q = Q₂ Q₁ indeed computes C = C₂ C₁.

$$ Q=Q_{2}\circ Q_{1} $$

$$ C=C_{2}\circ C_{1} $$

Theorem 4. Let C₁ and C₂ be two arithmetic circuits computed by QRPs Q₁ and Q₂. Assume the target polynomials of both QRPs have roots only on the same exceptional set A R, but no common roots. Allow also some of the input variables of C₂ to include some ‘ output variables from C₁, but let no other kind of overlapping between the arithmetic circuits be possible. Denote by C = C₂ C₁ the circuit obtained by stitching C₁ and C₂ together at those ‘ wires.

$$ C_{1} $$

$$ C_{2} $$

$$ Q_{1} $$

$$ Q_{2} $$

$$ A\subset R $$

$$ C_{2} $$

$$ C_{1} $$

$$ C=C_{2}\circ C_{1} $$

$$ C_{1} $$

$$ C_{2} $$

There exists a QRP Q with size jQj = jQ₁j + jQ₂j ‘ and deg(Q) = deg(Q₁) + deg(Q₂) that computes C. Q’s target polynomial is the product of the target polynomials for Q₁ and Q₂.

$$ |Q|=|Q_{1}|+|Q_{2}|-\ell $$

$$ \ e_{9}(Q)=d e g_{9}(Q_{1})+d e g_{9}(Q_{2}) $$

$$ Q_{1} $$

$$ Q_{2} $$

Proof. Let I_i=o; I₁_;i=o; I₂_;i=obe the indices of the input/output wires of C;C₁ and C₂, respectively. Suppose a_i=o= fa_k2 I_i=og is a valid input/output assignment for C. By denition, such input/output assignment can be extended to a valid assignment to all wires of C and hence in particular we can extend a_i=oto a valid assignment a~ = fa_k2I₁_;i=o[I₂_;i=og. Since Q₁ is a QRP, there exist coecients b = fb_k: k 2I₁g which are consistent with the valid assignment to I₁_;i=o and such that the polynomial X X

$$ \mathcal{I}{i/o},\mathcal{I}{1,i/o},\mathcal{I}_{2,i/o} $$

$$ C_{2}. $$

$$ C,C_{1} $$

$$ a_{i/o},=,\left{a_{k},\in,\ \mathcal{I}_{i/o}\right} $$

$$ a_{i/o} $$

$$ Q_{1} $$

$$ b={b_{k}:k\in\mathcal{I}_{1}} $$

$$ \tilde{a}=\left{a_{k}\in\mathcal{I}{1,i/o}\cup\mathcal{I}{2,i/o}\right} $$

$$ \mathcal{I}_{1,i/o} $$

$$ \begin{aligned}{p^{(1)}(x)=}&{{}\ \big(v_{0}^{(1)}(x)+\sum_{k\in\mathcal{I}{1}}b{k}\cdot v_{k}^{(1)}(x)\big)\cdot\big(w_{0}^{(1)}(x)+\sum_{k\in\mathcal{I}{1}}b{k}\cdot w_{k}^{(1)}(x)\big)}\ {}&{{}-\big(y_{0}^{(1)}(x)+\sum_{k\in\mathcal{I}{1}}b{k}\cdot y_{k}^{(1)}(x)\big)}\ \end{aligned} $$

(1) (2) is a multiple of t (x). The same reasoning can be applied to Q₂, for a polynomial p (x) dened from coecients c = fc_k: k 2I₂g which must exist by the fact that Q₂ is a QRP. By construction, b and c must be consistent for the indices in I₁ \I₂, as those are contained in both I₁_;i=oand I₂_;i=o, which were xed by the extended assignment a~. Therefore, we can dene a = fa_k2I₁ [I₂g as a_k= b_kfor all b_k2I₁ and a_k= c_kfor all c_k2I₂. Let X X

$$ t^{(1)}(x) $$

$$ Q_{2}. $$

$$ p^{(2)}(x) $$

$$ c={c_{k}:k\in\mathcal{I}_{2}} $$

$$ Q_{2} $$

$$ \mathcal{I}{1}\cap\mathcal{I}{2}. $$

$$ \mathcal{I}_{1,i/o} $$

$$ \mathcal{I}_{2,i/o}; $$

$$ b_{k}\in\ {\mathcal{I}}_{1} $$

$$ a_{k}=b_{k} $$

$$ a={a_{k}\stackrel{\cdot}{\in}\mathcal{I}{1}\cup\mathcal{I}{2}} $$

a k = b k for all b k 2I₁ and a k = c k for all c k 2I₂ . Let

$$ c_{k}\in\mathcal{I}_{2} $$

$$ a_{k}=c_{k} $$

$$ \begin{aligned}{p(x)=}&{{}\ \big(v_{0}(x)+\sum_{k\in\mathcal{I}{1}\cup\mathcal{I}{2}}a_{k}\cdot v_{k}(x)\big)\cdot\big(w_{0}(x)+\sum_{k\in\mathcal{I}{1}\cup\mathcal{I}{2}}a_{k}\cdot w_{k}(x)\big)}\ {}&{{}\quad-\big(y_{0}(x)+\sum_{k\in\mathcal{I}{1}\cup\mathcal{I}{2}}a_{k}\cdot y_{k}(x)\big)}\ \end{aligned} $$

(i) (i) (i) where v^k(x);w^k(x) and y^k(x) are dened from v ⁽x⁾;w ⁽x⁾ and y ⁽x), i 2f1*;* 2g, as described k k k above (note the hypothesis of Lemma3are satised). We show that t(x) divides p(x). Since v_k(x) = (1) (1) (1) (1) (1) ⁽¹⁾ v (x) mod t (x), w^k(x) w (x) mod t (x) and y^k(x) y (x) mod t (x) for all k, and k k k (1)(1) since v(x) = w(x) = y(x) 0 mod t (x) for all k 2I₂ nI₁, we conclude that t (x) divides k k k (2) p(x). Applying analogous reasoning, we can deduce that t (x) divides p(x) and, thus, t(x) = ⁽¹⁾ (2) t (x) t (x) divides p(x)

$$ v_{k}(x),w_{k}(x) $$

$$ y_{k}(x) $$

$$ y_{k}^{(i)}(x),i\in{1,2} $$

$$ v_{k}^{(i)}(x),w_{k}^{(i)}(x) $$

$$ t(x) $$

$$ v_{k}^{(1)}(x) $$

$$ p(x) $$

$$ v_{k}(x)= $$

$$ t^{(1)}(x),,w_{k}(x)\equiv w_{k}^{(1)}(x) $$

$$ t^{(1)}(x) $$

$$ y_{k}(x)\equiv y_{k}^{(1)}(x) $$

$$ t^{(1)}(x) $$

$$ v_{\tilde{k}}\big(x\big)=w_{\tilde{k}}\big(x\big)=y_{\tilde{k}}\big(x\big)\equiv0 $$

$$ t^{(1)}(x) $$

$$ \check{k}\in\mathcal{I}{2}\setminus\mathcal{I}{1} $$

$$ t^{(1)}(x) $$

$$ p(x) $$

$$ t^{(2)}(x) $$

$$ t^{(1)}(x)\cdot t^{(2)}(x) $$

$$ p(x) $$

$$ t(x),= $$

$$ p(x) $$

Conversely, let p(x) be dened from the polynomial sets V; W and Y as above and such that t(x) divides p(x). We show that any set of coecients a enabling such divisibility contains a valid assignment a_i=o= fa_k2I_i=og to the input/output wires of C. As p(x) 0 mod t(x), by Lemma3, (i) p(x) 0 mod t ⁽x) for i 2f1*;* 2g. Since Q₁ and Q₂ are QRPs, it follows that a must then contain valid assignment to the input/output wires of C₁ and C₂. As I_i=oI₁_;i=o[I₂_;i=o, we have found a valid assignment a_i=oto the input/output wires of C.

$$ p(x) $$

$$ t(x) $$

$$ p(x) $$

$$ a_{i/o}=\left{a_{k}\in\mathcal{I}_{i/o}\right} $$

$$ p(x)\equiv0 $$

$$ t(x) $$

$$ p(x)\equiv0 $$

$$ i\in{1,2} $$

$$ Q_{1} $$

$$ t^{(i)}(x) $$

$$ Q_{2} $$

$$ C_{1} $$

$$ C_{2}. $$

$$ \mathcal{I}{i/o}\subseteq\mathcal{I}{1,i/o}\cup\mathcal{I}_{2,i/o} $$

$$ a_{i/o} $$

Finally, we conclude by showing how to build a QRP for any arithmetic circuit by using the previous results from this section.

Theorem 5. Let C be an arithmetic circuit with n inputs in (a subring of ) R and s < jAj multi- plication gates, each with fan-in 2*. If each output wire of C is the output of a multiplication gate,* there is a QRP with size n + s and degree s that computes C.

$$ s<|A| $$

$$ n+s $$

Proof. We obtain this result by combining Theorem3and Theorem4, one multiplication gate at a time. As long as s < jAj, we can ensure that the target polynomials of the QRPs for each multiplication gate do not have common roots, so that Theorem4can be invoked.

$$ s,<|,A| $$

There is only one small task remaining. Let C be a circuit with n~ 1 output wires which are not the output of multiplication gates. Our last result does not teach us how to deal with C, but we can build a modied circuit C~ for which the hypothesis of Theorem5are satised. As in [GGPR13], C~ has one additional ‘dummy’ input wire, which is required to be always assigned to the multiplicative identity 1. Furthermore, C~ has a n additional multiplication gates: For each of them, the left gate-input wire is the ‘dummy’ circuit-input wire and the right gate-input wire is one of the circuit-output wires which did not satisfy the hypothesis of Theorem5. It follows that the QRP of size n + s + ~n + 1 and degree s + ~n that computes C also computes the original C.

$$ \tilde{n}\geq1 $$

$$ \tilde{C} $$

$$ s+\tilde{n} $$

$$ n+s+\tilde{n}+1 $$

$$ \tilde{C} $$

3.2 Direct QRP construction.

Given a circuit C, we can construct a QRP for C using the composition theorem above. We can also construct a QRP directly for the given circuit without relying on composition. Let C be a circuit whose gates have fan-in two and fan-out one. To build a QRP, we will make use of an exceptional set A as follows. In order to dene the target polynomial, we will pick elements rg2 A for each Q multiplication gate g 2 C and dene t(x) = (x r_g). We dene the polynomials v_k(x);w_k(x) g2C and y_k(x) by interpolating over those same points in the same way one proceeds in the QAP case [PHGR13]. As an example for this procedure, see Figure1.

$$ r_{g}\in A $$

$$ g\in C $$

$$ \textstyle{t\bigl(x\bigr)=\prod_{q\in C}\bigl(x-r_{g}\bigr)} $$

$$ v_{k}(x),w_{k}(x) $$

$$ y_{k}(x) $$

$$ (\mathcal{V},\mathcal{W},\mathcal{Y},t(x)) $$

$$ v_{3}(r_{5})=1 $$

$$ w_{4}(r_{5})=1 $$

$$ y_{5}(r_{5})=1 $$

$$ v_{k}(r_{5})=0, $$

$$ w_{k}(r_{5})=0, $$

$$ y_{k}(r_{5})=0, $$

$$ k\neq3 $$

$$ k\neq4 $$

$$ k\neq5 $$

$$ v_{1}(r_{6})=v_{2}(r_{6})=1 $$

$$ w_{5}(r_{6})=1 $$

$$ y_{6}(r_{6})=1 $$

$$ v_{k}(r_{6})=0, $$

$$ w_{k}(r_{6})=0, $$

$$ y_{k}(r_{6})=0, $$

$$ k\neq1,2 $$

$$ k\neq5 $$

$$ k\neq6 $$

Fig. 1. Arithmetic circuit and equivalent QRP. The polynomials V = fvk(x) : k 2 [6]g; W = fwk(x) : k 2 [6]g; Y = fyk(x) : k 2 [6]g and the target polynomial t(x) = (x r₅)(x r₆) are dened in terms of their evaluations at two random points belonging to the same exceptional set (r₅;r₆ 2 A), one for each multiplicative gate.

$$ \mathcal{V}:=:{v_{k}(x):::k:\in:[6]},\mathcal{W}:=:{w_{k}(x):::k:\in:[6]} $$

$$ \mathcal{Y}=\left{y_{k}(x):k\in[6]\right} $$

$$ t(x)=\big(x-r_{5}\big)\big(x-r_{6}\big) $$

4 Secure Encoding Schemes over Rings

To construct a SNARK, we follow the framework in [GGPR13]. The QRP polynomials are represented by encodings of the polynomials evaluated at a secret point, and the encoding used is additively homomorphic in the ring of computation. We now dene these encodings and their properties.

Denition 6(Encoding scheme). An encoding scheme Encode over a ring R consists of a tuple of algorithms (Gen*;E).*

{ (pk*;sk) Gen(1 ), a key generation algorithm that takes as input a security parameter and* outputs a secret key sk*, and public information* pk*.*

$$ -,(\ {mathsf p p},{\mathsf s}{\mathsf k})\leftarrow{\mathsf G e}(1^{\kappa}) $$

{ s E(a), a probabilistic encoding algorithm mapping a ring element a 2 R to an encoding s in encoding space S such that the sets ffE(a)g : a 2 Rg partition S, where fE(a)g is the set of encodings of a. Depending on the encoding algorithm, E could require the secret state sk*. To* ease notation, we will omit this additional argument.

$$ -\ s{\leftarrow}{mathsf E}(a) $$

$$ a\in R $$

$$ {{\mathsf{E}(a)}:a\in R} $$

$$ {\ {\mathsf{E}}(a)} $$

An encoding scheme has to satisfy the following properties:

{ ‘-Linearly homomorphic: There is an ecient algorithm Eval that on input public information P ‘ ‘ pk*, encodings* E(a₁);::: E(a_‘) and coecients c₁;:::;c_‘2 R computes the encoding E( c_i i₌₁ a_i).

$$ \mathsf{E}(a_{1}),\ldots\mathsf{E}(a_{\ell}) $$

$$ c_{1},\ldots,c_{\ell}\in R^{\ell} $$

$$ \textstyle\mathsf{E}(\sum_{i=1}^{\ell}c_{i},. $$

$$ a_{i}) $$

{ Quadratic root detection: There exists an algorithm that given secret key sk*;(E(a₁);:::* E(a_d)), and a quadratic polynomial Q(x₁;:::;x_t) 2 R[X₁;:::;X_t], can distinguish whether Q(a₁;:::;a_t) = 0*.*

$$ (\mathsf{E}(a_{1}),\dots\mathsf{E}(a_{d})) $$

$$ Q(x_{1},\ldots,x_{t})\in R[X_{1},\ldots,X_{t}] $$

$$ Q(a_{1},\ldots,a_{t})= $$

{ Image verication: There exists an ecient algorithm that given sk*, and an element c, can* detect if c is a valid encoding of some element in R.

{ Correctness: We say that the encoding scheme is (statistically) correct if all valid encodings are decoded successfully (with overwhelming probability).

4.1 Secure Encodings

While the denition of encoding above can be satised by, for instance, the identity function, we will only be interested in secure encodings, i.e. those which satisfy certain cryptographic assumptions. In the following, A (resp. A) denotes an exceptional set of a commutative ring with identity R (resp. R, the units of that ring).

$$ A^{*}) $$

$$ R^{*} $$

Assumptions. We rely on computational assumptions about the encoding scheme. These have been previously used in the discrete-logarithm group setting, and here we generalize them to encodings over rings. We also show (in AppendixB) how our assumptions follow from the more intuitive, but + stronger, notion of linear-only extractable encodings from [BCI 13].

We start by giving a generalized version of the q-PDH problem used in [GGPR13]. This assumption has two dierences with respect to the original one. First of all, the adversary is able to q+1 win the game as long as it outputs a pair (a;y) such that a 6= 0 and y 2fE(a s)g. In the eld 1 q+1 q+1 case, this is trivially equivalent to the original q-PDH assumption, as a E(a s) = E(s). Nevertheless, in the ring case, we need to deal with elements a 2 R which might be zero divisors. q Second, in order to have the assumption work for any given q, we need to ensure that s² 6= 0. Due to this and additional security reasons, we restrict s to be a unit. Furthermore, we need s to be part of a big enough exceptional set, so that we can prove the soundness of our SNARKs by invoking the Generalized Schwartz-Zippel lemma.

$$ a\neq0 $$

$$ (a,y) $$

$$ y \in \left{\mathrm {E} \left(a \cdot s ^ {q + 1}\right) \right} $$

$$ a^{-1}\cdot\mathsf{E{}}(a\cdot s^{q+1})=\mathsf{E}(\ s^{q+1}) $$

$$ a\in R $$

$$ s^{2q}\neq0 $$

Assumption 1 (Generalized q-PDH) The generalized q-power Die-Hellman assumption holds for an encoding scheme Encode if, for every non-uniform PPT algorithm A, the following holds:

$$ q^{\mathrm{{\ H D H}}}) $$

$$ \Pr \left(a \neq 0 \wedge y \in {\mathrm {E} (a \cdot s ^ {q + 1}) }: \begin{array}{c} (\mathrm {p k}, \mathrm {s k}) \leftarrow \operatorname {G e n} \left(1 ^ {\kappa}\right), \ s \leftarrow A ^ {*}, \ \sigma = (\mathrm {p k}, \mathrm {E} (1), \mathrm {E} (s), \dots , \mathrm {E} \left(s ^ {q}\right), \mathrm {E} \left(s ^ {q + 2}\right), \mathrm {E} \left(s ^ {2 q}\right)), \ (a, y) \leftarrow \mathcal {A} (\sigma) \end{array}\right) \leq \frac {1}{| A |} + \operatorname {n e g l} (\kappa). $$

Note that we linked our generalization of q-PDH to the size of the exceptional set A. Usually, we will consider A to be of exponential size in the security parameter, so that the previous probability is just negligible in the security parameter. Nevertheless, for the purpose of parallel soundness amplication techniques, in some cases it will be useful to consider even exceptional sets of constant size.

$$ q^{\mathrm{{P D D}}} $$

$$ A^{*} $$

$$ A^{*} $$

We also need a q-power knowledge assumption, which is both augmented to handle the designated verier setting and generalized to encodings over rings.

Assumption 2 (Generalized Augmented q-PKE) The generalized augmented q-power knowl- edge of encoding assumption holds for an encoding scheme Encode and for the class Z of \benign" auxiliary input generators if, for every non-uniform PPT auxiliary input generator Z 2 Z and for all non-uniform PPT algorithm A there exists a non-uniform PPT extractor_Asuch that the following probability is negligible in the security parameter: 0 1

$$ q{\ \cdot}\mathtt{P K E}) $$

$$ Z;\in;\mathcal{Z} $$

$$ \chi_{A} $$

$$ \operatorname*{P r}\left(\begin{matrix}{\hat{c}-\alpha c=0}&{(\mathsf{p k},\mathsf{s k})\leftarrow\mathsf{G e n}(1^{\kappa}),\alpha\in R mathsf{s}^{\kappa},s\leftarrow A^{\kappa},}\ {\stackrel{\wedge}{c\neq\sum_{i=0}^{q}a_{i}s^{i}}}&{\ \ \sigma=(\mathsf{p k},\mathsf{E}(1),\mathsf{E}(s),\ldots,\mathsf{E}(s^{q}),\mathsf{E}(\alpha),\mathsf{E}(\alpha s),\ldots,\mathsf{E}(\alpha s^{q})),}\ {}&{z\leftarrow\mathsf{Z}(\sigma))}\ {(\mathsf{E}(c),\mathsf{E}(\mathsf{e});a_{0},\ldots,a_{q})\leftarrow(\mathcal{A}||\chi_{\mathcal{A}})(\sigma,z)}\ \end{matrix}\right). $$

In the above, (x; y) (Ajj_A)(;z) denotes that on input (;z), A outputs x, and_Agiven the same input (;z), and A’s random tape, outputs y. When we assume that Z is benign, we mean that the auxiliary information z is generated with a dependency on sk*;s* and that is limited to the extent that it can be generated eciently from.

$$ (x;y)\leftarrow(\mathcal{A}||\chi_{\mathcal{A}})(\sigma,z) $$

$$ (\sigma,z) $$

$$ x! $$

$$ \chi_{\mathcal{A}} $$

$$ y_{\ } $$

$$ (\sigma,z) $$

$$ \scriptstyle $$

$$ \mathsf{s k},s $$

$$ \alpha $$

$$ \sigma $$

5 Designated Verier SNARK

The QRP characterization allows a test for satisability of an arithmetic circuit, by checking if the P P P target polynomial divides p(x) = c_kv_k(x) c_kw_k(x) c_ky_k(x) . If divisibility holds, there is a quotient polynomial that is guaranteed to exist that serves as a witness for this test. To construct a succinct proof, we follow the blueprint of [GGPR13,PHGR13]: the QRP test is performed in a probabilistic way at a random point chosen during the setup. Toward this end, the prover is expected to give, in the proof, the polynomials V (x);W(x);Y (x) computed as a linear combination of the QRP polynomials using the intermediate witness values c_kas coecients. The prover also provides the quotient polynomial H(x), and verication checks whether V (s) W (s) Y (s) = H(s) t(s), where s is the random point that is hidden from the prover. The CRS consists of an encoding of this secret point together with encodings of the QRP polynomials, and the prover homomorphically computes the elements in the proof.

$$ p(x):=:(\textstyle\sum c_{k}:\cdot:v_{k}(x)):\cdot:(\textstyle\sum c_{k}:\cdot w_k x) $$

$$ V(x),W(x),Y(x) $$

$$ c k $$

$$ H(x) $$

$$ Y(s)=H(s)\cdot t(s) $$

$$ V(s)\cdot W(s)- $$

Besides the security assumptions we introduced in the previous section, our designated verier SNARK construction will mostly rely on the two following technical lemmas. The rst one will be useful to dene the concrete soundness error of our construction, while the second one is an analogue of [GGPR13, Lemma 10]. At a high level, this second lemma will be invoked in the security proof to ensure that, if the adversary outputs a false proof that passes verication that implicitly uses some V (x) that is not in the span of the QRP polynomial set fv_k(x)g, then the reduction will be able to use that false proof to solve a q-PDH challenge.

$$ V(x) $$

$$ {v_{k}(x)} $$

Lemma 4. Given an exceptional set of size n in R, we can construct another exceptional set A = f0*;a₁;:::;a*_{n 1}: a_i2 R g. When an exceptional set has the latter form, we say it is given in its canonical form.

$$ A=\left{0,a_{1},\ldots,a_{n-1}:a_{i}\in R^{*}\right} $$

Proof. Let B = fb₁;:::;b_ng R be an exceptional set. For all i 2f1*;:::;n* 1g, dene a_i= b_nb_i. By the denition of B, we have that a_i2 R and hence so is (0 a_i). Furthermore,8i 6= j;a_ia_j= (b_nb_i) (b_nb_j) = b_ib_jwhich is again a unit by the denition of B.

$$ B=\left{b_{1},\ldots,b_{n}\right}\subset R $$

$$ i\in{1,\ldots,n!-!1} $$

$$ a_{i}=b_{n}\ b_{i} $$

$$ a_{i}\in R^{*} $$

$$ (0!-!a_{i}) $$

$$ \forall i\neq j,a_{i}!-!a_{j}= $$

$$ \left(b_{n}-b_{i}\right)-\left(b_{n}-b_{j}\right)=b_{i}-b_{j} $$

:(e) Lemma 5. Let R[x]_edenote the polynomials in R[x] of degree at most e. Let R[x] denote e polynomials over R[x] that have a zero coecient for x. Let A R be an exceptional set. We :(e) dene A [x]_e, A [x] analogously. Given a set U = fu_i(x)g R[x]_esuch that jUj = m, let span(U) denote the set of polynomials that can be generated as R-linear combinations of the polynomials in U. Let a(x) 2 A [x]_e+1be generated uniformly at random subject to the constraint :(e+1) that fa(x) u_i(x) : u_i(x) 2Ug R[x]. Let s A . Then, if e > m 1*, for all algorithms A,*

$$ R[x]_{\leq e} $$

$$ R[x] $$

$$ R[x]^{\neg(e)} $$

$$ R[x] $$

$$ x^{e} $$

$$ A^{}\subset R^{} $$

$$ A^{}[x]_{\leq e},\dot{A^{}[x]^{\neg{(e)}}} $$

$$ {\mathcal{U}},=,{u_{i}(x)},\subset,{\mathcal{R}}[x]_{\leq e} $$

$$ |mathcal U=m $$

$$ a(x)\in A^{*}[x]_{\leq e+1} $$

$$ {a(x)\cdot u_{i}(x)\ \colon\ u{{}_{i}(x)}\in{\mathcal{U}}}\subset{\ \mathrm{R}}[x]^{\neg(e+1)} $$

$$ f f,e>m-1 $$

$$ s\gets A^{*} $$

$$ \Pr \left( \begin{array}{c} u (x) \in R [ x ] _ {\leq e} \wedge \ u (x) \notin \operatorname {s p a n} (\mathcal {U}) \wedge \ a (x) \cdot u (x) \in R [ x ] ^ {\neg (e + 1)} \end{array} : u (x) \leftarrow \mathcal {A} \left(\mathcal {U}, s, a (s)\right) \right) \leq \frac {1}{\left| A ^ {*} \right|} $$

e Proof. Let u(x) = u₀ + u₁x + ::: + u_ex 2 R[x] and u(x) 2= span(U). Dene the vector u = (u₀; :::;u_e;0), corresponding to the coecients of the monomials in u and padded with a zero, and similarly dene ui= (ui;0;:::;ui*;e;0) for every ui(x) 2U. Then, u is not in the span of the vectors S e_{+1 e} (s;s;:::; 1) u_i. This follows from the assu*mption that u(x) 2= span(U) and the fact that i2[m] e+1 e the last element of u is a 0 and that of (s;s;:::; 1) is 1.

$$ u (x) = u _ {0} + u _ {1} x + \dots + u _ {e} x ^ {e} \in R [ x ] $$

$$ uboldsymbol=(left\boldsymbol{u}_{0}) $$

$$ u(x)\notin s p a n(\mathcal{U}) $$

$$ \dots,u_{e},0) $$

$$ u_{i}=\left(u_{i,0},\ldots,u_{i,e},0\right) $$

$$ u_{i}(x)\in\mathcal{U} $$

$$ \textstyle(s^{e+1},s^{e},\ldots,1)\bigcup_{i\in[m]}u_{i} $$

$$ u(x)\notin s p a n(\mathcal{U}) $$

$$ (s^{e+1},s^{e},\ldots,1) $$

This time following the opposite order, dene a vector a = (a_e+1;:::;a₀) from the coecients e+1 of a(x) = a₀ + + a_e+1x. Th^en, A has the following information about a(x):

$$ \ \ a\(\ a_{e+1},\ldots,a_{0}) $$

$$ a(x)=a_{0}+\cdots+a_{e+1}\cdot x^{e+1} $$

$$ a(x) $$

$$ \begin{aligned}{\langle\mathbf{a},(s^{e+1},s^{e},\dots,1)\rangle}&{{}=a(s)}\ {\langle\mathbf{a},(u_{i,0},\dots,u_{i,e},0)\rangle}&{{}=0,\quad i\in[m]}\ \end{aligned} $$

(2)

:(e+1) Where the second set of equations comes from the fact that fa(x) u_i(x) : u_i(x) 2Ug R[x]. This provides a system of m + 1 linear equations on the e + 2 coecients a, so as e > m 1 by hypothesis, a appears uniformly random to A.

$$ {\alpha(x)\cdot u_{i}(x)\ u_{i}(x)\in\mathcal{U}}\subset mathbf{mathit R[[}x]^{\neg(e+1)} $$

$$ e>m-1 $$

Finally, assume that A manages to satisfy the last missing condition for u(x), that is a(x) u(x) 2 S :(e+1) e+1 _e R[x], which is equivalent to ha; ui = 0. Since u is not in the span of (s;s;:::; 1) u_i, _i2[m] it is not a linear combination of the equations constituting the system in (2). Hence, since every a_i2 A and a appears uniformly random to A (subject to the constraints provided by the system of linear equations), by looking at u as the coecients of a polynomial u(x₁;:::;x_e+2) = u₀ x₁ + u₁ x₂ + + u_ex_e+1+ 0 x_e+2, we have that Pr[ha; ui = 0] = Pr[u₍a) = 0] 1*=jA j* as a direct consequence of the Generalized Schwartz-Zippel Lemma (Lemma2).

$$ R[x]^{\neg(e+1)} $$

$$ a(x)!\cdot!u(x)\in $$

$$ u(x) $$

$$ \langle a,u\rangle=0 $$

$$ \textstyle\big(s^{e+1},s^{e},\ldots,1\big)\bigcup_{i\in[m]}u_{i}; $$

$$ a_{i}\in A^{*} $$

$$ \tilde{u}(x_{1},\ldots,x_{e+2})=u_{0}\cdot x_{1}+ $$

$$ u_{1}\cdot x_{2}+\cdots+u_{e}\cdot x_{e+1}+0\cdot x_{e+2} $$

$$ \operatorname*{P r}[\langle\mathbf{a},\mathbf{u}\rangle=0]=\operatorname*{P r}[\tilde{u}(\mathbf{a})=0]\leq1/|A^{*}| $$

5.1 Construction from QRP

Let C be an arithmetic circuit over R, with m wires and d multiplication gates. Let A be an exceptional set given in canonical form and A_Q= f0*;a₁;:::;a*_{d 1}g A. Using A_Q, dene the m QRP Q = (t(x); fv^k(x);w^k(x);y^k(x)g) which computes C. Let A = A n A_Q, which satises that k=0 A R, since A is in canonical form.

$$ A_{\mathcal{Q}}=\left{0,a_{1},\ldots,a_{d-1}\right}\subset A $$

$$ A_{Q} $$

$$ A^{*}=A\setminus A_{Q} $$

$$ A^{}\subseteq R^{} $$

We denote by I_io= 1*;* 2*;:::‘* the indices corresponding to the public input and public output values of the circuit wires and by I_mid= ‘ + 1*;:::m*, the wire indices corresponding to non-input, non-output intermediate values. We construct a SNARK scheme Rinocchio = (Setup*;Prove;*Verify) for ring arithmetic as described in Figure2.

$$ I_{i o}=1,2,\dots\ell $$

$$ I_{m i d}=\ell+1,\ldots m $$

Setup(1; R) (pk*;sk) Gen(1); s A ; rv;rw R ; ry* = rv rw ;v;w;y R ; R nf0g i d crs = fE(s)gⁱ₌₀; fE(rv vk(s))gk2Imid; fE(rw wk(s))gk2Imid; fE(ry yk(s))gk2Imid; fE(rv vk(s))gk2Imid; fE(rw wk(s))gk2Imid; fE(ry yk(s))gk2Imid; i d fE(s)gⁱ₌₀; fE( (rv vk(s) + rw wk(s) + ry yk(s))gk2Imid;pk (3) vk = (sk;crs;s;;;rv;rw;ry) Prove(crs;u;w) Verify(vk;u;) u = (a₁;:::;a_‘); a₀ = 1*;* w = (a;:::;a) = (A; A;B; ^ B;C; ^ C;D; ^ D;F ^); ‘+1 m Pm^ ^ A = E(rv Vmid); A = E(rv Vmid); v(x) =k=0akvk(x) P ^ ^ B = E(rw Wmid); B = E(rw Wmid); vmid(x) =k2Imidakvk(x) C = E(r Y); C^ = E(r Y^); Pm y mid y mid w(x) =k=0akwk(x) ^ = E( ^) P D = E(H); D H; F = E(L) wmid(x) = akwk(x) ‘ k2Imid vio(x) = P aivi(x) P Pi=0 m ‘ y(x) =k=0akyk(x) wio(x) = aiwi(x) P Pi=0 y (x) = a y (x)‘ mid k2Imid k k yio(x) = aiyi(x) i=0 v(x)w(x) y(x) Lspan = rv Vmid+ rw Wmid+ ry Ymid h(x) = P = (v (s) + V) (w (s) + W) (y (s) + Y) t(x)io mid io mid io mid Check: V^ = V; f = rv vmid(s) + rw wmid(s) + ry ymid(s) mid mid ^ = E( W^ = W*;* A = E(rv vmid(s)); A rv v vmid(s)); mid mid B = E(r w (s)); B^ = E(r w (s)); Y^ = Y; w mid w w mid mid mid C = E(r y (s)); C^ = E(r y (s)); ^ = y mid y y mid H H (4) D = E(h(s)); D^ = E(h(s)); F = E(f): L = Lspan (5) return = (A; A;B; ^ B;C; ^ C;D; ^ D;F ^) P = H t(s) (6)

$$ \alpha,\alpha_{v},\alpha_{w},\alpha_{y}\gets R^{*},,\beta\gets R\setminus\left{0\right} $$

$$ \left{\mathrm {E} \left(\alpha s ^ {i}\right) \right} _ {i = 0} ^ {d}, \left{\mathrm {E} \left(\beta \left(r _ {v} w _ {k} (s) + r _ {w} w _ {k} (s) + r _ {y} y _ {k} (s)\right)\right) \right} _ {k \in I _ {m i d}}, \mathrm {p k}) $$

$$ \mathsf{v k=}\left(\mathsf{s k,c r s},s,\alpha,\beta,r_{v},r_{w},r_{y}\right) $$

$$ u=\big(a_{1},\ldots,a_{\ell}\big),\ a_{0}=1 $$

$$ \pi=(A,\hat{A},B,\hat{B},C,\hat{C},D,\hat{D},F), $$

$$ w=\left(a_{\ell+1},\ldots,a_{m}\right) $$

$$ A=\mathsf{E}\big(r_{v}V_{m i d}\big),;;\hat{A}=\mathsf{E}\big(r_{v}\hat{V}_{m i d}\big), $$

$$ v(x)=\sum_{k=0}^{m}a_{k}v_{k}(x) $$

$$ B=\mathsf{E}\big(r_{w}W_{m i d}\big),\hat{B}=\mathsf{E}\big(r_{w}\hat{W}_{m i d}\big), $$

$$ \begin{array}{r}{v_{m i d}\big(\boldsymbol{x}\big)=\sum_{k\in{I_{m i d}}}a_{k}v_{k}\big(\boldsymbol{x}\big)}\end{array} $$

$$ C = \mathsf {E} \left(r _ {y} Y _ {m i d}\right), \hat {C} = \mathsf {E} \left(r _ {y} \hat {Y} _ {m i d}\right), $$

$$ w(x)=\sum_{k=0}^{m}a_{k}w_{k}(x) $$

$$ D=\mathsf{E}(\dot{H}),;\hat{D}=\mathsf{E}(\dot{H}),;\dot{F}=\mathsf{E}(\boldsymbol{L}) $$

$$ w_{m i d}\big(\boldsymbol{x}\big)=\sum_{k\in I_{m i d}}a_{k}w_{k}\big(\boldsymbol{x}\big) $$

$$ v_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}v_{i}\big(x\big) $$

$$ w_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}w_{i}\big(x\big) $$

$$ y(x)=\sum_{k=0}^{m}a_{k}y_{k}(x) $$

$$ y_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}y_{i}\big(x\big) $$

$$ y_{m i d}\big(\boldsymbol{x}\big)=\sum_{k\in I_{m i d}}a_{k}y_{k}\big(\boldsymbol{x}\big) $$

$$ L_{s p a n}=r_{v}V_{m i d}+r_{w}W_{m i d}+r_{y}Y_{m i d} $$

L h ( x ) = span = r v V mid + r w W mid + r y Y mid

$$ h(x)={\frac{v(x)w(x)-y(x)}{t(x)}} $$

$$ P\dot{=}(v_{i o}(s)+V_{m i d})\cdot(w_{i o}(s)+dot{W}{m i d})-(y{i o}(s)+Y_{m i d}) $$

$$ f=r_{v}v_{m i d}(s)+r_{w}w_{m i d}(s)+r_{y}y_{m i d}(s) $$

$$ \hat{V}{m i d}=\alpha V{m i d}, $$

$$ A=\ \ mathsf E{(r_{v}\upsilon_{\mathrm{}{m i d}}(s))},\ \hat{A}=\ \mathsf E({r_{v}\alpha_{v}\upsilon_{\mathrm{}{m i d}}(s)}). $$

$$ \hat{W}{m i d}=\alpha W{m i d}, $$

$$ B = \mathrm {E} \left(r _ {w} w _ {m i d} (s)\right), \hat {B} = \mathrm {E} \left(r _ {w} \alpha_ {w} w _ {m i d} (s)\right), $$

$$ \hat{Y}{m i d}=\alpha Y{m i d}, $$

$$ C=\mathsf{E}(r_{y}y_{\mathrm{}{m i d}}(s)),\ \hat{C}=\mathsf{E}(r_{y}\alpha_{y}y_{\mathrm{}{m i d}}(s)) $$

$$ {\hat{H}}=\alpha H $$

$$ D=\mathsf{E}(h(s)),\ \hat{D}=\mathsf{E}(\alpha h(s)),\ F=\mathsf{E}(\beta f) $$

$$ L=\beta L_{s p a n} $$

$$ {\mathrm{r e t u r n}},\pi=,(A,{\hat{A}},B,{\hat{B}},{\mathcal{C}},{\hat{C}},D,{\hat{D}},F) $$

$$ P=H\cdot t(s) $$

Fig. 2. The Rinocchio scheme for (zk-)SNARKs over a ring R.

Zero-knowledge. We can make our construction zero-knowledge by randomizing the elements in the proof such that the checks verify and the proof is statistically indistinguishable from random encodings. The idea is for the prover to add random multiples of t(x) to the proof terms so that we can dene a simulator that \fakes" the proof elements from completely random values. Specically,

$$ t(x) $$ the prover chooses random_v;_w;_yR, and adds_vt(s) inside the encoding to v_mid(s);_wt(s) to w_mid(s); and_yt(s) to y_mid(s). It is easy to see that the modied value of p(x) remains divisible by t(x).

$$ \delta_{v},\delta_{w},\delta_{y}\leftarrow R $$

$$ \delta_{v}t(s) $$

$$ w_{m i d}(s) $$

$$ v_{m i d}(s);,\delta_{w}t(s) $$

$$ \delta_{y}t(s) $$

$$ y_{m i d}(s) $$

$$ p(x) $$

$$ t(x) $$

The following terms should be added to crs: E(r_vt(s));E(r_wt(s)), E(r_yt(s)), E(_vr_vt(s)); E(_wr_wt(s)); E(_yr_yt(s); E(r_vt(s)), E(r_wt(s)), E(r_yt(s)). The prover can now compute the new values in using the terms in the crs, and the verication proceeds as before.

$$ \mathsf{E}(r_{v}t(s)),\mathsf{E}(r_{w}t(s)),\mathsf{E}(r_{y}t(s)),\mathsf{E}(\alpha_{v}r_{v}t(s)),;\mathsf{E}(\alpha_{w}r_{w}t(s)) $$

$$ \mathsf{E}(\alpha_{y}r_{y}t(s),\ \mathsf{E}(r_{v}{\beta}t(s)),\ \mathsf{E}(r_{w}{\beta}t(s)),\ \mathsf{E}(r_{y}{\beta}t(s)) $$

Remark 1. Note that our construction has a proof size of nine elements, as opposed to eight elements in Pinocchio [PHGR13]. This saving in Pinocchio is a result of removing the repeated (with scalar) encoding of the quotient polynomial h(x). We remark that this means that in the proof of security, one cannot invoke PKE to extract the quotient polynomial. Indeed, Pinocchio does not extract the polynomial explicitly and, for the security proof to go through, they require multiplication of encoded values (multiplication in the exponent). This relies on more than just quadratic root detection from the encoding, it needs one quadratic computation in the reduction. While exponentiation admits this multiplication via pairings, we do not make the assumption that an encoding scheme in the designated verier setting allows this in general. Therefore, we fall back on including an additional proof element, and additional CRS elements to enable this computation.

$$ \alpha) $$

$$ h(x) $$

Remark 2. Another aspect of our construction that could look surprising to the reader is the definition of A : Why do we not include the elements in A_Qused to dene the QRP? As previously discussed, we do this in order to precisely dene the soundness of our construction. In some cases, as we will discuss in Section6.3, it could be useful to use parallel repetition strategies for soundness amplication. Previous works in the eld setting, using pairings, did not need to make such a concrete analysis, since if circuits are assumed to be of polynomial size in the security parameter, the probability that a randomly sampled s F would be precisely one of the points used to dene the QRP would be negligible, because F has exponential size in the security parameter. In all rigour, nevertheless, the concrete soundness error of those constructions is also bounded by the size of F minus the size of the QRP⁵. We prefer this concrete analysis even when rings might have exceptional sets of exponential size in the security parameter.

$$ A_{Q} $$

$$ s\gets\mathbb{F} $$

$$ \mathbb{F} $$

$$ \mathbb{F} $$

$$ \mathrm{Q R P^{5}} $$

5.2 Security proof

We are now ready to prove that Rinocchio satises the properties of a SNARK as stated in Denition

1. We remark that we do not prove strong soundness, which demands that soundness holds even when the prover has access to the verication oracle. While some designated-verier schemes are provably strongly sound, the reduction requires the d-PKEQ assumption (see Assumption3in AppendixB) on the encoding scheme to hold. For the sake of keeping Rinocchio as general as possible in the choice of rings and encodings, we do not make that assumption, but our result could be adapted to that case.

Theorem 6. Let R be commutative ring with identity with an exceptional subset A, and d be an upper bound on the degree of the QRP. Assuming that the generalized augmented (4d + 3)-PKE and the generalized q-PDH assumptions hold for the encoding scheme Encode over R (and A ) for q = 4d+ 4*, the protocol* Rinocchio described above is a SNARK as per Denition1, with soundness error 1=jA j.

$$ q=4d+4 $$

$$ A^{*} $$

$$ 1/|A^{*}| $$

⁵ In order to see this, consider a proof that consists purely of encodings of zero. The checks in the verication equations would pass if s happened to coincide with a value in the QRP used to describe a multiplication gate with no connections to input or output wires. This applies to e.g. [PHGR13].

Completeness. Assuming the encoding scheme Encode satises (statistical) correctness, then it follows by inspection that the verication equations are satised by a correctly generated proof. Therefore (statistical) completeness of the Rinocchio protocol follows by QRP completeness.

Soundness. Assume there exists an adversary A who returns the proof of a false statement. We use this adversary A in order to construct an adversary B who breaks the q-PDH assumption.

Setting up the CRS. Adversary B is given the description of the encoding scheme, and the challenge q q+2 q E(1);E(s); :::; E(s), E(s);:::; E(s²). B provides the crs to A by constructing it as follows. It 0 0 d+1 0 2(d+1) samples r_v0;r_w;;_v;_w;_yat random from R and sets r_y0= r_v0r_w. Let r_v= r_v0s, r_w= r_ws, 3(^d+1) and r_y= r_y0s. The value is chosen as follows. Sample a polynomial_poly(x) 2 A [X] of degree at most 3d + 3 uniformly at random, subject to the constraint that^poly(x) (rv0v_k(x) + 0 (d+1) 2(d+1) d+3 q (4_d+3) r_wx w_k(x)+r_y0x y_k(x)) has a zero coecient for x³ for all k. B sets = s_poly(s). q (4d+3) Looking ahead in our proof, the polynomial x_poly(x) will play the role of a(x) in Lemma5. B sets the CRS as follows:

$$ \mathsf{E}(1),\mathsf{E}(s),;.;..;,mathsf{E}(s^{q}),;\mathsf{E}(s^{q+2}),\ldots,\mathsf{E}(s^{2q}) $$

$$ r_{v}^{\prime},r_{w}^{\prime},\alpha,\alpha_{v},\alpha_{w},\alpha_{y} $$

$$ R^{*} $$

$$ r_{y}^{\prime}=r_{v}^{\prime}r_{w}^{\prime} $$

$$ r_{v}=r_{u}^{I}s^{d+1},r_{w}=r_{u}^{I\prime s}s{{}}^{2(d+1)} $$

$$ r_{y};=;r_{y}^{\prime}s^{3(d+1)} $$

$$ \beta $$

$$ \beta_{p o l y}(x),\in,A^{*}[X] $$

$$ 3d+3 $$

$$ \beta_ {p o l y} (x) \cdot \left(r _ {v} ^ {\prime} v _ {k} (x) + \right. $$

$$ r_{w}^{\prime}x^{(d+1)}w_{k}(x)!+!r_{y}^{\prime}x^{2(d+1)}y_{k}(x), $$

$$ x^{3d+3} $$

$$ \beta=s^{q-(4d+3)}\beta_{p o l y}(s) $$

$$ x^{q-(4d+3)}\cdotp\beta_{p o l y}(x) $$

$$ a(x) $$

$$ \begin{array}{l} \mathrm {c r s} = \left({\mathrm {E} \left(s ^ {i}\right) }{i = 0} ^ {d}, {\mathrm {E} \left(r _ {v} v _ {k} (s)\right) }{k \in I _ {m i d}}, {\mathrm {E} \left(r _ {w} w _ {k} (s)\right) }{k \in I _ {m i d}}, {\mathrm {E} \left(r _ {y} y _ {k} (s)\right) }{k \in I _ {m i d}}, \right. \ \left{\mathrm {E} \left(\alpha_ {v} r _ {v} v _ {k} (s)\right) \right} _ {k \in I _ {m i d}}, \left{\mathrm {E} \left(\alpha_ {w} r _ {w} w _ {k} (s)\right) \right} _ {k \in I _ {m i d}}, \left{\mathrm {E} \left(\alpha_ {y} r _ {y} y _ {k} (s)\right) \right} _ {k \in I _ {m i d}}, \ \left{\mathrm {E} \left(\alpha s ^ {i}\right) \right} _ {i = 0} ^ {d}, \left{\mathrm {E} \left(\beta \left(r _ {v} v _ {k} (s) + r _ {w} w _ {k} (s) + r _ {y} y _ {k} (s)\right)\right) _ {k \in I _ {m i d}}, \mathrm {p k}\right) \ \end{array} $$

We now argue that B can construct the above crs using the terms provided in its challenge. Consider the term in the proof that involves, which is the nal proof term that the prover will have to compute using the CRS.

$$ \beta, $$

$$ \begin{aligned}{}&{{}\mathsf{E}(\beta(r_{v}v_{m imathrm}{{d}}(s)+r_{w}w_{imathrm{{{m d d}}}}(s)+r_{y}y_{i d}(s)))}\ {}&{{}=\mathsf{E}(\beta(r_{v}^{\prime}s^{d+1}v_{i d}(s)+r_{w}^{\prime}s^{2(d+1)}w_{i{imathrm}{}}(s)+r_{y}^{\prime}s^{3(d+1)}y_{i}i s({)})).}\ \end{aligned} $$

In this term, is multiplied by a polynomial evaluated at s. Note that B generated also as a polynomial evaluated at s. If we further rewrite (7) by expressing in terms of s, we have

(7)

$$ \beta $$

$$ \beta $$

$$ \beta $$

$$ \begin{aligned}{}&{{}\mathsf{E}(s^{q-3d-2}r_{a}^{\prime}\beta_{\mathrm{}{p o l y}}(s)v_{\mathrm{}{m i d}}(s)+s^{q-2d-1}r_{a}^{\prime}\beta_{\mathrm{}{p o l y}}(s)w_{\mathrm{}{m i d}}(s)+s^{q-d}r_{y}^{\prime}\beta_{\mathrm{}{p o l y}}(s)y_{\mathrm{}{m i d}}(s))}\ {}&{{}=\mathsf{E}(s^{q-3d-2}\beta_{\mathrm{}{p o l y}}(s)(r_{v}^{\prime}w_{\mathrm{}{m i d}}(s)+s^{d+1}r_{w}^{\prime}w_{\mathrm{}{m i d}}(s)+s^{2d+2}r_{y}^{\prime}y_{\mathrm{}{m i d}}(s))).}\ \end{aligned} $$

(8)

0 d+1 d+2 d+3 Since^poly(x) (rv0v^k(x) + r^wx w^k(x) + r^y0x² y^k(x)) has a zero coecient in front of x³, q+1 the value underneath the encoding in (8) has a zero in front of s. The powers of s in the encoding go up to (q 3d 2) + (3d+ 3) + (2d+ 2) +d = q+ 3d+ 3 2q. The polynomials v_k(x);w_k(x);y_k(x) q+1 are of degree d, and none of the other elements in the CRS contain s inside the encoding. Since we have q 4d + 4, all the elements in the CRS can be generated using terms in the challenge.

$$ \beta_{p o l y}(x)\cdot(r_{v}^{\prime}v_{k}(x)+r_{w}^{\prime}x^{d+1}w_{k}(x)+r_{w}^{\prime}x^{2d+2}y_{k}(x)) $$

$$ x^{3d+3} $$

$$ s^{q+1} $$

$$ (q-3d-2)+(3d+3)+(2d+2)+,=d=q+3d+3\leq2q. $$

$$ v_{k}(x),w_{k}(x),y_{k}(x) $$

$$ s^{q+1} $$

$$ q\geq4d+4 $$

We need to make sure that a crs generated as above has a distribution which is indistinguishable to the one given in our protocol. Note that, as_poly(x) is a polynomial of degree at most 3d+ 3 and q (4d⁺³⁾ = s_poly(s), we have that Pr[ = 0] (3d + 3)=jA j (Lemma2). This is a bigger chance for = 0 than in our protocol, but notice that A never sees in the clear, but rather encodings of it. There are hence two cases: Either E(0) is computationally indistinguishable from any E(a) where a 6= 0, or it is not (as it happens in the exponentiation-based encodings of e.g. [GGPR13,PHGR13]). In the former case, A will accept the crs. In the latter case, B checks whether = 0 by distinguishing whether the last term of crs is E(0) and, if so, samples a new_poly(x) and repeats the process above until the last term is not E(0).

$$ \beta_{p o l y}(x) $$

$$ \beta=s^{q-(4d+3)}\beta_{p o l y}(s) $$

$$ 3d\ +3 $$

$$ \operatorname*{P r}[big\ \beta=0\big]\leq\big(3d+3\big)/\big|A^{*}\big| $$

$$ \beta=0 $$

$$ Emathsf(00 $$

$$ \mathsf{E}(a) $$

$$ a\neq0 $$

$$ \beta=0 $$

$$ \beta_{p o l y}(x) $$

Extraction. With the CRS set this way, B can now obtain a purported proof from A. Due to the indistinguishability of simulated CRS and real CRS, A aborting on input the tailored CRS is negligible. Let ^ be a purported proof returned by A, which is parsed as follows:

$$ \hat{\pi} $$

$$ \begin{array}{l} \hat {\pi} = \left(\mathrm {E} \left(r _ {v} V _ {m i d}\right), \mathrm {E} \left(r _ {w} W _ {m i d}\right), \mathrm {E} \left(r _ {y} Y _ {m i d}\right), \mathrm {E} (H), \right. \ \mathrm {E} \left(r _ {v} \hat {V} _ {m i d}\right), \mathrm {E} \left(r _ {w} \hat {W} _ {m i d}\right), \mathrm {E} \left(r _ {y} \hat {Y} _ {m i d}\right), \mathrm {E} (\hat {H}), \mathrm {E} (L) \ \end{array} $$

d+1 0 2(d+1) 3(d+1) Since B knows that r_v= r_v0s, r_w= r_ws, an^d r_y= r_y0s, it can reinterpret ^ as follows:

$$ r_{v}=r_{v}^{\prime}s^{d+1},,r_{w}=r_{w}^{\prime}s^{2(d+1)} $$

$$ \hat{\pi{}} $$

$$ r_{y},=,r_{y}^{\prime}s^{3(d+1)} $$

$$ \begin{array}{l} \left(\mathrm {E} r _ {v ^ {\prime}} ^ {\prime} \left(s ^ {d + 1} V _ {m i d}\right), \mathrm {E} r _ {w ^ {\prime}} ^ {\prime} \left(s ^ {2 d + 2} W _ {m i d}\right), \mathrm {E} r _ {y ^ {\prime}} ^ {\prime} \left(s ^ {3 d + 3} Y _ {m i d}\right), \mathrm {E} (H), \right. \ \mathrm {E} r _ {v ^ {\prime}} ^ {\prime} \left(s ^ {d + 1} \hat {V} _ {m i d}\right), \mathrm {E} r _ {w ^ {\prime}} ^ {\prime} \left(s ^ {2 d + 2} \hat {W} _ {m i d}\right), \mathrm {E} r _ {y ^ {\prime}} ^ {\prime} \left(s ^ {3 d + 3} \hat {Y} _ {m i d}\right), \mathrm {E} (\hat {H}), \mathrm {E} (L) \ \end{array} $$

Notice that the proof elements are now being treated as if they belonged to four dierent encodings: E*;* E^r0; E^r0; E^r0, ^where the four latter are dened as E^a(b) = E(a b). It is easy to see that, by the fact v w y 0 that r;r;r 2 R and the assumption that E is a secure encoding, so are E_r0; E_r0; E_r0. Since ^ v0 w y0v w y passes verication (in particular Equation (4)), we can apply the following reasoning for E and any of the other three encodings. As (E(H);E(H^)) is of the form (E(H);E(H)), B can use the d-PKE P d i extractor_Ato extract a polynomial H(x) = h_ix of _degree at most d such that H = H(s). i=0 This is because the CRS given to A is of the form (;z), where:

$$ \mathsf{E},\mathsf{E}{r{\ }^{\prime},},\mathsf{E}{r{\ }^{\prime},},\mathsf{E}{r{_}{^\prime}} $$

$$ \mathsf{E}_{a}(b)=\mathsf{E}(a!\cdot!b) $$

$$ r_{v}^{\prime},r_{w}^{\prime},r_{y}^{\prime^\prime}\in R^{*} $$

$$ \mathsf{E}{r{v}^{\prime}},\mathsf{E}{r{w}^{\prime}},\mathsf{E}{r{u}^{\prime}} $$

$$ \hat{\pi} $$

$$ (\mathsf{E}(H),\mathsf{E}(\hat{H})) $$

$$ (\mathsf{E}(H),\mathsf{E}(\alpha H)) $$

$$ \chi_{A} $$

$$ H(x)=\sum_{i=0}^{d}h_{i}x^{i} $$

$$ (\sigma,z) $$

$$ H=H(s) $$

$$ \sigma=\big(\mathsf{p k},{\mathsf{E}(s^{i})}{i=0}^{d},{\mathsf{E}(\alpha s^{i})}{i=0}^{d}\big),\quad z=\mathsf{c r s}\setminus\sigma $$

d+1 Note that the auxiliary information z is independent of, as the relation between e.g. E^r0 (s V^mid) v d⁺¹^ and E_r0 (s V_mid) is an i.i.d._v. If we look at any of the three remaining encodings E_r0 ( ), E_r⁰ ( ) ^v v _v or E_r0 ( ), we will next show that B can extract V_mid(x) of degree at most d and such that V_mid= v V_mid(s) due to the (2d+ 1)-PKE assumption (resp. W_mid(x) due to (3d+ 2)-PKE and Y_mid(x) due to (4d+ 3)-PKE). Focusing on V_mid(x), notice that A does not have a (2d+ 1)-PKE challenge, but the following (where the problem is with ~_v, not with z)

$$ \alpha, $$

$$ \mathsf{E}{r{v}^{\prime}}(s^{d+1}V_{m i d}) $$

$$ \mathsf{E}{r{v}^{\prime}}(s^{d+1}\hat{V}_{m i d}) $$

$$ \alpha_{v} $$

$$ \mathsf{E}{r{v}^{\prime}}(\cdot),:\mathsf{E}{r{v}^{\prime}}(\cdot) $$

$$ \mathsf{E}{r{\eta}^{\prime},(\cdot)} $$

$$ V_{m i d}(x) $$

$$ V_{m i d}= $$

$$ V_{m i d}(s) $$

$$ W_{m i d}(x) $$

$$ (3d+2)\mathrm{-}\mathrm{P K E} $$

$$ Y_{m i d}(x) $$

$$ (4d+3)\mathrm{-}P\mathrm{K E}, $$

$$ V_{m i d}(x) $$

$$ \tilde{\sigma}_{v} $$

$$ \tilde{\sigma}{v}=\big(\mathsf{p k},{\mathsf{E}{r_{v}^{\prime}}\big(s^{d+1}v_{k}(s)\big)}{k\in I{m i d}},{\mathsf{E}{r{v}^{\prime}}\big(\alpha_{v}s^{d+1}v_{k}(s)\big)}{k\in I{m i d}}\big),\quad z=\mathsf{c r s}\setminus\tilde{\sigma}_{v} $$

i 2=0 d+1 i d+1 which diers from the expected^v= (pk*; fE^r0 (s)g; fE^r0 (^vs g²) ⁱn two ways: It is comv i v i=0 i d pletely missing* the powers fs g an_d, for those between d + 1 and 2d + 1, it instead has the i=0 d+1 evaluation at s of the polynomials fx v_k(x)g_k2I. Informally, sⁱnce B can compute ~_vfrom_v, mid we can extract. In more syntactic rigour, B can send_vto a (2d+ 1)-PKE adversary A_vwho runs internally the SNARK prover A on ~v, so as Equation (4) veries, then, by the PKE assumption P d+1 d d+1+i there exists an extractor_Avwhich gets a polynomial x V_mid(x) = v_ix of _degree _i=0 at most 2d + 1 such that V_mid= V_mid(s). Applying the same reasoning, we can conclude on the extraction of polynomials W_mid(x);Y_mid(x) of degree at most d such that W_mid= W_mid(s) and Y_mid= Y_mid(s).

$$ \sigma_ {v} = \left(\mathrm {p k}, \left{\mathsf {E} _ {r _ {v} ^ {\prime}} \left(s ^ {i}\right) \right} _ {i=0} ^ {2 d + 1}, \left{\mathsf {E} _ {r _ {v} ^ {\prime}} \left(\alpha_ {v} s ^ {i}\right) \right} _ {i=0} ^ {2 d + 1}\right) $$

$$ {s^{i}}_{i=0}^{d} $$

$$ d+1 $$

$$ 2d+1 $$

$$ {x^{d+1}v_{k}(x)}{k\in I{m i d}} $$

$$ \tilde{\sigma}_{v} $$

$$ \sigma_{v}. $$

$$ \sigma_{v} $$

$$ \mathcal{A}_{v} $$

$$ \tilde{\sigma}_{v} $$

$$ x^{d+1}V_{m i d}(x)=\sum_{i=0}^{d}v_{i}x^{d+1+i} $$

$$ \chi_{A_{v}} $$

$$ 2d+1 $$

$$ V_{m i d}=V_{m i d}(s) $$

$$ W_{m i d},=,W_{m i d}(s) $$

$$ W_{m i d}(x),Y_{m i d}(x) $$

$$ Y_{m i d}=Y_{m i d}(s) $$

Reducing to PDH. Since the proof ^ veries but the statement is false, we show that then one of P the following must hold, where V (x) = c_kv_k(x) + V_mid(x) and similarly W (x) and Y (x): k2Iio

$$ \hat{\pi} $$

$$ V(x)=\sum_{k\in I_{i o}}c_{k}v_{k}(x)+V_{m i d}(x) $$

Case 1: V (x) W (x) Y (x) 6= H(x) t(x), but Equation (6) holds, therefore, V (s) W (s) Y (s) = H(s) t(s).

$$ H(s)\cdot t(s) $$

Case 2: The polynomial

$$ U(x)=r_{v}^{\prime}x^{d+1}V_{m i d}(x)+r_{w}^{\prime}x^{2(d+1)}W_{m i d}(x)+r_{y}^{\prime}x^{3(d+1)}Y_{m i d}(x) $$

is not in the module S generated by the R-linear combinations of the polynomials fu_k(x) = d+1 0 2(d+1) 3(d+1) rv0x vk(x) + rwx wk(x) + ry0x yk(x)gk2I. mid

$$ {u _ {k} (x) = $$

$$ r_{v}^{\prime}x^{d+1}v_{k}(x)+r_{w}^{\prime}x^{2(d+1)}w_{k}(x)+r_{y}^{\prime}x^{3(d+1)}y_{k}(x)}{k\in I{m i d}}. $$

We demonstrate that those are the only cases for a false ^ by proving that, if none of them holds, then V (x);W(x) and Y (x) are a QRP solution, which would then mean that ^ is a valid proof. So, towards contradiction, assume both that U (x) 2 S and V (x) W (x) Y (x) = H(x) t(x). P Since U (x) 2 S, it can be expressed as U (x) = c_ku_k(x), where c_k2 R. Thus, k2Imid

$$ \hat{\pi} $$

$$ V(x),W(x) $$

$$ \hat{\pi} $$

$$ Y(x) $$

$$ U(x)\in S $$

$$ U(x)\in S $$

$$ U (x) = \sum_ {k \in I _ {m i d}} c _ {k} u _ {k} (x) $$

$$ c_{k}\in R $$

$$ U(x)=r_{v}^{\prime}x^{d+1}v^{\prime}(x)+r_{w}^{\prime}x^{2(d+1)}w^{\prime}(x)+r_{u}^{\prime}x^{3(d+1)}y^{\prime}(x), $$

P P P 0 0 0 where we dene v (x) = c^kv^k(x);w (x) = ckw^k(x) and y (x) = c^ky^k(x). k2Imidk2Imidk2Imid Note that v⁰(x);w⁰(x);y⁰(x) have degree at most d, since they are in the spans of fv_k(x)g^k2I; fw_k(x)g_{k2I mid} mid and fy_k(x)g^k2Irespectively. Since V_mid(x);W_mid(x);Y_mid(x) are also polynomials of degree at mid d+1+i 2(d+1)+i 3(d+1)+i most d, and since the R-submo_dules fx : i 2 [0*;d*]g, fx : i 2 [0*;d*]g, an_d fx : i 2 [0*;d*]g of R[x] are disjoint (except at zero) we have that

$$ v ^ {\prime} (x) = \sum_ {k \in I _ {m i d}} c _ {k} v _ {k} (x), w ^ {\prime} (x) = \sum_ {k \in I _ {m i d}} c _ {k} w _ {k} (x) $$

$$ y^{\prime}(x boldsymbol\ x=\sum_{k\in I_{m i d}}c_{k}y_{k}(\boldsymbol x) $$

$$ v^{\prime}(x),w^{\prime}(x),y^{\prime}(x) $$

$$ d, $$

$$ \big{v_{k}\big(x\big)\big}{k\in I{m i d}},\big{w_{k}\big(x\big)\big}{k\in I{m i d}} $$

$$ {y_{k}(x)}{k\in I{m i d}} $$

$$ V_{m i d}(x),W_{m i d}(x),Y_{m i d}(x) $$

$$ {x^{d+1+i},:,i,\in,[0,,d]},,,\{x^{2(d+1)+i},:,i,\in,[0,,d]}} $$

$$ {x^{3(\tilde{d}+1)+i} $$

$$ i\in[0,d]} $$

$$ R[x] $$

$$ \begin{aligned}{U(x)}&{{}=r_{v}^{\prime}x^{d+1}V_{\mathrm{}{m i d}}(x)+r_{w}^{\prime}x^{2(d+1)}W_{\mathrm{}{m i d}}(x)+r_{y}^{\prime}x^{3(d+1)}Y_{\mathrm{}{m i d}}(x)}\ {}&{{}=r_{v}^{\prime}x^{d+1}v^{\prime}(x)+r_{w}^{\prime}x^{2(d+1)}w^{\prime}(x)+r_{y}^{\prime}x^{3(d+1)}y^{\prime}(x),}\ \end{aligned} $$

we conclude that Vmid(x) = v⁰(x), Wmid(x) = w⁰(x) and Ymid(x) = y⁰(x). Therefore, V (x) = P P P P ckvk(x)+Vmidx) = ckvk(x)+ ckvk(x);W(x) = ckwk(x)+W^mid(x) = Pk2Iio P (k2Iiok2Imid Pk2Iio P ckwk(x) + ckwk(x), and Y (x) = ckyk(x) + Ymid(x) = ckyk(x) + Pk2Iiok2Imidk2Iiok2I_io c_ky_k(x). Finally, as we assumed that V (x) W (x) Y (x) = H(x) t(x), we have that k2I_mid V (x);W(x);Y (x) can be written as the same linear combination fc_kg_k2Iio[Iof their respective mid sets, and that t(x) divides V (x) W (x) Y (x). Therefore, V (x);W(x);Y (x) are a QRP solut_ion.

$$ V_{m i d}(x);=;v^{\prime}(x),;;W_{m i d}(x);=;w^{\prime}(x) $$

$$ Y_{m i d}(x),=,y^{\prime}(x) $$

$$ V(x),= $$

$$ \sum_ {k \in I _ {i o}} c _ {k} v _ {k} (x) + V _ {m i d} (x) = \sum_ {k \in I _ {i o}} c _ {k} v _ {k} (x) + \sum_ {k \in I _ {m i d}} c _ {k} v _ {k} (x), W (x) = \sum_ {k \in I _ {i o}} c _ {k} w _ {k} (x) + W _ {m i d} (x) = $$

$$ \textstyle\sum_{k\in I_{\mathrm{}{i o}}}c_{k}w_{k}(x):+:\sum_{k\in I_{\mathrm{}{m i d}}}c_{k}w_{k}(x) $$

$$ Y(x)\ \ stackrel==\\textstyle_{k\in I_{i o}}c_{k}y_{k}(x):+:Y_{m i d}(x)\ =\ \sum_{k\in I_{i o}}c_{k}y_{k}(x)\ + $$

$$ \textstyle\sum_{k\in I_{m i d}}c_{k}y_{k}(x) $$

$$ V(x),\cdot,\dot{W(x)},-,Y(x),=,H(x),\cdot,t(x) $$

$$ V(){{\tilde{()}},{{\tilde{W}}}({boldsymbol x))}}Y({\boldsymbol{x}}) $$

$$ {c_{k}}{k\in I{i o}\cup I_{m i d}} $$

$$ V(x)\cdot W(x)-Y(x) $$

We now address the two cases corresponding to a false proof ^ and show that, in both Case 1 and Case 2, B can break the Generalized q-PDH (Assumption1).

$$ V(x),W(x),Y(x) $$

Case 1: V (x) W (x) Y (x) 6= H(x) t(x). The non-zero polynomial (x) = V (x) W (x) Y (x) k H(x) t(x) has degree k 2d and s as a root. Express (x) =_kx + ^(x), where k 2d, q+1 k k6= 0 and deg(^(x)) < k. Since s is a root of (x), it is also a root of x (x). Hence, q+1 q+1 k q+1 ^q+1 k ^ks = s ^(s). B can compute E(^ks) by computing E( s ^(s)), which is a i q known linear combination of the fE(s)g values belonging to the q-PDH instance. This solves i=0 the q-PDH challenge.

$$ V(x)\cdot W(x)-Y(x)\neq H(x)\cdot t(x) $$

$$ \gamma(x)=V(x)\cdot W(x)-Y(x)- $$

$$ H(x)\cdot t(x) $$

$$ k\leq2d $$

$$ \gamma(x)=\gamma_{k}\cdot x^{k}+\hat{\gamma}(x) $$

$$ k\leq2d. $$

$$ \gamma_{k}\neq0 $$

$$ \deg(\hat{\gamma}(x)),<,k $$

$$ \gamma(x) $$

$$ x^{q+1-k}\gamma(x) $$

$$ \gamma_{k}\cdot s^{q+1}=-s^{q+1-k}\hat{\gamma}(s).;k $$

$$ \mathsf{E}(\gamma_{k}\cdot s^{q+1}) $$

$$ \mathsf{E}(-s^{q+1-k}\hat{\gamma}(s)) $$

$$ \left{\mathsf {E} \left(s ^ {i}\right) \right} _ {i = 0} ^ {q} $$

Case 2: The polynomials Vmid(x);Wmid(x);Ymid(x) are not in the required spans. There does P P not exist fc_kg_k2Isuch that V_mid(x) = ckvk(x);W_mid(x) = ckwk(x) and mid k2Imidk2Imid P d+1 0 2(d+1) Y_mid(x) = c_ky_k(x). Then, the polynomial U (x) = rv0x V_mid(x) +r_wx W_mid(x) + k2Imid 3(d₊₁₎ r_y0x Y_mid(x) is not in the module S generated by the R-linear combinations of the polynod+1 0 2(d+1) 3(d+1) mials fu_k(x) = r_v0x v_k(x) + r_wx w_k(x) + r_y0x y_k(x)g. Recall that B chose a polynomial_poly(x) 2 A [X] of degree at most 3d+ 3 subject to the constraint that all polynomials in 0 (d+1) 2(d+1) d+3 f_poly(x) (rv⁰v_k(x)+rwx w_k⁽x)+r_y0x y_k(x))g have a zero coecient for x³. Thus, by q+1 q (4d+3) Lemma5, the coecient of x in the polynomial*!(x) = x_poly(x) U (x) is a 2 Rnf0g*

$$ V_{m i d}(x),W_{m i d}(x),Y_{m i d}(x) $$

$$ {c_{k}}{k\in I{m i d}} $$

$$ \textstyle V_{\mathrm{}{m i d}}(x);=;\sum_{k\in I_{\mathrm{}{m i d}}}c_{k}\upsilon_{k}(x),\ W_{\mathrm{}{m i d}}(x);=;\sum_{k\in I_{\mathrm{}{m i d}}}c_{k}w_{k}(x) $$

$$ Y_{m i d}(x boldsymbol)=\sum_{k\in I_{m i d}}c_{k}y_{k}(\boldsymbol x) $$

$$ U(x)=r_{v}^{\prime}x^{d+1}V_{m i d}(x)+r_{w}^{\prime}x^{2(d+1)}W_{m i d}(x)+ $$

$$ r_{y}^{\prime}x^{3(d+1)}Y_{m i d}(x) $$

$$ S $$

$$ {u_{k}(x){\ =\ }r_{v}^{\prime}x^{d+1}v_{k}(x){\ +\ }r_{w}^{\prime}x^{2(d+1)}w_{k}(x){\ +\ }r_{y}^{\prime}x^{3(d+1)}y_{k}(x)} $$

$$ \beta_{p o l y}(x)\in A^{*}[X] $$

$$ 3d\ +33 $$

$$ \left{\beta_ {p o l y} (x) \cdot \left(r _ {v} ^ {\prime} v _ {k} (x) + r _ {w} ^ {\prime} x ^ {(d + 1)} w _ {k} (x) + r _ {y} ^ {\prime} x ^ {2 (d + 1)} y _ {k} (x)\right) \right} $$

$$ x^{3d+3} $$

$$ \omega (x) = x ^ {q - (4 d + 3)} \cdot \beta_ {p o l y} (x) \cdot U (x) $$

$$ x^{q+1} $$

$$ a\in R\backslash{0} $$ with probability 1 1*=jA j*. Furthermore, B can compute all the coecients of*!*(x) on its own, so q (4d+3) d+1 2(d+1) 3(d+1) it can subtract from E(L) = E(s_poly(s) (s V_mid(s)+s W_mid(s)+s Y_mid(s))) j q+1 all the monomials corresponding to E(s) for j 6= q + 1 and obtain E(a s). Note that this is q+1 possible even when_poly(s) = 0. By outputting (a; E(a s)), B breaks the generalized q-PDH assumption.

$$ 1!{-}1/|A^{*}| $$

$$ \omega(x) $$

$$ \dot{\mathsf{E}}(L)\dot{=}\mathsf{E}(s^{q-(4d+3)}\beta_{p o l y}(s)\dot{\cdot}(s^{d+1}V_{m i d}(s)+s^{2(d+1)}W_{m i d}(s)+s^{3(d+1)}Y_{m i d}(s))) $$

$$ \mathsf{E}(s^{j}) $$

$$ j\neq q+1 $$

$$ \mathsf{E}(a\cdot s^{q+1}) $$

$$ \beta_{p o l y}(s)=0 $$

$$ q^{\mathrm{{P D H}}} $$

$$ (a,\mathsf{E}(a\cdot s^{q+1})) $$

6 Designated Verier SNARKs for computation over Z₂k

$$ \mathbb{Z}_{2^{k}} $$

We instantiate our previous designated verier SNARK using QRPs where the underlying R is the k Galois Ring GR(2*;). As R is a free module over Z₂k* of rank, we can embed elements from Z₂k into the rst coordinate of R. Hence, a QRP for arithmetic circuits over Z₂k can be embedded in a QRP for arithmetic circuits over R. We divide this section into three smaller ones. In the rst k one, we discuss a suitable encoding scheme for R = GR(2*;*). Second, we provide a simple, direct instantiation of Theorem6using said encoding. Finally, we provide some QRP gadgets to perform useful computation such as bit decomposition.

$$ G R(2^{k},\delta) $$

$$ \mathbb{Z}_{2}k, $$

$$ \delta, $$

$$ \mathbb {Z} _ {2 ^ {k}} $$

$$ \mathbb{Z}_{2}k $$

$$ R=G R(2^{k},\delta) $$

k 6.1 A secure encoding for GR(2;)

$$ G R(2^{k},\delta) $$

We will use the Joye-Libert (JL) cryptosystem [JL13], which has Z₂k as message space, as building block for our encoding of Galois Ring elements.

$$ \mathbb{Z}_{2}k, $$

KeyGen(1*;k*): According to the security parameter, choose two random primes p;q satisfying the equivalences: k p 1 (mod 2) and q 3 (mod 4):

$$ {\mathsf{K e y G e n}}(1^{\kappa},k). $$

$$ \kappa, $$

$$ p,q $$

$$ p\equiv{\mathrm{}}1\pmod2^{k}\quad{\mathrm{a n d}}\quad q\equiv3{\mathrm{}}\ 4\mathrm.{{~}}. $$

k For simplicity, pic^k p = 2 p⁰ + 1 and q = 2q⁰ + 1, where p⁰;q⁰ are primes. Let g be a random generator of both Z_pand Z_q, N = p q and = p⁰. We dene pk = (g;k;N) and sk =. m 2k Encpk(m): Given m 2 Z₂k, sample x Z and output C = g x (^mod N). N

$$ q=2q^{\prime}+1 $$

$$ p=2^{k}p^{\prime}+1 $$

$$ p^{\prime},q^{\prime} $$

$$ \mathbb{Z}_{p}^{*} $$

$$ \mathbb{Z}_{q}^{*},,N=p\cdot q $$

$$ \mu=p^{\prime} $$

$$ {\mathsf{s k}}=\mu $$

$$ \mathrm {p k} = (g, k, N) $$

$$ {mathsf E n n}_{\mathsf{p k}}(m) $$

$$ m\in\mathbb{D}_{2k} $$

$$ x\gets\mathbb{Z}_{N}^{*} $$

$$ C=g^{m}\cdot x^{2^{k}} $$

$$ \operatorname {D e c} _ {\mathrm {s k}} (C) $$

Decsk(C): Compute c = C mod p and then retrieve m bit by bit as follows. Observe that c = C P m k k 1 j mod p = (g) mod p, where g is an element of order 2 in Z_p. Let m = 2 m_j; m_j2 j₌₀ 2k 1 f0*;* 1g. We can compute its least signicant bit m₀ by computing c mod p. Set m₀ = 0 if ^{2k 1} c mod p = 1, and 1 otherwise. After computing m_{i 1};:::;m₀, compute m_ias follows: Set m_i= 0 if and only if !₂k i 1

$$ c=C^{\mu} $$

$$ c=C^{\mu} $$

$$ p=(g^{\mu})^{m} $$

$$ g^{\mu} $$

$$ 2^{k} $$

$$ \mathbb{Z}_{p}^{*} $$

$$ m = \sum_ {j = 0} ^ {k - 1} 2 ^ {j} m _ {j}, m _ {j} \in $$

$$ {0,1} $$

$$ m_{0} $$

$$ c^{2^{k-1}} $$

$$ c^{2^{k-1}} $$

$$ m_{0}=0 $$

$$ p=1 $$

$$ p cdot $$

$$ m_{i-1},\ldots,m_{0} $$

$$ m_{i}=0 $$

$$ m_{i} $$

$$ \left(\frac{c}{(g^{\mu(\sum_{j=0}^{i-1}2^{j}m_{j})})}\right)^{2^{k-i-1}}=1\mod p $$

Note that whereas the decryption cost is linear in k, there is empirical evidence [CRFG19, Section 5] that it can be faster than more common encryption schemes such as Paillier. The JL cryptosystem is secure under the assumption that k-quadratic residuosity is hard [JL13]. It is linearly homomorphic over Z₂k, and it has already been employed in the context of ecient twoparty computation over Z₂k (see [CRFG19] for concrete eciency estimates).

$$ \mathbb{Z}_{2}k, $$

k 1 Let R = GR(2*;). Given a 2 R written in its additive form a = a₀ + a₁X + ::: + a₁X (see Equation (1)), we dene our encoding E:* JL as follows:

$$ R=G R(2^{k},\delta) $$

$$ [\mathrm{C R F G}]9 $$

$$ \mathbb{Z}_{2}k, $$

$$ a=a_{0}+a_{1}X+\ldots+a_{\delta-1}X^{\delta-1} $$

$$ a\in R $$

{ (pk*;sk) Gen(1 ) calls KeyGen(1;k*) in the JL cryptosystem and outputs (pk*;*sk).

$$ -(\mathsf{p k},\mathsf{s k})\leftarrow\mathsf{G e n}(1^{\kappa}) $$

$$ {\mathsf{K e y G e n}}(1^{\kappa},k) $$

$$ (\mathsf{p k},\mathsf{s k}) $$

{ Z_N1::: Z_NE*:* JL_pk(a) is a probabilistic encoding algorithm mapping a ring element a 2 R to an encoding space Z = Z_N1::: Z_Nsuch that the sets ffE*:* JL(a)g : a 2 Rg partition Z, where fE*:* JL(a)g is the set of encodings of a. Concretely:

$$ -,\mathbb{Z}{N{1}}\times\ldots\times\mathbb{Z}{N{\delta}}\leftarrow\mathsf{E.J L}_{\mathfrak{p}k}(a) $$

$$ a\in R $$

$$ Z=\mathbb{Z}{N{1}}\times\ldots\times\mathbb{Z}{N{\delta}} $$

$$ {{{\mathsf{E L.J L}}(a)}:a\in R} $$

$$ Z $$

$$ \mathsf{E.J L}(a)=\left(\mathsf{E n c}{\mathsf{p k}}(a{0}),\ldots,\mathsf{E n c}{\mathsf{p k}}(a{d-1})\right) $$

On the suitability of the encoding. The scheme E*:* JL clearly satises all non-security properties required from an encoding. Under the security assumptions of the JL scheme, it is also reasonable to assume that q-PDH (and q-PKE) hold for the encoding scheme too, where A has a success probability negligible in d. This dependence on d is intrinsic to the arithmetic in R, as A can simply P k 1 d 1 ‘ output (a;y) = (2*;* E*:* JL( s_‘;₀X)), where s_‘;0are A’s guesses for the least signicant bit of ‘=0 each s_‘2 Z₂_k that conform the additive representation of s. Note that the fact that Enhanced-CPA cannot be supported by the JL cyptosystem, as brought up by [CRFG19], is not an issue here. Such notion requires interaction with an oracle which the Adversary does not have access to in our construction, as we do not aim to provide strong soundness.

$$ (textstyle\ a,y)=(2^{k-1},\mathsf{E.J L}(\sum_{\ell=0}^{d-1}s_{\ell,0}\cdot X^{\ell})) $$

$$ s_{\ell,0} $$

$$ \ ^{\ {}\ }\mathrm{}\mathrm{s} $$

$$ s_{\ell}\in\mathbb{Z}_{2^{k}} $$

6.2 A simple construction

k We now have everything we need to instantiate the protocol dened in Section5.1for R = GR(2*;). It follows from inspection that, representing elements of R in their additive notation, A = fai2 R* : P ₁ j a_i= a_i;jX;a_i;j2f0*;* 1gg is an exceptional set in canonical form. Let C be a circuit with j=0 d multiplication gates and dene A as described in Section5.1. Then, using the secure encoding scheme E*:* JL from Section6.1, we can invoke Theorem6to obtain a DV-SNARK for R Z₂k with 1 1 a soundness error of jA j = (2 d).

$$ R=G R(2^{k},\delta) $$

$$ A={a_{i}\in R $$

$$ \textstyle\alpha_{i}\ {\textstyle==\ }sum_{i=0}^{\delta-1}\alpha_{i,j}\ \cdot\ X X^j,\alpha_{i,j}\ \in\ {0,1}} $$

$$ A^{*} $$

$$ R \supset \mathbb {Z} _ {2 ^ {k}} $$

$$ |A^{*}|^{-1}=(2^{\delta}-d)^{-1} $$

Eciency considerations. Whereas in this construction is logarithmic in the desired soundness error, we insist on the fact that our QRP does not suer from the overhead of adding roughly k k multiplication gates whenever a modular reduction x mod 2 has to be computed, as it would happen if the circuit was to be run by a SNARK over elds (see our discussion in Section1.1). Hence, avoiding this and using Rinocchio allows us not blow-up the degree of the QRP, which was an eciency bottleneck in e.g. [PHGR13]. We would further like to note that FFT-style techniques k can be applied to Galois Rings [CK91] and that the price of working with circuits over GR(2*;), rather than Z₂k*, has the potential to be amortized, as it has happened in the context of Multi-Party + Computation protocols which faced similar limitations (c.f. [ACD 19,DLS20]).

$$ \delta $$

$$ x $$

$$ 2^{k} $$

$$ G R(2^{k},\delta) $$

$$ \mathbb{Z}_{2}^{k} $$

In AppendixDwe show how to build QRPs for bit decomposition, which is useful for practical bit-wise operations such as comparisons.

6.3 Soundness amplication

Despite the previous arguments, there is a concern as to what is the practical impact of the extension degree in the previous construction. We believe that this is an interesting question to explore in experimental work, comparing the dierent strategies above. We suggest one strategy here. While it would seem that we cannot escape from being logarithmically proportional to the soundness error, we show that it is good enough to apply a parallel amplication strategy and choose any integer > log(d), where d is the number of multiplication gates in the QRP Q.

$$ \delta $$

$$ \delta $$

$$ \delta>\log(d) $$

For simplicity, we will explain how to do this in the worst case, which is when d is a power of two. If we chose to set = log(d) + 1, we would then have that jA_Qj = d and jA j = jAjjA_Qj = 2.

$$ \delta=\log(d)+1 $$

$$ |A_{Q}|=d $$

$$ \left|A^{*}\right|=\left|A\right|-\left|A_{Q}\right|=2 $$

S Let our target soundness error be 2. We can then run S independent instances of Rinocchio k over R = GR(2*;*log(d) + 1) for the same QRP (that is, S dierent crs from S independent Setup executions), for each of which the prover computes the Prove step from the (common) QRP witness. S The verier only accepts if all the S proofs pass verication, yielding a soundness error of jA j = ^S 2.

$$ 2^{-S} $$

$$ R=G R(2^{k},\log(d)+1) $$

$$ |A^{*}|^{-S}= $$

$$ 2^{-S} $$

Let us note that this parallel repetition strategy does not greatly aect the overall proof size. The reason behind this is that working over a smaller degree extension of Z₂k not only improves the computational eciency, but it also reduces the size of each individual proof when using the E*:* JL encoding. In more detail, if we let N denote the ciphertext size in the Joye-Libert JL cryptosystem k [JL13], our worst-case example that executes S proofs over GR(2*;log(d) + 1) transmits exactly k 9(S 1)N more ciphertexts than if we were to execute Rinocchio once over GR(2;*log(d) + S). We would like to stress once again that this is a worst case scenario and that there is a whole trade-o space between proof size and computational eciency to be explored, concretely log(d) < log(d) + S.

$$ \mathbb{Z}_{2}k $$

$$ G R(2^{k},\log(d)+1) $$

$$ 9(S-1)N $$

$$ G R(2^{k},\log(d)+S) $$

$$ \delta\leq\log(d)+S $$

$$ \log(d)< $$

7 SNARKs for computation over Encrypted Data

In this section we detail how we can apply Rinocchio to the problem of veriable computation over encrypted data. Our approach is generic, where we just run a proving mechanism { the (zk-)SNARK { on pre-existing Homomorphic Encryption (HE) schemes in a modular way. Taking advantage of our generic SNARK construction from Section5, this reduces to nding secure encoding schemes over a ring that are compatible with the ciphertext space of the underlying HE scheme.

In Section7.1we review some popular homomorphic encryption schemes that are good candidates for realising our privacy-preserving VC scheme. Then, by using a secure encoding scheme E as the ones we provide in Section7.2, we can invoke Theorem6to obtain a DV-SNARK for R_q, as explained in Section7.3.

$$ \ \mathcal{R}_{q}. $$

7.1 Homomorphic Encryption schemes and their parameters

The rst fully homomorphic encryption schemes were based on the Learning With Errors (LWE) problem [Reg05], which is the main assumption behind schemes with ciphertexts in the ring Z_q such as [Bra12]. Nevertheless, the most ecient HE schemes are based on the Ring-LWE problem, which is dened in [LPR10]. The LWE (resp. Ring-LWE) problem reduces, under some conditions, to hard problems on euclidean lattices (resp. ideal lattices).

$$ \mathbb{Z}_{q} $$

In Ring-LWE-based schemes, the ring of plaintext is R_p= Z_p[Y]=(f (Y)) and the ring of cyphertexts is R_q= Z_q[Y]=(f (Y)) for some degree-N polynomial f (Y). This is usually picked to be a cyclotomic polynomial, so that it factors into ‘ irreducible factors modulo p. More concretely, Q ‘ f (Y) f_i(Y) mod p, where each f_i(Y) has degree (N)=‘. By imposing p 1 mod N, this i=1 N creates ‘ \plaintext slots", and hence a popular choice is f (Y) = Y + 1, where N is a power of two. In order to deal with the noise growth that aects all of these schemes, q is usually chosen large (several hundreds of bits). Besides the size of q, the rank of the associated lattice, which 10 corresponds to N, has to be high enough to meet the security requirements (usually between 2 ¹⁵ and 2). Q

$$ \mathcal{R}{p}=\mathbb{Z}{p}[Y]/(f(Y)) $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ f(Y) $$

$$ p. $$

$$ \textstyle{f(Y)\equiv\prod_{i=1}^{\ell}f_{i}(Y)} $$

$$ f_{i}(Y) $$

$$ p, $$

$$ p\equiv1 $$

$$ \phi(N)/\ell $$

$$ f(Y)=Y^{N}+1 $$

$$ q, $$

$$ 2^{15}| $$

$$ 2^{10} $$

k Frequently, q is chosen so that q = pⁱ. While this does not aect the asymptotic complexity i=1 of operations on ciphertexts, it brings an important gain in practice: The polynomials of R_qare represented as k polynomials of same degree but with smaller coecients, thanks to the ring

$$ \textstyle q=\prod_{i=1}^{k}p_{i} $$

$$ \mathcal{R}_{q} $$ isomorphism given by the CRT. Being able to eciently deal with non-prime choices for q is hence a signicant advantage of our work, compared to that of [FNP20].

Concrete Ring-LWE schemes. The works that we will consider as a candidate for HE in our privacy-preserving VC are: Brakerski and Vaikunthanatan [BV11b], BGV [BGV12], FV [FV12]. We are interested in the Somewhat Homomorphic variants of these schemes, where the parameters are set just large enough so as to enable homomorphic evaluation of some target function which will be represented as a QRP and hence xed by the SNARK’s crs.

In this setting, schemes like BGV [BGV12] use the so-called modulo-switching. They require a chain of moduli q₀ < < qLto be able to scale the noise down after each multiplication by switching the ciphertext to a smaller modulus. When evaluating circuits with large multiplicative depth, one needs to choose a large chain of moduli and thus use higher dimensions resulting in poor performance.

$$ q_{0}<\cdots<q_{L} $$

Scale invariant schemes allow to partially overcome this limitation by removing the need of the modulus-switching procedure which potentially results in the possibility of evaluating circuits with a bigger multiplicative depth. In his seminal work [Bra12], Brakerski introduced a new scaleinvariant scheme based on classical LWE where the noise grows only linearly during multiplication removing thereby the necessity of modulus switching. This more eective noise control mechanism makes the scale-invariant schemes particularly interesting. In [FV12], the scale-invariant scheme of Brakerski is adapted to the Ring-LWE setting.

Applications for each HE scheme. From the dierent Ring-LWE schemes, each scheme is best suited for certain types of operations: BGV [BGV12] uses, in general, slow operations, but benet from massively optimizations to treat many bits at the same time, while FV [FV12] allows to perform large vectorial arithmetic operations as long as the multiplicative depth of the evaluated circuit remains small. We are able to apply our SNARK for rings to proving homomorphic evaluations of these schemes by rst mapping the dierent ciphertext spaces of the dierent schemes to a common algebraic structure, using some natural homomorphisms.

We observe the algebraic structure of the plaintext and ciphertext spaces from dierent HE schemes:

{ FV: plaintexts on the ring R_p= Z_p[Y]=(f (Y)) for some integer p (a prime, a power of 2 or a 2 small number 1 (mod 2N), depending on the functionality), ciphertexts on R_q

$$ R_{p}=\mathbb{Z}_{p}[Y]/(f(Y)) $$

$$ R_{q}^{2} $$

2 { BGV: plaintexts on the ring R_p= Z[Y]=(f (Y)), ciphertexts on R_q

$$ R_{p}=\mathbb{Z}[Y]/(f(Y)) $$

$$ R_{q}^{2} $$

7.2 Secure Encodings for (Ring-)LWE ciphertexts

We introduce two dierent instantiations for the encoding scheme, one suitable for the ciphertext ring Z_qthat appears in LWE-based HE and the other one for a polynomial ring R_q, as in the ciphertext ring of Ring-LWE-based schemes.

$$ \mathbb{Z}_{q} $$

$$ \mathcal{R}_{q}, $$

Regev-style Encoding. Here we consider the input space of the encoding (the ring R over which the QRP is dened) as the ones used in HE schemes based on standard LWE, i.e. the ring Z_q, for q 2 N. One example of such schemes is [BV11a]. Note that Zqis not a eld, since q is not required Q to be a prime. A popular choice for q is a product of co-prime numbers q = q_iwith some extra i conditions on q_i’s as discussed in works as [Reg05,Pei09].

$$ q\in\mathbb{N} $$

$$ \mathbb{Z}_{q}. $$

$$ \mathbb{Z}_{q} $$

$$ q $$

$$ q=\prod_{i}q_{i} $$

$$ q_{i}{{}^{\ }!} $$

The encoding E*:* Regev we consider over the ring Z_qis the same as the one used to construct lattice-based SNARGs and SNARKs in [GMNO18,Nit19], a slight variation of the classical LWE cryptosystem initially presented by Regev [Reg05]. The encryption scheme is described by parameters (q;Q;n;), with q;Q;n 2 N such that (q;Q) = 1, and 0 < < 1. We will also consider (S), the discrete Gaussian distribution over a discrete set S with mean 0 and parameter.

$$ \mathbb{Z}_{q} $$

$$ \varGamma\gets(q,Q,n,\alpha) $$

$$ 0<\alpha<1 $$

$$ (q,Q)=1 $$

$$ q,Q,n\in\mathbb{N} $$

$$ \sigma $$

$$ \chi_{\sigma}(S) $$

n Gen(1*;*): Choose some random striⁿg s Z. Output sk = s. Q

$$ \operatorname {G e n} \left(1 ^ {\kappa}, \Gamma\right) $$

$$ s\gets\mathbb{D}_{O}^{n} $$

n E_sk(m): Given m 2 Z_q, sample a Z, deⁿe = Q; e (Z_q). Output C = ( a; a s + Q qe + m). D (C): Parse sk = s;C = (a₀;c₁) Compute m = (a₀ s + c₁) mod q.

$$ \mathsf{E}_{\mathsf{s k}}(m) $$

$$ m\in\mathbb{Z}_{q} $$

$$ \ {\cal{C}}=(-a,;a\cdot s+ $$

$$ \sigma = Q \alpha ; e \leftarrow \chi_ {\sigma} \left(\mathbb {Z} _ {q}\right) $$

$$ a\gets\mathbb{Z}_{Q}^{n} $$

$$ q e+m) $$

$$ \mathbf{D}{\mathsf{s k}}(C)\ \ \ mathrm{P a r s e}\ \mathbf{s k}=\mathfrak{s},C=(\mathbf{a}{0},c_{1})\ \ {{\operatorname{C o m p u t e}}\ m}m=(\mathbf{a}{0}\cdot s\ c{1})\ \ q. $$

On the suitability of the encoding. It is easy to see that this is a statistically-correct encoding scheme. When encodings are added together and multiplied by scalars, the noise starts to build up. Nevertheless, for any xed ‘ there is a choice of parameters such that the encoding is ‘- linearly-homomorphic. Consequently, in order to ensure that we obtain a valid encoding of the expected result, we need to start with suciently small noise in each of the initial encodings. A more detailed discussion about the noise growth and the choices for can be found in the work of Banaszczyk [Ban95] and in more recent articles [GMNO18,BISW17,BISW18] that specically address SNARK applications of this encoding. The quadratic root detection and image verication can be implemented using D_sk.

$$ \mathbb{D}_{\mathsf{s k}} $$

Security: Regarding security, this encoding scheme was already used and conjectured as linear-only and secure against generalized q-PDH assumption over elds by prior works. Our generalized q-PDH assumption over rings extends this, taking into account encodings over rings. The constructions in [BISW17,BISW18] also employ E*:* Regev to instantiate their SNARG(K) and this is assumed to be linear-only extractable, a stronger assumption than secure encoding, i.e. it implicitly satises both the Generalized q-PDH and the Generalized Augmented q-PKE assumptions as shown in AppendixB.

$$ q^{\mathrm{{P D H}}} $$

Extension to Ring-LWE. Our Regev-style encoding can be extended to an encoding over the ring R_qused in Ring-LWE based schemes by combining N copies of the encoding above, similar to what we did in Section6.1.

$$ \mathcal{R}_{q} $$

Torus Encoding. We will use a variant of the Torus FHE (TFHE) cryptosystem from [CGGI20]. We let R_R= R[Y]=(f (Y)), R_Z= Z[Y]=(f (Y)) and R_q= Z_q[Y]=(f (Y)) denote the quotient rings N with respect to some polynomial f (Y) = Y + 1, where m is an integer and N is a power of 2. We let T = R*=*Z be the torus, which is a Z-module structure but not a ring.

$$ \mathcal{R}{\mathbb{R}}=\mathbb{R}[Y]/(f(Y)),:\mathcal{R}{\mathbb{Z}}=\mathbb{Z}[Y]/(f(Y)) $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ f(Y)=Y^{N}+1 $$

$$ \mathbb{T}=\mathbb{R}/\mathbb{Z} $$

We consider the R_Z-module T_R= R_R=R_Z. The plaintext for the TFHE cryptosystem is the Z-module T = R*=Z. Our encoding scheme E:* Torus has Z_qas message space and will be used for encoding of elements in R_q= Z_q[Y]=(f (Y)). The key remark is that the ring R_qcan be identied N N 1 with a subgroup of the torus T via the map R_q’ Z_qthat identies q Z*=Z ’ Z_qas an N N isomorphism of Z-modules. Also, T ’ T_Rbecause T can be seen as a vector of coecients. The N+1 module structure of the encoding space T allows us to conjecture that E:* Torus scheme only supports linear homomorphic operations.

$$ \mathbb{T}{\mathcal{R}}=\mathcal{R}{\mathbb{R}}/\mathcal{R}_{\mathbb{Z}} $$

$$ \mathbb{T}=\mathbb{R}/\mathbb{Z}. $$

$$ \mathbb{Z}_{q} $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ \mathcal{R}_{q} $$

$$ \mathcal{R}{q},\simeq,\mathbb{Z}{q}^{N} $$

$$ q^{-1}\mathbb{Z}/\mathbb{Z};\simeq;\mathbb{Z}_{q} $$

$$ \mathbb{T}^{N}\simeq\mathbb{T}_{\mathcal{R}} $$

$$ \mathbb{T}^{N} $$

Let B = f0*;* 1g. The encoding scheme E*:* Torus is described by parameters (q;N;), with q;N 2 N such that 0 < < 1. The noise parameter is the standard deviation for a concentrated distribution on the torus (more details can be found in [CGGI20]). Below, we describe the algorithms of the encoding:

$$ \mathbb{B},=,{0,1} $$

$$ \varGamma\leftarrow(q,N,\alpha) $$

$$ q,N\in\mathbb{N} $$

$$ 0<\alpha<1 $$

N Gen(1*;*): Choose a random vector s 2 B. Output sk = s.

N 1 E_sk(m): Given sk = s 2 B and m 2 Z_q, apply the map Z_q’ q Z*=*Z to m and get m⁰ 2 T such N that m⁰ m=q mod 1, sample a vector a 2 T and compute b = s a + m⁰ + e where e 2 T is sampled according to a noise distribution dened by the standard deviation.

$$ \boldsymbol{s}\in\mathbb{B}^{N} $$

$$ \mathrm {n} \left(1 ^ {\kappa}, \Gamma\right) $$

$$ \mathsf{s k}=s $$

$$ \ \ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ =\ \mathfrak{s}\mathbb{B}^{N} $$

$$ \mathsf{E}_{\mathsf{s k}}(m) $$

$$ \mathbb{Z}_{q}\simeq q^{-1}\mathbb{Z}/\mathbb{Z} $$

$$ m\in\mathbb{Z}_{q}. $$

$$ m^{\prime}\in\mathbb{T} $$

$$ m^{\prime}\equiv m/q $$

$$ a\in\mathbb{T}^{N} $$

$$ b = \boldsymbol {s} \cdot \boldsymbol {a} + m ^ {\prime} + e $$

$$ e\in\mathbb{T} $$

$$ \alpha $$

D_sk(C): Parse sk = s;C = (a;b). Compute m" = b a s = m" +e. Round m" to the nearest point 1 m⁰ on the torus with respect to a distance function and apply the equivalence q Z*=*Z ’ Z_qto recover m.

$$ \mathrm {k} = \boldsymbol {s}, C = (\boldsymbol {a}, b) $$

$$ m^{\ } $$

$$ \mathsf{D}_{\mathsf{s k}}(C) $$

$$ m ^ {\prime \prime} = b - \boldsymbol {a} \cdot \boldsymbol {s} = m ^ {\prime \prime} + e $$

$$ m^{\prime} $$

$$ q^{-1}\mathbb{Z}/\mathbb{Z}\simeq\mathbb{Z}_{q} $$

On the suitability of the encoding. It is easy to see that this is a statistically-correct encoding scheme and due to the linearly-homomorphic property of the cryptosystem (see AppendixEfor specic details), for a xed ‘, there is a choice of parameters such that we have ‘-linearly-homomorphic. The quadratic root detection and image verication can be implemented using D_sk.

$$ \mathsf{D}_{\mathsf{s k}} $$

Security: E*:* Torus is semantically secure under the assumption TLWE, a generalized intractability problem similar to LWE. Also, it is plausible that E*:* Torus scheme only permits linear homomorphisms, therefore we conjecture that this is a secure encoding, satisfying both q-PDH and q-PKE assumptions. A heuristic argument for believing multiplication of two encoded values is impossible is the torus structure of the encoding space, T is a Z-module and not a ring (i.e., the product q+1 of elements in T is not well dened), so there is no way for one to compute any missing E(s) to solve q-PDH. Of course, the original encryption scheme TFHE as dened in [CGGI20] is more elaborate and overcomes this limitation: it consists of three major encryption/decryption schemes, each represented by a dierent plaintext space and makes use of tools like key-switching, gate bootstrapping and gadget decomposition function to perform computations other than additions. These operations are possible only if some extra keys are available, for example some precomputed ciphertexts of the binary secret key in the case of gate bootstrapping. Since we do not consider all these extensions and we do not provide encodings of the secret key in the crs, our encoding E*:* Torus is limited to basic linear operations.

$$ q^{\mathrm{D D H}} $$

$$ \mathbb{I} $$

$$ \mathbb{T} $$

$$ \mathsf{E}(s^{q+1}) $$

7.3 (zk-)SNARKs for Ring-LWE-based homomorphic encryption

We now have everything we need to instantiate the protocol dened in Section5.1. We pick the ring R_q= Z_q[Y]=(f (Y)), to match the ciphertext space of the Ring-LWE scheme from Section7.1. Depending on the choice of q and f (Y) in the underlying schemes, we have dierent options for Q k our exceptional sets. Generally speaking, if q = pi, where p < p₁ < p₂ < ::: < pkand p comes i=1 from the plaintext space R_p, we can always nd the exceptional set A = f1*;* 2*;:::;p₁* 1g R. Hence, if p₁ is big enough we don’t need to worry about anything else. Otherwise, we can move to an extension of the ciphertext ring or apply the parallel soundness amplication strategy, similar to what we did in Section6.

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)). $$

$$ q $$

$$ f(Y) $$

$$ \textstyle q=\prod_{i=1}^{k}p_{i} $$

$$ p<p_{1}<p_{2}<\ldots<p_{k} $$

$$ \mathcal {R} _ {p}, $$

$$ A^{}=\left{1,2,\ldots,p_{1}-1\right}\subset R^{} $$

$$ p_{1} $$

We can next choose a secure encoding scheme E from the ones in Section7.2. Assuming that the evaluation algorithm of the underlying homomorphic encryption scheme (e.g. [FV12]) does not involve modulus switching and rounding operations, we directly obtain a Designated Verier SNARK for computation on encrypted data by invoking Theorem6for R_q, as explained in Section7.3. We could choose schemes such as BGV [BGV12] that employ modulus switching techniques, and can deal with the quadratic growth of the noise after a multiplication. In order to represent this operation as part of the arithmetic circuit represented by the QRP, we introduce a \mod q_i" gate in AppendixD. Even though the overall circuit remains over R_q, we would like to note that there is no need to repeatedly apply the \mod q_i" gate after e.g. every addition until switching to the next

$$ \mathcal {R} _ {q}, $$

$$ q_{i}^{\ 93} $$

$$ \mathcal{R}_{q} $$

$$ q{i}^{92} $$ modulus q_{i 1}happens. The reason behind this is that adding m elements smaller than q_iresults in a value smaller than m q_i, thus not compromising correctness. Therefore, we only need to place this gate in the circuit whenever correctness would otherwise be lost.

$$ q_{i-1} $$

$$ q_{i} $$

$$ m\cdot q_{i} $$

Context hiding. Another challenge for our VC scheme would be preserving privacy of the inputs against the verier. Such a property would turn useful in the following two example scenarios. In the rst one, the person holding the secret key for HE and the verier (who holds the secret key for the encoding) checking the computation over the ciphertexts are dierent entities. In the second scenario, the Prover wants to compute on ciphertext from the verier using some secret coecients (e.g. a Machine Learning model, or his own input in a two-party computation scenario) that he wants to remain private.

The context hiding property roughly says that output encodings together with input verication tokens do not reveal any information on the input. Note that this is required to hold even against a party that is in possession of the secret key for the encryption scheme. A formal denition of context-hiding is given in AppendixA.1. We can make our VC scheme context-hiding using the same techniques as proposed in [FNP20]. In the HE schemes we propose, information about the underlying plaintexts may be inferred from the distribution of the noise recovered during decryption of the result. To address this, the strategy is to statistically hide the noise. In a nutshell, the trick is to add to the public key some honestly generated encryptions of 0 and then ask the untrusted party to add these to the result of the computation.

Comparison with [FNP20]. The advantage of choosing our SNARK for ring computation as a candidate for the VC scheme is that the resulting scheme enables a set of optimisations on the underlying homomorphic encryption scheme leading to a total computational overhead smaller than in prior works. One main reason is that the ciphertext spaces from existing HE schemes are rings, so a QRP can be dened directly for the evaluation circuit of the HE scheme. Our SNARK, instantiated with encoding schemes that work directly over the ciphertext space, avoids the limitation of previous SNARKs for computation over elds.

The work by Fiore et al. [FNP20] relies on bilinear-group based primitives such as commitments and SNARKs, and therefore imposes specic parameters to the ciphertext space, the polynomial ring R_q= Z_q[Y]=(f (Y)), which are not optimal for the relevant homomorphic schemes known today. Moreover, they do not support modulo switching or other scaling operations. Another drawback of this work comes from the trick of moving from ciphertexts in R_q= Z_q[Y]=(f (Y)) to scalars in F_q. This requires expensive computations on large degree polynomials in Z_q[Y]. The prover needs to carry all the circuit computations on the ciphertext polynomials without reduction modulo f (Y) along the way (where f (Y) is the quotient polynomial that denes R_q= Z_q[Y]=(f (Y))). Even if this is not counted in the cost of proof generation, it is an overhead for the worker performing the homomorphic evaluation of the HE scheme. In our work, such an overhead is not necessary, our techniques allow for the worker/prover to use the existing HE schemes with their latest optimisations for computations over ciphertexts. After the HE evaluation, the prover can use the intermediate ciphertexts from the homomorphic evaluation of the circuit as witness to our SNARK. We remark that these are all elements in the ring R_qas opposed to large degree integer polynomials in Z_q[Y] computed in Fiore et al. [FNP20]. Q

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/(f(Y)) $$

$$ \mathbb{F}_{q} $$

$$ \mathbb{Z}_{q}[Y] $$

$$ f(Y) $$

$$ f(Y) $$

$$ \mathcal{R}{q}=\mathbb{Z}{q}[Y]/\big(f(Y)\big). $$

$$ \mathcal{R}_{q} $$

$$ \mathbb{Z}_{q}[Y] $$

L Another major advantage of our SNARK is that it supports generic rings Rqwith q = qⁱfor i⁼⁰ a chain of moduli fq₀;:::;q_Lg as in the state-of-art leveled HE schemes. Our SNARK also enables noise reduction operations as modulo switching in the evaluation circuit to be proven. A circuit for

$$ \mathcal{R}_{q} $$

$$ \textstyle{q=\prod_{i=0}^{L}q_{i}} $$

$$ {q_{0},\ldots,q_{L}} $$ the modulo switching procedure and its overhead in terms of QRP is detailed in AppendixD.2. A qualitative dierence is that the scheme of [FNP20] is a commit-and-prove scheme; and has the inherent drawback that it is limited by the choice of schemes which are compatible with both the commitment scheme and the proof system. Our scheme is an instantiation of a SNARK without combining two dierent proof systems. We believe one could turn our scheme into a commitand-prove SNARK along the lines of [AGM18] by \extracting" a suitable encoding to act as a commitment to the input wire values from the SNARK. We leave working out the details to obtain a concrete commit-and-prove scheme for ring computation to future work.

Acknowledgements

We would like to thank Ivan Damgard and Simon Holmgaard Kamp for helpful discussions and suggestions. During his time at Aarhus University, Eduardo Soria-Vazquez was supported by the Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM).

References

⁺ ACD 19.Mark Abspoel, Ronald Cramer, Ivan Damgard, Daniel Escudero, and Chen Yuan. Ecient informationk theoretic secure multiparty computation over Z*=p* Z via galois rings. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 471{501. Springer, Heidelberg, December 2019. AGM18.Shashank Agrawal, Chaya Ganesh, and Payman Mohassel. Non-interactive zero-knowledge proofs for composite statements. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 643{673. Springer, Heidelberg, August 2018. n Ban95.Wojciech Banaszczyk. Inequalities for convex bodies and polar reciprocal lattices iⁿ R. Discrete & Computational Geometry, 13(2):217{231, 1995. BCC88.Gilles Brassard, David Chaum, and Claude Crepeau. Minimum disclosure proofs of knowledge. Journal of computer and system sciences, 37(2):156{189, 1988. BCCT12.Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 326{349, 2012. BCFK20.Alexandre Bois, Ignacio Cascudo, Dario Fiore, and Dongwoo Kim. Flexible and ecient veriable computation on encrypted data. Cryptology ePrint Archive, Report 2020/1526, 2020. https: //eprint.iacr.org/2020/1526. ⁺ BCG 13.Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 90{108. Springer, Heidelberg, August 2013. ⁺ BCG 14.Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 459{474. IEEE Computer Society Press, May 2014. ⁺ BCI 13.Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct noninteractive arguments via linear interactive proofs. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 315{333. Springer, Heidelberg, March 2013. BCPS18.Anurag Bishnoi, Pete L Clark, Aditya Potukuchi, and John R Schmitt. On zeros of a polynomial in a nite grid. Combinatorics, Probability and Computing, 27(3):310{333, 2018. BCTV14.Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct non-interactive zero knowledge for a von neumann architecture. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, pages 781{796. USENIX Association, August 2014. BFM88.Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In 20th ACM STOC, pages 103{112. ACM Press, May 1988. ⁺ BFR 13.Benjamin Braun, Ariel J Feldman, Zuocheng Ren, Srinath Setty, Andrew J Blumberg, and Michael Walsh. Verifying computations with state. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 341{357, 2013.

$$ \mathbb{Z}/p^{k}\mathbb{Z} $$

⁺ BGG 90.Michael Ben-Or, Oded Goldreich, Sha Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Sha Goldwasser, editor, CRYPTO’88, volume 403 of LNCS, pages 37{56. Springer, Heidelberg, August 1990. BGV12.Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Sha Goldwasser, editor, ITCS 2012, pages 309{325. ACM, January 2012. BISW17.Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. Lattice-based SNARGs and their application to more ecient obfuscation. In Jean-Sebastien Coron and Jesper Buus Nielsen, editors, EURO- CRYPT 2017, Part III, volume 10212 of LNCS, pages 247{277. Springer, Heidelberg, April / May 2017. BISW18.Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. Quasi-optimal SNARGs via linear multi-prover interactive proofs. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 222{255. Springer, Heidelberg, April / May 2018. Bra12.Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 868{886. Springer, Heidelberg, August 2012. BSCGT13.Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. Fast reductions from rams to delegatable succinct constraint satisfaction problems. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 401{414, 2013. BV11a.Zvika Brakerski and Vinod Vaikuntanathan. Ecient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, 52nd FOCS, pages 97{106. IEEE Computer Society Press, October 2011. BV11b.Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 505{524. Springer, Heidelberg, August 2011. CCKP19.Shuo Chen, Jung Hee Cheon, Dongwoo Kim, and Daejun Park. Veriable computing for approximate computation. Cryptology ePrint Archive, Report 2019/762, 2019. https://eprint.iacr.org/2019/762. CF85.Josh D. Cohen and Michael J. Fischer. A robust and veriable cryptographically secure election scheme (extended abstract). In 26th FOCS, pages 372{382. IEEE Computer Society Press, October 1985. ⁺ CFH 15.Craig Costello, Cedric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur. Geppetto: Versatile veriable computation. In 2015 IEEE Symposium on Security and Privacy, pages 253{270. IEEE, 2015. CFQ19.Matteo Campanelli, Dario Fiore, and Anas Querol. LegoSNARK: Modular design and composition of succinct zero-knowledge proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2075{2092. ACM Press, November 2019. CGGI20.Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene. TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34{91, January 2020. ⁺ CHM 20.Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 738{768. Springer, Heidelberg, May 2020. CK91.David G Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693{701, 1991. CKV10.Kai-Min Chung, Yael Kalai, and Salil P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 483{501. Springer, Heidelberg, August 2010. CL01.Jan Camenisch and Anna Lysyanskaya. An ecient system for non-transferable anonymous credentials with optional anonymity revocation. In Birgit Ptzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 93{118. Springer, Heidelberg, May 2001. CRFG19.Dario Catalano, Mario Di Raimondo, Dario Fiore, and Irene Giacomelli. Monza: Fast maliciously secure two party computation on Z₂k. Cryptology ePrint Archive, Report 2019/211, 2019. https://eprint. iacr.org/2019/211. CS97.Jan Camenisch and Markus Stadler. Ecient group signature schemes for large groups (extended abstract). In Burton S. Kaliski Jr., editor, CRYPTO’97, volume 1294 of LNCS, pages 410{424. Springer, Heidelberg, August 1997. DFGK14.George Danezis, Cedric Fournet, Jens Groth, and Markulf Kohlweiss. Square span programs with applications to succinct NIZK arguments. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part I, volume 8873 of LNCS, pages 532{550. Springer, Heidelberg, December 2014.

$$ \mathbb{Z}_{2^{k}} $$

DFKP16.Antoine Delignat-Lavaud, Cedric Fournet, Markulf Kohlweiss, and Bryan Parno. Cinderella: Turning shabby X.509 certicates into elegant anonymous credentials with the magic of veriable computation. In 2016 IEEE Symposium on Security and Privacy, pages 235{254. IEEE Computer Society Press, May 2016. DLS20.Anders Dalskov, Eysa Lee, and Eduardo Soria-Vazquez. Circuit amortization friendly encodings and their application to statistically secure multiparty computation. In ASIACRYPT. Springer, Heidelberg, 2020. FFS87.Uriel Feige, Amos Fiat, and Adi Shamir. Zero knowledge proofs of identity. In Alfred Aho, editor, 19th ACM STOC, pages 210{217. ACM Press, May 1987. FGP14.Dario Fiore, Rosario Gennaro, and Valerio Pastro. Eciently veriable computation on encrypted data. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014, pages 844{855. ACM Press, November 2014. FNP20.Dario Fiore, Anca Nitulescu, and David Pointcheval. Boosting veriable computation on encrypted data. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS, pages 124{154. Springer, Heidelberg, May 2020. For87.Lance Fortnow. The complexity of perfect zero-knowledge (extended abstract). In Alfred Aho, editor, 19th ACM STOC, pages 204{209. ACM Press, May 1987. FV12.Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryp- tology ePrint Archive, 2012:144, 2012. GGP10.Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive veriable computing: Outsourcing computation to untrusted workers. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 465{482. Springer, Heidelberg, August 2010. GGPR13.Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 626{645. Springer, Heidelberg, May 2013. ⁺ GKM 18.Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. Updatable and universal common reference strings with applications to zk-SNARKs. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 698{728. Springer, Heidelberg, August 2018. ⁺ GKP 13.Sha Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. How to run turing machines on encrypted data. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 536{553. Springer, Heidelberg, August 2013. GKR08.Sha Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 113{122. ACM Press, May 2008. GMNO18.Rosario Gennaro, Michele Minelli, Anca Nitulescu, and Michele Orru. Lattice-based zk-SNARKs from square span programs. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 556{573. ACM Press, October 2018. GMR89.Sha Goldwasser, Silvio Micali, and Charles Racko. The knowledge complexity of interactive proof systems. SIAM Journal on computing, 18(1):186{208, 1989. GMW86.Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th FOCS, pages 174{187. IEEE Computer Society Press, October 1986. GMW87.Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218{229. ACM Press, May 1987. Gro10.Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 321{340. Springer, Heidelberg, December 2010. Gro16.Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sebastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305{326. Springer, Heidelberg, May 2016. GW11.Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99{108. ACM Press, June 2011. k JL13.Marc Joye and Beno^t Libert. Ecient cryptosystems from 2-th power residue symbols. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 76{92. Springer, Heidelberg, May 2013.

Kil92.Joe Kilian. A note on ecient zero-knowledge proofs and arguments. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 723{732, 1992. ⁺ KPP 14.Ahmed E. Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, Mahmoud F. Sayed, Elaine Shi, and Nikos Triandopoulos. TRUESET: Faster veriable set computations. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, pages 765{780. USENIX Association, August 2014. KPS18.Ahmed E. Kosba, Charalampos Papamanthou, and Elaine Shi. xJsnark: A framework for ecient veriable computation. In 2018 IEEE Symposium on Security and Privacy, pages 944{961. IEEE Computer Society Press, May 2018. Lip12.Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 169{189. Springer, Heidelberg, March 2012. Lip13.Helger Lipmaa. Succinct non-interactive zero knowledge arguments from span programs and linear errorcorrecting codes. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part I, volume 8269 of LNCS, pages 41{60. Springer, Heidelberg, December 2013. LPR10.Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1{23. Springer, Heidelberg, May / June 2010. MBKM19.Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2111{2128. ACM Press, November 2019. Mic94.Silvio Micali. Cs proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 436{453. IEEE, 1994. Nao03.Moni Naor. On cryptographic assumptions and challenges (invited talk). In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 96{109. Springer, Heidelberg, August 2003. Nit19.Anca Nitulescu. Lattice-based zero-knowledge SNARGs for arithmetic circuits. In Peter Schwabe and Nicolas Theriault, editors, LATINCRYPT 2019, volume 11774 of LNCS, pages 217{236. Springer, Heidelberg, 2019. NY90.Moni Naor and Moti Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC, pages 427{437. ACM Press, May 1990. Pei09.Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 333{342. ACM Press, May / June 2009. PHGR13.Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical veriable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238{252. IEEE Computer Society Press, May 2013. Reg05.Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84{93. ACM Press, May 2005. Wan03.Zhe-Xian Wan. Lectures on nite elds and Galois rings. World Scientic Publishing Company, 2003. Wee05.Hoeteck Wee. On round-ecient argument systems. In Lus Caires, Giuseppe F. Italiano, Lus Monteiro, Catuscia Palamidessi, and Moti Yung, editors, ICALP 2005, volume 3580 of LNCS, pages 140{152. Springer, Heidelberg, July 2005.

A More Preliminaries

A.1 Veriable Computation

Veriable computation [GKR08,GGP10] addresses the setting where a computationally limited client wishes to outsource the computation of a function to an untrusted, but computationally powerful worker. The goal is to enable to client to outsource the computation and be able to verify the correctness of the result such that this verication is less work than the evaluation of the function itself.

Denition 7(Veriable Computation). A veriable computation scheme is a tuple of polyno- mial time algorithms (KGen*;ProbGen;Compute;*Ver) dened as follows.

{ (SK*;PK) KGen(1;F*): A randomized key generation algorithm takes a function F as input and outputs a secret key SK*, a public key* PK_F, and evaluation key EK_F.

$$ -(S K,P K)\leftarrow K G e n(1^{\kappa},F) $$

$$ {\mathsf{P}}{\mathsf{K}}_{F} $$

$$ {\mathsf{E K}}_{F} $$

{ ([x];VK_x) ProbGen_PK(x) A randomized problem generation algorithm takes the public key PK_F, an input x, and outputs an encoding of x, together with a private verication key VK_x.

$$ {\sf{P K}}_{F} $$

{ [y] Compute_PK([x]) A deterministic worker computation algorithm takes the evaluation key EK_F, the encoded input [x] to compute a value [y].

$$ \ \mathrm{V K}_{x} $$

$$ \bf\cdot\ \ y]\leftarrow\sf{C o m p u t e}_{\sf P K}([x]) $$

{ y Ver_SK(VK_x; [y]) A verication algorithm uses the verication key VK_x, the worker’s output [y], and outputs y 2f0*;* 1g [?, where y is the output of the computation and ? indicates that the client rejects the worker’s output.

$$ -\ y\leftarrow\mathsf{V e r}{\mathsf{S K}}(\mathsf{V K}{x},[y]) $$

$$ {\sf{V K}}_{x} $$

$$ y\in{0,1}^{*}\cup\bot $$

A veriable computation scheme satises correctness, eciency and security properties.

{ Correctness. Correctness guarantees that if the worker is honest, the verication test will pass. That is, for all F, and for all x in the domain of F, 0 1

$$ \Pr \left(y = F (x): \begin{array}{c} (\mathrm {S K}, \mathrm {P K}) \leftarrow \mathrm {K G e n} \left(1 ^ {\kappa}, F\right) \ ([ y ], \mathrm {V K} _ {x}) \leftarrow \mathrm {P r o b G e n} _ {\mathrm {P K}} ([ x ]) \ [ y ] \leftarrow \mathrm {C o m p u t e} _ {\mathrm {P K}} ([ x ]) \ y \leftarrow \mathrm {V e r} _ {\mathrm {S K}} \left(\mathrm {V K} _ {x}, [ y ]\right) \end{array}\right) = 1 $$

{ Eciency. The eciency requirement states that the complexity of the outsourcing algorithm ProbGen*, and verication algorithm* Ver together is less than the computation required to evaluate F. A VC myust satisfy the property that for any x and any [y], the time required for ProbGen(x) plus the time required for Ver(VK_x; [y]) is o(T), where T is the time required to compute F(x). { Security. A VC scheme is secure if a malicious worker cannot make the verication algorithm accept an incorrect answer. That is, a scheme is secure if the advantage of any PPT adversary Ver Ver A in the game Expt_Adened as Pr Expt_A[VC;F;] = 1 is negligible.

$$ \mathsf{V e r}(\mathsf{V K}_{x},[y]) $$

$$ o(T) $$

$$ F(x) $$

$$ {\sf{E x p t}}_{\mathcal{A}}^{V e r} $$

$$ \operatorname*{P r}\left({\mathsf{E x p t}}_{\mathcal{A}}^{V e r}[V C,F,\kappa]=1\right) $$

Context-Hiding. An additional property that can be dened for a VC scheme is called contexthiding. This captures the setting where one wants to hide information on the input x even from the verier. Such a property would turn useful in scenarios where the data encoder and the verier are dierent entities. Informally, this property says that output encodings [y], as well as the input verication tokens verication key VK_xdo not reveal any information on the input x. Notably this should hold even against the holders of the secret key SK. We formalize this denition in zeroknowledge style, requiring the existence of a simulator algorithm that, without knowing the input, should generate (VK_x; [y]) that look like the real ones. More formally:

$$ {\sf{V}}{\sf{K}}_{x} $$

$$ (\mathsf{V}\mathsf{K}_{x},[y]) $$

Ver procedure Game Expt_A(VC;F;) (SK*;PK) KGen(1;F*) for i = 1*;:::;‘* = poly() do xi = A(PK*;x₁;* [x₁];:::;xi 1*;* [xi 1]) ([xi];VKxi) ProbGenPK(xi) end for (i;[y]) = A(PK*;x₁;* [x₁];:::;x‘; [x‘]) y VerSK(VKxi; [y]) return ((y 6=?) ^ (y 6= F (xi))) end procedure

$$ \operatorname{G A M E}\ \mathsf{E x p t}_{\mathcal{A}}^{\mathrm{}{V e r}}(\underline{{V C}},F,\kappa) $$

$$ (\mathsf{S K},\mathsf{P K})\leftarrow\mathsf{K G e n}(1^{\kappa},F) $$

$$ i=1,\ldots,\ell={\mathsf o l y}(\kappa) $$

$$ \ \ x==mathcalmathcal{A}(\mathsf{P K},x_{1},[x_{1}],\dots,x_{i-1},[x_{i-1}]) $$

$$ \left(\left[ x _ {i} \right], \mathrm {V K} _ {x _ {i}}\right) \leftarrow \operatorname {P r o b G e n} _ {\mathrm {P K}} \left(x _ {i}\right) $$

$$ y\leftarrow\mathsf{V e r S_{K K}}(\mathsf{V K}{x{i}},[y]) $$

$$ (i,[y])=\mathcal{A}(\mathsf{P K},x_{1},[x_{1}],\dots,x_{\ell},[x_{}])} $$

$$ \left((y\neq\bot)\land(y\neq F(x_{i}))\right) $$

Denition 8(Context-Hiding). A VC scheme is context-hiding for a function F if there exist simulator algorithms S₁;S₂ such that:

$$ S_{1},S_{2} $$

{ the keys (SK*;PK) and (SK⁰;PK⁰) are statistically indistinguishable, where (SK;PK) KGen(1;F*) and (SK⁰*;PK⁰;td) S₁(1;f*);

$$ (\mathrm {S K}, \mathrm {P K}) \leftarrow \mathrm {K G e n} \left(1 ^ {\kappa}, F\right) $$

$$ (\mathsf{S K}^{\prime},\mathsf{P K}^{\prime},\mathsf{t d})\leftarrow S_{1}(1^{\kappa},f) $$

{ for any input x, the following distributions are negligibly close

$$ (\mathsf{S K}^{\prime},\mathsf{P K}^{\prime},\mathsf{V K}{x},[x],[y])\approx(\mathsf{S K}^{\prime},\mathsf{P K}^{\prime},\mathsf{V K}{x}^{\prime},[x],[y]^{\prime}) $$

$$ \mathrm{}{w h e r e~}(\mathsf{S K}^{\prime},\mathsf{P K}^{\prime},\mathsf{t d})\leftarrow S_{1}(1^{\kappa},f),;([x],\mathsf{V K}{x})\leftarrow\mathsf{P r o b G e n}{\mathsf{P K}^{\prime}}(x), $$

$$ []leftarrowleftarrow\mathsf{C o m p u t e}{}{\mathsf{P K}}([x]),\mathrm{}{a n d}([\ ]{}^{\prime},\mathsf{V K}{x}^{\prime})\leftarrow S_{2}(\mathsf{t d},\mathsf{S K}^{\prime},F(x)). $$

B Assumptions on Ring Encodings

Consider an encryption scheme which satises the properties required for an encoding scheme (see Denition6). If the encryption scheme can be assumed to be linear-only extractable, which is + the assumption in [BCI 13,BISW17,BISW18], then it automatically is a secure encoding, i.e. it satises both the Generalized q-PDH and the Generalized Augmented q-PKE assumptions. We + recall the linear-only extractable denition from [BCI 13], which we adapt to the broader context of (non-eld) commutative rings with identity.

$$ \left[ \mathrm {B C I} ^ {+} 1 3 \right. $$

Denition 9(Linear-only extractable). An encoding scheme Encode = (Gen*;E) over R is linear-only extractable if for all probabilistic polynomial time algorithms A, there exists a proba- bilistic polynomial time extractor_Asuch that the following probability is negligible in the security parameter. 0 1 (pk;sk) Gen(1 );*

$$ = (\mathrm {G e n}, \mathrm {E}) $$

$$ \chi_{A} $$

$$ \Pr \left( c \neq a _ {0} + \sum_ {i = 1} ^ {n} a _ {i} x _ {i}: \begin{array}{c} (\mathrm {p k}, \mathrm {s k}) \leftarrow \operatorname {G e n} \left(1 ^ {\kappa}\right), \ x _ {1}, \dots , x _ {n} \stackrel {R} {\leftarrow} R, \ \sigma = (\mathrm {p k}, \mathrm {E} \left(x _ {1}\right), \dots , \mathrm {E} \left(x _ {n}\right)), \ (\mathrm {E} (c); a _ {0}, \dots , a _ {n}) \leftarrow (\mathcal {A} | | \chi_ {\mathcal {A}}) (\sigma) \end{array} \right). $$

Lemma 6. If an encoding scheme Encode = (Gen*;*E) is IND-CPA secure and linear-only ex- tractable, then it is an encoding scheme that satises Generalized Augmented q-PKE (Assump- tion2).

$$ {\bf\Pi}=\ \mathsf(\mathsf G{G e n},\mathsf{E}) $$

q q Proof. Let = (pk*;E(1);E(s);:::;* E(s);E();E(s);:::; E(s)). We will show that Encode satises q-PKE, meaning we will show that for any adversary A able to produce c; c^ such that c c^ = 0, Pq i there exists an extractor_Awhich outputs coecients a_isatisfying c = a_is w_ith non neglii=0 gible probab_ility.

$$ \sigma=(\mathsf{p k},\mathsf{E}(1),\mathsf{E}(s),\ldots,\mathsf{E}(s^{q}),\mathsf{E}(\alpha),\mathsf{E}(\alpha s),\ldots,\mathsf{E}(\alpha s^{q})) $$

$$ c,\hat{c} $$

$$ \alpha c!-!\hat{c}=0 $$

$$ \chi_{A} $$

$$ a{}i $$

$$ c=\sum_{i=0}^{q}a_{i}s^{i} $$

We dene two adversaries B_cand B_c^that, upon receiving as input, run exactly the same code as A and output, respectively, c and c^. By our linear-only extractable assumption on E, there exist an extractor_c(resp._c^) for B_c(resp. B_c^) which outputs a₀;:::;a_q;b₀;:::;b_q(resp. 0q 0q a⁰₀;:::;a;b⁰₀;:::;b) such that P P P P

$$ \mathcal{B}_{c} $$

$$ \mathcal{B}_{\hat{c}} $$

$$ \sigma: $$

$$ a_{0},\ldots,a_{q},b_{0},\ldots,b_{q} $$

$$ \chi_{c} $$

$$ \mathcal{B}_{c} $$

$$ \mathcal{B}_{\hat{c}}) $$

$$ a_{0}^{\prime},\ldots,a_{q}^{\prime},b_{0}^{\prime},\ldots,b_{q}^{\prime}) $$

$$ c=\sum_{i=0}^{q}a_{i}s^{i}+\sum_{i=0}^{q}b_{i}\alpha s^{i},\quad\hat{c}=\sum_{i=0}^{q}a_{i}^{\prime}s^{i}+\sum_{i=0}^{q}b_{i}^{\prime}\alpha s^{i} $$

with non negligible probability.

$$ \alpha c-\hat{c}=0 $$

Knowing that c c^ = 0 implies either that the polynomial P P

$$ P(X,Y)=X^{2}\sum_{i=0}^{q}b_{i}Y^{i}+X\sum_{i=0}^{q}(a_{i}-b_{i}^{\prime})Y^{i}-\sum_{i=0}^{q}a_{i}^{\prime}Y^{i} $$

is the zero polynomial, or that (;s) are roots of P (X;Y). We rule out the second case by the IND-CPA security of the encoding scheme and the generalized Schwartz-Zippel lemma. Hence, 0i 0i P (X;Y) = 0, which gives us that for every i 2 [q], b_i= a = 0 and a_i= b. Therefore, we have dened an extractor_Afor the Generalized Augmented q-PKE assumption, which outputs the coecients a_iobtained from_c.

$$ (\alpha,s) $$

$$ P(X,Y) $$

$$ P(X,Y)=0 $$

$$ i\in[q],,b_{i}=a_{i}^{\prime}=0 $$

$$ a_{i}=b_{i}^{\prime} $$

$$ \chi_{\mathcal{A}} $$

$$ aalpha_{i} $$

$$ \chi_{c} $$

Lemma 7. If an encoding scheme Encode = (Gen*;*E) is IND-CPA secure and linear-only ex- tractable, then it is an encoding scheme that satises the Generalized q-PDH assumption (As- sumption1).

$$ {\bf\Pi}={\bf\Pi}({\sf G e n},{\sf E}}){\bf\Pi} $$

Proof. Consider an adversary A that breaks q-PDH of the scheme Encode. We construct an adversary B that breaks IND-CPA. Consider the adversary B playing left-or-right oracle game where the adversary gets access to an encryption oracle that receives a pair of chosen messages always returns a ciphertext encrypting either the left or the right message. The adversary wins if it guesses the left-or-right bit.

B samples s₀;s₁ uniformly from an exceptional set A R. B gets access to the left-ork k right encryption oracle, makes queries on pairs (s⁰;s¹) for k 2 f0*;:::;q;q* + 2*;:::;2qg*, and ib 2q;i6=q+1 ib receives fE(s)g for challenge bit b. B now runs the q-PDH adversary A on fE(s)g. A i=0 q+1 returns y 2 fE(s)g. B now invokes the extractor that exists since Encode satises linear-only b extractability (c.f. Denition9)._A, given the same input as A and its internal randomness, P₂q;i6=q+1 q+1 ib returns a₀;;a_q;a_q+2;a₂_qsuch that a₀ + a_is ₌ s. Since B knows s₀;s₁, it checks i=1 b P₂q;_i6=q+1 q+1P₂q;i6=q+1 q+1 i i whether a₀ + a_is₀ ₌ s₀ or a₀ + ais₁ = s₁, and outputs the bit b for which i=1 i=1 this holds. Notice that the previous strategy will output a single possible value for b with high probability, which further matches the challenge bit b. This is because, for the random s₁b, we P₂q;i6=q+1 _q+1 i have that a₀ + a_is₁ ₌ s₁ w_ill hold only with probab_il_ity q=jA j, by the generalized i=1 b b Schwartz-Zippel lemma.

$$ s_{0},s_{1} $$

$$ A^{}\ \subset\ R^{} $$

$$ (s_{0}^{k},s_{1}^{k}) $$

$$ k,\in,\left{0,\ldots,q,q+2,\ldots,2q\right} $$

$$ {\mathsf{E}(s_{b}^{i})}_{i=0}^{2q,i\neq q+1} $$

$$ {\mathsf{E}(s_{b}^{i})} $$

$$ q^{\mathrm{{D H}}} $$

$$ y,\in,{\mathsf{E}(s_{b}^{q+1})} $$

$$ \chi_{\mathcal{A}}. $$

$$ a_{0},\cdots,a_{q},a_{q+2},a_{2q} $$

$$ a_{0}+\sum_{i=1}^{2q,i\neq q+1}a_{i}s_{b}^{i}=s_{b}^{q+1} $$

$$ s_{0},s_{1} $$

$$ a_{0}+\sum_{i=1}^{2q,i\neq q+1}a_{i}s_{0}^{i}=s_{0}^{q+1} $$

$$ a_{0}+\sum_{i=1}^{2q,i\neq q+1}a_{i}s_{1}^{i}=s_{1}^{q+1} $$

$$ b^{*} $$

$$ b^{*} $$

$$ \ddot{a}{0}+\sum{i=1}^{2q,i\neq q+1}a_{i}s_{1-b}^{i}=s_{1-b}^{q+1} $$

$$ s_{1-b}, $$

$$ q/|A^{*}| $$

Informally, the linear-only extractability assumption captures the fact that an adversary can perform only ane operations over the encodings provided as input. It can be argued that the PDH asssumption is in some sense weaker than linear-only extractability since the former is implied by the latter. However, if for an encoding scheme like JL, the linear-only extractability property is broken, computing non-linear homomorphisms would be possible which would mean ecient fully homomorphic encryption which is not known using current techniques. In [CRFG19], the authors consider a seemingly related notion called enhanced CPA and show that an additively homomorphic encryption scheme over Z₂k cannot satisfy enhanced CPA. We note that their attack relies on the

$$ \mathbb{Z}_{2}k, $$ fact that the adversary has access to an oracle that checks the validity of a ciphertext. In our use of a encoding scheme in constructing a SNARK, we are concerned only with one-time soundness and our setting does not provide access to such oracles to the adversary (see also the remark at the end of Section2). In proving multi-theorem soundness of designated-verier SNARK constructions, one needs to make a stronger assumption called the q power-knowledge of equality (q-PKEQ) assumption. The following q-PKEQ assumption is needed in the designated verier setting where the adversary has access to a verication oracle (in the public verication setting, this is for free and the adversary has no additional advantage). This assumption is invoked to prove multi-statement soundness in the proof to test if two (potentially adversarially generated) encodings have the same value underneath without having the secret key.

$$ q\mathrm{P K E Q} $$

Assumption 3 (Generalized q-PKEQ) The generalized q power-knowledge of equality assump- tion holds for an encoding scheme Encode if for all non-uniform probabilistic polynomial time al- gorithm A, there exists a non-uniform probabilistic polynomial time extractor_Asuch that the following probability is negligible in the security parameter. 0 1

$$ \chi_{\mathcal{A}} $$

$$ \Pr \left( \begin{array}{c c} (b = 0 \wedge \hat {c} \in {\mathrm {E} (c) }) \ \vee \ (b = 1 \wedge \hat {c} \notin {\mathrm {E} (c) }) \end{array} : \begin{array}{c} (\mathrm {p k}, \mathrm {s k}) \leftarrow \operatorname {G e n} \left(1 ^ {\kappa}\right), \ s \stackrel {R} {\leftarrow} A ^ {*}, \ \sigma = (\mathrm {p k}, \mathrm {E} (1), \mathrm {E} (s), \dots , \mathrm {E} \left(s ^ {q}\right), \mathrm {E} \left(s ^ {q + 2}\right), \dots , \mathrm {E} \left(s ^ {2 q}\right)), \ (\mathrm {E} (c), \hat {c}; b) \leftarrow (\mathcal {A} | | \chi_ {\mathcal {A}}) (\sigma) \end{array} \right). $$

C QRP as an Abstraction

In this section, we highlight the generality of our notion of QRP and our construction by outlining + how our notion recovers the QPP based construction of [KPP 14] for polynomial circuits. We sketch how the SNARK construction via QPP is a special case of our construction via QRP below.

$$ [\mathrm{K P P^{+}14}] $$

QPP as an instantiation of QRP. The following denition is recovered by Denition5, where R = F_p[Z];A = F_pR, i.e. the degree-zero polynomials, and A = F_p. The bivariate polynomial p(x;z) accounts for the wire values themselves being polynomials.

$$ R=\mathbb{F}{p}[Z],A=\mathbb{F}{p}\subset R $$

$$ Aboldsymbol^{}=\mathbb{F}_{p}^{} $$

$$ p(x,z) $$

• Denition C1 (Quadratic Polynomial Program (QPP) [KPP 14]) A QPP Q consists of three sets of polynomials, V = fv_k(x)g; W = fw_k(x)g; Y = fy_k(x)g and a target polynomial t(x). Let C be a polynomial circuit. We say that Q computes C if the following holds:

$$ \mathbf{\bar{K}P^{+}14]} $$

$$ \ \mathcal V\{=\ v_k x x},\mathcal W\ \ {=\ }\ {w{}_{k}(x)},} $$

$$ t(x) $$

a₁(z);:::;an(z);am n0+1(z);:::am(z) is a valid assignment to the input/output variables of C if and only if there exist polynomials an+1(z);:::;am n0 (z) such that t(x) divides p(x;z), where P P P

$$ a_{1}(z),\ldots,a_{n}(z),a_{m-n^{\prime}+1}(z),\ldots a_{m}(z) $$

$$ a_{n+1}(z),\ldots,a_{m-n^{\prime}}(z) $$

$$ t(x) $$

$$ p(x,z) $$

$$ \textstyle{p(x,z)=\big(\sum_{k=1}^{m}a_{k}(z)\cdot v_{k}(x)\big)\cdot\big(\sum_{k=1}^{m}a_{k}(z)\cdot w_{k}(x)\big)-\big(\sum_{k=1}^{m}a_{k}(z)\cdot y_{k}(x)\big)} $$

The degree of Q is said to be deg(t(x)).

D Some useful QRPs

While the QRP construction described in Section3would allow us to easily describe arithmetic circuits over e.g. Z₂k or the rings Rqused for homomorphic encryption, in practical scenarios one is also interested in performing bit-wise operations such as comparisons and, as it is specially the case in some levelled HE schemes, modular reduction.

$$ R_{q} $$

$$ \mathbb{Z}_{2}{}^{k} $$

D.1 Bit Decomposition Gate

We show how to build a QRP which, given an input a 2 R, gives as an output wires holding values a_i2f0*;* 1g which correspond to the ‘binary representation’ of a. Our following description is k specialized for R = GR(2*;d*), but it can be easily adapted to other rings such as those employed in Section7.1.

$$ a,\in,R $$

$$ a_{i}\in{0,1} $$

$$ a. $$

$$ R=G R(2^{k},d) $$

We provide two dierent versions of this gate. For the rst one, nothing is known about a, whereas in the second case, better eciency is achieved by assuming that a 2 Z₂k. When interested in computation over Z₂k only, the former version of the gate where potentially a =2 Z₂k is necessary only if the prover is providing some inputs to the QRP in a zero-knowledge way. Nevertheless, once the inputs from the prover have been asserted to be elements of Z₂k, one can use the more ecient Z₂k-splitter gate during the rest of the circuit. The provers inputs can be tested to be from Z₂k either by inspection when those are provided in the clear, or when they are provided in ZK, by e.g. applying the general R-splitter gate to them and outputting to the verier all the wires that should be always equal to zero in a ‘binary representation’ of an element in Z₂k R. Let A R be the exceptional set.

$$ a{,cdot} $$

$$ a\in\mathbb{Z}_{2^{k}} $$

$$ \mathbb{Z}_{2}k, $$

$$ a\notin\mathbb{Z}_{2^{k}} $$

$$ \mathbb{Z}_{2^{k}} $$

$$ \mathbb{Z}_{2^{k}} $$

$$ \mathbb{Z}_{2^{k}\mathrm{-s p l i t t e r}} $$

$$ \mathbb{Z}_{2^{k}}\subset R $$

$$ A\subset R $$

1. Z₂k-splitter gate: This mini-QRP has one input wire, holding a 2 Z₂k, and k output wires P k i 1 holding a₁;:::;a_k2 f0*;* 1g such that a = 2 a_i. Label the input wires as 1*;:::;k* and i=1 Q k the output wire as k + 1. Let t(x) = (x r) (x r_i), where r;r₁;:::;r_k2 A are pairwise i=1 dierent. In an approach similiar to Pinocchio [PHGR13], we set:

$$ \mathbb{Z}_{2^{k\mathrm{-p l l t t e e}}} $$

$$ a \in \mathbb {Z} _ {2 ^ {k}} $$

$$ a_{1},\ldots,a_{k}\in{0,1} $$

$$ \textstyle{a,=,\sum_{i=1}^{k}2^{i-1}a_{i}} $$

$$ 1,\ldots,k $$

$$ k+1 $$

$$ \textstyle t\bigl(x\bigr)=\bigl(x-r\bigr)\prod_{i=1}^{k}\bigl(x-r_{i}\bigr) $$

$$ r,r_{1},\ldots,r_{k}\in A $$

$$ v_{0}(r)=0,v_{i}(r)=2^{i-1},\mathrm{f o r}1\leq i\leq k,v_{k+1}(r)=0, $$

$$ w_{0}(r)=1,w_{i}(r)=0,\mathrm{f o r}1\leq i\leq k,w_{k+1}(r)=0, $$

$$ y y_{0}(r)=0,y_{i}(r)=0,\mathrm{f o r}\mathbf{1}\leq\mathbf{}\underset{}{i\ }\ \leq\mathbf{}k,y_{k+1}(r)=\mathbf{1} $$

For 1 j k:

$$ 1\leq j\leq k{} $$

$$ vupsilon_j(r_{j})=1,v_{i}(r_{j})=0{\mathrm{f o ra l l~}}i\neq j, $$

$$ w_{0}(r_{j})=1,w_{j}(r_{j})=-1,w_{i}(r_{j})=0\mathrm{f o ra l l~}i\neq0,j, $$

$$ y _ {i} \left(r _ {j}\right) = 0 \mathrm {f o r a l l} i $$

P P P If (v₀(x) + akvk(x)) (w₀(x) + akwk(x)) (y₀(x) + akyk(x)) is divisible by t(x), then it P k i 1 must be 0 at r, and therefore, by the rst set of equations, this gives, a = 2 a_i. The i₌₁ second set of equations guarantee that each r_jis a root, which implies, a_j(1 a_j) = 0. Since all the zero divisors of R belong to the maximal ideal (2), it follows that if a_jis a zero divisor then a_j1 is not, and thence the only solutions for the previous equation are a_j2f0*;* 1g. Together, these give the guarantee that all a_iare bits, and are the binary decomposition of a.

$$ \textstyle(v_{0}(x)+\sum a_{k}v_{k}(x))\cdot(w_{0}(x)+\sum a_{k}w_{k}(x))-(y_{0}(x)+\sum a_{k}y_{k}(x)) $$

$$ t(x) $$

$$ a=\sum_{i=1}^{k}\dot{2^{i-1}}a_{i} $$

$$ r! $$

$$ r_{j} $$

$$ a_{j}\big(1-a_{j}\big)=0 $$

$$ a_{j}\pm1 $$

$$ a_{j} $$

$$ a_{j}\in{0,1} $$

$$ \ {a\ },{}boldsymbol{\alpha}{i} $$

2. R-splitter gate: This works essentially as the previous version of the splitter gate repeated times in parallel, once for every component of R seen as a free-module of rank over Z₂k.

$$ \delta $$

D.2 Modular reduction gate

$$ \delta $$

$$ \mathbb{Z}_{2}{}k $$

In leveled homomorphic schemes, namely capable of evaluating circuits of arbitrary size, but known beforehand, without involving the costly bootstrapping procedure, the key tool is the modulus switching procedure which allows to switch a ciphertext encrypted under a modulus q to a smaller modulus q₀ in order to keep the noise level \constant". Hence by selecting a chain of moduli fq₀;:::;q_Lg long enough to perform the desired computations, bootstrapping is no longer needed. The modulus switching allows to decrease the size of the noise of a level j > 0 ciphertext, as soon as it becomes too important. Roughly, the idea is to drop one (or several) levels in the ladder of moduli by scaling the ciphertext by qi=qjfor i < j, which roughly scales down the noise by the same factor.

$$ q_{0} $$

$$ {q_{0},\ldots,q_{L}} $$

$$ j>0 $$

$$ q!,q_{j} $$

$$ i<j $$

Of special interest for the application of SNARKs over Homomorphic Encryption schemes is the fact of having a way to compute modular reductions at a reasonable cost. We provide below a \mod q_i" gate, which has a cost of (dlog qe+ dlogq_ie+ 3) d multiplication gates in the underlying QRP over R_q, where R_q= Z_q[Y]=(f (Y)) and d = deg(f (Y)). The cost of the gate can be further optimized to (dlog qe + dlogq_ie + 1) d + 2, as we will sketch after its more expensive but simpler to explain implementation.

$$ \ q_{i}^{\prime2} $$

$$ \left(\left\lceil\log q\right\rceil+\left\lceil\log q_{i}\right\rceil+3\right)\cdot d $$

$$ R_{q}. $$

$$ R_{q}=\mathbb{Z}_{q}[Y]/(f(Y)) $$

$$ d=d e g(f(Y)) $$

$$ \left(\left\lceil\log{q}\right\rceil+\left\lceil\log{q_{i}}\right\rceil+1\right)\cdot d+2 $$

Let Q = dlogqⁱe. What our QRP will prove is the following: Given z 2 R^q, expressed as P P d 1 ‘ d ₁ ‘ z = z_‘Y;z_‘2 Z_q, the Prover can prove that z~ = z_‘Y, where z_‘z_‘mod q_i. ‘=0 ‘=0 He does so by providing, for each ‘ 2 [d], values x_‘; z~_‘;t_‘2 Z_q(where the two latter are actually provided in a bit-decomposed manner) such that:

$$ Q;=;\lceil\log q_{i}\rceil $$

$$ z;\in;R_{q}. $$

$$ z=\sum_{\ell=0}^{d-1}z_{\ell}\cdot Y^{\ell},z_{\ell}\in\mathbb{Z}_{q} $$

$$ \tilde{z}=\sum_{\ell=0}^{d-1}\tilde{z}_{\ell}\cdot Y^{\ell} $$

$$ \tilde{z}{\ell}\equiv z{\ell} $$

$$ \ell\in[d] $$

$$ q_{i} $$

$$ x_{\ell},\tilde{z}{\ell},t{\ell}\in\mathbb{Z}_{q} $$

$$ \tilde{z}{\ell}=\begin{cases}{\sum{k=0}^{Q-1}2^{k}\cdot\tilde{z}{\ell,k};\quad\tilde{z}{\ell,k}\in{0,1}}\ {z_{\ell}-x_{\ell}\cdot q_{i}}\ {end\ }cases\end{cases} $$

(9)

$$ t_{\ell}=\begin{array}{l}{\sum_{k=0}^{\lceil\log q\rceil-1}2^{k}\cdot t_{\ell,k};\quad t_{\ell,k}\in{0,1}}\ {\tilde{z}{\ell}-q{i}}\end{array} $$

(10)

$$ f_{z_{\ell}}=\sum_{k=Q}^{\lceil\log q\rceil-1}t_{\ell,k}\neq0 $$

(11)

Equation (9) can be veried by a slightly optimized Bit Decomposition gate, which costs Q+ 1 multiplication gates. The purpose of this part of the circuit is proving both that z_‘is a representative k of the class z_‘mod q_ismaller than 2. Note that we are not done at this point, as the Prover could k be providing a value ~z‘such that qi< z‘< 2. This is ruled out by the combination of Equations k (10) and (11), which ensure that ~z_‘q_i> 2. Their cost is that of a Bit Decomposition for the former (i.e. dlog qe + 1 multiplication gates) and one multiplication gate for the latter. In more detail, we check that every fzwhich results form computing ~z‘z‘mod qiis not zero by checking whether Q_‘ 6 f_z6= 0 . z_‘ ‘

$$ Q+1 $$

$$ z_{\ell} $$

$$ \tilde{z}_{\ell} $$

$$ 2^{k} $$

$$ q_{i} $$

$$ \tilde{z}_{\ell} $$

$$ q_{i}<\tilde{z}_{\ell}<2^{k} $$

$$ \tilde{z}{\ell}!-!q{i}>2^{k} $$

$$ \ \vert log q\vert+1 $$

$$ \tilde{z}{\ell}\equiv z{\ell} $$

$$ f_{z_{\ell}} $$

$$ \textstyle\prod_{z_{\ell}}f_{z_{\ell}}\neq0^{6} $$

$$ q_{i} $$

The more ecient implementation of the \mod q_i" gate, costing (dlog qe + dlogq_ie + 1) d + 2 multiplication gates, can be built in almost the same way as in our previous exposition, but \packing" each of the equality tests at the bottom part of Equations (9) and (10) into a single equality check over R_q. More specically, these can be implemented as:

$$ q i^{\ 3} $$

$$ \left(\left\lceil{\mathrm{l o g}},q\right\rceil+\left\lceil{\mathrm{l o g}},q_{i}\right\rceil+1\right)\cdot d+ $$

$$ R_{q} $$

$$ \tilde{z}=\sum_{\ell=0}^{d-1}\tilde{z}{\ell}\cdot Y^{\ell}=z-q{i}\cdot(\sum_{\ell=0}^{d-1}x_{\ell}\cdot Y^{\ell}) $$

(12)

⁶ Note that fz‘, which is the sum of a few bits, will not be a zero divisor in our concrete application. One should be careful to deal with such case in more general scenarios.

$$ f_{z_{\ell}}. $$

$$ t=\sum_{\ell=0}^{d-1}t_{\ell}\cdot Y^{\ell}=\tilde{z}-q_{i}\cdot(\sum_{\ell=0}^{d-1}Y^{\ell}) $$

(13)

E Further details on SNARKs for computation over Encrypted Data

E.1 Further details on Torus encoding

Multiplying encoded elements with elements from R: We next show explicitly how our TFHE-based encoding is R-linear homomorphic. R = Z_m[Y]=(f (Y)) is a free module over Z_mof rank d, i.e. we d 1 can nd a basis for R. Let be a root of f (Y), we have that f¹;;:::; g is one of such basis. The d d 1 map : R ! (Z_m), which sends b = b₀ + + b_{d 1}to (b) = (b₀;:::;b_{d 1}) is an isomorphism of Z_m-modules. We will make extensive use of this isomorphism going forward.

$$ {\overline{{R=\mathbb{Z}_{m}[Y]/(f(Y))}}} $$

$$ \mathbb{Z}_{m} $$

$$ d, $$

$$ \xi $$

$$ f(Y) $$

$$ {1,\xi,\ldots,\xi^{d-1}} $$

$$ \phi:R\to(\mathbb{Z}_{m})^{d} $$

$$ b = b _ {0} + \dots + b _ {d - 1} \xi^ {d - 1} \text {t o} \phi (b) = \left(b _ {0}, \dots , b _ {d - 1}\right) $$

$$ \mathbb{Z}_{m} $$

$$ \begin{aligned}{\mathsf{E}{\mathsf{p k}}:R}&{{}\to(\mathbb{T})^{d}}\ {a}&{{}\mapsto\mathsf{E}{\mathsf{p k}}(a)=(\mathsf{T F H E}(a_{0}),...,\mathsf{T F H E}(a_{d-1}))}\ \end{aligned} $$

The encoding we use is the following:

For our QRPs, we wish to compute values of the form E(a b), where a;b 2 R, given E(a) and b. d The problem is that E(a) 2 (T), an^d the torus does not allow us to simply and directly compute b E(a) as in previous occasions. Rather, we have to look at the R-module endomorphism_bwhich is induced by multiplication of any element of R with b, and use this to manipulate the d individual values TFHE(a₀);:::; TFHE(a_{d 1}) 2 T.

$$ E(\b a\cdot\ \ \ b) $$

$$ a,b\in R $$

$$ E(a) $$

$$ E(a)\in(\mathbb{T})^{d} $$

$$ b\cdot E(a) $$

$$ \cdot_{b} $$

$$ \mathsf{T F H E}(a_{0}),...,\mathsf{T F H E}(a_{d-1})\in\mathbb{T} $$

In a more explicit and step-by-step fashion,_bis an R-module endomorphism and hence a Z_m- d d module homomorphism_b: (Z_m)! (Z_m). We can therefore represent this operation as follows:

$$ \cdot $$

$$ \mathbb{Z}_{m^{-}} $$

$$ \cdot_{b}:(\mathbb{Z}{m})^{d}\to(\mathbb{Z}{m})^{d} $$

$$ \cdot_{b}:(\mathbb{Z}{m})^{d}\to(\mathbb{Z}{m})^{d} $$

$$ a\mapsto M_{b}\cdot a $$

where M_b2M_{d d}(Z_m). As a side note, in fact, M_bcan be easily dened from the polynomial f (Y) d used to construct R ’ (Z_m). Our goal can now be re-stated as computing E(_b(a)), given E(a) and b 2 R. We are almost done, as TFHE(x) + TFHE(y) = TFHE(x + y) and T allows for external multiplication with elements in Z. In full formalism, let N_b2M_{d d}(Z) such that N_bM_bmod n. We only need to compute:

$$ f(Y) $$

$$ M_{b} $$

$$ M_{b}\in\mathcal{M}{d\times d}(\mathbb{Z}{m}) $$

$$ R,(\simeq,(\mathbb{Z}_{m})^{d} $$

$$ E(\cdot_{b}(a)) $$

$$ E(a) $$

$$ b\in R $$

$$ {\mathsf{T F H E}}(x)+{\mathsf{T F H E}}(y)={\mathsf{T F H E}}(x+y) $$

$$ \mathbb{T} $$

$$ \mathbb{Z} $$

$$ N_{b}\in\mathcal{M}_{d\times d}(\mathbb{Z}) $$

$$ N_{b}\equiv M_{b} $$

$$ N_{b}\cdot E(a)=E(N_{b}\cdot a)=E(M_{b}\cdot a)=E(\cdot_{b}(a))=E(a\cdot b) $$

F [Gro16]-Like Construction based on Linear-Only Encodings

We construct a zk-SNARK scheme for ring computations with eciency close to its eld-restricted counterpart proposed in [Gro16].

Let C be an arithmetic circuit over R, with m wires and d multiplication gates. Let Q = m (t(x); fv^k(x);w^k(x);y^k(x)g) be a QRP which computes C. We denote by I^io= 1*;* 2*;:::‘* the k=0 indices corresponding to the public input and public output values of the circuit wires and by I_mid= ‘ + 1*;:::m*, the wire indices corresponding to non-input, non-output intermediate values. Let Encode = (Gen*;*E) be a secure encoding scheme and A R an exceptional set.

$$ Q\ = $$

$$ (t(x),{v_{k}(x),w_{k}(x),y_{k}(x)}_{k=0}^{m}) $$

$$ I_{i o},=,1,2,\ldots, $$

$$ I_{m i d}=\ell+1,\ldots m $$

$$ A^{}\subset R^{} $$

Our scheme is based on the assumption of linear-only encodings and consists in 3 algorithms RingSNARK = (Setup*;Prove;*Verify) described in Figure3.

$$ {\sf R i n g S N A R K}=({\sf S e t u p},{\sf P r o v e},{\sf V e r i f y y}) $$

$$ \alpha,\beta,\gamma,\delta\leftarrow R^{},\quad s\leftarrow A^{},\qquad(\mathsf{p k},\mathsf{s k})\leftarrow\mathsf{G e n}(1^{\kappa}) $$

$$ \textstyle\mathsf{c r s}=\Big(\mathsf{p k},{\mathsf{E}\big(s^{i}\big)}{i=0}^{d-1},\ {\mathsf{E}\big(\frac{\beta v{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\gamma}\big)}{k\in I{i o}}, $$

$$ \textstyle{\mathsf{E}(\frac{\beta v_{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\delta})}{k\in I{\mathrm{}{m i d}}},;\bigl\ \mathsf\ E{\bigl(\frac{s^{i}t(s)}{\delta}\bigr)\bigr}_{i=0}^{d-1}\Bigr)} $$

$$ \mathsf{P r o v e}(\mathsf{c r s},u,w) $$

$$ u=\big(a_{1},\ldots,a_{\ell}\big),\ a_{0}=1 $$

$$ \mathsf{v k}=\left(\mathsf{s k},\mathsf{c r s},s,\alpha,\beta,\gamma,\delta\right) $$

$$ \pi=(A,B,C) $$

$$ w=\left(a_{\ell+1},\ldots,a_{m}\right) $$

$$ A=\ \ mathsf\ E{\ A_{v}}, $$

$$ v(x)=\sum_{k=0}^{m}a_{k}v_{k}(x) $$

$$ B=\ {\mathsf E}(B_{w}). $$

$$ v_{m i d}(x\boldsymbol)=\sum_{k boldsymbol\in I_{m i d}}a_{\boldsymbol k}v_{\boldsymbol k}(\boldsymbol x) $$

$$ C=\mathsf{E}(C_{y}) $$

$$ v_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}v_{i}\big(x\big) $$

$$ w(x)=\sum_{k=0}^{m}a_{k}\tilde{w_{k}}(x) $$

$$ w_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}w_{i}\big(x\big) $$

$$ w_{m i d}\big(\boldsymbol{x}\big)=\sum_{k\in I_{m i d}}a_{k}w_{k}\big(\boldsymbol{x}\big) $$

$$ y(x)=\sum_{k=0}^{m}a_{k}y_{k}(x) $$

$$ y_{i o}\big(x\big)=\sum_{i=0}^{\ell}a_{i}y_{i}\big(x\big) $$

$$ y_{m i d}\big(\boldsymbol{x}\big)=\sum_{k\in I_{m i d}}a_{k}y_{k}\big(\boldsymbol{x}\big) $$

$$ f_{i o}=\frac{\beta v_{i o}(s)+\alpha w_{i o}(s)+y_{i o}(s)}{\gamma} $$

$$ \textstyle{h(x)={\frac{(v(x)w(x)-y(x))}{t(x)}}} $$

$$ f_{m i d}=\frac{\beta v_{m i d}(s)+\alpha w_{m i d}(s)+y_{m i d}(s)}{\Lambda} $$

$$ F=\mathsf{E}(f_{i o}) $$

$$ A=\ {mathsf E E}\big(\alpha+v(s)\big) $$

$$ A B=\mathsf{E}(\alpha)\mathsf{E}(\beta)+\gamma F+\delta\mathcal{C} $$

$$ B = \mathsf {E} \left(\beta + w (s)\right) $$

$$ C=\mathsf{E}(f_{m i d}+\frac{t(s)h(s)}{\hbar}) $$

Fig. 3. RingSNARK Construction from Linear-only Encodings.

$$ A_{v}B_{w}=\alpha\beta+\gamma f_{i o}+\delta C_{y} $$

$$ \pi=(A,B,C) $$

Theorem 7. Let R be commutative ring with identity with an exceptional subset A, and d be an upper bound on the degree of the QRP. Assuming that the linear-only extractable assumption as per Denition9holds for the encoding scheme Encode over R (and A ), the protocol RingSNARK described in Fig.3is a SNARK as per Denition1, with soundness error 1*=jA j.*

$$ A^{*} $$

$$ 1/|A^{*}| $$

F.1 Proof of Security

We rst give a variant of the Schwartz-Zippel lemma for Laurent polynomials over rings that we will rely on in the proof.

1 Lemma 8. Let A be an exceptional set. Let h(X) 2 R[X₁;X;:::;X_n;X_n] where no term in any 1 1 X_ihas degree less than D or larger than D. Let us assume that h(X) is not the zero-polynomial. n Let a 2 (A) be chosen uniformly at random. Then

$$ X_{i} $$

$$ h(X) $$

$$ a\in(A)^{n} $$

$$ \operatorname*{P r}[h(\mathbf{a})=0]\leq{\frac{2n D}{|A|}}. $$

Q ⁿ Proof. We notice that f (X) := X h(X) is an ordinary polynomial of degree 2nD. Since i=1 iD h(a) = 0 implies f (a) = 0, by the generalized Schwartz-Zippel lemma (Lemma2), we have that

$$ \textstyle f\big(X\big):=\prod_{i=1}^{n}X_{i}^{D}\cdot h\big(X\big) $$

$$ h(a)=0 $$

$$ \leq2n D $$

$$ f(\boldsymbol{a})=0 $$

$$ \operatorname*{P r}[h(a)=0]\leq\operatorname*{P r}[f(a)=0]\leq{\frac{2n D}{|A|}}, $$

nishing the proof.

We are now ready to give the security proof of our scheme RingSNARK:

Theorem 8. Let R be commutative ring with identity with an exceptional subset A, and d be an upper bound on the degree of the QRP. Assuming that the linear-only extractable assumption as per Denition9holds for the encoding scheme Encode over R (and A ), the protocol RingSNARK described in Fig.3is a SNARK as per Denition1, with soundness error 1*=jA j.*

$$ 1/|A^{*}| $$

Proof. Completeness. Completeness of the SNARK protocol follows by QRP completeness and by the (statistical) correctness of the Encode scheme.

Knowledge Soundness. We will show the existence of an extrator that on same input and random coins as A can produce a valid witness whenever the prover A outputs a valid proof. Let A be the PPT adversary in the game for knowledge soundness (Denition1) able to produce a proof for which the verication algorithm returns true. By linear-only extractable assumption9we can m run an extractor that gives us a vector of coecients A;A;A ;A ; fA^kg and polynomials k=0 A(x);A_h(x) of degree d 1*;d* 2 such that the value encoded in the proof element A can be written as a linear combination of the initial values encoded in the crs:

$$ \mathrm{P P T} $$

$$ A_{\alpha},A_{\beta},A_{\gamma},A_{\delta},{\mathcal{A}{k}}{k=0}^{m} $$

$$ A(x),A_{h}(x) $$

$$ d - 1, d - 2 $$

$$ \begin{aligned}{A_{v}=A_{\alpha}\alpha+A_{\beta}\beta+A_{\gamma}\gamma+A(s)+\sum_{k=0}^{\ell}A_{k}\frac{\beta v_{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\gamma}+}\ {}&{{}+\sum_{k=\ell+1}^{m}A_{k}\frac{\beta v_{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\delta}+A_{h}(s)\frac{t(s)}{\delta}}\ \end{aligned} $$

(14)

We can write out B_wand C_yin a similar fashion. We can see the verication equation as an equality of multivariate Laurent polynomials. By Lemma8, A has negligible success probability unless the verication equation holds when viewing A_v;B_wand C_yas formal polynomials in indeterminates x;x;x ;x ;x_s.

$$ B_{w} $$

$$ C_{y} $$

$$ 8,\mathcal A $$

$$ A_{v},B_{w} $$

$$ C_{y} $$

$$ x_{\alpha},x_{\beta},x_{\gamma},x_{\delta},x_{s} $$

Using the verication test equations and following the same reasoning as the proof in [Gro16] we eliminate coecient by coecient until we obtain:

$$ A(x)=\sum_{k=0}^{m}a_{k}v_{k}(x),\quad B(x)=\sum_{k=0}^{m}a_{k}w_{k}(x),\quad C(x)=\sum_{k=0}^{m}a_{k}y_{k}(x). $$

This implies that w = (a_‘+1;:::;a_m) is a witness for u = (a₁;:::;a_‘).

$$ w=\left(a_{\ell+1},\ldots,a_{m}\right) $$

$$ u=(a_{1},\ldots,a_{\ell}) $$