# Rinocchio: SNARKs for Ring Arithmetic
Chaya Ganesh¹, Anca Nitulescu², and Eduardo Soria-Vazquez³
1
Indian Institute of Science, India.
2
Protocol Labs, USA.
3??
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 F*p* 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 Fpat the cost of *m* + 1 multiplication gates, where *m* = *d*log(*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 Fpis 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 Fp. 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 *R*q= 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= Zq[*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
Fq. 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= Zq[*Y*]*=*(*f* (*Y*)). Instead, it computes the circuit *C* over
Zq[*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 ofAon 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 Zp*k* 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*A*such 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 nf*0*g* for which *9 q 2 R nf*0*g* 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 nf*0*g*, 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* = 1*2 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*m*g*. 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 a1a1ai
*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*i*x*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*m*be 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*n*g R. We say that A is an exceptional set if 8i 6*= *j;a*i*a*j*2 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 Pra 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})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*) = 0*j: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}
$$
4
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 x*i) 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=1
*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* = Zp*k* [*X*]*=*(*h*(*X*))*, where p is a prime, k a*
*positive integer and h*(*X*) *2* Zp*k* [*X*] *a monic polynomial of degree d* 1 *such that its reduction*
*modulo p is an irreducible polynomial in* Fp[*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 Zp*k*, there is a unique degree *d* Galois extension of Zp*k*, 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 Fp*d* = *GR*(*p;d*) and nite rings
k
of the form Zp*k* = *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*)=Fp*d*, and thus a canonical homomorphism : *R !* Fp*d*
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*n*;a*m n0+1*;:::a*m*2 R is a valid assignment to the input/output variables of C if*
m n n0
*and only if there exist a*n+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
wk(*x*) *and Y* (*x*) = *y₀*(*x*) + *a*k*y*k(*x*)*.*
k=1
$$
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 ta*r*get 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₁;:::;X*m 1) = *c₀* +
P P
m 1 m 1
*c*i*X*i(resp.2(*X₁;:::;X*m 1) = *d₀*+ *d*i*X*i) *t*o 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 2f*0*;:::;m* 1*g*, 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*m*2 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 2f*1*;* 2*g*, let *Q*ibe a QRP computing an arithmetic circuit *f*i. Let *I*ibe the set of indices
representing all wires in *f*iand 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*i*g; W* =
k
(i) (i) (i) (i)
*fw* (*x*) : *k 2I*i*g; Y* = *fy* (*x*) : *k 2I*i*g* and target polynomial *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 2f*1*;* 2*g*, 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 2f*1*;* 2*g*, let *t* (*x*) = (*x r*). Dene ideals *I*i;ji= (*x r*), where 1 *j*i*d*i.
jii=1 jiji
Dene *S* = *fI*i;ji: 1 *i* 2*;* 1 *j*i*d*i*g*. All the ideals in *S* are pairwise 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*k*2 I*i=o*g* 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*k*2I₁*;i=o*[I₂*;i=o*g*. 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*k*2I₁ [I₂g* as
*a*k= *b*kfor all *b*k*2I₁* and *a*k= *c*kfor all *c*k*2I₂*. 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 2f*1*;* 2*g*, 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) (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*) =
(1) (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*k*2I*i=o*g* 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 2f*1*;* 2*g*. 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=o*I₁*;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)
$$
| Roots | Polynomials in QRP($\mathcal{V},\mathcal{W},\mathcal{Y},t(x)$) | | |
| --- | --- | --- | --- |
| Gates | Left inputs | Right inputs | Outputs |
| $r_{5}$ | $v_{3}(r_{5})=1$ | $w_{4}(r_{5})=1$ | $y_{5}(r_{5})=1$ |
| $r_{5}$ | $v_{k}(r_{5})=0,$ | $w_{k}(r_{5})=0,$ | $y_{k}(r_{5})=0,$ |
| $r_{5}$ | $k\neq 3$ | $k\neq 4$ | $k\neq 5$ |
| $r_{6}$ | $v_{1}(r_{6})=v_{2}(r_{6})=1$ | $w_{5}(r_{6})=1$ | $y_{6}(r_{6})=1$ |
| $r_{6}$ | $v_{k}(r_{6})=0,$ | $w_{k}(r_{6})=0,$ | $y_{k}(r_{6})=0,$ |
| $r_{6}$ | $k\neq 1,2$ | $k\neq 5$ | $k\neq 6$ |
$$
(\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 ff*E(*a*)*g* : *a 2 Rg partition S, where f*E(*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=1
*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 2f*E(*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*A*such 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*, andAgiven 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*k*v*k(*x*) *c*k*w*k(*x*) *c*k*y*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* = *f*0*;a₁;:::;a*n 1: *a*i*2 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*n*g R* be an exceptional set. For all *i 2f*1*;:::;n* 1*g*, dene *a*i= *b*n*b*i.
By the denition of *B*, we have that *a*i*2 R* and hence so is (0 *a*i). Furthermore,*8i 6*= *j;a*i*a*j=
(*b*n*b*i) (*b*n*b*j) = *b*i*b*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*]e*denote 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*]e*such 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+1*be 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*e*x 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*;:::;u*i*;*e;0) for every *u*i(*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 ass*u*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+1*x*. Then, *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*i*2 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*e*x*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= *f*0*;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 nf*0*g*
i d
crs = *f*E(*s*)*g*i=0*; f*E(*rv vk*(*s*))*gk2Imid; f*E(*rw wk*(*s*))*gk2Imid; f*E(*ry yk*(*s*))*gk2Imid;*
*f*E(*rv vk*(*s*))*gk2Imid; f*E(*rw wk*(*s*))*gk2Imid; f*E(*ry yk*(*s*))*gk2Imid;*
i d
*f*E(*s*)*g*i=0*; f*E( (*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(r*v* 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 v*mid*(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 randomv*;*w*;*y*R*, and addsv*t*(*s*) inside the encoding to *v*mid(*s*);w*t*(*s*)
to *w*mid(*s*); andy*t*(*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*v*t*(*s*))*;*E(*r*w*t*(*s*)), E(*r*y*t*(*s*)), E(v*r*v*t*(*s*))*;* E(w*r*w*t*(*s*))*;*
E(y*r*y*t*(*s*)*;* E(*r*v*t*(*s*)), E(*r*w*t*(*s*)), E(*r*y*t*(*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* (4*d* + 3)*-PKE*
*and the generalized q-PDH assumptions hold for the encoding scheme* Encode *over R (and A ) for*
*q* = 4*d*+ 4*, the protocol* Rinocchio *described above is a SNARK as per Denition1, with soundness*
error 1=jA j*.*
$$
q=4d+4
$$
$$
A^{*}
$$
$$
1/|A^{*}|
$$
5
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*v0*r*w. Let *r*v= *r*v0*s*, *r*w= *r*w*s*,
3(d+1)
and *r*y= *r*y0*s*. The value is chosen as follows. Sample a polynomialpoly(*x*) *2 A* [*X*]
of degree at most 3*d* + 3 uniformly at random, subject to the constraint thatpoly(*x*) (*rv*0vk(*x*) +
0 (d+1) 2(d+1) d+3 q (4d+3)
*r*w*x w*k(*x*)+*r*y0*x 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
Sincepoly(*x*) (*rv*0vk(*x*) + *r*w*x w*k(*x*) + *r*y0*x² 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* 3*d* 2) + (3*d*+ 3) + (2*d*+ 2) +*d* = *q*+ 3*d*+ 3 2*q*. 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* 4*d* + 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, aspoly(*x*) is a polynomial of degree at most 3*d*+ 3 and
q (4d+3)
= *s*poly(*s*), we have that Pr[ = 0] (3*d* + 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 newpoly(*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*v0*s*, *r*w= *r*w*s*, and *r*y= *r*y0*s*, 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*;* Er0*;* Er0*;* Er0, where the four latter are dened as Ea(*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 Er0*;* Er0*;* Er0. 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
extractorAto extract a polynomial *H*(*x*) = *h*i*x* 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. Er0 (*s V*mid)
v
d+1^
and Er0 (*s V*mid) is an i.i.d.v. If we look at any of the three remaining encodings Er0 ( ), Er0 ( )
v v v
or Er0 ( ), 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 (2*d*+ 1)-PKE assumption (resp. *W*mid(*x*) due to (3*d*+ 2)-PKE and *Y*mid(*x*) due
to (4*d*+ 3)-PKE). Focusing on *V*mid(*x*), notice that *A* does not have a (2*d*+ 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 expectedv= (pk*; f*Er0 (s)g*; f*Er0 (v*s* g²) in two ways: It is comv i v i=0
i d
pletely missin*g* the powers *fs g* and, for those between *d* + 1 and 2*d* + 1, it instead has the
i=0
d+1
evaluation at *s* of the polynomials *fx v*k(*x*)*g*k2I. Informally, *s*ince *B* can compute ~vfromv,
mid
we can extract. In more syntactic rigour, *B* can sendvto a (2*d*+ 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 extractorAvwhich gets a polynomial *x V*mid(*x*) = vi*x* of degree
i=0
at most 2*d* + 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*k*v*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.
mi*d*
$$
\{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*k*u*k(*x*), where *c*k*2 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*k*v*k(*x*)*;w* (*x*) = ckwk(x) and y (x) = ck*y*k(*x*).
k2Imidk2Imidk2Imid
Note that *v⁰*(*x*)*;w⁰*(*x*)*;y⁰*(*x*) have degree at most *d*, sin*c*e 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*-submodules *fx* : *i 2* [0*;d*]*g*, *fx* : *i 2* [0*;d*]*g*, and *fx* :
*i 2* [0*;d*]*g* of *R*[*x*] are disjoint (except at zero) *w*e 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 *Y*mid(*x*) = y⁰(x). Therefore, V (x) =
P P P P
ckvk(*x*)+*V*midx) = ckvk(*x*)+ ckvk(x);W(x) = ckwk(x)+Wmid(x) =
Pk2Iio P (k2Iiok2Imid Pk2Iio P
ckwk(*x*) + ckwk(x), and Y (x) = ckyk(x) + Ymid(x) = ckyk(x) +
Pk2Iiok2Imidk2Iiok2Iio
ckyk(x). Finally, as we assumed that *V* (*x*) *W* (*x*) *Y* (*x*) = *H*(*x*) *t*(*x*), we have that
k2Imid
*V* (*x*)*;W*(*x*)*;Y* (*x*) can be written as the same linear combination *fc*k*g*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 solution.
$$
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* 2*d* and *s* as a root. Express (*x*) =k*x* + ^(*x*), where *k* 2*d*,
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
k*s* = *s* ^(*s*). *B* can compute E(k*s*) by computing E( *s* ^(*s*)), which is a
i q
known linear combination of the *f*E(*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 *V*mid(*x*)*;W*mid(*x*)*;Y*mid(x) are not in the required spans. There does
P P
not exist *fc*k*g*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*k*y*k(*x*). Then, the polynomial *U* (*x*) = *rv*0*x V*mid(*x*) +*r*w*x W*mid(*x*) +
k2Imid
3(d+1)
*r*y0*x 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*v0*x v*k(*x*) + *r*w*x w*k(*x*) + *r*y0*x y*k(*x*)*g*. Re*c*all that *B* chose a polynomialpoly(*x*) *2 A* [*X*] of degree at most 3*d*+ 3 subject to the constraint that all polynomials in
0 (d+1) 2(d+1) d+3
*f*poly(*x*) (*rv*0vk(*x*)+*rwx w*k(*x*)+*r*y0*x 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 Rnf*0*g*
$$
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 whenpoly(*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, pick *p* = 2 *p⁰* + 1 and *q* = 2*q⁰* + 1, where *p⁰;q⁰* are primes. Let *g* be a random
generator of both Zpand Zq, *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 Zp. Let *m* = 2 *m*j*; m*j*2*
j=0
2k 1
*f*0*;* 1*g*. We *c*an 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 computin*g m*i 1*;:::;m₀*, com*p*ute *m*ias follows: Set
*m*i= 0 if and only if
!2*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*1*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})
$$
---
{ ZN1*:::* ZNE*:* JLpk(*a*) is a probabilistic encoding algorithm mapping a ring element *a 2 R*
to an encoding space *Z* = ZN1*:::* ZNsuch that the sets *ff*E*:* JL(*a*)*g* : *a 2 Rg* partition *Z*,
where *f*E*:* 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*‘;0*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* = *fa*i*2 R* :
P
1 j
*a*i= *a*i;j*X;a*i;j*2f*0*;* 1*gg* 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-SNA*R*K 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*Q*j* = *d* and *jA j* = *jAjjA*Q*j* = 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 Zq
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= Zp[*Y*]*=*(*f* (*Y*)) and the ring of cyphertexts is *R*q= Zq[*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
15
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*i. 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}<\cdotsp= Zp[*Y*]*=*(*f* (*Y*)) for some integer *p* (a prime, a power of 2 or a
2
small number 1 (mod 2*N*), 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 Zqthat 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 Zq, 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 Zqis 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 string *s* Z. Output sk = *s*.
*Q*
$$
\operatorname {G e n} \left(1 ^ {\kappa}, \Gamma\right)
$$
$$
s\gets\mathbb{D}_{O}^{n}
$$
n
Esk(*m*): Given *m 2* Zq, sample *a* Z, dene = *Q*; *e* (Zq). 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 Dsk.
$$
\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= Zq[*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 TR= *R*R*=R*Z. The plaintext for the TFHE cryptosystem is the
Z-module T = R*=*Z. Our encoding scheme E*:* Torus has Zqas message space and will be used for
encoding of elements in *R*q= Zq[*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*’* Zqthat identies *q* Z*=*Z *’* Zqas an
N N
isomorphism of Z-modules. Also, T *’* TRbecause 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 = *f*0*;* 1*g*. 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
Esk(*m*): Given sk = *s 2* B and *m 2* Zq, apply the map Zq*’ 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
$$
Dsk(*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 *’* Zqto
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 Dsk.
$$
\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= Zq[*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* = *f*1*;* 2*;:::;p₁* 1*g 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}
$$
$$
pq, 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 1happens. 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= Zq[*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= Zq[*Y*]*=*(*f* (*Y*)) to scalars in Fq.
This requires expensive computations on large degree polynomials in Zq[*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= Zq[*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 Zq[*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 *Rq*with q = *q*ifor
i=0
a chain of moduli *fq₀;:::;q*L*g* 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 in *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* PKF*, and evaluation key* EKF*.*
$$
-(S K,P K)\leftarrow K G e n(1^{\kappa},F)
$$
$$
{\mathsf{P}}{\mathsf{K}}_{F}
$$
$$
{\mathsf{E K}}_{F}
$$
{ ([*x*]*;*VKx) ProbGenPK(*x*) *A randomized problem generation algorithm takes the public key*
PKF*, an input x, and outputs an encoding of x, together with a private verication key* VKx*.*
$$
{\sf{P K}}_{F}
$$
{ [*y*] ComputePK([*x*]) *A deterministic worker computation algorithm takes the evaluation key*
EKF*, 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* VerSK(VKx*;* [*y*]) *A verication algorithm uses the verication key* VKx*, the worker’s output*
[*y*]*, and outputs y 2f*0*;* 1*g [?, 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(VKx*;* [*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* ExptA*dened as* Pr ExptA[*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 VKxdo 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 (VKx*;* [*y*]) that look like the real ones. More formally:
$$
{\sf{V}}{\sf{K}}_{x}
$$
$$
(\mathsf{V}\mathsf{K}_{x},[y])
$$
---
Ver
procedure Game ExptA(VC;F;)
(SK*;*PK) KGen(1*;F*)
for *i* = 1*;:::;‘* = poly() do
*xi* = *A*(PK*;x₁;* [*x₁*]*;:::;xi* 1*;* [*xi* 1])
([*xi*]*;*VK*xi*) ProbGenPK(*xi*)
end for
(*i;*[*y*]) = *A*(PK*;x₁;* [*x₁*]*;:::;x‘;* [*x‘*])
*y* VerSK(VK*xi;* [*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*A*such 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 extractorAwhich outputs coecients *a*isatisfying c = ai*s* with non neglii=0
gible prob*a*bility.
$$
\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 extractorc(resp.c^) for *B*c(resp. *B*c^) which outputs *a₀;:::;a*q*;b₀;:::;b*q(resp.
0q 0q
*a⁰*0*;:::;a;b⁰*0*;:::;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 extractorAfor the Generalized Augmented *q*-PKE assumption, which outputs the
coecients *a*iobtained fromc.
$$
(\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*0*;s*1) for *k 2 f*0*;:::;q;q* + 2*;:::;*2*qg*, and
ib 2q;i6=q+1 ib
receives *f*E(*s*)*g* for challenge bit *b*. *B* now runs the *q*-PDH adversary *A* on *f*E(*s*)*g*. *A*
i=0
q+1
returns *y 2 f*E(*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*i*s* = *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₀* + ais₀ = 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
h*a*ve that *a₀* + *a*i*s₁* = *s₁* will hold only with pro*ba*bility *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*A*such 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* = Fp[*Z*]*;A* = Fp*R*, i.e. the degree-zero polynomials, and *A* = Fp. 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*)*;:::;a*n(*z*)*;a*m n*0*+1(*z*)*;:::a*m(*z*) *is a valid assignment to the input/output variables of C*
*if and only if there exist polynomials a*n+1(*z*)*;:::;a*m n*0* (*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 *R*qused 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*i*2f*0*;* 1*g* 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*k*2 f*0*;* 1*g* such that *a* = 2 ai. Label the input wires as 1*;:::;k* and
i=1
Q
k
the output wire *a*s *k* + 1. Let *t*(*x*) = (*x r*) (*x r*i), where *r;r₁;:::;r*k*2 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 r~a l l~}}i\neq j,
$$
$$
w_{0}(r_{j})=1,w_{j}(r_{j})=-1,w_{i}(r_{j})=0\mathrm{~f o r~a 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*) + *a*k*v*k(*x*)) (*w₀*(*x*) + *a*k*w*k(*x*)) (*y₀*(*x*) + *a*k*y*k(*x*)) is divisible by t(x), then it
P
k i 1
mus*t* be 0 at *r*, and therefore, by the rst set of equations, this gives, *a* = 2 *a*i. The
i=1
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 ma*x*imal 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*j*2f*0*;* 1*g*. 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*L*g* 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}
$$
$$
ii*"* gate, which has a cost of (*d*log *qe*+ *d*log*q*i*e*+ 3) *d* multiplication gates in the underlying
QRP over *R*q, where *R*q= Zq[*Y*]*=*(*f* (*Y*)) and *d* = *deg*(*f* (*Y*)). The cost of the gate can be further
optimized to (*d*log *qe* + *d*log*q*i*e* + 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* = *d*log*q*i*e*. What our QRP will prove is the following: Given *z 2 R*q, expressed as
P P
d 1 ‘ d 1 ‘
*z* = *z*‘*Y;z*‘*2* Zq, 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* Zq(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. *d*log *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 *q*iis 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 (*d*log *qe* + *d*log*q*i*e* + 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)
6
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* = Zm[*Y*]*=*(*f* (*Y*)) is a free module over Zmof rank *d*, i.e. we
d 1
can nd a basis for *R*. Let be a root of *f* (*Y*), we have that *f*1*;;:::; g* is one of such basis. The
d d 1
map : *R !* (Zm), which sends *b* = *b₀* + + *b*d 1to (*b*) = (*b₀;:::;b*d 1) is an isomorphism
of Zm-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), and 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 endomorphismbwhich
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 Zm-
d d
module homomorphismb: (Zm)*!* (Zm). 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*b*2M*d d(Zm). As a side note, in fact, *M*bcan be easily dened from the polynomial *f* (*Y*)
d
used to construct *R ’* (Zm). 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*b*2M*d d(Z) such that *N*b*M*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})
$$
---
| Setup(1$^{\kappa}$,R):$\alpha,\beta,\gamma,\delta\leftarrow R^{*},s\leftarrow A^{*},\left(pk,sk\right)\leftarrow Gen(1^{\kappa})$crs $=\left(pk,\{E(s^{i}\}_{i=0}^{d-1},\{E(\frac{\beta v_{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\gamma})\}_{k\in I_{io}},\{E(\frac{\beta v_{k}(s)+\alpha w_{k}(s)+y_{k}(s)}{\delta})\}_{k\in I_{mid}},\{E(\frac{s^{i}t(s)}{\delta})\}_{i=0}^{d-1})$vk $=\left(sk,crs,s,\alpha,\beta,\gamma,\delta\right)$return(crs,vk) | Verify(vk,u,π)$\pi=(A,B,C)$A $=E(A_{v})$B $=E(B_{w})$,C $=E(C_{y})$$v_{io}(x)=\sum_{i=0}^{\ell}a_{i}v_{i}(x)$$w_{io}(x)=\sum_{i=0}^{\ell}a_{i}w_{i}(x)$$y_{io}(x)=\sum_{i=0}^{\ell}a_{i}y_{i}(x)$$f_{io}=\frac{\beta v_{io}(s)+\alpha w_{io}(s)+y_{io}(s)}{\gamma}$F $=E(f_{io})$Check on encodingsAB $=E(\alpha)E(\beta)+\gamma F+\delta C$i.e.$A_{v}B_{w}=\alpha \beta+\gamma f_{io}+\delta C_{y}$ |
| --- | --- |
| Prove(crs,u,w)$u=(a_{1},\ldots,a_{\ell}),a_{0}=1$w $=(a_{\ell+1},\ldots,a_{m})$v(x) $=\sum_{k=0}^{m}a_{k}v_{k}(x)$$v_{mid}(x)=\sum_{k\in I_{mid}}a_{k}v_{k}(x)$$w(x)=\sum_{k=0}^{m}a_{k}w_{k}(x)$$w_{mid}(x)=\sum_{k\in I_{mid}}a_{k}w_{k}(x)$$y(x)=\sum_{k=0}^{m}a_{k}y_{k}(x)$$y_{mid}(x)=\sum_{k\in I_{mid}}a_{k}y_{k}(x)$$h(x)=\frac{(v(x)w(x)-y(x))}{t(x)}$$f_{mid}=\frac{\beta v_{mid}(s)+\alpha w_{mid}(s)+y_{mid}(s)}{\delta}$A $=E(\alpha+v(s))$B $=E(\beta+w(s))$C $=E(f_{mid}+\frac{t(s)h(s)}{\delta})$return $\pi=(A,B,C)$ | Verify(vk,u,π)$\pi=(A,B,C)$A $=E(A_{v})$B $=E(B_{w})$,C $=E(C_{y})$$v_{io}(x)=\sum_{i=0}^{\ell}a_{i}v_{i}(x)$$w_{io}(x)=\sum_{i=0}^{\ell}a_{i}w_{i}(x)$$y_{io}(x)=\sum_{i=0}^{\ell}a_{i}y_{i}(x)$$f_{io}=\frac{\beta v_{io}(s)+\alpha w_{io}(s)+y_{io}(s)}{\gamma}$F $=E(f_{io})$Check on encodingsAB $=E(\alpha)E(\beta)+\gamma F+\delta C$i.e.$A_{v}B_{w}=\alpha \beta+\gamma f_{io}+\delta C_{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*i*has 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
n
*Proof.* We notice that *f* (*X*) := *X h*(*X*) is an ordinary polynomial of degree 2*nD*. 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*k*g* 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})
$$