# MyOPE: Malicious securitY for Oblivious Polynomial Evaluation
;3;4;4
Malika Izabachene¹, Anca Nitulescu², Paola de Perthuis¹, and David Pointcheval³
1
Cosmian
2
Protocol Labs
3
DIENS, Ecole normale superieure, CNRS, PSL University, Paris, France
4
INRIA, Paris, France
## Abstract.
Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a
sender with a private polynomial and a receiver with a private evaluation point where the receiver
learns the evaluation of the polynomial in their point and no additional information. They are used
in Private Set Intersection (PSI) protocols.
We introduce a scheme for OPE in the presence of malicious senders, enforcing honest sender
behavior and consistency by adding veriability to the calculations. The main tools used are FHE for
input privacy and arguments of knowledge for the veriability property. MyOPE deploys sublinear
communication costs in the sender’s polynomial degree and one to ve rounds of interaction.
In other words, it can be used as a veriable computation scheme for polynomial evaluation over
FHE ciphertexts. While classical techniques in pairing-based settings allow generic succinct proofs
for such evaluations, they require large prime order subgroups which highly impact the communication complexity, and prevent the use of FHE with practical parameters. MyOPE builds on generic
secure encodings techniques that allow composite integers and enable real-world FHE parameters
and even RNS-based optimizations. It is best adapted for the unbalanced setting where the degree
of the polynomial and the computing power of the sender are large.
MyOPE can be used as a building block in specialized two-party protocols such as PSI (this use-
case is hereafter described), oblivious keyword search, set membership and more using the OPE
instantiation.
As another contribution, our techniques are generalized to applications other than OPE, such as
Symmetric Private Information Retrieval (SPIR), to make them secure against a malicious sender.
## 1 Introduction
## 1.1 Oblivious Polynomial Evaluation
*Secure Two-Party Computations (2PC).* Secure two-party computations enable two parties to
mutually run a protocol computing the execution of a function *f* (*;*) on their private inputs
*x;y*, and allowing the parties to learn the output *f* (*x;y*) but nothing else about the inputs.
Seminal results from the 80s, e.g. [Yao86] have shown that with 2PC it is possible to securely
evaluate any boolean circuit. Since these rst feasibility results, a long line of works focused
on improving the eciency of the computational and communication costs in 2PC protocols.
Two approaches were followed in these eorts: (1) improving generic protocols that compute
any boolean or arithmetic circuit and (2) designing tailored protocols for practical functions.
The latter approach focuses on taking advantage of these functions’ particular structure to gain
eciency. Some examples of such 2PC are schemes designed for search problems [HT10,Ver11],
RSA key generation [Gil99], set intersection [JL09,HN12], or polynomial evaluation [NP99].
*Malicious Security of 2PC.* An important aspect to consider when designing 2PC schemes is the
adversarial model. In the *semi-honest* (or passive) adversarial model, a.k.a. honest-but-curious,
the corrupted parties follow the protocol, but try to learn more about the private inputs of other
parties, so there is no impact on the correctness of computation results. On the other hand,
in the *malicious* (active) adversarial model, corrupted parties can collaborate in any way and
misbehave arbitrarily, without following the protocol description. Therefore, assuring not only
the privacy of the inputs, but also the correctness of the outputs (robustness) is essential in
such scenarios. Most often, a 2PC protocol execution preserves the privacy of the inputs against
malicious adversaries. Regarding the correctness of the output, giving consistency guarantees
on the outputs of the honest parties generally comes with big overheads.
---
*Oblivious Polynomial Evaluation.* A particular case of 2PC is Oblivious Polynomial Evaluation,
where the function to be evaluated is a polynomial f(*X*) of xed degree *N* secretly chosen by
the sender. The receiver chooses the secret evaluation point m. After running OPE, the receiver
obtains the value f(m) without learning anything else about the polynomial f and without giving
the sender any information about the point m.
OPE is an important building block for various 2PC schemes that generally require multiple executions of an OPE protocol for the same polynomial and dierent evaluation points.
However, the standard denition of receiver privacy does not preclude the sender from cheating by using a polynomial of higher degree than expected or changing the polynomial between
multiple executions. Therefore, extending the security to malicious senders is essential for such
applications.
Unfortunately, when relying on general 2PC protocols to securely perform the OPE functionality in the malicious setting, some eciency overheads incur: schemes for Boolean circuits
apply the cut-and-choose technique which requires repeating the computation *K* times in order
K
to prevent cheating except with probability 2, while 2PC schemes for arithmetic circuits run
an expensive preprocessing model to generate correlated randomness.
## 1.2 Motivation: Applications of OPE
The rst custom OPE protocol was dened and introduced in [NP99] and is secure only against
passive adversaries. While few constructions were built since, the OPE functionality can lead
to various interesting applications such as data mining [LP00], private set intersection (PSI)
(in their original paper [NP99], Naor and Pinkas mention the contact discovery use-case),
privacy-preserving keyword search [JL09], set membership (related to PSI), and RSA key generation [Gil99].
*Private Set Intersection.* Private Set Intersection (PSI) is a well-studied specialized form of 2PC
that allows two parties to jointly compute the intersection of their input sets, without revealing
any other information about them (other than upper bounds on their sizes). Although protocols
for PSI have been built upon generic 2PC, more ecient custom protocols can be achieved by
taking advantage of the problem’s structure.
A recent line of works reduces interactions in *unbalanced* PSI schemes by using (Leveled)
Fully Homomorphic Encryption (FHE) as a tool [CLR17,CHLR18]. In an unbalanced PSI protocol the sender has a set of much larger size than the receiver, and also bigger storage and
computational power. While [CLR17] achieves few rounds of interaction, it is secure only against
passive adversaries. The follow-up work [CHLR18] extends the security to consider malicious
receivers. This is done at the cost of an expensive preprocessing phase with a linear number
of interactive rounds in the receiver’s set size, and does not address the more relevant case of
malicious senders.
The real challenge in PSI is enforcing that the sender performs the correct computation. In
the schemes mentioned above, the sender can deviate from the prescribed protocol and make
the receiver compute an arbitrary intersection. Since the sender obtains a homomorphically
encrypted copy of the receiver’s set, they could compute other circuits than the pre-established
one. Therefore, if the protocol returns the intersection result to the sender, then not only the
result but also the receiver’s privacy are compromised. For example, in FHE-based PSI schemes,
it is possible for the sender to force the receiver to output their full set as the result of an
intersection.
In [CHLR18] the authors heuristically argue that the misbehavior of a *malicious sender* can
be mitigated by using a complex hash function *H* that the sender is unable to evaluate for an
encrypted input *y*. Given the fast-paced advancements made by FHE schemes in recent years,
there is no guarantee that a higher degree polynomial could not be evaluated and such a PSI
system is insecure when one considers malicious senders. We address these limitations and show
an alternative way to build unbalanced PSI with *malicious senders*.
---
## 1.3 Related Work
Despite its broad applicability, the study of the OPE functionality includes only few practical
and secure protocols, initiated in [NP99] and further continued in works like [CL01,ZB05,HL09].
While [NP99] proposed the rst construction for OPE, it relies on a newly introduced intractability assumption: the noisy polynomial interpolation. Naor and Pinkas conjectured that it
could be reduced to a more widely studied assumption, the polynomial reconstruction problem.
Nevertheless, as shown in [BN00], this conjecture seems not to hold in general.
*OPE Schemes with Active Security.* Among recent OPE schemes, to the best of our knowledge,
the only ones secure against malicious attacks are [HL09,Haz18]. However [HL09] has at least 17
rounds of interaction and the parties send each other *O*(*N*) Paillier encryptions, where is the
security parameter and *N* the degree of the polynomial. Also, their claimed eciency holds only
for suciently low degree polynomials. [GNN17] has active security too, but communication is
also linear in *N*.
[Haz18] shows an OPE scheme for polynomial evaluation in the exponent of a DLog group
using algebraic Pseudo-Random Functions (PRF). They focus on improving the computational
eciency of [HL09] by reducing the number of modular exponentiations, and removing the
trusted setup requirement, while preserving the same number of rounds of interaction and
communication complexity as in [HL09], and apply their scheme to private set membership
2PC.
[PRTY20] gives malicious security for PSI with symmetric set sizes a bit smaller than ours,
but the communication is linear and with concrete parameters it is about the same order as our
20
for sets of size 2.
*Veriable Computation (VC).* Introduced by [GGP10], VC schemes are cryptographic systems that enable checking the integrity of results from delegated computations. More recent
works [FNP20,BCFK20] have improved the eciency and the expressivity of VC schemes to
work for computations over encrypted data. These schemes, however, require proving the entire
FHE circuit evaluation which is very expensive. Moreover, they neither allow using practical
parameters for the FHE scheme, nor speedups through classical optimisations such as Residue
Number System (RNS).
*Polynomial Commitments (PC).* First introduced by [KZG10], PCs are commitments for polynomials of maximal degree *N* and coecients in a eld F that support an interactive argument
of knowledge to prove the correct evaluation of a committed secret polynomial in a given point.
However, while this ensures veriability of the evaluation result, it does not protect the privacy
of the evaluation point.
*Private Information Retrieval (PIR) Using Somewhat Homomorphic Encryption (SwHE).* A
long line of PIR articles such as introduced in [TP11] uses Somewhat Homomorphic Encryption
with ciphertexts of zero or one multiplied with elements of the sender’s database, added up and
sent back to the receiver. However, communication is linear in the size of the sender’s set, and
there is no veriability.
## 1.4 Our Contribution
In this work, we study the Oblivious Polynomial Evaluation (OPE) functionality in the malicious
setting and show an application to Private Set Intersection (PSI): the untrusted sender is asked
to commit an input polynomial and prove consistency of the evaluation with respect to the
initial commitment.
More precisely, we introduce MyOPE, a scheme for oblivious evaluation of polynomials of
=d
high degree *N* that achieves *O*(*N¹*) communication costs, where *d* can be freely chosen and
optimized with respect to the ciphertext sizes. This sublinear communication improves on the
state-of-the-art. Concretely, in order to avoid malicious attacks, we enforce honest behavior of
the sender (the evaluator) by asking an extra proof for the claimed result of the evaluation with
$$
\mathcal{O}(N^{1/d})
$$ respect to some committed polynomial. This is of main importance when OPE is used in PSI,
where the same or related polynomials have to be evaluated on distinct inputs. MyOPE is best
adapted for large degree polynomials in the unbalanced setting with computationally powerful
20 40
senders. In our experiments we consider polynomials with degrees *N* from 2 to 2.
$$
2^{20}
$$
MyOPE can be seen as a Veriable Computation over encrypted data, in the following
sense: the sender provides a proof of their honest behavior during the homomorphic polynomial
evaluation, to convince the receiver.
$$
2^{40}
$$
*Our Techniques.* In a nutshell, MyOPE uses FHE to encrypt the receiver’s input m under their
key, so that the sender can proceed with the homomorphic evaluation over the ciphertext c to
obtain an encryption of f(m) that the receiver can thereafter decrypt. For ecient veriability,
we also need a commitment *C*fof f(*X*) that is compatible with the FHE. At this point we
remark that the sender needs to perform an expensive evaluation over the FHE ciphertext c with
a multiplicative depth corresponding to the logarithm of the degree of their polynomial f(*X*).
Practical FHE schemes may still not be ecient enough for this when the degree of f(*X*) is large.
To overcome this, we can nd the best trade-o between communication and computational
=d
costs, depending on the polynomial degree *N*. Namely, the receiver will send *O*(*N¹*) encrypted
powers of m for some carefully chosen *d*. Then the sender will homomorphically compute the
i
ciphertexts ciof the remaining powers m of m in order to evaluate a ciphertext of f(m) by a
simple inner product with the vector of the coecients. The computation of the ciphertexts ci
will require an only *d* multiplicative-depth for the FHE circuit.
$$
C_{\mathbf f}
$$
$$
\mathcal{O}(N^{1/d})
$$
$$
m{}^{i}
$$
$$
c_{i}
$$
$$
c_{i}
$$
At this step, a malicious sender could just use arbitrary values ciinstead. Our scheme
MyOPE requires the prover/sender to (compactly) commit the vector of ciphertexts (ci)iand
prove it indeed coincides with the correct values. To check this, the receiver asks for a random
linear combination of the ci’s. Since the vector (ci)iis committed before seeing the random
challenge, the sender has negligible probability to compute the expected value if the committed
values are incorrect.
$$
c_{i}
$$
$$
(\mathsf{c}_{i})_{i}
$$
$$
\mathrm {c} _ {i} ^ {\prime} \mathrm {s}
$$
$$
(\mathtt{c}_{i})_{i}
$$
The core argument used in this step enables checking that an inner product between a
committed vector of ciphertexts and a public vector (here a random challenge chosen by the
receiver) has an expected value when decrypted (value unknown to the prover). Similarly, for
the nal step, the sender has to convince the receiver that the inner product between the vector
of the ciphertexts ci’s committed at the previous step and the initial polynomial commitment
*C*fwas performed correctly.
$$
\ {{\bf{}}_{i}}^{\ \ }
$$
$$
C_{\mathbf{f}}
$$
While FHE will protect receiver’s privacy (the message m), some additional noise will be
added by the sender to the nal ciphertext to let the receiver learn f(m) but nothing else about
f. The sender will also give guarantees about the added noise.
*Applications.* The MyOPE checks are useful when we furthermore need to ensure consistency
between repetitions. In the context of PSI, in order to determine the intersection of the sets *X* =
*fx₁;:::;x*N*g* owned by the prover and Y = fy₁*;:::;y*K*g* owned by the verier, the sender/prover
Q
N
generates the polynomial f = (*X x*i), commits it, and the receiver will learn whether
i=1
f(*y*j) = 0 for each of their *y*j’s, but nothing else, by multiple evaluations of the same polynomial
on multiple inputs. To check whether the evaluations are equal to zero or not, the sender
rst commits f in *C*fand to avoid information leakage, the polynomial is randomized by a
multiplication factor at each evaluation. After the initial commitment *C*f, the sender/prover
draws a random invertible coecient r for each evaluation in a specic point *x*, commits r f and
proves it is f multiplied with a secret r using the zero-knowledge quadratic check from Section
3. MyOPE is then used to evaluate r f(*x*), which is equal to zero i f(*x*) = 0.
$$
\{x_{1},\ldots,x_{N}\}
$$
$$
\ {mathcal X=}
$$
$$
\mathcal{Y}=\left\{y_{1},\ldots,y_{K}\right\}
$$
$$
\textstyle{\mathsf{f}}=\prod_{i=1}^{N}(X-x_{i})
$$
$$
\mathsf{f}(y_{j})=0
$$
$$
{_y^{{}prime}\mathrm{S}}
$$
$$
C_{\mathbf f}
$$
$$
^\mathrm{f}
$$
$$
C_{\mathrm f}
$$
$$
{\mathcal{X}}.
$$
$$
{\mathsf{f}}(x)=0
$$
$$
\ {mathfrak r\cdot mathsf f}x!
$$
*Extensions.* We believe that our techniques for lifting OPE from passive security to malicious
sender security are generic and of independent interest. The main tool is a proven inner-product
that can be applied to lift other 2PC computation protocols to the malicious setting. We illustrate such an extension in the case of Symmetric Private Information Retrieval (SPIR). SPIR schemes allow a receiver to ask for a secret index of a data in the sender’s set, and the receiver
then only learns this sole data. Our augmented SPIR protocol allows a receiver to recover the
*i*-th eld of a private database owned by the sender, without leaking the index *i*, even against
a malicious sender, once the database has been compactly committed.
*Eciency in Practice.* When using the Fan-Vercauteren FHE scheme [FV12], from the plaintext
n
ring Zt[*X*]*=*r(*X*), where r(*X*) = *X* +1, into the ciphertext ring Zq[*X*]*=*r(*X*), the core parameters
are the integers *n;q*, and *t*. In order to understand various parameter choices, we provide some
rough cost estimates for the FHE: each ciphertext is 2*n*log*q* bits long, and the underlying
30
plaintexts *n*log*t* bits long. With a MyOPE instantiation for polynomials of degree *N* = 2, we
15
set *n* = 2 and use *t* on 56 bits and *q* on 839 bits, to obtain appropriate semantic security for
the FHE and decryption correctness. Then, the size of the FHE ciphertexts to be sent is a bit
more than 1 GByte. Our proof of the sender’s honest behavior has less than 25 MByte size for
30 80
a soundness of 2, with 5 rounds. The non-interactive proof with a soundness in 2 requires
less than 100 MBytes.
$$
\mathbb{Z}_{t}[X]/\mathsf{r}(X)
$$
$$
{\mathsf{r}}(X)=X^{n}{+}1
$$
$$
{\mathbb{Z}}_{q}[X]/{\mathfrak{r}}(X)
$$
$$
n,q.
$$
$$
2n
$$
$$
N=2^{30}
$$
$$
n=2^{15}
$$
$$
q
$$
$$
2^{-30}
$$
$$
2^{-80}
$$
## 2 Preliminaries
## 2.1 OPE: Oblivious Polynomial Evaluation
To dene an OPE protocol as a two party protocol run between a receiver and a sender over a
ring R, we rst agree on the input and output:
$$
\mathsf\{X{}\\ in\\mathsf{R}
$$
Input: Receiver { an input x *2* R, Sender { a polynomial f(*X*) *2* R[*X*].
$$
\mathsf{f}(X)\in\mathsf{R}[X]
$$
Output: Receiver { f(x), Sender { nothing.
$$
-sf f x
$$
We consider the simplied setting where the sender gets no output. Such a protocol should
satisfy correctness, sender privacy and receiver privacy, which are rst dened in the honestbut-curious setting. Thereafter, we will deal with malicious senders. Privacy notions can be
formulated as indistinguishability games:
Denition 1(Sender Privacy with an Honest-but-Curious Receiver). *For any* PPT
*adversary A executing honestly the receiver’s part on input* x*, for any* f 6= f⁰ *2* R[*X*]*, such that*
f(x) = f⁰(x)*, the views that A sees in case the sender’s input is* f *and in case the sender’s input*
*is* f⁰ *are computationally indistinguishable.*
$$
f \neq f ^ {\prime} \in R [ X ]
$$
$$
\mathbf{X},
$$
$$
f (x) = f ^ {\prime} (x)
$$
Denition 2(Receiver Privacy with an Honest-but-Curious Sender). *For any* PPT
*adversary A executing honestly the sender’s part, for any* x 6= x⁰ *2* R*, the views that A sees in*
*case the receiver’s input is* x *and in case the receiver’s input is* x⁰ *are computationally indistin-*
*guishable.*
$$
x^{\prime}
$$
*Malicious Sender Security.* To get receiver privacy and correctness even in the case of a malicious
sender, one usually enforces honest sender behavior: the sender rst commits the polynomial
f(*X*) and then proves the answers are consistent with that initial commitment.
## 2.2 FHE: Fully Homomorphic Encryption
Fully homomorphic encryption has been introduced in [Gen09]. Since the initial construction,
major improvements have been made, with now practical and ecient solutions. In this work
we will use the Fan-Vercauteren FHE scheme [FV12].
The Fan-Vercauteren FHE. One usually denotes *R*t= Zt[*X*]*=*r(*X*) the plaintext message
space and *R*q= Zq[*X*]*=*r(*X*) the ciphertext space.
$$
\mathcal{R}_{t}=\mathbb{Z}_{t}[X]/\mathsf{r}(X)
$$
$$
\mathcal{R}_{q}=\mathbb{Z}_{q}[X]/{\mathsf{r}}(X)
$$
The FV encryption scheme [FV12] is described by parameters = (*q;t;*), with *q;N 2* N
such that 0 < < 1, where the size of q and noise parameter depend on several constraints,
and namely the expected multiplicative depth for the correctness and the security of the Ring-
LWE problem for the semantic security.
$$
\varGamma=(q,t,\sigma)
$$
$$
q,N\in\mathbb{N}
$$
$$
0<\sigma<1
$$
$$
\sigma
$$
$$
q
$$
For eciency reasons, with the possibility of using FHE with RNS [BEHZ16], we will assume
Q
‘
*q* = *p*ifor prime factors *t* = *p₁ ::: p*‘. We additionally take *t* such that *tjq*. We denote
i=1
$$
\textstyle q=\prod_{i=1}^{\ell}p_{i}
$$
$$
t=p_{1}\leq\ldots\leq p_{\ell}
$$
$$
t | q
$$
---
= *q=t* and the Gaussian distribution on Z with standard deviation. The FV encryption
scheme [FV12] consists in the following algorithms:
$$
\varDelta=q/t
$$
$$
\sigma
$$
KG(1*;*)*!* (sk*;*pk): On input the security parameter and the eciency parameters, sample a*;* s *R*qand set (p*;*p⁰) = ( (a s + e)*;*a) *2 R²*q. sk = s is the secret key, where the
coecients of e are taken from. The public key pk contains (p*;*p⁰) with a relinearization
key rlk.
$$
{\mathsf{K G}}(1^{\lambda},\ \ Gamma)\to({\mathsf{s k}},{\mathsf{p k}})
$$
$$
\mathsf{a},\mathsf{s}\gets\mathcal{R}_{q}
$$
$$
(\mathsf{p},\mathsf{p}^{\prime})\,=\,(-(\mathsf{a}\,\cdot\,\mathsf{s}+\,\mathsf{e}),\,\mathsf{a})\,\in\,\mathcal{R}_{q}^{2}.\,\,\mathsf{s k}\,=
$$
$$
(\mathsf{p},\mathsf{p}^{\prime})
$$
Enc(pk*;*m)*!* (c*;*c⁰): Using (p*;*p⁰) from pk and a message m *2R*t, compute ciphertext (c*;*c⁰) =
(p u + e₁ + m mod *q;* p⁰ u + e₂ mod *q*)*;* with coecients of u*;*e₁*;*e₂ also taken from.
Dec(sk*;*(c*;*c⁰))*!* m: Given sk = s, compute
$$
(\mathsf{p k},\mathsf{m})\to(\mathsf{c},\mathsf{c}^{\prime})
$$
$$
({\mathsf{p}},{\mathsf{p}}^{\prime})
$$
$$
\mathsf{m}\in\mathcal{R}_{t}.
$$
$$
({\mathsf{c}},{\mathsf{c}}^{\prime})=
$$
$$
(\mathrm {p} \cdot \mathrm {u} + \mathrm {e} _ {1} + \Delta)
$$
$$
q, \mathsf {p} ^ {\prime} \cdot \mathsf {u} + \mathsf {e} _ {2} \bmod q)
$$
$$
\mathsf{u},\mathsf{e}_{1},\mathsf{e}_{2}
$$
$$
\mathsf{D e c}(\mathsf{s k},(\mathsf{c},\mathsf{c}^{\prime}))\to
$$
$$
\mathsf{d}=\mathsf{c}+\mathsf{c}^{\prime}\cdot\mathsf{s}=\varDelta\cdot\mathsf{m}-\mathsf{e}\cdot\mathsf{u}+\mathsf{e}_{2}\cdot\mathsf{s}+\mathsf{e}_{1}=\varDelta\cdot\mathsf{m}+\mathsf{v}\bmod q
$$
$$
\mathrm {m} ^ {\prime} = \left\lfloor \mathrm {d} / \Delta \right\rceil = \left\lfloor (\Delta \cdot \mathrm {m} + \mathrm {v}) / \Delta \right\rceil = \mathrm {m} + \left\lfloor \mathrm {v} / \Delta \right\rceil \bmod t
$$
where v = e u + e₂ s + e₁ is the error term: m⁰ = m if *k*v*k₁ =*2.
$$
v = - e \cdot u + e _ {2} \cdot s + e _ {1}
$$
$$
\ {\mathfrak{m}}^{\prime}={\mathfrak{m}}
$$
0i 0f
Eval(pk*;f;* (ci*;* c)i=1;:::;‘)*!* (cf*;* c): Given p*k*, an arithmetic circuit *f* with bounded multiplica-
0i 0f
tive depth and *‘* ciphertexts (ci*;* c)i*=*1;:::;‘output the ciphertext (cf*;* c).
$$
\|\ {mathsf v\\}|{}_{\infty}\leq\varDelta/2{}.
$$
$$
\mathsf{E v a l}(\mathsf{p k},f,(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime})_{i=1,\dots,\ell})\to(\mathsf{c}_{f},\mathsf{c}_{f}^{\prime})
$$
The addition of two ciphertexts is a ciphertext of the sum of the plaintexts. Multiplicative operations have also been shown possible with additional information to relinearize the ciphertext
0f
after a product using rlk. For Eval to be correct, Dec(sk*;*(cf*;* c)) should return *f* (*m₁;:::;m‘*)
0i
where Dec(sk*;*(ci*;* c)) = *m*ifor *i* = 1*;:::;‘*, with overwhelming probability. More detail on the
FV parameters is provided in AppendixE.
$$
(\mathsf{c}_{f},\mathsf{c}_{f}^{\prime})
$$
$$
(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime})_{i=1,\ldots,\ell}
$$
$$
\mathsf{D e c}(\mathsf{s k},(\mathsf{c}_{f},\mathsf{c}_{f}^{\prime}))
$$
$$
f(m_{1},\ldots,m_{\ell})
$$
$$
\left(\mathsf{s k},\left(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime}\right)\right)=m_{i}
$$
$$
i=1,\ldots,\ell
$$
*Remarks.* We stress that for veriable computations, the evaluator will have to provide proofs
of correct operations on the ciphertexts (c*;*c⁰) *2R²*q. We will thus have to deal with polynomials
over rings (and not elds).
$$
(\mathsf{c},\mathsf{c}^{\prime})\in\mathcal{R}_{q}^{2}
$$
Since the verier can decrypt, we also need to require circuit privacy [SYY99]. This ensures
the nal ciphertext reveals no information about f. Indeed, not only is the encrypted input
impacted by executing f, but also the noise, which might thus leak information about the
function f. While several approaches have been proposed to avoid such leakage, we will apply
the *noise-ooding* proposed by Gentry, which consists in adding a larger random noise to the
nal result. This will then make the nal noise independent of f.
## 2.3 SNARKs: Succinct Non-Interactive Arguments of Knowledge
Zero-knowledge proofs/arguments are cryptographic protocols between two parties, a prover
Prove and a verier Ver, in which the prover can convince the verier about the validity of a
statement without leaking any extra information beyond the statement validity. SNARKs are
non-interactive such protocols with a proof size independent of the size of the statement to be
proven.
+
Bitansky *et al.* [BCI 13] provide an abstract model to build SNARKs 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 computing only linear combinations of their
inputs. These proofs can then be transformed into SNARKs by means of extractable linear-only
encoding schemes that will restrict the prover to linear-only operations. Our techniques are
similar and use generic linear-only encodings adapted for FHE ciphertexts.
Formal denitions of SNARKs and zk-SNARKs are given in AppendixA.
## 2.4 Secure Encoding Schemes over Rings
As stressed above, we will have to consider polynomials over rings. So we revisit the linear
+
encodings dened in [BCI 13,GGPR13] in order to deal with rings.
Denition 3(Encoding Scheme). *An encoding scheme over a ring* R *consists in a tuple of*
*algorithms* (Gen*;*E)*.*
---
{ (pk*;*sk*;*vk) Gen(1 )*, a key generation algorithm that takes as input a security parameter*
*and outputs public information* pk*, a secret key* sk*, and a verication key* vk*, that can be*
*either public or private;*
$$
-(p k p,k,y k)\leftarrow G\ n(1^{\lambda})
$$
{ *E* Esk(*a*)*, a (probabilistic) encoding algorithm mapping a ring element a 2* R *in the*
*encoding space E, using the secret key* sk*.*
$$
E\,\leftarrow\,\mathsf{E}_{\mathsf{s k}}(a)
$$
$$
a\;\in\;\mathsf{R}
$$
Properties. An encoding scheme should satisfy the following properties, with ecient and
correct algorithms:
{ *L*-Linearly homomorphic: An algorithm Evalpk(*E₁;:::;E*L;*c₁;:::;c*L), on input public information pk, encodings *E₁* = Esk(*a₁*), . . . , *E*L= Esk(*a*L), and coecients *c₁;:::;c*L*2* R,
P
L
outputs an encoding of *c*i*a*i;
i=1
$$
\ \mathsf{E v a l}_{\mathfrak p k k}(E_{1},\ldots,E_{L};c_{1},\ldots,c_{L})
$$
$$
E _ {1} = \mathrm {E} _ {\mathrm {s k}} \left(a _ {1}\right), \dots , E _ {L} = \mathrm {E} _ {\mathrm {s k}} \left(a _ {L}\right)
$$
$$
c_{1},\ldots,c_{L}\in\mathsf{R}.
$$
$$
\textstyle{\sum_{i=1}^{L}c_{i}\cdot a_{i}};
$$
{ *L*-Quadratic root verication: An algorithm QCheckvk(*Q;E₁;:::;E*L), on input the verication key vk, a quadratic polynomial *Q 2* R[*X₁;:::;X*L] and encodings *E₁* = Esk(*a₁*), . . . ,
*E*L= Esk(*a*L), checks whether or not the relation *Q*(*a₁;:::;a*L) = 0 is satised in R;
$$
\ h e c\!\\!\\!\\_\ \ \ \\
$$
$$
Q\in\mathsf{R}[X_{1},\ldots,X_{L}]
$$
$$
E_{L}=\mathsf{E}_{\mathsf{s k}}(a_{L})
$$
$$
E _ {1} = \mathrm {E} _ {\mathrm {s k}} \left(a _ {1}\right), \dots ,
$$
$$
Q(a_{1},\ldots,a_{L})=0
$$
{ Image verication: An algorithm Verifyvk(*E*), on input the verication key vk and an element
*E*, veries *E* is an actual encoding of some element in R: this algorithm not only veries
that *E 2E*, but also that there exists an element *a 2* R such that *E* can be an encoding of
*a*.
$$
\mathsf{V e r i f y}_{\mathsf{v k}}(E)
$$
$$
a\in\mathsf{R}
$$
$$
E\in{\mathcal{E}}
$$
According to the verication key that can be either public or private, the verication processes
will be either public or private.
Secure Encodings. We now formally dene the soundness properties for the above verication
algorithms, in terms of knowledge-soundness:
Denition 4(Linear-Only Extractability). *An encoding scheme* (Gen*;*E) *over* R *is ex-*
*tractable if for any* PPT *adversary A, there exists a* PPT *extractor* ExtA*such that the following*
*probability is negligible in the security parameter:*
"! #
$$
\mathsf{E x t}_{\mathcal{A}}
$$
$$
\operatorname*{P r}\left[\mathsf{Q C h e c k}_{\mathsf{v k}}\left(X-\sum_{i=1}^{n}c_{i}X_{i},E,E_{1},\ldots,E_{n}\right)=\mathsf{f a l s e}\left|\mathsf{V e r i f f}_{\mathsf{v k}}(E)=\mathsf{t r u e}\right]\right.
$$
$
*on the probability space* (pk*;*sk*;*vk) Gen(1 )*, a₁;:::;a*nR*, E*iEsk(*a*i)*, for i* = 1*;:::;n,*
*and* (*E*;*c₁;:::;c*n) (*Ajj*ExtA)(pk*;* (*E*i)i)*.*
$$
(\mathrm {p k}, \mathrm {s k}, \mathrm {v k}) \leftarrow \operatorname {G e n} \left(1 ^ {\lambda}\right), a _ {1}, \dots , a _ {n} \leftarrow^ {\$} \mathrm {R}, E _ {i} \leftarrow \mathrm {E} _ {\mathrm {s k}} \left(a _ {i}\right), f o r i = 1, \dots , n
$$
$$
(E;c_{1},\ldots,c_{n})\leftarrow(\mathcal{A}||\mathsf{E x t}_{\mathcal{A}})(\mathsf{p k},(E_{i})_{i})
$$
While the encoding is linearly-homomorphic, the above extractability property requires that
it be impossible to derive new valid encodings excepted by linear combinations: any new valid
P
encoding *E* of some *a 2* R will necessarily satisfy *a* = *c*i*a*i, for extractable elements *c*i*2*
i
R. Intuitively, when an encoding *E* passes the verication test, one can extract the linear
combination of the given initial encodings.
$$
a\in\mathsf{R}
$$
$$
\textstyle a\,=\,\sum_{i}c_{i}a_{i}
$$
$$
\ {c_{i}\ \in\ }\ {}
$$
Zero-Knowledge Proofs. The above properties will be enough for a binding commitment,
but additional blinding factors in an appropriate masking set *M* will be required for hiding
commitments, which will depend on the ring R (see below for the particular case of R = Zq).
Then, Zero-Knowledge proofs will be needed for Quadratic root verications with private linear
0
combinations: ZKLQCheckvk(*Q;E₁;:::;E*L;*E₁;:::;E⁰*), on input a quadratic polynomial *Q 2*
0
R[*X₁;:::;X*L] and encodings *E₁* = Esk(*a₁*), . . . , *E*L= Esk(*a*L), *E₁* = Esk(*b₁*), . . . , *E⁰* = Esk(*b*).
The verication key vk on the verier side and the private coecients c₁*;:::;c* on the prover
P
side prove that the relation *Q*(*a₁;:::;a*L) = *c*i*b*iis satised. The *c*i’s will be the blinding
factors in *M*.
$$
\mathsf{R}=\mathbb{Z}_{q})
$$
$$
\mathsf{R}[X_{1},\ldots,X_{L}]
$$
$$
Q\in
$$
$$
\mathsf{Z}\mathsf{K L}\mathsf{Q}\mathsf{C}\mathsf{h}e cmathsf{\mathsf{k}}_{\mathsf{v k}}(Q,E_{1},\ldots,E_{L};E_{1}^{\prime},\ldots,E_{\mu}^{\prime})
$$
$$
E_{\mathbf{1}}=\mathsf{E_{s k}}(a_{1}),\:\ldots,\:E_{L}=\mathsf{E_{s k}}(a_{L}),\:E_{1}^{\prime}=\mathsf{E_{s k}}(b_{1}),\:\ldots,\:E_{\mu}^{\prime}=\mathsf{E_{s k}}(b_{\mu})
$$
$$
c_{1},\ldots,c_{\mu}
$$
$$
Q(a_{1},\ldots,a_{L})=\sum c_{i}\cdot b_{i}
$$
$$
c_{i}^{\ ?}
$$
Paillier-Based Secure Encodings. In AppendixB, we recall some constructions from pairingbased techniques (with public verication key vk) and from the linearly-homomorphic Paillier
encryption scheme [Pai99] (with private verication key vk), as already explained in [GGPR13].
As we will hereafter exploit it, we just recall the latter:
---
{ (pk*;*sk*;*vk) Gen(1 ): Run Paillier key generation KG*!* (sk*;*pk = *N*), where *N* is an RSA
$
modulus and set vk = (sk*;* Z).
*N*
$$
-(p k p k,k k)\leftarrow\mathsf{G e n}(1^{\lambda})
$$
x
{ (Enc(*a*)*;*Enc( *a*)) Esk(*a*): A Paillier ciphertext of a scalar *x 2* ZNis *E* = (1 + *N*)
N 2$
*r* mod *N*, for some random *r* Z. An encoding is thus 4 log*N* bit-long.
N
$$
{\mathsf{K G}}\to({\mathsf{s k}},{\mathsf{p k}}=N)
$$
$$
\mathbf {k} = \left(\mathrm {s k}, \alpha \leftarrow^ {\$} \mathbb {Z} _ {\mathcal {N}} ^ {*}\right)
$$
$$
-(nmathsf(n),\mathsf{E n c}(a\cdot a))\leftarrow\mathsf{E}_{\mathsf{S h}}(a)
$$
$$
x\in\mathbb{Z}_{\mathcal{N}}
$$
$$
r^{\mathcal{M}}
$$
$$
E=(1+\ \ \mathcal{N})^{x}
$$
$$
\mathcal {N} ^ {2}
$$
$$
r\xleftarrow{\S}\mathbb{Z}_{\mathcal{N}}^{*}
$$
This is an additively-homomorphic encryption scheme over ZN, but in order to get the *L*-
linear homomorphism over Zq, we will need *N > Lq²*. The linear-only extractability is reasonable
to assume, as this scheme is not known to be multiplicatively homomorphic when *N* is hard to
factor. Hence, for a quadratic check, the verier decrypts the ciphertexts modulo *N*, which is
the value in N, and one can then check the quadratic relation in Zqon the cleartexts.
$$
\mathbb{Z}_{N}
$$
$$
\mathbb{Z}_{q}
$$
$$
\mathcal{N}>L q\^{2}
$$
$$
\mathbb{Z}_{q}
$$
We stress that for our commitments to be hiding, we will need to add random masks to the
plaintexts: a random integer in *M* = [[0; 2 *Lq²*]], for a security parameter, will statistically
hide the plaintext *x*. More details are provided in AppendixB. For correct decryption and for
the soundness of the ZKLQCheck proofs on secret scalars, we will need *N >* 2*L* 2 *q³*. As
+3
will never be larger than 4, we will need *N > L* 2 *q³*.
$$
\mathcal{M}=[0;2^{\lambda}L q^{2}]
$$
$$
\mu
$$
$$
\mathcal{N}>L\cdot2^{\lambda+3}q^{3}
$$
$$
\ {mathcal N}>2\mu L cdot^{{\lambda}}q^{3}
$$
$$
\mu
$$
For our concrete instantiations, in Section5, we take *N* between 2560 and 3072 bits, which
for an RSA modulus is consistent with a security parameter between 80 and 128.
## 3 Commitments
A major contribution of this paper is the construction of commitments of multivariate polynomials over rings so that succinct proofs can later be described. This is in the same vein as
in [FNP20], but the latter is only dened for secure encodings based in pairings, whereas we
describe here the construction from any security encodings. While not publicly veriable anymore, this will be useful to build compact commitments of polynomials over Zq, where *q* may
contain small prime factors (but still larger than the degree of the polynomials), for a designated verier. These commitments may not hide the polynomials but just guarantee the binding
property, with a unique opening. We thereafter show how to also make them hiding, so that
no information leaks about the committed polynomials (when needed), with zero-knowledge
arguments for the relations the polynomials may satisfy, for a designated verier.
$$
\mathbb{Z}_{q};
$$
## 3.1 Binding Commitments
Because of the linear-only combinations, one can limit encodings in sub-spaces. As we can
also do quadratic verications, we will be able to check products of two polynomials. From an
encoding scheme (Gen*;*E) over a ring R, we can dene a compact binding commitment scheme
over multivariate polynomials. More precisely, such commitment schemes will be dened by 4
algorithms:
{ Setup(1*; R;*(*R*)) generates the public key pk and the verication key vk, according to the
polynomial space *R*, and the authorized subspaces (*R*);
$$
-\ {\mathsf S e t u p}(1^{\lambda},{\mathcal R},({\mathcal R}_{\pi})_{\pi})
$$
$$
\mathcal{R}
$$
$$
(\mathcal{R}_{\pi})_{\pi}
$$
{ Commitpk(u*; R*), for a polynomial u *2R R*, outputs a commitment *C* of u;
$$
\mathsf{C o m m i t}_{\mathsf{p k}}(\mathsf{u},\mathcal{R}_{\pi})
$$
$$
\mathsf{u}\in\mathcal{R}_{\pi}\subseteq\mathcal{R}
$$
$$
U
$$
{ Validityvk(*C; R*), for a commitment *C*, veries whether this is a valid commitment for an
(unknown) polynomial u in the appropriate subspace *R*;
$$
\mathsf{V a l i d i t y}_{\mathsf{v k}}(C,\mathcal{R}_{\pi})
$$
$$
\mathcal{R}_{\pi}
$$
{ Quadraticvk(*Q;C₁;:::;C*‘), for valid commitments *C*iof (unknown) polynomials uiand a
quadratic polynomial *Q* in *‘* variables, veries whether *Q*(u₁*;:::;*u‘) = 0 in *R*.
$$
-\Omega_{\alpha}a a d a t i c_{\alpha}(Q,C_{1},\ldots,C_{\ell})
$$
$$
C_{i}
$$
$$
\ {boldsymbol u_{{i}}}
$$
For the above denition to make sense, for any adversary *A*, there exists an extractor ExtAsuch
that for any valid commitment *C* generated by *A*, ExtAoutputs the committed polynomial
u *2R*.
$$
Q(\ {\mathsf u}_{1},\ldots,{\mathsf u}_{\ell})=0
$$
$$
\mathcal{R}
$$
$$
\mathsf{E x t_{A}}
$$
$$
\mathcal{A},\,\mathsf{E x t}_{\mathcal{A}}
$$
$$
\mathsf{u}\in\mathcal{R}_{\pi}
$$
While *R* will usually be a global ring of polynomials, such as R[*X*] or R[*X;Y*], the sub-spaces
n 1 N n 1 N
*R* will only be the module generated by a limited basis, R[*X*], R[*Y*], or R[*X;Y*], where
the explicit exponents limit the degrees.
$$
{\mathsf{R}}[X]
$$
$$
\mathcal{R}_{\pi}
$$
$$
\mathsf{R}|X,Y|
$$
$$
\mathsf{R}[X^{n-1}],\check{\mathsf{R}}[\mathring{Y}^{N}]
$$
$$
\mathsf{R}[\acute{X^{n-1}},Y^{N}]
$$
A Warm-Up with the Ring of Polynomials *R* = R[*X*]. Before dealing with multivariate
polynomials, we start with univariate polynomials, to illustrate some requirements and some
issues:
$$
\ {mathcal R=\\ }\mathsf{R}[X]
$$ n 1
{ Setup(1*; R* = R[*X*]*;* (*R₁* = R[*X*])) rst runs (pk⁰*;*sk⁰*;*vk⁰) Gen(1 ), chooses a random
$i
element *s* R and, for *i 2* [[0;*n* 1]], sets *E*iE *0* (*s*). Then, the public key of the
sk
commitment scheme is pk = (pk⁰*; fE*i*g*i), while the verication key is vk = vk⁰;
P
$$
- \operatorname {S u p e t} \left(1 ^ {\lambda}, \mathcal {R} = \mathrm {R} [ X ], \left(\mathcal {R} _ {1} = \mathrm {R} \left[ X ^ {n - 1} \right]\right)\right)
$$
$$
(\mathsf{p k}^{\prime},\mathsf{s k}^{\prime},\mathsf{v k}^{\prime})\leftarrow\mathsf{G e n}(1^{\lambda})
$$
$$
s \leftarrow^ {\$} R ^ {*}
$$
$$
i\,\in\,[0;n-1]\,
$$
$$
E_{i}\leftarrow\mathsf{E}_{\mathsf{s k}^{\prime}}(s^{i})
$$
$$
\mathsf{p k}=(\mathsf{p k}^{\prime},\{E_{i}\}_{i})
$$
$$
v k = v k ^ {\prime};
$$
n 1 i
{ Commitpk(u*; R₁*), for a polynomial u = uiX *2 R₁ R* of degree at most *n* 1,
Pi=0
i
o*u*tputs *E* = Eval(*fE*igi*; fu*i*g*i) = E( *u*i*s*) = E(u(*s*));
i
$$
\mathfrak{I}=\sum_{i=0}^{n-1}u_{i}X^{i}\in\mathcal{R}_{1}\subset\mathcal{R}
$$
$$
\mathsf{C o m m i t}_{\mathsf{p k}}(\mathsf{u},\mathcal{R}_{1})
$$
$$
n-1
$$
$$
Etextstyle E=\mathsf{E v a l}(\{E_{i}\}_{i},\{u_{i}\}_{i})=\mathsf{E}(\sum_{i}u_{i}s^{i})=\mathsf{E}(\mathsf{u}(s))
$$
{ Validityvk(*E*) is exactly the Verify of the encoding scheme, as it outputs whether this is a
valid encoding or not, and thus a valid commitment or not.
$$
-\ {\mathsf{V a l i d i t y}}_{\mathsf{v k}}(E)
$$
Thanks to the linear-only extractability, when a player generates a valid encoding (or commitment) *E*, being only given (*E₀;:::;E*n 1), one can extract (*c*i) such that E is an encoding of
P
n 1 i
*c₀* + *c₁s* + *:::c*n 1s in R, and thus of the polynomial c = *c*i*X* in *R*. Our above comi
mitment *s*cheme on polynomials is thus extractable under the linear-only extractability of the
secure encoding scheme.
$$
(E_{0},\ldots,E_{n-1})
$$
$$
(c i)
$$
$$
\ {\mathsf{c}}\,=\,\textstyle\sum_{i}c_{i}X^{i}
$$
$$
c_{0}+c_{1}s+\ldots c_{n-1}s^{n-1}
$$
$$
\mathcal{R}
$$
In addition, thanks to the quadratic verication on the encodings, if we have four polynomials
u, v, m and r such that m = u v mod r, which means that m = u v+r q, where all the polynomials
are of degree at most *n* 1, we can check such a product: from valid commitments *U* and *V* of u
and v, *R* and *Q* of r and q, respectively, and *M* of the polynomial m, all of degree at most *n* 1,
as they are all simple encodings, QCheck(*X₁X₂*+*X₃X₄ X₅;U;V;R;Q;M*) = true implies that
m(*s*) = u(*s*) v(*s*) + r(*s*) q(*s*). According to the ring R, this might imply the expected relation,
or not. If R is a large enough eld, this is true.
$$
\mathbf{u},\mathbf{v},
$$
$$
\ \mathsf{m}=\mathsf{u}\cdot\mathsf{V}
$$
$$
m = u \cdot v + r \cdot q
$$
$$
n-1
$$
$$
n-1
$$
$$
(X_{1}X_{2}+X_{3}X_{4}-X_{5},U,V,R,Q,M)=
$$
$$
\ {mathfrak m}({\mathfrak s})={\mathfrak U}({\mathfrak s})\cdot{\mathfrak V}({\mathfrak s})+{\mathfrak r}({\mathfrak s})\cdot{\mathfrak q}({\mathfrak s})
$$
However, in the following, we will be interested in the particular case of R = Zq, with
q = p₁ ::: p‘a product of ‘ prime integers p₁ < ::: < p‘. Having m(s) = u(s) v(s) +
r(*s*) q(*s*) mod *q* while m 6= u v + r q in Zq[*X*] means there is an index *j 2* [[1;*‘*]] such that
m(*s*) = u(*s*) v(*s*) + r(*s*) q(*s*) mod *p*jwhile m 6= u v + r q in Zpj[*X*]. Under the Schwartz-Zippel
lemma [Sch80,Zip79], this probability is bounded by 2*n=p*jfor each *j*, as the total degree of
the relation is at most 2*n*. Hence, the probability over *s* to have a false positive is bounded by
2*n‘=t*. This probability is unfortunately non-negligible for polynomial prime factors. According
to the expected soundness parameter *"*, to reduce the probability of false positive cases, the
natural solution is to iterate *K* times, with multiple evaluation points *s*k, for *k 2* [[1;*K*]], so
K
that (2*n‘=t*) *"*. But then, we have to make sure the same polynomials are committed in
each point. We now directly deal with bivariate polynomials, and this could be extended to
multivariate polynomials, but notations would become hard to follow.
$$
\mathrm {R} = \mathbb {Z} _ {q}
$$
$$
q\,=\,p_{1}\cdot\ldots\cdot p_{\ell}
$$
$$
p_{1}\,<\,\ldots\,<\,p_{\ell}
$$
$$
{\mathfrak{r}}(s)\cdot{\mathfrak{q}}(s)
$$
$$
{\mathfrak{n}}\ (\ \!)\,=\,{\mathsf{u}}\big(\\ \!)\,\cdot\,{\mathsf{v}}\big(\ \\ )\,+
$$
$$
\neq{\pm{\mathsf{u}}}\cdot{\pmb{v}}+{\pmb{r}}\cdot{\pmb{q}}
$$
$$
\mathbb{Z}_{q}[X]
$$
$$
j\in[1;\ell]
$$
$$
\mathrm {m} (s) = \mathrm {u} (s) \cdot \mathrm {v} (s) + \mathrm {r} (s) \cdot \mathrm {q} (s)
$$
$$
p_{j}
$$
$$
\neq\ {\pm{\pmb\ u{}}}\cdot{\pmb{}\}{{\pmb v\}{}}+{\pmb{\pm r\ {}}}\cdot{\pmb{\}}{{\pmb\eta}}}}}
$$
$$
\mathbb{Z}_{p_{j}}[X]
$$
$$
[\mathrm{S c h80,i p}79]
$$
$$
2n/p_{j}
$$
$$
2n\ell/t
$$
$$
\varepsilon_{,}
$$
$$
s_{k}.
$$
$$
(2n\ell/t)^{K}\,\leq\,\varepsilon
$$
$$
k\,\in\,[1;K]\,\mathrm{~}
$$
## 3.2 Commitments on Bivariate Polynomials
We now build commitments on bivariate polynomials over Zqfor a composite *q*, providing
a way to deal with scalars and univariate polynomials, when they are evaluated in one-xed
coordinate or a xed point. In addition, a bivariate polynomial is a way to encode multiple
P
i
univariate polynomials: given *N* polynomials uj= uj;iX 2 Zq[X], of degree *n* 1, we can
PiP
j i j
consider the polynomial in Zq[*X;Y*]: u(*X;Y*) = *Y u*j(*X*) = *u*j;i*X Y*.
j j;i
$$
\mathbb{Z}_{q}
$$
$$
q,
$$
$$
\mathfrak{U}_{j}=\sum_{i}u_{j,i}X^{i}\in\mathbb{Z}_{bar q[[}X]
$$
$$
n-1
$$
$$
\textstyle\mathbb{Z}_{q}[X,Y];\,\mathfrak{u}(X,Y)\doteq\sum_{j}\overline{{Y^{j}}}\dot{\mathfrak{u}_{j}}(X)=\sum_{j,i}\dot{u}_{j,i}X^{i}Y^{j}
$$
As explained above, in order to reduce the probability of errors with the Schwartz-Zippel
lemma, we will use encodings in *K* multiple points. We will additionally prove they all encode
the same polynomial.
n 1 N
Setup(1*; R* = Zq[*X; Y*]*; R₂* = Zq[*X; Y*]) rst runs (pk⁰*;*sk⁰*;*vk⁰) Gen(1 ), chooses
$
*K* tuples of random elements *s*k*;t*kZqand, for *k 2* [[1;*K*]], *i 2* [[0;*n* 1]], and *j 2* [[0;*N*]], sets
ik j n 1 N
*E*k;j;iE *0* (s t). To explicitly limit to some degrees, such as *R₂* = Zq[*X;Y*] or even to
sk k
(1) (2) $
univariate polynomials. One also chooses *K* tuples of random elements *r;r* Zq. Then,
k k
(2) (2) ik j
for *k 2* [[1;*K*]], *i 2* [[0;*n* 1]], and *j 2* [[0;*N*]], one sets *E* E *0* (*r s t*) for bivariate
k;j;i sk k k
n 1 N
polynomials in *R₂* = Zq[*X;Y*]. The public key of the commitment scheme is composed of
0 (2) 0
the above encodings pk = (pk*; fE*k;j;i*;E g*k;j;i), and the verication key is vk = vk. For our
k;j;i
n 1 N
application, other sub-spaces will be added, but in this section, we focus on *R₂* = Zq[*X;Y*].
( )
More spaces are detailed in AppendixC, with other random values *r*.
k
$$
\ {bf delta}{\bf{t u p}}({\bf1}^{\lambda},\mathcal{R}=\mathbb{Z}_{q}[X,Y],\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}])
$$
$$
(\mathsf{p k}^{\prime},\mathsf{s k}^{\prime},\mathsf{v k}^{\prime})\leftarrow\mathsf{G e n}(1^{\lambda})
$$
$$
s_{k},t_{k}\xleftarrow{\ }\mathbb{D}_{q}^{*}
$$
$$
k \in [ 1; K ], i \in [ 0; n - 1 ]
$$
$$
E_{k,j,i}\gets\mathsf{E}_{\mathsf{s k}^{\prime}}(s_{k}^{i}\cdot t_{k}^{j})
$$
$$
j\in[0;N]
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
r _ {k} ^ {(1)}, r _ {k} ^ {(2)} \leftarrow^ {\$} \mathbb {Z} _ {q} ^ {*}
$$
$$
E_{k,j,i}^{(2)}\gets\mathsf{E}_{\mathsf{s k}^{\prime}}(r_{k}^{(2)}\cdot s_{k}^{i}\cdot t_{k}^{j})
$$
$$
k \in [ 1; K ], i \in [ 0; n - 1 ]
$$
$$
j \in [ 0; N ]
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
\mathsf{p k}=(\mathsf{p k}^{\prime},\{E_{k,j,i},E_{k,j,i}^{(2)}\}_{k,j,i})
$$
$$
\mathsf{v k}=\mathsf{v k}^{\prime}
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
r_{k}^{(\iota)}
$$
---
P P
n 1 N N n 1 i j n 1 N
Commit(u*;* Zq[*X; Y*]), for a polynomial u = *u*j;i*X Y* in *R₂* = Zq[*X;Y*],
j=0 i=0
(2)
outputs *C* = (*E*u= (*E*k*;E*)k*;*u), for *k 2* [[1;*K*]], withudetailed later, where
k
$$
\left(\mathsf{u},\mathbb{Z}_{q}[X^{n-1},Y^{N}]\right)
$$
$$
\mathsf{u}=\sum_{j=0}^{N}\sum_{i=0}^{n-1}u_{j,i}X^{i}Y^{j}\,\mathrm{i n}\,\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
C = \left(E _ {\mathrm {u}} = \left(E _ {k}, E _ {k} ^ {(2)}\right) _ {k}, \Pi_ {\mathrm {u}}\right)
$$
$$
k\in[1;K]\!
$$
$$
\Pi_{u}
$$
$$
\begin{aligned}{E_{k}}&{{}\gets\mathsf{E v a l}(\{E_{k,j,i}\}_{j,i},\{u_{j,i}\}_{j,i})=\mathsf{E}(\mathsf{u}(s_{k},t_{k}))}\\ {E_{k}^{(2)}}&{{}\gets\mathsf{E v a l}(\{E_{k,j,i}^{(2)}\}_{j,i},\{u_{j,i}\}_{j,i})=\mathsf{E}(r_{k}^{(2)}\cdot\mathsf{u}(s_{k},t_{k}))}\\ \end{aligned}
$$
$$
\mathrm {s u c h t h a t} \mathrm {Q C h e c k} \left(X _ {1} - X _ {2} \cdot X _ {3}, E _ {k} ^ {(2)}, E _ {k}, E _ {k, 0, 0} ^ {(2)}\right) = \mathrm {t r u e}
$$
(2)
The idea behind the twin encodings *E*u= (Ek*;E*)kis that the rst element *E*kis comk
patible between all the polynomials in *R* = Zq[*X;Y*], independently of the constraints on the
allowed monomials, while the second element restrains the polynomial space: the limited basis
(2) (2) n 1 N
in *fE g*j;iand the relation with *E* limits to *R₂* = Zq[*X;Y*]. Note there is still a
k;j;i k;0;0
non-negligible probability of false positives when accepting a twin encoding, as remarked above,
as the quadratic check might accept the relation on the specic points without the relation
holding on the polynomials. We will say an encoding *E*kis *valid* when the relation really holds
(2)
on the extracted polynomials from the twin encodings (*E*k*;E*). Intuitively, for each index *k*,
k
the probability of false positive (accepting an invalid twin encoding) is bounded by *‘D=t*, where
*D* will be the maximal total degree of the polynomials that one will be able to generate from the
(2)
elements in the basis provided as input, as *E* encodes a polynomial of degree 0. An additional
k;0;0
proofu(either provided from an interactive protocol or built in a non-interactive way) is thus
appended to the commitment to make the validity check sound, with error-probability *"*cfor
each commitment: a huge fraction of the encodings are valid and encode the same polynomial.
$$
E _ {\mathrm {u}} = \left(E _ {k}, E _ {k} ^ {(2)}\right) _ {k}
$$
$$
E_{k}
$$
$$
\mathcal{R}=\mathbb{Z}_{q}[X,Y]
$$
$$
\{E_{k,j,i}^{(2)}\}_{j,i}
$$
$$
E_{k,0,0}^{(2)}
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
E_{k}
$$
$$
(E_{k},E_{k}^{(2)})
$$
$$
\ell\mathcal{D}/t.
$$
$$
E_{k,0,0}^{(2)}
$$
$$
\ {cal Pi_{u}}
$$
$$
\varepsilon_{c}
$$
In this section, we target the soundness of the commitments, whereas our ultimate goal will
be a soundness bound *"*sfor our global proof. To achieve this soundness bound, we will rst
require all the commitments to be correct, excepted an error probability *"*s*=*3, the relations between the commitments to also hold excepted with error probability *"*s*=*3, and the bounds on the
noise-ooding to be small enough with error probability *"*s*=*3. Hence, we use a specic soundness
parameter *"*c*"*s*=*3cfor commitments, wherecwill be the total number of commitments.
$$
\varepsilon_{s}
$$
$$
\varepsilon_{s}/3
$$
$$
\varepsilon_{s}/3.
$$
$$
\varepsilon_{s}/3
$$
$$
\varepsilon_{c}\leq\varepsilon_{s}/3\nu_{c}
$$
$$
\nu_{c}
$$
Validity(*C*) rst veries the twin encodings, which checks the appropriate sub-spaces for each
(2)
*E*k: the quadratic check with the limited bases in *fE g*k;j;iguarantees the limited list of
k;j;i
monomials, but with an error probability bounded by 2*‘D=t*. Note that in this section, *D* =
*N* + *n* 1, because of the limited *R₂*, but monomials with higher degrees will be required
later. With *K* large enough, we can expect a large number of valid encodings *E*k: let us assume
more than *K=*5 encodings are not valid, this will remain undetected with probability at most
K=5 S
(*‘D=t*). If we impose *t* 2 2*‘D* (where *S* will be seen as a security margin, all along this
(S+1)K=5
analysis), the error probability is less than 2. Hence, the number of valid encodings
(S+1)K=5
*E*kis greater than 4*K=*5 excepted with probability upper-bounded by 2.
$$
E_{k}
$$
$$
\{E_{k,j,i}^{(2)}\}_{k,j,i}
$$
$$
\ {\mathcal D{}==}
$$
$$
N+n-1
$$
$$
2\ddot{\ell}\mathcal{D}/t
$$
$$
\mathcal{R}_{2}
$$
$$
E_{k}
$$
$$
K/5
$$
$$
(\ell\mathcal{D}/t)^{K/5}
$$
$$
t\geq2^{S}\times2\ell\mathcal{D}
$$
$$
S
$$
$$
2^{-(S+1)K/5}
$$
$$
E_{k}
$$
$$
2^{-(S+1)K/5}
$$
$$
4K/5
$$
But this is not enough to amplify the above Schwartz-Zippel lemma: one also has to make
sure that all the valid *E*kencode the same polynomial u to exploit the iterations in the quadratic
check between encoded polynomials:
$$
E_{k}
$$
$$
\begin{aligned}{\mathsf{u}_{k}(X,Y)-\mathsf{u}(X^{\prime},Y^{\prime})}&{{}=\mathsf{u}(X,Y)-\mathsf{u}(X^{\prime},Y^{\prime})}\\ {}&{{}=\mathsf{u}(X,Y)-\mathsf{u}(X,Y^{\prime})+\mathsf{u}(X,Y^{\prime})-\mathsf{u}(X^{\prime},Y^{\prime})}\\ {}&{{}=(Y-Y^{\prime})\cdot\mathsf{v}(X,Y,Y^{\prime})+(X-X^{\prime})\cdot\mathsf{w}(X,X^{\prime},Y^{\prime}).}\\ \end{aligned}
$$
$
This can be checked with random *x*m*;y*mZq, sent by the verier:
$$
x _ {m}, y _ {m} \leftarrow^ {\$} \mathbb {Z} _ {q},
$$
$$
\mathsf{u}(X,Y)-\mathsf{u}(x_{m},y_{m})=(Y-y_{m})\cdot\mathsf{v}_{m}(X,Y)+(X-x_{m})\cdot\mathsf{w}_{m}(X),
$$
from the proof
$$
\varPi_{\mathsf{u}}=(u_{m}\leftarrow\mathsf{u}(x_{m},y_{m}),(V_{k,m}\leftarrow\mathsf{E}(\mathsf{v}_{m}(s_{k},t_{k})),W_{k,m}\leftarrow\mathsf{E}(\mathsf{w}_{m}(s_{k})))_{k})_{m}
$$ that can be checked as
$$
\begin{aligned}{\mathsf{Q C h e c k}}&{{}(X_{1}-u_{m}-(X_{2}-y_{m})\cdot X_{3}-(X_{4}-x_{m})\cdot X_{5},}\\ {}&{{}E_{k},E_{k,1,0},V_{k,m},E_{k,0,1},W_{k,m})=\mathsf{t r u e}}\\ \end{aligned}
$$
For each *k 2* [[1;*K*]], if the above relations do not hold at the polynomial level (which means for
the polynomials vk;m, wk;m, encoded in *V*k;m, and *W*k;mrespectively, possibly in any sub-space)
for more than 1/3 of the *m 2* [[1;*M*]], they will remain undetected with probability at most
M=3 (S+1)M=3
(*‘*(*D* + 1)*=t*) 2. Otherwise
$$
k \in [ 1; K ]
$$
$$
\mathsf{v}_{k,m},\,{\mathsf{w}}_{k,m}
$$
$$
V_{k,m}
$$
$$
W_{k,m}
$$
$$
1/3
$$
$$
m\,\in\,[1;M]
$$
$$
\mathsf{u}_{k}(X,Y)-u_{m}=(Y-y_{m})\cdot\mathsf{v}_{k,m}+(X-x_{m})\cdot\mathsf{w}_{k,m}
$$
$$
(\ell(\mathcal{D}+1)/t)^{M/3}\leq2^{-(S+1)M/3}
$$
for more than 2*M=*3 indices *m*. Then, for any *k⁰* 6= *k*, that correspond to valid encodings *E*kand
*E*k*0*, at least *M=*3 common values (*x*m*;y*m) satisfy both relations in *k* and *k⁰*, hence uk(*x*m*;y*m) =
uk*0* (*x*m*;y*m) = *u*m. As a consequence, as the polynomials ukand uk*0* were committed before
seeing (*x*m*;y*m), there are *M=*3 random points in which the two polynomials are equal. Then
M=3 2M
uk= uk*0*, excepted with probability upper-bounded by (*‘D=t*) 2. A false acceptance for
(S+1)M=3
some pair (*k;k⁰*) of consecutive valid encodings is upper-bounded by 2*K* 2. Globally,
the probability of having a false positive among the valid encodings *E*kis bounded by 2*K*
(S+1)M=3
2.
$$
k^{\prime}\neq k
$$
$$
E_{k}
$$
$$
E_{k^{\prime}}.
$$
$$
(x_{m},y_{m})
$$
$$
k^{\prime}
$$
$$
\mathsf{u}_{k}(x_{m},y_{m})=
$$
$$
\mathsf{u}_{k^{\prime}}(x_{m},y_{m})\,=\,u_{m}
$$
$$
\mathtt{u}_{k^{\prime}}
$$
$$
\left(x_{m},y_{m}\right)
$$
$$
M/3
$$
$$
(\ell\mathcal{D}/t)^{M/3}\leq2^{-2M}
$$
$$
\mathsf{u}_{k}=\mathsf{u}_{k^{\prime}}
$$
$$
2K\cdot2^{-(S+1)M/3}
$$
$$
(k,k^{\prime})
$$
$$
E_{k}
$$
$$
2^{-\hat{(S+1)M}/3}
$$
$$
2K
$$
(2)
We thus complete the commitments in *R₂*: in addition to the twin encodings *E*u= (Ek*;E*)k,
k
after having received (or seen) (*x*m*;y*m)m, one completes the commitment with the proofsu,
for *k 2* [[1;*K*]], *m 2* [[1;*M*]]
n 1 N
{ in Commit(u*;* Z [*X;Y*]), = (*u;* (*V;W*));
$$
\ {mathcal R R}_{2}.
$$
$$
E_{\mathsf{u}}=(E_{k},E_{k}^{(2)})_{k}
$$
$$
(x_{m},y_{m})_{m}
$$
$$
I_{\mathrm{u}}
$$
$$
k\in[1;K],\,m\in[1;M]
$$
$$
- \text {i n} \operatorname {C o m m i t} (\mathrm {u}, \mathbb {Z} _ {q} [ X ^ {n - 1}, Y ^ {N} ]), \Pi_ {\mathrm {u}} = \left(u _ {m}, \left(V _ {k, m}, W _ {k, m}\right) _ {k}\right) _ {m};
$$
q u m k;m k;m k m
Then, we can state the following security result, which can be extended to other subspaces:
Theorem 5(Knowledge-Soundness of Commitments in *R₂*). *For any commitment C* =
(2)
(*E* = (*E*k*;E*)k*;* = (*u*m*;* (*V*k;m*;W*k;m)k)m)*, if C successfully passes all the validity checks and*
k
$2
*quadratic root checks, on randomly chosen* (*x*m*;y*m) Zq*, there exists a polynomial* u *2 R₂*
*such that at least* 4*K=*5 *of the twin encodings actually encode* u *(which can be extracted from the*
(S+1)K=5 (S+1)M=3
*extractability of valid encodings), excepted with probability less than* 2 +2*K* 2,
Q
‘ S
*where q* = pi*, with all p*i2 2*‘D, and D is the maximal degree of the polynomials in*
i=1
*the subspace.*
$$
\mathcal{R}_{2})
$$
$$
C=
$$
$$
\left(E = \left(E _ {k}, E _ {k} ^ {(2)}\right) _ {k}, \Pi = \left(u _ {m}, \left(V _ {k, m}, W _ {k, m}\right) _ {k}\right) _ {m}\right)
$$
$$
(x_{m},y_{m})\xleftarrow{\S}\mathbb{Z}_{q}^{2},
$$
$$
\mathsf{u}\in\mathcal{R}_{2}
$$
$$
4K/5
$$
$$
\ ^{-(S+1)K{5}}{+}K K{\cdot}2^{-(S+1)M{/}3}
$$
$$
\textstyle q=\prod_{i=1}^{\ell}p_{i}
$$
$$
p_{i}\geq2^{S}\times2\ell\mathcal{D}
$$
S
Quadratic Root Checks. According to the above analysis, if we assume *t* 2 2*‘D*, for all
the accepted commitments, we know that we have at least 4*K=*5 valid encodings of the same
polynomials in all twin encodings:
$$
t\geq2^{S}\times2\ell\mathcal{D}
$$
$$
4K/5
$$
{ if the number of invalid encodings is greater than *K=*5, they will remain undetected with
(S+1)K=5
probability less than 2.
$$
K/5
$$
$$
2^{-(S+1)K/5}
$$
{ all these valid encodings contain the same polynomial u, excepted with probability less than
(S+1)M=3
2*K* 2.
$$
2K\cdot2^{-(S+1)M/3}
$$
As a consequence, when all the verications succeed for the commitment, there are at least 4*K=*5
valid encodings on the same polynomial u, excepted with small error probability. Hence, when
4 commitments are involved in a quadratic check, at least *K=*5 common indices *k* correspond to
valid encodings on the same polynomials in the 4 commitments. Those polynomials then satisfy
K=5 S K=5
the relation excepted with probability less than (2*‘D=t*) 2.
$$
4K/5
$$
$$
K/5
$$
$$
(2\ell\mathcal{D}/t)^{K/5}\leq2^{-S\cdot K/5}
$$
n 1
More Parameters. Commitments in Zq[*X*] thus consist of 2*K* + *KM* = *K*(*M* + 2) enn 1 N
codings, and *M* scalars in Zqwhile commitments in Zq[*X;Y*] consist of 2*K* + 2*KM* =
2*K*(*M* + 1) encodings, and *M* scalars in Zq.
$$
\mathbb{Z}_{q}[X^{n-1}]
$$
$$
\mathbb{Z}_{q}
$$
$$
2K+K M=K(M+2)
$$
$$
\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
2K+2K M=
$$
$$
2K(M+1)
$$
$$
\mathbb{Z}_{q}
$$
The above analysis was for commitments that appear in quadratic checks involving *c* = 4
commitments, hence one required 4*K=*5 valid encodings. When other values of *c* in *f*2*;* 3*;* 4*g*,
this is enough to have *cK=*(*c* + 1) valid encodings in the *c* commitments to have *K=*(*c* + 1)
S K=(c+1)
common indices, and then the soundness of the equation is 2. More detail is provided
in AppendixC.
$$
c=4
$$
$$
4K/5
$$
$$
c K/(c+1)
$$
$$
K/(c+1)
$$
$$
2^{-S\cdot K/(c+1)}
$$
---
Corollary 6. *When all the tests pass in a quadratic check between at most c prover-generated*
*commitments, that are all valid, the relation is really satised on the committed polynomials*
*(which can be extracted from the extractability of valid encodings), excepted with probability less*
*S K=*(*c*+1)
*than* 2*.*
$$
2^{-S\cdot K/(c+1)}
$$
Bounds on *K* and *M* are detailed in AppendixF.
## 3.3 Hiding Commitments
These commitments with encodings are strongly binding, because of the knowledge-soundness,
but are not hiding, as sometimes expected from commitments. Because of the quadratic verication, if the verier hesitates between two polynomials in a commitment *C*, they can commit
them and do a simple linear verication, as they know vk.
To statistically hide the content, one has to add random blinding elements from the appropriate masking set *M* to every encodings, to get hiding encodings. We illustrate this here with
n 1 N N
with *R₂* = Zq[*X;Y*]. In AppendixC, we also detail the case of *R₃* = Zq[*Y*].
$$
\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
n 1 N
Commit (u*;* Zq[*X; Y*]), the hiding commitment for a bivariate polynomial u(*X;Y*) =
P P(2)
N n 1 i j n 1 N
*u*j;i*X Y 2R₂* = Zq[*X;Y*], outputs the tuple *C* = (*E*u= (*E;E;*k)k*;*u),
j=0 i=0 k k
0k$
where for all indices *k 2* [[1;*K*]] and *m 2* [[1;*M*]], withk*; M* :
$$
\left(\mathsf{u},\mathbb{Z}_{q}[X^{n-1},Y^{N}]\right)
$$
$$
\mathsf{u}(X,Y)\,=
$$
$$
\sum_{i=0}^{N}\sum_{i=0}^{n-1}u_{j,i}X^{i}Y^{j}\in\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
\mathcal{C}^{*}=(E_{\mathsf{u}}^{*}=(E_{k}^{*},E_{k}^{(\ **)},\pi_{k})_{k},\varPi_{\mathsf{u}}^{*})
$$
$$
k \in [ 1; K ]
$$
$$
m\in[1;M]
$$
$$
\rho_ {k}, \rho_ {k} ^ {\prime} \leftarrow^ {\$} \mathcal {M}
$$
$$
E_{k}^{*}\gets\mathsf{E v a l}(\{E_{k,j,i}\}_{j,i},\{E_{k,0,0}\},\{u_{j,i}\}_{j,i},\{\rho_{k}\})=\mathsf{E}(\mathsf{u}(s_{k},t_{k})+\rho_{k})
$$
$$
E _ {k} ^ {(2 *)} \leftarrow \operatorname {E v a l} \left(\left\{E _ {k, j, i} ^ {(2)} \right\} _ {j, i}, \left\{E _ {k, 0, 0} \right\}, \left\{u _ {j, i} \right\} _ {j, i}, \left\{\rho_ {k} ^ {\prime} \right\}\right) = \mathrm {E} \left(r _ {k} ^ {(2)} \cdot \mathrm {u} \left(s _ {k}, t _ {k}\right) + \rho_ {k} ^ {\prime}\right)
$$
$$
\mathrm{}{w i t h~}\pi_{k}=\{\mathsf{Z L L Q C h e c k}(X_{1}-X_{2}\cdot X_{3},E_{k}^{(2*)},E_{k}^{*},E_{k,0,0}^{(2)};E_{k,0,0},E_{k,0,0}^{(2)})=\mathsf{t r u e}\}
$$
0k (2) 0k
as the quadratique relation is equal to 1k*r*, with private scalarskand, and a
k
$
proof, using random *x*m*;y*mZqsent by the verier, of
$$
\rho_{k}
$$
$$
\rho_{k}^{\prime}\times1-\rho_{k}\times r_{k}^{(2)}
$$
$$
\rho_{k}^{\prime}
$$
$$
x_{m},y_{m}\xleftarrow{\S}\mathbb{Z}_{q}
$$
$$
\begin{aligned}{\mathsf{u}(X,Y)-\mathsf{u}(x_{m},y_{m})}&{{}=(Y-y_{m})\cdot\mathsf{v}_{m}(X,Y)+(X-x_{m})\cdot\mathsf{w}_{m}(X)}\\ {}&{{}=(Y-y_{m})\cdot\mathsf{v}_{m}+(X-x_{m})\cdot\mathsf{w}_{m}}\\ \end{aligned}
$$
which can be veried with
$$
\varPi_{\mathsf{u}}^{*}=(big V_{k,m}^{*}\gets\mathsf{E}(\mathsf{v}_{m}(s_{k},t_{k})+\rho_{k,m}),W_{k,m}^{*}\gets\mathsf{E}(\mathsf{w}_{m}(s_{k})+\rho_{k,m}^{\prime}),\pi_{k,m})_{k,m}
$$
0k;m$
for randomk;m; *M*, chosen by the prover for their privacy, and
$$
\rho_{k,m},\rho_{k,m}^{\prime}\stackrel{\mathfrak{S}}{\longleftarrow}\mathcal{M}
$$
$$
\begin{aligned}{\pi_{k,m}=\{}&{{}\mathsf{Z K L Q C h e c k}(X_{1}-(X_{2}-y_{m})\cdot X_{3}-(X_{4}-x_{m})\cdot X_{5},}\\ {}&{{}E_{k}^{*},E_{k,1,0},V_{k,m}^{*},E_{k,0,1},W_{k,m}^{*};E_{k,0,0},E_{k,0,0},E_{k,1,0}^{(m)},E_{k,0,1}^{(m)})=\mathsf{t r u e}\}}\\ \end{aligned}
$$
where anybody can compute
$$
E_{k,1,0}^{(m)}=\mathsf{E v a l}(\{E_{k,1,0},E_{k,0,0}\},\{1,-y_{m}\})=\mathsf{E}(t_{k}-y_{m})
$$
$$
E_{k,0,1}^{(m)}=\mathsf{E v a l}(\{E_{k,0,1},E_{k,0,0}\},\{1,-x_{m}\})=\mathsf{E}(s_{k}-x_{m})
$$
0k;m
as the quadratic relation is equal tok+ u(*x*m*;y*m)k;m(*t*k*y*m) (*s*k*x*m). One thus
proves their knowledge of the 4 private scalars,k*2M* (the same as above), *u*m= u(*x*m*;y*m) *2* R
0k;m
(the same for all the *k*’s), andk;m; *2M*.
$$
\rho_{k}+\mathsf{u}(x_{m},y_{m})-\rho_{k,m}(t_{k}-y_{m})-\rho_{k,m}^{\prime}(s_{k}-x_{m})
$$
$$
\rho_{k}\in\mathcal{M}
$$
$$
u_{m}=\mathsf{u}(x_{m},y_{m})\in\mathsf{R}
$$
$$
k^{\prime}\mathrm{s})
$$
$$
\rho_{k,m},\rho_{k,m}^{\prime}\in\mathcal{M}
$$
(2)
Let us assume that a reasonable fraction of the twin encodings (*E;E*) are valid for a
k k
n 1 N
polynomial u in Zq[*X;Y*]. For each *k*, the quadratic check guarantees that
k
$$
(E_{k}^{*},E_{k}^{(2*)})
$$
$$
\mathtt{u}_{k}^{*}
$$
$$
\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
k,
$$
$$
\begin{aligned}{\mathsf{u}_{k}^{*((X X,Y Y)}=\mathsf{u}_{k}(X,Y)+\rho_{k}}&{{}=(Y-y_{m})\cdot\mathsf{v}_{k,m}+(X-x_{m})\cdot\mathsf{w}_{k,m}}\\ {}&{{}+\rho_{k}+u_{m}-\rho_{k,m}\cdot(Y-y_{m})-\rho_{k,m}^{\prime}\cdot(X-x_{m})}\\ \end{aligned}
$$
excepted with the same error probability as in Theorem5. On the other hand, one can state:
---
Theorem 7(Hiding Property of Commitments in *R₂*). *For any commitment C* =
(2)
(*E* = (*E;E;*k)k*;* = (*V;W;*k;m)k;m)*, thanks to the random masks, and the zero-*
k k k;m k;m
*knowledge proofs, all the encodings are statistically indistinguishable from random encodings.*
$$
\mathcal{R}_{2})
$$
$$
C^{*}\ =
$$
Note that for a hiding commitment, we have zero-knowledge proofs on *K*(*M* + 1) equations
involving globally 2*K*(*M* + 1) + *M* private scalars (but at most 4 in each equation). In AppendixB.3, we detail the zero-knowledge proofs when the encoding relies on the Paillier’s en-
00 0
cryption scheme: soundness is 2, for < log₂ t, then one needs to iterate log₂("s=3c)=
times. Each proof consists of *K*(*M* + 1) Paillier ciphertexts and 2*K*(*M* + 1) + *M* scalars in Zq,
iterated log(3c*="*s)*=*log*t* times. Soundness also implies the RSA modulus needs to be larger
+3
than *L* 2 *q³*.
$$
K(M+1)
$$
$$
2K(M+1)+M
$$
$$
2^{-\lambda^{\prime}}
$$
$$
\lambda^{\prime}<\log_{2}t
$$
$$
-\log_{2}\ \ \bigl(\varepsilon_{s}/3\nu_{c}\bigr)/\lambda^{\prime}
$$
$$
\log(3\nu_{c}/\varepsilon_{s})/\log{t}
$$
$$
2K(M+1)+M
$$
$$
K(M+1)
$$
$$
L\cdot2^{\lambda+3}q^{3}
$$
$$
\mathbb{Z}_{q}
$$
## 3.4 Quadratic Root Check
The check Quadratic(*Q;C₁;:::;C*‘), on non-hiding commitments, for a quadratic polynomial *Q*,
that veries whether the committed polynomials *P*i’s in the *C*i’s satisfy the relation *Q*(*P₁;:::;P*‘) =
0, is performed as a QCheck on the encodings for each index *k*. Since a huge fraction of the indices *k* encode the same polynomials, for the prover-generated commitments, iterations amplify
the soundness.
$$
(Q,C_{1},\ldots,C_{\ell})
$$
$$
P_{i}
$$
$$
Q\rangle
$$
$$
C_{i}
$$
$$
Q(P_{1},\ldots,P_{\ell})=
$$
$$
0{,}
$$
When some hiding commitments are involved, one additionally has to prove the appropriate
blinding factors. More concretely, let us consider the binding commitment *D* of d, and the
hiding commitments *C* and *H* of c and h respectively, with blinding factorsk*;*k*2 M*
respectively. The relation c = d h can be checked as:
$$
C^{*}
$$
$$
^\mathrm,
$$
$$
H^{*}
$$
$$
c^{*}
$$
$$
\rho_{k},\sigma_{k}\,\in\,\mathcal{M}
$$
$$
\ \mathsf{c}^{*}=\mathsf{d}\times\mathsf{h}^{*}
$$
$$
\begin{aligned}{}&{{}\mathsf{Q u a d r a t i c}(X_{1}-X_{2}\cdot X_{3},C^{*},D,H^{*})}\\ {}&{{}\qquad\qquad=\mathsf{Z K I Q c h e c k}(X_{1}-X_{2}\cdot X_{3},C_{k}^{*},D_{k},H_{k}^{*};E_{k,0,0},D_{k})\ \mathrm{f o r\ a l l}\ k}\\ \end{aligned}
$$
as the quadratic relation is equal tok1kd, wherekandkare the same private values
as the ones used in the validity verication of the hiding commitments *C* and *H*.
$$
\rho_{k}\cdot1-\sigma_{k}\cdot\mathsf{d}
$$
$$
\rho_{k}
$$
$$
\sigma_{k}
$$
$$
C^{*}
$$
$$
H^{*}
$$
We stress that we only allow quadratic verications where at most one polynomial is committed in a hiding way in each quadratic product. In the end, we know that the quadratic
equations among polynomials are satised in at least *K=*5 random points. They are thus satis-
S K=5
ed by the polynomials excepted with probability less than 2, which is chosen to be much
less than *"*s*=*3e, whereeis the global number of equations to be checked.
$$
K/5
$$
$$
\varepsilon_{s}/3\nu_{e}
$$
$$
2^{-S\cdot K/5}
$$
$$
\nu_{e}
$$
## 3.5 Complete Construction of the Commitment
As already explained, in our application, we are considering *q* = *p₁ ::: p*‘, a composite modulus
n 1 2N
q, with ‘ prime factors p₁ < ::: < p‘. We will work in subspaces of R = Zq[X;Y]. We will
n 1 n 1 N N 2N
consider the subspaces *R₁* = Zq[*X*], *R₂* = Zq[*X;Y*], *R₃* = Zq[*Y*], and Zq[*Y*] with no
N 2N nN S
term in *Y*, denoted *R₄* = Zq[*Y*], hence *D* = 2*N*, so we will assume *t* 2 4*N‘*. Details
on the complete construction of the commitments with system setup and detailed contents and
checks are given in AppendixC.
$$
q=p_{1}\!\cdot\!\cdot\!\cdot\!p_{\ell}
$$
$$
p_{1}<\ldotsj)j2[[0;N]], committed by the sender/prover, where is a function known
j
by them both, depending on the application. If (m*;j*) = m, the inner product corresponds to
the Oblivious Polynomial Evaluation (OPE) of the polynomial F with coecients (fj)jon the
message m; if (m*;j*) =;j, with the Kronecker symbol and *2* [[0;*N*]] such that m is the
representation of, it provides the-th coecient of f, which would coincide with a Symmetric
Private Information Retrieval (SPIR) application. We now show how the sender can provide
this evaluation with fully homomorphic encryption in a provable way.
$$
\mathsf{F}=(\mathsf{f}_{j})_{j\in[0;N]}
$$
$$
\ Phi(\mathsf{m})=(\phi(\mathsf{m},0),\phi(\mathsf{m},1),\dots,\phi(\mathsf{m},N))
$$
$$
\phi
$$
$$
\phi(\mathsf{m},j)=\mathsf{m}^{j}
$$
$$
(\mathtt{f}_{j})_{j}
$$
$$
\phi(\mathsf{m},j)=\delta_{\mu,j}
$$
$$
\mu\in[;;\ \boldsymbol N right]]
$$
$$
\delta
$$
$$
\mu_{\}}
$$
---
More precisely, we consider the above FV scheme that encrypts messages from *R*t=
n S
Zt[*X*]*=*r(*X*), where r = *X* + 1, into *R*q= Zq[*X*]*=*r(*X*) for *q* = *p₁ ::: p*‘, with 2 4*N‘*
t = p₁ < ::: < p‘.
$$
\mathbb{Z}_{t}[X]/\mathsf{r}(X)
$$
$$
\mathcal{R}_{t}\ =
$$
$$
\ {mathfrak r=}\ X^{n}+1
$$
$$
\mathcal{R}_{q}=\mathbb{Z}_{q}[X]/{\mathsf{r}}(X)
$$
$$
q=p_{1}\times\ldots\times p_{\ell}
$$
$$
2^{S}\times4N\ell\leq
$$
$$
t=p_{1}<\ldotstunder their own key, and sends Enc(m) = (c*;*c⁰) *2*
N+1
*R²*q, in order to get back the homomorphic inner product of (m) = ( (m*;j*))j2[[0;N]]*2R*t
N+1
with F = (fj)j2[[0;N]]*2R*t, committed by the sender, with a proof of correct value (d*;*d⁰) =
Enc(*h* (m)*;* F*i*) *2R²*q, that thereafter decrypts to *h* (m)*;* F*i2R*t, using the receiver’s decryption
key.
$$
\mathsf{E n c}(\mathsf{m})=(\mathsf{c},\mathsf{c}^{\prime})\in
$$
$$
\mathfrak{m}\in\mathcal{R}_{t}
$$
$$
\mathcal{R}_{q}^{2}
$$
$$
\varPhi(\mathsf{m})=(\phi(\mathsf{m},j))_{j\in[0;N]}\in\mathcal{R}_{t}^{N+}
$$
$$
({\mathsf{d}},{\mathsf{d}}^{\prime})=
$$
$$
\mathrm {F} = \left(\mathrm {f} _ {j}\right) _ {j \in \llbracket 0; N \rrbracket} \in \mathcal {R} _ {t} ^ {N + 1}
$$
$$
\mathsf{E n c}(\langle\varPhi(\mathsf{m}),\mathsf{F}\mathring))in\mathring{\mathcal{R}}_{q}^{2}
$$
$$
\langle\varPhi(\mathsf{m}),\mathsf{F}\rangle\in\mathcal{R}_{t}
$$
From (c*;*c⁰), and possible additional intermediate ciphertexts, sent by the receiver, the sender
0j
is able to compute (uj*;* u) = Enc( (m*;j*)), for *j 2* [[0;*N*]], in any way they want, using the
homomorphic properties of the encryption scheme:
!
$$
(c,c^{\prime})
$$
$$
\left\langle\mathsf{u}_{j},\mathsf{u}_{j}^{\prime}\right\rangle=\mathsf{E n c}(\phi(m,j))
$$
$$
j\,\in\,[0;N]
$$
$$
(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})=\mathsf{E n c}(\phi(\mathsf{m},j))=\left(\sum_{i=0}^{n}u_{j,i}\cdot X^{i},\sum_{i=0}^{n}u_{j,i}^{\prime}\cdot X^{i}\right)\in\mathcal{R}_{q}^{2}.
$$
Thereafter, the goal is to evaluate the inner products:
0
$$
\begin{aligned}{(\mathsf{d},\mathsf{d}^{\prime})}&{{}=\mathsf{E n c}(\langle\ \ mathsf F\\ (\mathsf m),\mathsf F\rangle)=\mathsf{E n c}\left(\sum_{j=0}^{N}\mathsf f_{j}\cdot\phi(\mathsf m,j)\right)=\sum_{j=0}^{N}\mathsf f_{j}\cdot\mathsf{E n c}(\phi(\mathsf m,j))}\\ {}&{{}=\sum_{j=0}^{N}\mathsf f_{j}\cdot(\mathsf u_{j},\mathsf u_{j}^{\prime})=\left(\sum_{j=0}^{N}\mathsf f_{j}\cdot\mathsf u_{j},\sum_{j=0}^{N}\mathsf f_{j}\cdot\mathsf u_{j}^{\prime}\right).}\\ \end{aligned}
$$
The sender can add noise to hide F in the evaluation and prove the correct evaluation of d~ = d+z
~0~ ~0
and d = d⁰ + z⁰ so that (d*;* d) decrypts to *h* (m)*;* F*i*. The pair (z*;*z⁰) will be committed in
a hidden way, with a proof of correct noise, in the appropriate range, to ensure the correct
decryption.
$$
\tilde{\mathsf{d}}=\mathsf{d}+\mathsf{z}^{*}
$$
$$
\tilde{\mathsf{d}}^{\prime}=\mathsf{d}^{\prime}+\mathsf{z}^{\prime*}
$$
$$
(\tilde{\mathtt{d}},\tilde{\mathtt{d}}^{\prime})
$$
$$
\langle \Phi (\mathrm {m}), \mathrm {F} \rangle
$$
$$
\left(z ^ {*}, z ^ {\prime *}\right)
$$
This veriable evaluation will be done in two steps: rst, the sender will prove the correct
0j
evaluation of all the (uj*;* u), while committed in a very compact way. Then, a proof of the inner
product is provided. We will later explain how everything remains succinct.
$$
(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})
$$
For the following proof and analysis to hold, we need the property, in the particular case
where *L* = *N* + 1:
$$
L=N+1
$$
Denition 8((*L;d*)-*R*t-Linear-Homomorphism). *For any* ai*;* ui*2R*t*, for i* = 1*;:::;L,*
!
$$
\mathsf{a}_{i},\mathsf{U}_{i}\in\mathcal{R}_{t},\,\mathit{f o r}\;i=1,\ldots,L,
$$
$$
\mathsf{D e c}\left(\sum_{i=1}^{L}\mathsf{a}_{i}\cdot(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime})\right)=\sum_{i=1}^{L}\mathsf{a}_{i}\cdot\mathsf{u}_{i}\in\mathcal{R}_{t}
$$
0i
*where* (ci*;* c) *2R²*q*is an encryption of* ui*obtained from a circuit of multiplicative depth bounded*
*by d.*
$$
(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime})\in\mathcal{R}_{q}^{2}
$$
$$
\ _i,
$$
## 4.1 Commitment of F
One can rst note that ring elements in *R*tand *R*qare polynomials of degree at most *n* 1,
n 1 N+1
and can be encoded into *R₁* = Zq[*X*]. The sender’s vector F *2 R*tcan be committed
P P
N j n 1 i
using the polynomial f = fj*Y* in *R*t[Y], where fj= fj;iX, can be committed
i=0 i=0
P P
n 1 N N n 1 i N j
in a hidden way in *R₂* = Zq[*X;Y*] as *f* = *f*j;i*X Y* (with reverse order
j=0 i=0
coecients) into *F*.
$$
\ {mathcal R R}_{t}
$$
$$
\mathcal{R}_{q}
$$
$$
\mathcal{R}_{1}=\mathbb{Z}_{q}[X^{n-1}]
$$
$$
n-1
$$
$$
\mathsf{F}\,\in\,\mathcal{R}_{t}^{N+1}
$$
$$
\textstyle\ \mathsf{f}=\sum_{i=0}^{N}\mathsf{f}_{j}\cdot Y^{j}
$$
$$
\mathcal{R}_{t}[Y]
$$
$$
\mathsf{f}_{j}=\sum_{i=0}^{n-1}f_{j,i}\cdot X^{i}
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
\mathsf{f}^{*}=\sum_{j=0}^{N}\sum_{i=0}^{n-1}f_{j,i}\cdot X^{i}Y^{N-j}
$$
$$
F^{*}
$$
~ and d~*0*
The sender can also compute and publish the noisy inner products d in *R*q, the
expected ciphertext of the result, for some private q*;*q⁰*;* z*;*z⁰ *2R*q:
$$
\tilde{\textbf d}
$$
$$
\tilde{\mathrm{d}}^{\prime}
$$
$$
\mathcal{R}_{q}
$$
$$
{\mathsf q}^{*},{\mathsf q}^{\ *},{\mathsf z}^{*},{\mathsf z}^{\prime*}\in{\mathcal R}_{q}
$$
$$
\tilde{\mathsf{d}}=\sum_{j=0}^{N}\mathsf{f}_{j}\cdot\mathsf{u}_{j}+\mathsf{z}^{*}-\mathsf{q}^{*}\cdot\mathsf{r}\qquad\qquad\quad\tilde{\mathsf{d}}^{\prime}=\sum_{j=0}^{N}\mathsf{f}_{j}\cdot\mathsf{u}_{j}^{\prime}+\mathsf{z}^{\prime*}-\mathsf{q}^{\prime*}\cdot\mathsf{r}.
$$
---
The polynomials z*;*z⁰*;* q*;*q⁰ are committed in a hidden way in *Z;Z⁰;Q ;Q⁰*, in *R₁* =
n 1
Zq[*X*]. The inner products must be proven, which is the goal of the second part, after we
0j
have proven the correct computation of the (uj*;* u)’s, as both together will prove correctness of
~ ~0
the ciphertext (d*;* d).
$$
Z^{*},Z^{\prime*},Q^{*},Q^{\prime*}
$$
$$
\mathsf{z}^{*},\mathsf{z}^{\prime*},\mathsf{q}^{*},\mathsf{q}^{\prime*}
$$
$$
\mathbb{Z}_{q}[X^{n-1}]
$$
$$
\mathcal{R}_{1}\ =
$$
$$
(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})^{\backprime}\mathrm{S}.
$$
$$
(\tilde{\mathbf{d}},\tilde{\mathbf{d}}^{\prime})
$$
## 0j 4.2 Validity of the (uj; u)’s
$$
(\mathbf{}\mathbf{\ u}_{j},\mathbf{\}\mathbf{\ u}_{j}^{\prime})^{\intercal}\mathbf{s}}
$$
We thus start by proving the validity of the encryptions of the (m*;j*). From the ciphertexts
0j
(uj*;* u) that the prover computed on their own, they then dene the polynomials:
$$
\phi(\mathsf{m},j)
$$
$$
(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})
$$
$$
\mathsf{u}(X,Y)=\sum_{j=0}^{N}\mathsf{u}_{j}(X)\cdot Y^{j}=\sum_{j=0}^{N}\sum_{i=0}^{n-1}u_{j,i}X^{i}Y^{j}\qquad\qquad\mathsf{u}^{\prime}(X,Y)=\sum_{j=0}^{N}\mathsf{u}_{j}^{\prime}(X)\cdot Y^{j}
$$
n 1 N
and commit them from the sub-space *R₂* = Zq[*X;Y*] into *U* and *U⁰* respectively. Our rst
step is to prove that the polynomials committed in *U* and *U⁰* by the sender indeed satisfy,
0j
for any exponents *j 2* [[0;*N*]], (uj*;* u) = Enc( (m*;j*)), or more precisely that the decryptions
0j
Dec(uj*;* u) that we denote *’*m;jare indeed (m*;j*) *2R*t, for m initially encrypted by the verier
in (c*;*c⁰).
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
U^{\prime}
$$
$$
U^{\prime}
$$
$$
j\,\in\,[0;N],\;(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})\,=\,\mathsf{E n c}(\phi(\mathsf{m},j))
$$
$$
\mathbb{D}\mathsf{e}(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime})
$$
$$
\phi(\mathsf{m},j)\in\mathcal{R}_{t}
$$
$$
\varphi_{\mathsf{m},j}
$$
$$
(c,c^{\prime})
$$
$
The verier rst chooses and sends a random polynomial n *R*t(or it can be generated
by a hash function on the previous data to remove interaction). Both parties can compute,
P
j n 1 i n 1 N
nj= n = *n*j;i*X* in *R*t, for all *j 2* [[0;*N*]], and commit them in *R₂* = Zq[*X*;Y] as
i=0
P P
N n 1 i N j
t = *n*j;i*X Y* (with reverse order coecients) into *T*. Then, the prover computes
j=0 i=0
P
0 N 0j 2
and sends (b*;* b) = nj(uj*;* u) in *R*q.
j=0
$$
\xleftarrow{\S}\mathcal{R}_{t}
$$
$$
\mathfrak{n}_{j}=\mathfrak{n}^{j}=\sum_{i=0}^{n-1}n_{j,i}\cdot X^{i}
$$
$$
\ {cal R}_{t}
$$
$$
j \in [ 0; N ]
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
$$
$$
\big(\mathsf{b},\mathsf{b}^{\prime}\big)=\sum_{j=0}^{N}\mathsf{n}_{j}\cdot\big(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime}\big)
$$
$$
\mathcal{R}_{q}^{2}.
$$
0
Since this is symmetric, we now focus on the rst component (without), and similar analysis
0
will have to be done on the second component (with): the prover also computes and sends l
P
N n 1
so that njuj= b + l r, that they both commit as *L* in *R₁* = Zq[*X*].
j=0
$$
\sum_ {j = 0} ^ {N} \mathrm {n} _ {j} \cdot \mathrm {u} _ {j} = \mathrm {b} + \mathrm {l} \cdot \mathrm {r},
$$
$$
\mathcal{R}_{1}=\mathbb{Z}_{q}[X^{n-1}]
$$
$
The verier chooses and sends a sequence of random scalars Zq, for *2* [[1;]]. They
will dene *v*;j= uj() *2* Zqfor *j 2* [[0;*N*]]. We thus have the polynomial:
$$
\beta_{\kappa}\xleftarrow{\S}\mathbb{Z}_{q},
$$
$$
\kappa\in\left[1;\varLambda\right]
$$
$$
v_{\kappa,j}=\mathsf{u}_{j}(\beta_{\kappa})\in\mathbb{Z}_{q}
$$
$$
j\in\left[0;N\right]
$$
$$
\mathsf{v}_{\kappa}(Y)=\sum_{j=0}^{N}v_{\kappa,j}\cdot Y^{j}=\sum_{j=0}^{N}\mathsf{u}_{j}(\beta_{\kappa})\cdot Y^{j}=\sum_{j=0}^{N}\sum_{i=0}^{n-1}u_{j,i}\beta_{\kappa}^{i}\cdot Y^{j}=\mathsf{u}(\beta_{\kappa},Y)
$$
N
that can be committed as *V* in *R₃* = Zq[*Y*], and proven correct with the quadratic check
$$
V_{\kappa}
$$
$$
\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
$$
\mathsf{u}(X,Y)-\mathsf{v}_{\kappa}(Y)=\mathsf{u}(X,Y)-\mathsf{u}(\beta_{\kappa},Y)=(X-\beta_{\kappa})\cdot\mathsf{w}_{\kappa}(X,Y)
$$
(1)
n 1 N
on the commitment *W* of w *2R₂* = Zq[*X;Y*] and the public commitment *C* of *X*,
and thus only 3 prover-generated commitments (U, V, and *W*, as *C* is public). With t =
P
N j
t(*;Y*) = nj() *Y* publicly computed and committed in *T*, we can note that
j=0
X
$$
W_{\kappa}
$$
$$
\mathsf{w}_{\kappa}\in\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
C_{\kappa}
$$
$$
(U,\,V_{\kappa},
$$
$$
W_{\kappa}
$$
$$
C_{\kappa}
$$
$$
\ !{\mathfrak t}_{\kappa}\,=
$$
$$
\mathsf{t}(\beta_{\kappa},Y)=\sum_{j=0}^{N}\mathsf{n}_{j}(\beta_{\kappa})\cdot Y^{j}
$$
$$
T_{\kappa}
$$
$$
\begin{aligned}{\mathsf{v}_{\kappa}(Y)\cdot\mathsf{t}_{\mathsf{k}}(Y)}&{{}=\sum_{0\leq i,j\leq N}v_{\kappa,i}\cdot\mathsf{n}_{j}(\beta_{\kappa})\cdot Y^{N+i-j}}\\ {}&{{}=\sum_{0\leq i\leq N}v_{\kappa,i}\cdot\mathsf{n}_{i}(\beta_{\kappa})\cdot Y^{N}+\sum_{0\leq i\neq j\leq N}v_{\kappa,i}\cdot\mathsf{n}_{j}(\beta_{\kappa})\cdot Y^{N+i-j}}\\ \end{aligned}
$$
and
$$
\sum_{0\leq i\leq N}v_{\kappa,i}\cdot\mathsf{n}_{i}(\beta_{\kappa})=\sum_{0\leq i\leq N}\mathsf{u}_{i}(\beta_{\kappa})\cdot\mathsf{n}_{i}(\beta_{\kappa})=b_{\kappa}+l_{\kappa}\cdot r_{\kappa}
$$
where *b* = b(), *l* = l (), and *r* = r() can be publicly computed in Zq, so we can check:
X
$$
b_{\kappa}=\mathfrak{b}(\beta_{\kappa}),l_{\kappa}=|_{\kappa}(\beta_{\kappa})
$$
$$
r_{\kappa}=\ \ {mathsf r(\beta_{\kappa})}
$$
$$
\mathbb{Z}_{q}.
$$
$$
{mathsf{v}}_{\kappa}(Y)\cdot{\mathsf{t}}_{\kappa}(Y)-(b_{\kappa}+l_{\kappa}\cdot r_{\kappa})\cdot Y^{N}=\sum_{0q[*Y*] and *C*Na public commitment of *Y*, which
makes only 2 prover-generated commitments (*V* and *Y*).
$$
\mathbf{y}_{\kappa}
$$
$$
Y^{N}
$$
$$
C_{N}
$$
$$
(V_{\kappa}
$$
We stress that because of the repetitions in each commitment (up to *K*, according to the
kind of relations they are involved in, and the number of prover-generated commitments), we
know (see Corollary6) that when all the tests pass, the above equations (1) and (2) are all
(S+1)K=4
satised with error probability less than 2 2.
$$
Y_{\kappa})
$$
$$
2\Lambda\cdot2^{-(\hat{S}+1)\dot{K}/4}
$$
N
They altogether prove that, for each 2 [[1;]], *b* + *l r* is the coecient of *Y* in
P
v (*Y*) t (*Y*), and so uj() nj() = b() + l() r() mod *q* for the random, on
jP
polynomials committed beforehand, of degree *n*. Hence, ujnj= b + l r, excepted with error
j
S+1
probability bounded by *2‘n=t n=*2 *N*, from the Schwartz-Zippel lemma.
$$
\kappa\,\in\,[1;\varLambda],\,b_{\kappa}+l_{\kappa}\cdot r_{\kappa}
$$
$$
Y^{N}
$$
$$
\mathsf{v}_{\kappa}(Y)\cdot\mathsf{t}_{\kappa}(Y)
$$
$$
\sum_ {j} \mathrm {u} _ {j} \left(\beta_ {\kappa}\right) \cdot \mathrm {n} _ {j} \left(\beta_ {\kappa}\right) = \mathrm {b} \left(\beta_ {\kappa}\right) + \mathrm {l} \left(\beta_ {\kappa}\right) \cdot \mathrm {r} \left(\beta_ {\kappa}\right)
$$
$$
q
$$
$$
\beta_{\kappa}
$$
$$
\sum_ {j} u _ {j} \cdot n _ {j} = b + l \cdot r,
$$
$$
2\ell n/t\leq n/2^{S+1}N
$$
For large enough (to be set later), after all these steps, on both b and b⁰, one gets the
proof that, in *R*q,
$$
\ ^{\prime}
$$
$$
\mathcal{R}_{q}
$$
$$
\mathsf{b}=\sum_{j=0}^{N}\mathsf{n}_{j}\cdot\mathsf{u}_{j}\quad\mathsf{b}^{\prime}=\sum_{j=0}^{N}\mathsf{n}_{j}\cdot\mathsf{u}_{j}^{\prime}:\qquad(\mathsf{b},\mathsf{b}^{\prime})=\sum_{j=0}^{N}\mathsf{n}_{j}\cdot(\mathsf{u}_{j},\mathsf{u}_{j}^{\prime}).
$$
These relations hold for both b and b⁰ excepted with error probability bounded by 2 (2
(S+1)K=4 S+1
2 + (*n=*2 *N*)).
P P
$$
\ ^{\prime}
$$
$$
2\times(2\Lambda
$$
$$
2^{-(S+1)K/4}+(n/2^{S+1}N)^{\Lambda}\big)
$$
0 N j N j
The verier now checks that Dec(b*;* b) = n (m*;j*), which thus leads to n
j=0 j=0
P P
N j j
*’*m;j= n (m;j) in Rt. We can thus consider the polynomial (*’*m;j(m*;j*)) *Y*
j=0 j
$
in *R*t, which evaluates to zero in the random point n *R*t. Note that *R*tis a ring that
2k
is the product of large elds only: r = *X* + 1 is not irreducible in any Zp[*X*] for a prime
*p*, but for well-chosen prime, all the factors have large degrees: according to [BGM93], with
a k
*t* + 1 = 2 (2*p* + 1), for any integer *p*, *a* 2, and *n* = 2, then all the factors have degree
k+1 a
2. If one chooses *t* = 3 mod 8, *a* = 2, and there are just two irreducible factors of degree
k 1
2 = *n=*2: the above polynomial thus has all zero coecients by the Schwartz-Zippel lemma,
n=2
excepted with probability 2 *N=t*, as the polynomial is of degree *N* and n is randomly chosen
n=2
among *t* possible values in each of the two elds. Hence, *’*m;j= (m*;j*) in *R*t, excepted with
n=2
probability bounded by 2*N=t*, which is clearly negligible.
$$
\mathsf{D e c}(\mathsf{b},\mathsf{b}^{\prime})=\textstyle\sum_{j=0}^{N}\mathsf{n}^{j}\cdot\phi(\mathsf{m},j)
$$
$$
\sum_ {j = 0} ^ {N} \mathrm {n} ^ {j}
$$
$$
\varphi_{\mathsf{m},j}=\sum_{j=0}^{N}\mathsf{n}^{j}\cdot\phi(\mathsf{m},j)
$$
$$
\ {mathcal R}_{t}
$$
$$
\textstyle{\sum_{j}(\varphi_{\mathsf{m},j}-\phi(\mathsf{m},j))\cdot Y^{j}}
$$
$$
\ {mathcal R}_{t}
$$
$$
\xleftarrow{\ }\mathcal{R}_{t}
$$
$$
\mathcal{R}_{t}
$$
$$
{\mathsf{r}}\,=\,X^{2^{k}}+1
$$
$$
\mathbb{Z}_{p}[X]
$$
$$
p,
$$
$$
t+1=2^{a}(2p+1)
$$
$$
p,\,a\geq2
$$
$$
2^{k+1-a}
$$
$$
n=2^{k}
$$
$$
t=3
$$
$$
a=2
$$
$$
2^{k-1}=n/2
$$
$$
2\times N/t^{n/2}
$$
$$
t^{n/2}
$$
$$
\varphi_{\mathsf{m},j}=\phi(\mathsf{m},j)
$$
$$
\ {mathcal R_{{t}}}.
$$
$$
2N/t^{n/2}
$$
## 4.3 Validity of (~d; ~d⁰)
$$
(\tilde{\mathbf{d}},\tilde{\mathbf{d}^{\prime}})
$$
~ with respect to all (u ~0
As above, we focus on dj)jand z*;*q . The same should be done for d
0j
with respect to all (u)jand z⁰*;*q⁰, but for the same (fj)jand z*;*r:
$$
\tilde{\textbf d}
$$
$$
(\mathbf{u}_{j})_{j}
$$
$$
\ {mathbf z^{{*}}},{\mathbf{boldsymbol q}}{^{{}}}
$$
$$
\tilde{\mathbf{d}}^{\prime}
$$
$$
(\mathbf{u}_{j}^{\prime})_{j}
$$
$$
\ {boldsymbol z^{{\prime}}},{\boldsymbol{\boldsymbol{q}}}^{{\prime}*}
$$
$$
(\mathrm{f}_{j})_{j}
$$
$$
z,r:
$$
$$
\tilde{\mathsf{d}}=\sum_{j=0}^{N}\mathsf{f}_{j}\cdot\mathsf{u}_{j}+\mathsf{z}^{*}-\mathsf{q}^{*}\cdot\mathsf{r}.
$$
This following analysis is quite similar to the previous one, considering f, (z*;*q ), d~ instead
of t*;* p*;*b, and with hidden intermediate values, as (fj)jis private to the prover, contrarily to n
which was publicly chosen by the verier. One rst proves the quadratic relation on the hidden
P
N N j N
commitment of g (*Y*) = f (*;Y*) = *g*;j*Y* in *R₃* = Zq[*Y*], where *g*;j= fj(),
j=0
n N
and the hiding commitment of h (*X;Y*) in *R₂* = Zq[*X;Y*], so that
$$
\mathsf{f}{^**},\:(\mathsf{z}{{^*}},\mathsf{q}{{{^**}}}),\:\mathsf{\tilde{d}}
$$
$$
(\mathrm{f}_{j})_{j}
$$
$$
\mathsf{g}_{\kappa}^{*}(Y)=\mathsf{f}^{*}\big(\beta_{\kappa},Y\big)=\sum_{j=0}^{N}g_{\kappa,j}\cdot Y^{N-j}\mathrm{~i n~}\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
$$
g_{\kappa,j}\,=\,\mathsf{f}_{j}(\beta_{\kappa})
$$
$$
\mathsf{h}_{\kappa}^{*}(X,Y)
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n},Y^{N}]
$$
$$
\mathrm {f} ^ {*} (X, Y) - \mathrm {g} _ {\kappa} ^ {*} (Y) = \mathrm {f} ^ {*} (X, Y) - \mathrm {f} ^ {*} \left(\beta_ {\kappa}, Y\right) = \left(X - \beta_ {\kappa}\right) \cdot \mathrm {h} _ {\kappa} ^ {*} (X, Y)
$$
(3)
with only 3 prover-generated commitments. And similarly, one proves in a hidden way:
$$
\mathfrak{q}^{*}(X)-q_{\kappa}^{*}=\mathfrak{q}^{*}(X)-\mathfrak{q}^{*}(\beta_{\kappa})=\big(X-\beta_{\kappa}\big)\cdot\mathfrak{q}_{\kappa}^{*}(X)
$$
$$
\mathsf{z}^{*}\big(X\big)-z_{\kappa}^{*}=\mathsf{z}^{*}\big(X\big)-\mathsf{z}^{*}\big(\beta_{\kappa}\big)=\big(X-\beta_{\kappa}\big)\cdot\mathsf{z}_{\kappa}^{*}\big(X\big)
$$
(4)
(5)
---
| #variables | Binding or Hiding | Polynomials | #commitments |
| --- | --- | --- | --- |
| 1v | B | $v_{\kappa}, v^{\prime}_{\kappa}, y_{\kappa}, y^{\prime}_{\kappa}$ | 6A |
| 1v | H | $q^{*}, q^{\prime *}, q_{\kappa}^{*}, q_{\kappa}^{\prime *}, u_{k}^{*}, e_{1,k}^{*}, e_{2,k}^{*}, z_{\kappa}^{*}, z^{\prime *}, g_{\kappa}^{*}$ | 5A+2+3Z |
| 2v | B | u,u',w_{\kappa},w^{\prime}_{\kappa}$ | 2(A+1) |
| 2v | H | f^{*},h_{\kappa}^{*}$ | A+1 |
| Total | | | 14A+5+3Z |
$$
\mathsf{v}_{\kappa},\mathsf{v}_{\kappa}^{\prime},\:\mathsf{y}_{\kappa},\mathsf{y}_{\kappa}^{\prime}
$$
$$
q ^ {*}, q ^ {\prime *}, q _ {\kappa} ^ {*}, q _ {\kappa} ^ {\prime *}, u _ {k} ^ {*}, e _ {1, k} ^ {*}, e _ {2, k} ^ {*}, z _ {\kappa} ^ {*}, z _ {\kappa} ^ {\prime *}, g _ {\kappa} ^ {*}
$$
$$
\overline{{5\Lambda+2+3Z}}
$$
$$
\mathsf{u},\mathsf{u}^{\prime},\mathsf{w}_{\kappa},\mathsf{w}_{\kappa}^{\prime}
$$
$$
2(\varLambda+1)
$$
$$
\overline{{14\varLambda+5+3Z}}
$$
Fig. 1. Number of Commitments in the Global Proof, and Size in Number of Encodings, with =
*d*(log₂(24*="s*))*=*(*S* + 1 + log₂(*N=n*))*e*
with the private *q* = q () and *z* = z () in Zqthat will be also used below. There are only
2 prover-generated commitments in each relation. We can note
$$
\big[\big(\mathrm{l o g}_{22}\big(24/big\varepsilon_{s}\big)\big)\big/\big(S+1+\mathrm{l o g}_{2}\big(N/n\big)\big)
$$
$$
\Lambda =
$$
$$
\mathbb{Z}_{q}
$$
$$
q_{\kappa}^{*}=\mathsf{q}_{\kappa}^{*}(\beta_{\kappa})
$$
$$
z_{\kappa}^{*}=\mathsf{z}_{\kappa}^{*}(\beta_{\kappa})
$$
$$
\begin{aligned}{\mathsf{v}_{\kappa}(Y)\cdot\mathsf{g}_{\kappa}^{*}(Y)}&{{}=\sum_{0\leq i,j\leq N}v_{\kappa,i}\cdot g_{\kappa,j}\cdot Y^{N+i-j}}\\ {}&{{}=\sum_{0\leq i\leq N}v_{\kappa,i}\cdot g_{\kappa,i}\cdot Y^{N}+\sum_{0\leq i\neq j\leq N}v_{\kappa,i}\cdot g_{\kappa,j}\cdot Y^{N+i-j}}\\ \end{aligned}
$$
and
$$
\begin{array}{l} \sum_ {0 \leq i \leq N} v _ {\kappa , i} \cdot g _ {\kappa , i} = \sum_ {0 \leq i \leq N} u _ {i} \left(\beta_ {\kappa}\right) \cdot f _ {i} \left(\beta_ {\kappa}\right) = \tilde {\mathrm {d}} \left(\beta_ {\kappa}\right) - z ^ {*} \left(\beta_ {\kappa}\right) + q ^ {*} \left(\beta_ {\kappa}\right) \cdot r \left(\beta_ {\kappa}\right) \\ = \tilde {d} _ {\kappa} - z _ {\kappa} ^ {*} + q _ {\kappa} ^ {*} \cdot r _ {\kappa} \\ \end{array}
$$
where *d*~ = d~() and *r* = r() can be publicly computed, and so one proves
$$
\tilde{d}_{\kappa}=\tilde{\mathsf{d}}(\beta_{\kappa})
$$
$$
r_{\kappa}=\ \ {mathsf r(\beta_{\kappa})}
$$
$$
\mathsf{v}_{\kappa}\big(Y\big)\cdot\mathsf{g}_{\kappa}^{*}\big(Y\big)-\big(\tilde{d}_{\kappa}-z_{\kappa}^{*}+q_{\kappa}^{*}\cdot r_{\kappa}\big)\cdot Y^{N}=\mathsf{s}_{\kappa}\big(Y\big)
$$
(6)
2N nN N
with a commitment of s in *R₄* = Zq[*Y*] and a public commitment of *Y*.
$$
s_{\kappa}
$$
$$
Y^{N}
$$
$$
\mathcal{R}_{4}=\mathbb{Z}_{q}[Y^{2N\setminus N}]
$$
Again, from Corollary6, when all the tests pass, the above equations (3), (4), (5), and (6)
(S+1)K=4
are all satised with error probability less than 3 2.
$$
3\varLambda\\cdot2^{-(S+1)K/4}
$$
N
They altogether prove that, for each *2* [[1;]], *d z* + *q r* is the coecient of *Y* in
v (*Y*) g (*Y*), so
$$
Y^{N}
$$
$$
\kappa\in\ \ \ 1;\ Lambda\ ,\,d_{\kappa}-z_{\kappa}^{*}+q_{\kappa}^{*}\cdot r_{\kappa}
$$
$$
\mathsf{v}_{\kappa}(Y)\cdot\mathsf{g}_{\kappa}^{*}(Y)
$$
$$
\tilde{\mathsf{d}}(\beta_{\kappa})=\sum_{j}\mathsf{u}_{j}(\beta_{\kappa})\cdot\mathsf{f}_{j}(\beta_{\kappa})+\mathsf{z}^{*}(\beta_{\kappa})-\mathsf{q}^{*}(\beta_{\kappa})\cdot\mathsf{r}(\beta_{\kappa})\bmod q
$$
for the random, on polynomials committed beforehand. Hence,
$$
\beta_{\kappa}
$$
$$
\tilde{\mathsf{d}}=\sum_{j}\mathsf{u}_{j}\cdot\mathsf{f}_{j}+\mathsf{z}^{*}-\mathsf{q}^{*}\cdot\mathsf{r},
$$
S+1
excepted with error probability bounded by 2*‘n=t n=*2 *N*, for each. Again, these relations
~ and d~*0* (S+1)K=4
hold for both d excepted with error probability bounded by 2 (3 2 +
S+1
(*n=*2 *N*)).
$$
2\ell n/t\leq n/2^{S+1}N
$$
$$
{\kappa\cdot}
$$
$$
\tilde{\mathrm{d}}
$$
$$
\tilde{\mathrm{d}}^{\prime}
$$
$$
2 \times (3 \Lambda \cdot 2 ^ {- (S + 1) K / 4} +
$$
$$
(n/2^{S+1}N)^{\varLambda})
$$
(S+1)K=4 S+1
Globally, the error probability is bounded by 2 (5 2 +2 (*n=*2 *N*)). We thus
S+1 S+1
need to take = log₂(24*="*s)*=*log₂(2 *N=n*) dierent values for so that 4 (*n=*2 *N*)
(S+1)K=4
*"*s*=*6, and *K >* 4 log₂(60*="*s)*=*(*S* + 1) so that 2 5 2 *"*s*=*6 too, so that the global
error on the equations be bounded by *"*s*=*3.
$$
2\,\times\,(5\varLambda\,\cdot2!^{{-(S+1)K/4}}\!+\!2\,\times\!(n/2^{S+1}N)^{\varLambda})
$$
$$
4\times\,(n/2^{S+1}N)^{\varLambda}\leq
$$
$$
\varepsilon_{s}/6.
$$
$$
\varLambda=\lceil\operatorname{l o g}_{2}(24/\varepsilon_{s})/\operatorname{l o g}_{2}(2^{S+1}N/n)\rceil
$$
$$
\beta_{\kappa}
$$
$$
K>4\log_{2}(60\Lambda/\varepsilon_{s})/(S+!1)
$$
$$
2\times5\Lambda\cdot2^{-(S+1)K/4}\leq\varepsilon_{s}\big/6
$$
$$
\varepsilon_{s}/3
$$
On the other hand, as shown on Figure1, the global number of commitments is bounded
by 14 + 5 + 3*Z*. We explain the 3*Z* commitments in the next section to build (z*;*z⁰). We thus
need to take *"*c*"*s*=*(3c) = *"*s*=*(3(14 + 5 + 3*Z*)).
$$
1 4 \Lambda + 5 + 3 Z
$$
$$
(\mathbf{z}^{*},\mathbf{z}^{\prime*})
$$
$$
\varepsilon_{c}\leq\varepsilon_{s}/(3\times\nu_{c})=\varepsilon_{s}/(3(14A+5+3Z))
$$
~ and d~*0*~ ~0
Indeed, after all these steps, on both d, one gets the proof that, in *R*q, (d*;* d) is a
ciphertext of *h* (m)*;* F*i*, if the noise (z*;*z⁰) is correct.
$$
\tilde{\mathrm{d}}^{\prime}
$$
$$
\mathcal{R}_{q},\,(\tilde{\mathsf{d}},\tilde{\mathsf{d}}^{\prime})
$$
$$
(\mathsf{z}^{*},\mathsf{z}^{\prime}\mathsf{*})
$$
---
## 4.4 Proofs on the Noise (z;z⁰)
$$
(\mathbf{z}^{*},\mathbf{z}^{\prime*})
$$
We now have to prove that the polynomials (z*;*z⁰) are indeed of the form
$$
(\mathsf{z}^{*},\mathsf{z}^{\prime*})
$$
$$
(\mathsf{z}^{*},\mathsf{z}^{\prime*})\ {=}\ (\mathsf{p}\cdot\mathsf{u}+\mathsf{e}_{1}\bmod q,\mathsf{p}^{\prime}\cdot\mathsf{u}+\mathsf{e}_{2}\bmod q)\:,
$$
(7)
with coecients of u*;*e₁*;*e₂ small enough for the correctness of the decryption. The sender needs
to make them follow the appropriate distribution for their own privacy. Using noise-ooding,
the sender will thus choose u*;*e₁*;*e₂, commit them in a hidden way, and prove their relationship
with (z*;*z⁰), as a simple public linear combination of commitments.
$$
\mathsf{u},\mathsf{e}_{1},\mathsf{e}_{2}
$$
$$
\mathsf{u},\mathsf{e}_{1},\mathsf{e}_{2}
$$
$$
(\mathsf{z}^{*},\mathsf{z}^{\prime*})
$$
Then, the sender has to prove the bounds on the coecients of u*;*e₁*;*e₂. Let us focus on u (the
same should be done for e₁ and e₂), with the generation of multiple random polynomials rk, for
0
*k* = 1 *:::;Z*, according to a Gaussian distribution on Z with standard deviation. For random
$P
scalarsk[[;]], one asks to see the linear combination r =krk, with coecients
PkP
0
*r*i=k*r*k;ithat follow a Gaussian distribution on Z with standard deviationk.
kPk
0 128
They should thus be smaller than 10k(excepted with probability 2). One can
kP
0 0
thus check that. When true, this at least proves that *jr*k;i*j* 10k10*Z*, with
k
P$
0 0
overwhelming probability. We can thus dene u = rk, for random scalars f 1; 1g. We
k k k
0
then know that *k*u*k₁* 10*Z²*. We will then have to consider this bound *f*or the correctness
of the FHE decryption, the bound *B⁰⁰* on the nal ciphertext error.
$$
\mathrm {u}, \mathrm {e} _ {1}, \mathrm {e} _ {2}
$$
$$
\mathbf{e}_{1}
$$
$$
\mathrm{e}_{2})
$$
$$
k=1\ldots,Z,
$$
$$
r_{k}
$$
$$
\sigma^{\prime}
$$
$$
\delta_ {k} \leftarrow^ {\$} [ - \eta ; \eta ]
$$
$$
\mathrm {r} = \sum_ {k} \delta_ {k} \mathrm {r} _ {k}
$$
$$
r_{i}\,=\,\sum_{k}\delta_{k}r_{k,i}
$$
$$
10\cdot\sigma^{\prime}\cdot\textstyle\sum_{k}\delta_{k}
$$
$$
\sigma^{\prime}\cdot\sum_{k}\delta_{k}
$$
$$
\ r_{k,i}|\,\le\,10\,\ \cdot\,\sigma^{\prime}\,\cdot\,\textstyle\sum_{k}\delta_{k}\,\le\,10Z\,\cdot\,\sigma^{\prime}\eta.
$$
$$
\left\|\mathsf{u}\right\|_{\infty}\leq10Z^{2}\cdot\sigma^{\prime}\eta
$$
$$
\mathsf{u}=\sum_{k}\delta_{k}^{\prime}\mathsf{r}_{k}
$$
$$
\delta_{k}^{\prime}\xleftarrow{\&}\ \{-1,1\}
$$
$$
B^{\prime}
$$
Bounds are explained in detail in AppendixD. To reduce the probability of having false
negatives, linear combinations will be published. In the end we nd that with of the order of
1=5 0 +3
(1*="*s), we have = 5. We can then take *Z* = 8, = 2 *B⁰=*80, and *q* 2 2*tB⁰*(2*nB*+1).
128
This increases the initial size of *q* by + 3 + log more bits. With = 128, *"*s= 2, and
21
= 2, this is 152 more bits.
$$
\left(1 / \varepsilon_ {s}\right) ^ {1 / 5}
$$
$$
\theta=5
$$
$$
Z=8,\sigma^{\prime}=2^{\lambda}B^{\prime}/80
$$
$$
q\approx2^{\lambda+3}\eta\times2t B^{\prime}(2n B\!+\!1)
$$
$$
\lambda+3+\log\eta
$$
$$
\eta=2^{21}
$$
$$
\varepsilon_{s}=2^{-128}
$$
## 4.5 Protocol Overview
Here are all the steps in the interactive version of the protocol, that can be run in 5 rounds:
1.The public information for the encoding and the FHE are provided by the receiver to the
sender;
2.The receiver encrypts their message m *2R*twith possible additional intermediate ciphertexts. They send these ciphertexts;
$$
\in\mathcal{R}_{t}
$$
3.The sender commits their vector F, as f;
$$
\ {{\bf f}^{*}}.
$$
0i
4.The sender computes all the Enc( (m*;i*)) = (ui*;* u), for *i 2* [[0;*N* 1]] from the ciphertexts
sent by the receiver, and sends a compact commitment (*U;U⁰*);
$$
\mathrm {c} \left(\phi (\mathrm {m}, i)\right) = \left(\mathrm {u} _ {i}, \mathrm {u} _ {i} ^ {\prime}\right)
$$
$$
i\in[0;N-1]
$$
$$
(U,U^{\prime})
$$
5.The sender generates but sends hiding commitments of (u*;*e₁*;*e₂);
k;k;k
$$
(\mathsf{u}_{k}^{*},\mathsf{e}_{1,k}^{*},\mathsf{e}_{2,k}^{*})
$$
0
6.from a hash on these commitments, both parties can generate the scalars 2f1;+1g.
Pk
0 0 0
The sender can generate (z*;* z) = (p u + e₁*;* p u + e₂ mod *q*), and send the
k k k;k k;k
~ ~0
resultin*g* ciphertext (d*;* d). The receiver can derive the commitments (*Z;Z⁰*) on (z*;*z⁰);
$$
\delta_{k}^{\prime}\in\{-1,+1\}
$$
$$
(z^{*},mathsf\boldsymbol z{{}^{{\prime**}}})\,=\,\sum_{k}\delta_{k}^{\prime}(\mathsf{p}\cdot\mathsf{u}_{k}^{*}+\mathsf{e}_{1,k}^{*},\mathsf{p}^{\prime}\cdot\mathsf{u}_{k}^{*}+\mathsf{e}_{2,k}^{*}
$$
$$
q q)
$$
$$
(\tilde{\mathbf{d}},\tilde{\mathbf{d}}^{\prime})
$$
$$
(Z^{*},Z^{\prime*})
$$
7.The receiver can ask for (or derive from a hash) scalarsk2 [[;]], times, and the
P
0
sender sends the receiver thek(p u + e₁ mod *q;*p u + e₂ mod *q*) and the
k k;k k;k
aggregation of the random values for the related hidden commitment, so they can check the
coecients are small enough;
$$
(\mathbf{z}^{*},\mathbf{z}^{\prime*})
$$
$$
\delta_{k}\,\in\,[-\eta;\eta],\,\theta
$$
$$
\sum_{k}\delta_{k}(\mathsf{p}\cdot\mathsf{u}_{k}^{*}+\mathsf{e}_{1,k}^{*}
$$
$$
q,\mathsf{p}^{\prime}\cdot\mathsf{u}_{k}^{*}+\mathsf{e}_{2,k}^{*}
$$
$$
q q)
$$
8.from a hash on the (*U;U⁰*), both parties generate a challenge n *2R*t: the sender uses it to
generate and send (b*;*b⁰) and (l*;*l⁰);
$$
(U,U^{\prime})
$$
$$
\mathsf{n}\in\mathcal{R}_{t}
$$
9.The receiver can ask for (or derive from a hash) *f 2* Zq*g*, for *2* [[1;]];
$$
\left\{\beta_{\kappa}\in\mathbb{Z}_{q}\right\}
$$
$$
\mathsf{v}_{\kappa},\mathsf{w}_{\kappa},\mathsf{y}_{\kappa},\mathsf{s}_{\kappa}
$$
10.The sender generates v*;* w*;* y*;*s , as well as g*;* h*;* q*;* z*;*z , and the twin polynomials
0
with, and sends the twin encodings of these polynomials to the receiver;
$$
\kappa\in\left[mathbb;\varLambda\right]
$$
$$
\mathsf{g}_{\kappa}^{*},\mathsf{h}_{\kappa}^{*},\mathsf{q}_{\kappa}^{*},\mathsf{z}_{\kappa}^{*},\mathsf{z}_{\kappa}^{\ }
$$
11.The receiver can ask for (or derive from a hash) *f*(*x*m*;y*m) *2* Z²q*g*, for *m 2* [[0;*M*max]];
$$
\{(x_{m},y_{m})\in\mathbb{Z}_{q}^{2}\}
$$
$$
m\in[0;M_{\mathrm{m a x}}]
$$
12.The sender generates the proofs of all their previous commitments, and the zero-knowledge
proofs on the quadratic relations, with additional random challenges either from the receiver or derived from a hash, and the sender sends the answers to the receiver;
---
13.The receiver veries all the proofs with respect to the twin encodings and the required
~ ~0
quadratic checks to prove the correctness of (b*;*b⁰) and (d*;* d).
In the above protocol, some of the scalars can either be sent by the verier or taken from a hash
function, using the Fiat-Shamir paradigm [FS87].
$$
(\tilde{\mathbf{d}},\tilde{\mathbf{d}}^{\prime})
$$
In the latter setting, the challenges (k)k, () and (*x*m*;y*m)m, and challenges in the zeroknowledge proofs are derived from a hash function on the values that should not be modied by
the prover. This leads to a non-interactive protocol. When they are generated by the verier,
30
leading to a 5-round protocol, the soundness can be reduced to 2, as the prover should then
cheat on-line.
$$
(\delta_{k})_{k},\,(\beta_{\kappa})_{\kappa}
$$
$$
(x_{m},y_{m})_{m}
$$
$$
2^{-30}
$$
## 4.6 Security Claims
The security of such 2PC protocols is two-folds, with privacy and correctness. The former
guarantees that no information leaks about the parties’ inputs beyond the obtained result, and
the latter ensures the result is correct.
Honest-but-Curious Security. In the honest-but-curious case described in denitions1and
2, where the players play honestly, thanks to the correctness of the FHE scheme, the result
obtained after decryption by the receiver is the correct one.
The receiver’s privacy is ensured as they send only ciphertexts of their input message: under
the semantic security of the FHE, no information leaks about m.
The sender’s privacy is also ensured thanks to the hidden commitment on their vector F,
~ ~0
that is statistically hiding, but also with the noise-ooding in the nal ciphertext (d*;* d) that
hides the evaluated circuit too, and thus the vector F, but only reveals *h*F*;*(m)*i*: the sender’s
privacy is statistical.
$$
(\tilde{\mathsf{d}},\tilde{\mathsf{d}}^{\prime})
$$
$$
\langle\mathsf{F},\varPhi(\mathsf{m})\rangle
$$
Security against a Malicious Sender. The goal of our work was to enhance security a
against malicious sender, which can only impact the correctness, as the sender does not receive
any information: thanks to the additional proofs, the receiver has a guarantee of correct output
~ ~0
(d*;* d) and correct decryption.
Contributions. During all the descriptions, we have shown the correctness and soundness
30
of the commitments and proofs. Soundness diers for interactive proofs (with *"*s= 2) and
non-interactive proofs (with *"*s= 2).
$$
\varepsilon_{s}=2^{-30})
$$
$$
\varepsilon_{s}=2^{-\lambda},
$$
Knowledge-soundness comes from the linear-only extractability of the encoding scheme:
the above soundness proves the extracted polynomials are valid witnesses, and satisfy all the
equations.
Thanks to the hiding commitments and the zero-knowledge proofs, the above global proof
is also zero-knowledge from the prover’s point of view: no information leaks on their private
inputs.
*Succinctness.* Beside the security, this is our main goal: the proof essentially consists of a few
millions encodings, plus a similar number of zero-knowledge proofs: communication complexity
only depends on the security parameter. Concrete sizes for the proofs are provided on Figure2,
but we would rst like to show that our construction is asymptotically succinct in the case of
OPE: we want to evaluate f(m) for a polynomial f of degree *N*, using the FV FHE scheme, and
the above SNARK.
*Ciphertexts to be sent:* Let us consider any constant *d 2* N, and dene the basis *b* = *d*(*N* +
P
1=d+1 d i
1) *e*. Then, any *k 2* [[0;*N*]] can be written in basis *b* as *x*i*b*, with *x*i*2* [[0;*b* 1]]. Hence,
i=0
x bi
from the ciphertexts of all the powers mifor *x 2* [[0;*b* 1]] and *i 2* [[0;*d*]], one can compute
i
ciphertexts of all the powers. The verier will thus have to send (*d* + 1)*b* ciphertexts, where
d =d
*b N* so about *dN¹* ciphertexts, and the prover will be able to rebuild all the ciphertexts
with circuits of maximal multiplicative depth *d*.
$$
1)^{1/d+1}
$$
$$
d\in\mathbb{N},
$$
$$
b\,=\,\lceil(N+\,
$$
$$
k\in[0;N]
$$
$$
\textstyle\sum_{i=0}^{d}x_{i}b^{i}
$$
$$
x_{i}\in\ 0;b\!-\!1\!]
$$
$$
\ {mathfrak m}^{x_{i}b^{i}}
$$
$$
x_{i}\in[0;b-1]
$$
$$
i\in[0;d]
$$
$$
b^{d}\sim N
$$
$$
d N^{1/d}
$$
$$
(d+1)b
$$
---
*The Receiver’s Privacy:* As recalled in AppendixE, the semantic security of the FV scheme
relies on the decision Ring-LWE problem, which is related to the SIVP problem with some
*p*
approximation factor (*n*) [PRS17]. If we take = *q* = n, for the Gaussian distribution of
*p*
the secret key a*n*d the noise, then we have (*n*) *q* log*n*, which will be polynomial in *n*, in
our case, as shown below.
$$
\gamma(n)
$$
$$
\sigma=\alpha q={\sqrt{n}},
$$
$$
\gamma(n)\leq q{\sqrt{\log n}}
$$
$$
n,
$$
*The Sender’s Privacy:* In order to hide the evaluated circuit, we add some noise to the nal
result: in order to make the global noise statistically independent of the circuit, we add a noise
2 times larger than the original noise. We discuss below the original noise for the correctness,
and we will then multiply it by 2. The proof of correct noise does not exclude a noise that is
a bit larger, which even improves the sender’s privacy.
$$
2^{\lambda}
$$
$$
2^{\lambda}
$$
*Correctness:* As recalled in AppendixE, using the [LN14] noise derivation formula, the error
noise growth after having evaluated a sequence of *d* multiplications with a fresh ciphertext is
d d 1 d 1
bounded by *C₁V* + *dC₁ C₂* = *C₁* (*C₁V* + *dC₂*), where:
$$
\mathcal{C}_{1}^{d}V+d C_{1}^{d-1}\mathcal{C}_{2}=\mathcal{C}_{1}^{d-1}\cdot\left(\mathcal{C}_{1}V+d C_{2}\right)
$$
$$
C_{1}\leq11t n^{5/2}\qquad\qquad\qquad C_{2}\leq20n^{\frac{3}{2}}t^{2}(n+\ell)\qquad\qquad\qquad V\leq201n^{2}
$$
With reasonable assumptions on our parameters we nd the correctness result on this noise,
and also when it is greatened with the noise ooding, as detailed in AppendixE.
d
*Communication:* With theses parameters, for a xed constant *d*, with *N* = *n*,
$$
N=n^{d}
$$
$$
\operatorname{l o g}t\approx\big(d+1\big)\operatorname{l o g}n\qquad\qquad\quad\operatorname{l o g}q\approx3(d+1)\operatorname{l o g}t\approx3(d+1)^{2}\operatorname{l o g}n.
$$
2
A ciphertext thus consists of 2*n* elements in Zq: 6(*d* + 1) *n*log*n* bits each. The verier rst
1=d+1 d=d+1 2 1=d+1
sends (*d* + 1) (*N* + 1) *dn* ciphertexts, so approximately 6*d*(*d* + 1) *n²* log*n*
~(=d
bits, which is in *O*(*n²* log*n*) = *O N²*).
$$
2n
$$
$$
\mathbb{Z}_{q}\colon6(d+1)^{2}n
$$
$$
(d+1)\lceil(N+1)^{1/d+1}\rceil\,\approx\,d n^{d/d+1}
$$
$$
6d(d+1)^{2}n^{2-1/d+1}
$$
$$
\mathcal{O}(n^{2}\log n)=\tilde{\mathcal{O}}(N^{2/d})
$$
The size of the encoding being only linearly impacted by the size of *q*, we have a proof size
in *O*~(1) when *N* grows. This provides the succinctness of the proof.
$$
\tilde{\cal O{}}(1)
$$
$$
q,
$$
## 5 Applications
The protocol described in this paper can be deployed for several applications, depending on
the function dening the receiver vector ( (m*;*0)*;:::;*(m*;N*)) from which we get the scalar
product with the sender’s vector. Hereafter we detail the cases of PSI (using OPE), and of
SPIR.
$$
\phi
$$
$$
\left(\phi(\mathsf{m},0),\ldots,\phi(\mathsf{m},N)\right)
$$
## 5.1 Application to Private Set Intersection
As already explained, we can apply this technique to PSI, where the receiver owns a set *X* =
*fx₁;:::;x*a*g* of cardinality #*X*, the sender a set *Y* = *fy₁;:::;y*b*g* of cardinality #*Y*, and the
receiver wants to learn the intersection. We consider the case where #*Y* is much larger than
#*X*, and hope to get a protocol essentially linear in #*X* only. To this aim, we follow the basic
Q
N
approach from [FNP04], with the polynomial *P* (*Y*) = (*Y* hi) committed once for all in
i=1
*P*, where the values hi*2R*tencode the elements *y*iin the sender’s set, and the degree *N* = #*Y*.
Then the receiver wants to check whether *P* (*x*i) = 0 on every input *x*i.
$$
\chi=
$$
$$
\{x_{1},\ldots,x_{a}\}
$$
$$
\#\boldsymbol{x}
$$
$$
\mathcal{Y}=\left\{y_{1},\ldots,y_{b}\right\}
$$
$$
\#y
$$
$$
\#y
$$
$$
\#\chi
$$
$$
\textstyle{P(Y)=\prod_{i=1}^{N}(Y-\mathsf{h}_{i})}
$$
$$
\mathsf{h}_{i}\in\mathcal{R}_{t}
$$
$$
P^{*}
$$
$$
y_{i}
$$
$$
P(x_{i})=0
$$
$$
N=\#y
$$
$$
x_{i}
$$
Thanks to the veriability of our proof, and even the knowledge-soundness of our commitments, our PSI protocol is secure against malicious senders, as they cannot use distinct
polynomials as *P* in each execution.
The protocol can be adapted to support adding elements to the sender’s set, with a new
check to make sure the old sender’s polynomial divides the new one which only has additional
roots.
---
| $|N| | |n| | d | $\ell$ | S | |t| | |q| | ReceiverCommun. | | |N| | SenderCommunications | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | | | | | FHESecurity | TotalSize | | $\varepsilon_{s}:2^{-30}$ | ; $2^{-80}$ | ; $2^{-128}$ |
| 20 | 14 | 4 | 14 | 21 | 47 | 656 | 100 | 218MB | 2133 | 8MB | 74MB | 267MB |
| 25 | 15 | 5 | 16 | 16 | 48 | 753 | 251 | 636MB | 2430 | 13MB | 137MB | 503MB |
| 30 | 14 | 5 | 16 | 11 | 48 | 753 | 81 | 583MB | 2434 | 24MB | 271MB | 1.03GB |
| 30 | 15 | 5 | 15 | 20 | 56 | 839 | 209 | 1.3GB | 2693 | 9MB | 90MB | 324MB |
| 35 | 15 | 5 | 15 | 15 | 56 | 839 | 209 | 2.28GB | 2698 | 14MB | 149MB | 550MB |
| 35 | 15 | 5 | 14 | 25 | 66 | 922 | 179 | 2.51GB | 2947 | 6MB | 54MB | 207MB |
| 40 | 15 | 5 | 15 | 10 | 56 | 839 | 209 | 4.01GB | 2703 | 26MB | 317MB | 1.2GB |
$$
\varepsilon_{s}:2^{-30}
$$
$$
;,2^{-80}
$$
$$
;2^{-128}
$$
Fig. 2. Parameters and Security Bounds for the Fully Homomorphic Encryption (FHE) and the Proof, with
S
*t* 2 4*N‘*. FHE size encompasses all the ciphertexts sent by an honest-but-curious receiver, and the proof sizes
columns encompass all the elements the sender (with enforced honest behavior) sends back, including cleartexts.
*jxj* is the bit-length of *x*.
$$
t\geq2^{S}\cdot4N\ell
$$
$$
x.
$$
## 5.2 Application to Symmetric Private Information Retrieval
In the Symmetric PIR setting, the sender owns a set *Y* = *fy₁;:::;y*N*g* of cardinality *N*, and
the receiver wants to retrieve an element of the sender’s set with a private index. To this aim,
the sender denes F as a vector of representations of their set elements in *R*t, the receiver a
representation m = () of their index in *R*t(optimizations could be made using a smaller
space than *R*t), and we apply our scheme with (m*;j*) =;j, where is the Kroenecker
P P
d k d k
symbol. Writing and *j* in the basis *b* with =kb and j = jk*b*, where the
k=0 k=0
k*;j*k*2* [[0;*b* 1]]:
d d
Y Y
$$
\mathcal{Y}=\left\{y_{1},\ldots,y_{N}\right\}
$$
$$
N,
$$
$$
\mu,
$$
$$
\mu
$$
$$
{\mathcal{R}}_{t},
$$
$$
\ {mathfrak m=}tau(\mu)
$$
$$
\ {mathcal R R}_{t}
$$
$$
\ \mathcal{R}_{t})
$$
$$
\phi(\mathsf{m},j)\,=\,\delta_{\mu,j}
$$
$$
\delta
$$
$$
\mu
$$
$$
j
$$
$$
\mu=\sum_{k=0}^{d}\mu_{k}b^{k}
$$
$$
j\,=\,\sum_{k=0}^{d}j_{k}b^{k}
$$
$$
\mu_ {k}, j _ {k} \in [ 0; b - 1 ]
$$
$$
\phi(\tau(\mu),j)=\delta_{\mu,j}=\delta_{\sum_{k=0}^{d}\mu_{k}b^{k},\sum_{k=0}^{d}j_{k}b^{k}}=\prod_{k=0}^{d}\delta_{\mu_{k},j_{k}}=\prod_{k=0}^{d}\phi(\tau(\mu_{k}),j_{k})
$$
So sending the encryptions of (m*;k;i*) = ( (i)*;k*) =i;kfor *i 2* [[0;*d*]]*;k 2* [[0;*b* 1]]
allows the sender to calculate all the required ciphertexts with circuits of multiplicative depth
*d* =d
d. Because *b N*, the receiver sends (*d* + 1)*b dN¹* ciphertexts. This is the same number
of ciphertexts as in the PSI application.
$$
\psi(\mathsf{m},k,i)\,=\,\phi\big(\tau(\mu_{i}),k\big)\,=\,\hat{\delta}_{\mu_{i},k}
$$
$$
i\,\in\,[0;d],k\,\in\,[0;b-1]\,
$$
$$
b^{d}\sim N
$$
$$
(d+1)b\approx d N^{1/d}
$$
This can also be adapted to growing sender databases, adding new elements as coecients
of the sender polynomial and making sure the dierence of the new one and the old one only
has monomials of a specied degree range.
## 5.3 Experiments
Parameters and Sizes. Concrete sizes are provided in Figure2, for one execution of our
OPE protocol on a polynomial of degree *N*. Security bounds on the privacy of FHE use the
20 40
LWE estimator [APS15], for *N* between 2 and 2, for a variable security margin *S* 6 in
S
*t* 2 2*‘D*. Indeed, the size of the proof depends a lot on. The larger *N=n* is, the shorter
the proof, but *S* also has a huge impact, as shown on Figure2, when *S* makes decrease, with
the number of encodings. However, when *S* grows, so does *t*, which can lower FHE security and
make the FHE ciphertexts heavier. In Figure2, parameter sets either in favor of lowering the
weight of the receiver or the sender’s communications are given for a particular *N*.
$$
2^{20}
$$
$$
2^{40}
$$
$$
S\geq6
$$
$$
t\geq2^{S}\times2\ell\mathcal{D}
$$
$$
N/n
$$
In this gure, the parameter was not toggled, as our choice seemed a good compromise
between FHE ciphertexts size and proof sizes, but of course it could be.
$$
\phi
$$
One can note these results are quite practical, in particular with the interactive version,
where only a few MBytes have to be sent for the proof, which is much less than for the FHE
ciphertexts, even for high security levels. A python script to test more parameters is provided
in AppendixF, along with a description of all the optimizations performed in this script.
## References
APS15.Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors.
*Journal of Mathematical Cryptology*, 9(3):169{203, 2015.
---
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.
+
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.
BEHZ16.Jean-Claude Bajard, Julien Eynard, M. Anwar Hasan, and Vincent Zucca. A full RNS variant of FV
like somewhat homomorphic encryption schemes. In Roberto Avanzi and Howard M. Heys, editors,
*SAC 2016*, volume 10532 of *LNCS*, pages 423{442. Springer, Heidelberg, August 2016.
2k
BGM93.Ian F. Blake, Shuhong Gao, and Ronald C. Mullin. Explicit factorization of *x* + 1 over F*p* with
prime *p* = 3 mod 4. *Appl. Algebra Eng. Commun. Comput.*, 4:89{94, 1993.
BN00.Daniel Bleichenbacher and Phong Q. Nguyen. Noisy polynomial interpolation and noisy Chinese
remaindering. In Bart Preneel, editor, *EUROCRYPT 2000*, volume 1807 of *LNCS*, pages 53{69.
Springer, Heidelberg, May 2000.
CHLR18.Hao Chen, Zhicong Huang, Kim Laine, and Peter Rindal. Labeled PSI from fully homomorphic
encryption with malicious security. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng
Wang, editors, *ACM CCS 2018*, pages 1223{1237. ACM Press, October 2018.
CL01.Yan-Cheng Chang and Chi-Jen Lu. Oblivious polynomial evaluation and oblivious neural learning. In
Colin Boyd, editor, *ASIACRYPT 2001*, volume 2248 of *LNCS*, pages 369{384. Springer, Heidelberg,
December 2001.
CLR17.Hao Chen, Kim Laine, and Peter Rindal. Fast private set intersection from homomorphic encryption.
In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, *ACM CCS 2017*,
pages 1243{1255. ACM Press, October / November 2017.
Dam92.Ivan Damgard. Towards practical public key systems secure against chosen ciphertext attacks. In
Joan Feigenbaum, editor, *CRYPTO’91*, volume 576 of *LNCS*, pages 445{456. Springer, Heidelberg,
August 1992.
FNP04.Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Ecient private matching and set intersection.
In Christian Cachin and Jan Camenisch, editors, *EUROCRYPT 2004*, volume 3027 of *LNCS*, pages
1{19. Springer, Heidelberg, May 2004.
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.
FS87.Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identication and signature
problems. In Andrew M. Odlyzko, editor, *CRYPTO’86*, volume 263 of *LNCS*, pages 186{194. Springer,
Heidelberg, August 1987.
FV12.Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology
ePrint Archive, Report 2012/144, 2012. http://eprint.iacr.org/2012/144.
Gen09.Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor,
*41st ACM STOC*, pages 169{178. ACM Press, May / June 2009.
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, *EURO-*
*CRYPT 2013*, volume 7881 of *LNCS*, pages 626{645. Springer, Heidelberg, May 2013.
Gil99.Niv Gilboa. Two party RSA key generation. In Michael J. Wiener, editor, *CRYPTO’99*, volume 1666
of *LNCS*, pages 116{129. Springer, Heidelberg, August 1999.
GNN17.Satrajit Ghosh, Jesper Buus Nielsen, and Tobias Nilges. Maliciously secure oblivious linear function
evaluation with constant overhead. Cryptology ePrint Archive, Report 2017/409, 2017. http://
eprint.iacr.org/2017/409.
Haz18.Carmit Hazay. Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs.
*Journal of Cryptology*, 31(2):537{586, April 2018.
HL09.Carmit Hazay and Yehuda Lindell. Ecient oblivious polynomial evaluation with simulation-based
security. Cryptology ePrint Archive, Report 2009/459, 2009. http://eprint.iacr.org/2009/459.
HN12.Carmit Hazay and Kobbi Nissim. Ecient set operations in the presence of malicious adversaries.
*Journal of Cryptology*, 25(3):383{433, July 2012.
HT10.Carmit Hazay and Tomas Toft. Computationally secure pattern matching in the presence of malicious
adversaries. In Masayuki Abe, editor, *ASIACRYPT 2010*, volume 6477 of *LNCS*, pages 195{212.
Springer, Heidelberg, December 2010.
JL09.Stanislaw Jarecki and Xiaomin Liu. Ecient oblivious pseudorandom function with applications to
adaptive OT and secure computation of set intersection. In Omer Reingold, editor, *TCC 2009*, volume
5444 of *LNCS*, pages 577{594. Springer, Heidelberg, March 2009.
KZG10.Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials
and their applications. In Masayuki Abe, editor, *ASIACRYPT 2010*, volume 6477 of *LNCS*, pages
177{194. Springer, Heidelberg, December 2010.
$$
x^{2^{k}}+1
$$
$$
\mathbb{F}_{p}
$$
---
LN14.Tancrede Lepoint and Michael Naehrig. A comparison of the homomorphic encryption schemes FV
and YASHE. In David Pointcheval and Damien Vergnaud, editors, *AFRICACRYPT 14*, volume 8469
of *LNCS*, pages 318{335. Springer, Heidelberg, May 2014.
LP00.Yehuda Lindell and Benny Pinkas. Privacy preserving data mining. In Mihir Bellare, editor,
*CRYPTO 2000*, volume 1880 of *LNCS*, pages 36{54. Springer, Heidelberg, August 2000.
NP99.Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In *31st ACM STOC*,
pages 245{254. ACM Press, May 1999.
Pai99.Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques
Stern, editor, *EUROCRYPT’99*, volume 1592 of *LNCS*, pages 223{238. Springer, Heidelberg, May
1999.
PRS17.Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandomness of ring-LWE for any
ring and modulus. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, *49th ACM STOC*,
pages 461{473. ACM Press, June 2017.
PRTY20.Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. PSI from PaXoS: Fast, malicious private
set intersection. In Anne Canteaut and Yuval Ishai, editors, *EUROCRYPT 2020, Part II*, volume
12106 of *LNCS*, pages 739{767. Springer, Heidelberg, May 2020.
Sch80.Jack T. Schwartz. Fast probabilistic algorithms for verication of polynomial identities. *Journal of*
*ACM*, 27(4):701{717, 1980.
SYY99.Tomas Sander, Adam Young, and Moti Yung. Non-interactive cryptocomputing for NC1. In *40th*
*FOCS*, pages 554{567. IEEE Computer Society Press, October 1999.
TP11.Jonathan T. Trostle and Andy Parrish. Ecient computationally private information retrieval from
anonymity or trapdoor groups. In Mike Burmester, Gene Tsudik, Spyros S. Magliveras, and Ivana
Ilic, editors, *ISC 2010*, volume 6531 of *LNCS*, pages 114{128. Springer, Heidelberg, October 2011.
Ver11.Damien Vergnaud. Ecient and secure generalized pattern matching via fast Fourier transform. In
Abderrahmane Nitaj and David Pointcheval, editors, *AFRICACRYPT 11*, volume 6737 of *LNCS*,
pages 41{58. Springer, Heidelberg, July 2011.
Yao86.Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In *27th FOCS*,
pages 162{167. IEEE Computer Society Press, October 1986.
ZB05.Huafei Zhu and Feng Bao. Augmented oblivious polynomial evaluation protocol and its applications.
In Sabrina De Capitani di Vimercati, Paul F. Syverson, and Dieter Gollmann, editors, *ESORICS 2005*,
volume 3679 of *LNCS*, pages 222{230. Springer, Heidelberg, September 2005.
Zip79.Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, *Symbolic*
*and Algebraic Computation, EUROSAM ’79*, volume 72 of *LNCS*, pages 216{226. Springer, 1979.
---
# Supplementary Material
## A SNARKs and zk-SNARKs
Let us recall the formal denition of (zero-knowledge) succinct non-interactive arguments of
knowledge (zk-SNARKs), for a Boolean relation *R* on words or statements *u* and witnesses *w*,
of an NP language.
$$
w,
$$
Denition 9(SNARK). *A SNARK is dened by three algorithms,*
Gen(1*; R*): *on input a security parameter 2* N *and an* NP *relation R, the generation algorithm*
*outputs a common reference string* crs*;*
$$
\mathsf{G e n}(1^{\lambda},\mathcal{R})
$$
$$
\lambda\in\mathbb{N}
$$
Prove(crs*;u;w*): *given a common reference string* crs*, an instance u and a witness w such that*
*R*(*u;w*) = true*, this algorithm produces a proof;*
$$
\ \!(\mathsf{C r s},u,w)
$$
$$
\ {mathcal R(u,w)}=\mathsf{t r u e}
$$
Ver(crs*;u;*): *on input the common reference string* crs*, an instance u, and a proof, the verier*
*algorithm outputs* false *(reject) or* true *(accept);*
*satisfying the following properties:*
$$
\mathsf{V e r}(\mathsf{c r s},u,\pi)
$$
$$
u,
$$
Correctness. *For all valid statement u (i.e., it exists a witness w such that R*(*u;w*) = true*),*
$$
\ {mathcal R(u,w)=\mathsf{t r u e})}
$$
$$
\operatorname*{P r}\left[\mathsf{V e r}(\mathsf{c r s},u,\pi)=\mathsf{f a l s e}\Big|\:\mathsf{c r s}\leftarrow\mathsf{G e n}(1^{\lambda},\mathcal{R}),\pi\leftarrow\mathsf{P r o v e}(\mathsf{c r s},u,w)\right]=\mathsf{n e g l}(\lambda);
$$
Succintness. *The size of the proof is linear in the security parameter, i.e. independent of*
*the size of the computation or the witness;*
$$
\lambda,
$$
Knowledge-Soundness. *for the class Z of auxiliary input generators: for any* PPT *adversary*
KS
*A there exists a* PPT *extractor* ExtA*such that:*
$$
\mathcal{Z}
$$
$$
\ ^{A^{K S}}
$$
$$
\mathsf{E x t}_{\mathcal{A}}
$$
$$
\operatorname{{{operatorname*{P r}}}}\left[\begin{matrix}{\ \mathsf{V e r}(\mathsf{c r s},u,\pi)=\mathsf{t r u e}}&{\ \mathsf{c r s}\leftarrow\mathsf{G e n}(1^{\lambda},\mathcal{R}),\mathsf{a x x}\leftarrow\mathcal{Z}(\mathsf{c r s})}\\ {\wedge\ \mathcal{R}(u,w)=\mathsf{f a l s e}}&{\ \ (u(,\pi);w)\leftarrow(\mathcal{A}^{\mathsf{K S}}\|\mathsf{E x t}_{\mathcal{A}})(\mathsf{c r s},\mathsf{a u x})}\\ \end{matrix}\right]=\mathsf{n e g l}(\lambda).
$$
*Intuitively, this means that for any prover able to produce a valid proof for a statement in the*
*language, there exists an ecient extractor that outputs a witness for the given statement;*
crs Prove
Zero Knowledge. *There exists a stateful interactive polynomial-size simulator* Sim = (Sim*;*Sim)
*such that for all stateful interactive distinguishers D, for every large enough security param-*
*eter 2* N*, every auxiliary input* aux*, the two probabilities are negligibly close:*
$$
{\mathsf{S i m}}=({\mathsf{S i m}}^{\mathsf{c r s}},{\mathsf{S i m}}^{\mathsf{P r o v e}})
$$
$$
\lambda\in\mathbb{N}
$$
$$
\operatorname*{P r}[\mathcal{R}(u,w)=\mathsf{t r u e}\wedge\mathcal{D}(\pi)=1\,|\,\mathsf{c r s}\leftarrow\mathsf{G e n}(1^{\lambda},\mathcal{R}),(u,w)\leftarrow\mathcal{D}(\mathsf{c r s},\mathsf{a w v}),
$$
$$
\pi\leftarrow{\mathsf r o o v e}(\ \mathsf{c r s},u,w)];
$$
$$
\begin{array}{c}{\operatorname*{P r}[\mathcal{R}(u,w)=\mathsf{t r u e}\land\mathcal{D}(\pi)=1\mid(\mathsf{c r s s},\mathsf{t r a p})\leftarrow\mathsf{S i m}^{\mathsf{c r s}}(1^{\lambda}),(u,w)\leftarrow\mathcal{D}(\mathsf{c r s},\mathsf{a u x}),}\\ {\pi\leftarrow\mathsf{S i m}^{\mathsf{P o r s}}(\mathsf{c r s},\mathsf{t r a p},u,\mathsf{a u x})].}\\ \end{array}
$$
## B Encodings
In this section we illustrate the denition of secure encodings with two distinct constructions.
the rst provides public veriability whereas the second will be for designated verier only.
## B.1 Encodings over R = Zqfrom Pairings
$$
\mathsf{R}=\mathbb{Z}_{q}
$$
The Knowledge of Exponent Assumption, introduced by Damgard [Dam92] states that given
*g* and *g* in a group G, it is hard to create *c* and ^*c* in that group G so that ^*c* = *c*, without
a a
knowing *a* such that *c* = *g*. The only way to compute ^*c* being to generate (*g*).
$$
g^{\alpha}
$$
$$
g
$$
$$
\hat{c}
$$
$$
\mathbb{G}
$$
$$
\hat{c}=c^{\alpha}
$$
$$
\hat{c}
$$
$$
c=g^{a}
$$
$$
(g^{\alpha})^{a}
$$
---
In a pairing-friendly setting pk = (G₁*;*G₂*;* GT*;q;g;*g*;e*), one can check the appropriate relation between *c* and *c*^, with g. We can thus consider such a pairing-friendly setting with
q = p₁ ::: p‘a product of ‘ prime integers p₁ < ::: < p‘(possibly with ‘ 6= 1, so that Zq
is a ring, but not necessarily a eld), we denote *G* = *e*(*g;* g). The verication key is vk = g
$a a a 2
for the secret key Zq: the encoding function Eskis Esk(*a*) = (*g;g;* g) *2* G₁ G₂. It
is clearly *L*-linearly-homomorphic for any *L*. The bilinear map *e* allows public quadratic root
a a
verication, on the elements *g* and g : for example, *Q* = *X₁ X₂ X₃* on encodings of *a₁*, *a₂*
a1a2a3Q(a1;a2;a3)
and *a₃*, it can be done with *e*(*g;* g) *e*(*g;*g) = *e*(*g;* g). This must be done after
a a a a
image verication of any individual encoding with *e*(*g;*g) = *e*(*g;*g) and *e*(*g;*vk) = *e*(*g;*g).
They are both public, as vk is public.
$$
\ {mathfrak p k}=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},\mathfrak{q},\mathfrak{g},\mathfrak{g},\mathfrak{g},\mathfrak{e})
$$
$$
\hat{c}_{,}
$$
$$
\mathfrak{g}^{\alpha}
$$
$$
p_{1}<\ldotsisuch that *Q*(*a₁;:::;a*L) = *c*i*b*imod *q* is satised, one has to prove the knowledge of (*c*i)i
such that
Y
*Q*(*a*1*;:::;a*) *b c*
V = e(g; g) = e(g;g)
$$
E^{\prime}=(g,g^{\alpha},\mathfrak{g})
$$
$$
\mathcal{M}=\mathbb{Z}_{a}
$$
$$
\mu
$$
$$
c_{i}
$$
$$
Q(a_{1},\ldots,a_{L})=\textstyle c_{i}b_{i}
$$
$$
q
$$
$$
V=e(g,{mathfrak}g)^{Q(a_{1},\ldots,a_{L})}=\prod e(g^{b_{i}},{\mathfrak{g}})^{c_{i}}
$$
$$
(c i).
$$
Q(a1;:::;aL)
which can be done with a classical Schnorr-proof, from the encodings Esk(*b*i), as *V* = *e*(*g;* g)
can be computed thanks to the pairing. Using the Fiat-Shamir paradigm[FS87], this proof can
$Q
biki
be non-interactive: with random exponents *k*iZq, the prover sets *D* = *e*(*g;*g), gets
a random challenge e = H(V; fEsk(bi)g;D) 2 [[0; 2]], with 2 < p₁, and generates the proof
= (*fs*i= *k*i*ec*imod *qg;e*) *2* Zq[[0; 2]]. The verier can compute
Y
$$
\ {sf E E}_{\sf s k}(b_{i})
$$
$$
V=e(g,{\mathfrak{g}})^{Q(a_{1},\ldots,a_{L})}
$$
$$
k_{i}\xleftarrow{9}\mathbb{Z}_{q}
$$
$$
\textstyle{=\prod e(g^{b_{i}},{\mathfrak{g}})^{k_{i}}}
$$
$$
e=\mathcal{H}(V,\{\mathsf{E}_{\mathsf{s k}}(b_{i})\},D)\in[0;2^{\lambda}
$$
$$
2^{\lambda}\,<\,p_{1}
$$
$$
\ \mathit Pi\!=\left(\{s{_i==k k_i}-e c_{i}\right.
$$
$$
q\},e)\in\mathbb{Z}_{q}^{\mu}\times[0;2^{\lambda}]
$$
$$
D^{\prime}=\prod e(g^{b_{i}},\mathfrak{g})^{s_{i}}\times V^{e}
$$
? 0
and check whether *e* = *H*(*V; f*Esk(*b*i)*g;D*). Indeed, if the statement is true
Y Y Y
$$
e\stackrel{?}{=}\mathcal{H}(V,\{\mathsf{E}_{\mathsf{s k}}(b_{i})\},D^{\prime})
$$
$$
\begin{aligned}{\prod e(g^{b_{i}},\mathfrak{g})^{s_{i}}\times V^{e}}&{{}=\prod e(g^{b_{i}},\mathfrak{g})^{s_{i}}\times(\prod e(g^{b_{i}},\mathfrak{g})^{c_{i}})^{e}}\\ {}&{{}=\prod e(g^{b_{i}},\mathfrak{g})^{s_{i}+e c_{i}}=\prod e(g^{b_{i}},\mathfrak{g})^{k_{i}}=D.}\\ \end{aligned}
$$
The linear-only extractability relies on the above Knowledge of Exponent Assumption, that
requires the hardness of the discrete logarithm in the bilinear generic group model, which
additionally requires all prime factors *p*kto be large enough (at least 2 bits, for a security
parameter). An encoding is a tuple of elements in *E* = G²1G₂, and a zero-knowledge proof
of scalars contains elements from Zqand the challenge in [[0; 2]]. If case of multiple proofs,
one can use a unique global challenge *e*, and the same (*k*i*;s*i) can be used for the same private
0 0
scalars *c*i. Hence, globally, the size if thus elements from Zqwhere is the total number of
private scalars, independently of the number of equations, plus one challenge. The requirement
of large prime factors will be prohibitive when used with Fully Homomorphic Encryption, as
this will make quite large *q*, the modulus of the ciphertext space. We thus do not detail more.
$$
p_{k}
$$
$$
\lambda)
$$
$$
\mathcal{E}=\mathbb{G}_{1}^{2}\times\mathbb{G}_{2}
$$
$$
\mu
$$
$$
\mu
$$
$$
\mathbb{Z}_{q}
$$
$$
\left[0;2^{\lambda}\right]
$$
$$
(k_{i},s_{i})
$$
$$
e,
$$
$$
c_{i i}.
$$
$$
\mu^{\prime}
$$
$$
\mu^{\prime}
$$
$$
\mathbb{Z}_{q}
$$
$$
q,
$$
## B.2 Encodings over R = Zqfrom a Linear-Only Encryption Scheme
$$
\mathsf{R}=\mathbb{Z}_{q}
$$
Given a linear-only encryption scheme (Enc*;*Dec) from Zqonto *C*, for any integer *q*, one chooses a
$
random private element Zq, to be the secret key of the encoding. Then, pk is the public key
of the encryption scheme, while vk is together with the secret decryption key of the encryption
scheme. It is thus private. Then, the encoding function Eskis Esk(*a*) = (Enc(*a*)*;*Enc( *a*)) *2CC*.
It is clearly linearly-homomorphic from an additively-homomorphic encryption scheme. The
decryption algorithm allows any root verication using the decryption key in vk, while the
image verication tests whether the two decryption values verify the secret ratio. The linearonly extractability depends on the specic encryption scheme: but either the encryption scheme
is fully/somewhat homomorphic, or this property is satised. An encoding is a pair of elements
in *E* = *CC*.
$$
\mathbb{Z}_{q}
$$
$$
\alpha\xleftarrow{\ }mathbb Z{}_{q}^{*}
$$
$$
\mathsf{E}_{\mathsf{s k}}(a)=(\mathsf{E n c}(a),\mathsf{E n c}(\alpha{\cdot}a))\in\mathcal{C}{\times}\mathcal{C}
$$
$$
\mathsf{E_{s k}}
$$
$$
\alpha
$$
$$
\mathcal{E}=\mathcal{C}\times\mathcal{C}
$$
---
More concretely, one can use Paillier encryption scheme [Pai99] with a large RSA modulus
x *N* 2$
N, the encryption of *x 2* ZNis *E* = (1 + *N*) *r* mod *N*, for *r* Z. The ciphertext space
N
is thus *C* = Z2. For the decryption, one needs the value *’* = *’*(*N*) which is equivalent of the
N
’ x’
knowledge of the factorisation of *N*: as *’*(*N²*) = *N ’*, *E* = (1 + *N*) = 1 + *x’ N* mod *N²*.
If *’* is invertible modulo *N*, one can extract *x* modulo *N*.
$$
E=(1+\mathcal{N})^{x}\cdot r^{\mathcal{N}}
$$
$$
x\in\mathbb{Z}_{\mathcal{N}}
$$
$$
r \leftarrow^ {\$} \mathbb {Z} _ {\mathcal {N}} ^ {*}
$$
$$
\ {\mathcal N}
$$
$$
\ {cal\Lambda}.
$$
$$
\mathcal{C}=\mathbb{Z}_{N\^{2}}^{*}
$$
$$
\varphi=\varphi(\mathcal{N})
$$
$$
\mathcal{N}:
$$
$$
\varphi(\mathcal{N}^{2})=\mathcal{N}\varphi,\:E^{\varphi}=(1+\mathcal{N})^{x\varphi}=1+x\varphi\cdot\mathcal{N}
$$
$$
\mathcal{N}
$$
$$
\mathcal{N}^{2}
$$
$$
\operatorname{I f}\varphi\,
$$
$$
\ {cal\Lambda}.
$$
For the encoding, the public key pk is thus the modulus *N*, the secret key sk is a random
$
element Z, and the verication key vk is the decryption key *’*(*N*) and the secret value
N
:
$$
\varphi(\mathcal{N})
$$
$$
\alpha\xleftarrow{\S}\mathbb{Z}_{\mathcal{N}}^{*}
$$
N
{ Verifyvk(*C₀;C₁*) rst decrypts both ciphertexts using *’*(*N*) to get *x₀;x₁* mod *N*, and checks
whether *x₁* = *x₀* mod *N*.
$$
-\,{\sf V e r i f y}_{\sf v k}(C_{0},C_{1})
$$
$$
\varphi(\mathcal{N})
$$
$$
x_{0},x_{1}
$$
$$
\ {cal\Lambda,}
$$
$$
x_{1}=\alpha\cdot x_{0}
$$
$$
\mathcal{N}
$$
## An encoding is thus 4 logN bit-long.
We want an encoding on Zq, one can thus take *N > q* to encode elements *x 2* [[0;*q* 1]].
Decoding rst decrypts both ciphertexts modulo *N*, with the elements in [[*N =*2; *N =*2]], checks
the relation with modulo *N*, and reduces it again modulo *q* in [[0;*q* 1]] to extract the encoded
value in Zq. For further verications (quadratic checks), one just considers the decryption of
the rst ciphertext in [[*N =*2; *N =*2]], and relations among the cleartexts.
$$
\mathbb{Z}_{q}.
$$
$$
\mathcal{N}>q
$$
$$
x\in[0;q-1]
$$
$$
\ {cal\Lambda N}
$$
$$
[ \ll - \mathcal {N} / 2; \mathcal {N} / 2 ] ]
$$
$$
\ {cal\Lambda..}
$$
$$
[ 0; q - 1 ]
$$
$$
\mathbb{Z}_{q}.
$$
$$
[ - \mathcal {N} / 2; \mathcal {N} / 2 ]
$$
xi2$
From *L* ciphertexts *E*i= (1 + *N*) *r*iNmod N, for riZ, one can compute the linear
Q*N*PQ
i cixi i N
combination with coecients smalle*r* than *q*, *E* = (1 + *N*) ( *r*), which is an
P PicPic
encryption of ciximod N. It decodes to cixiif j cixij < N =2: we thus have to take
*N >* 2*L q²* if the encodings are fresh encodings that encrypt elements in [[0;*q* 1]]. For a
quadratic check, using vk, the verier can decrypt all the encodings modulo *N* and reduce them
modulo *q* to check the relation modulo *q*. There is no more constraint on *N*.
$$
E_{i}=(1+\mathcal{N})^{x_{i}}\cdot r_{i}^{\cdot{\mathcal{N}}}
$$
$$
\mathcal {N} ^ {2}
$$
$$
r_{i}\xleftarrow{\S}\mathbb{Z}_{\mathcal{N}}^{*},
$$
$$
q, \prod E _ {i} ^ {c _ {i}} = (1 + \mathcal {N}) ^ {\sum c _ {i} x _ {i}} \cdot (\prod r _ {i} ^ {c _ {i}}) ^ {\mathcal {N}}
$$
$$
\sum c_{i}x_{i}
$$
$$
\sum c_{i}x_{i}
$$
$$
\big|\sum c_{i}x_{i}\big|\,<\,\mathcal{N}/2
$$
$$
\mathcal {N} > 2 L \cdot q ^ {2}
$$
$$
[ 0; q - 1 ]
$$
$$
\mathcal{N}
$$
To hide the content of an encoding, even with respect to the owner of the secret key, one
uses a random encoding of a random private mask in [[0; 2 *Lq²*]], to act as a statistically hiding
one-time pad, furthermore randomized with *N*-th powers to remove any information in the
initial random coins. In this case, one needs *N >* 2*L* 2 *q²* for correct decryption modulo *N*,
without wrapping around modulo *N* before the reduction modulo *q*. Hence *M* = [[0; 2 *Lq²*]].
$$
[ 0; 2 ^ {\lambda} L q ^ {2} ]
$$
$$
\mathcal{N}
$$
$$
\mathcal{N}>2L\cdot2^{\lambda}q^{2}
$$
$$
q.
$$
$$
\mathcal{M}=[0;2^{\lambda}L q^{2}]\,
$$
About the zero-knowledge verication ZKLQCheck(Q;(Ei)i; (E)i), to prove the existence of
Pi0
coecients *c*i*2M* such that *Q*(*a₁;:::;a*L) = *c*i*b*imod *q* is satised, on the encodings *E₁* =
0
Esk(*a₁*), . . . , *E*L= Esk(*a*L), *E₁* = Esk(*b₁*), . . . , *E⁰* = Esk(*b*), one has to prove the knowledge
of (*c*i) in *V* = Eval(*fE g; fc*i*g*), for *i 2* [[1;]], where the verier knows, after decryption of the
i0
0 Q(a1;:::;aL) mod q
encodings (*E*i)iand quadratic computations modulo *q*, *V* = (1 + *N*) mod *N²*.
0 0
One wants to prove that *V* and *V* decrypt to the same value modulo *q*: *V* = *V* (1 +
qr1*N*
N) *r₀* mod *N²*, but for unknown values *r₀;r₁*. We stress that we only consider the rst
ciphertext in the encodings. One thus proves the knowledge of ci2M for i 2 [[1;]] such that
Q*c*
i 0 qr1N 2 2
*V* = *E* = *V* (1+*N*) *r₀* mod *N*. The *c*i’s are the masks in [[0; 2 *Lq*]], but one can use
i0
their *q*-reduction. Then, as the encodings *E* can encrypt elements in [[ *Lq²*;*Lq²*]], *jr₁qj Lq³*.
i0
$$
c_{i}\in\mathcal{M}
$$
$$
(Q,(E_{i})_{i};(E_{i}^{\prime})_{i})
$$
$$
Q(a_{1},\ldots,a_{L})=\sum c_{i}b_{i}
$$
$$
E_{1}=
$$
$$
\ {sf E}_{\sf s k}(a_{1}),\ \ldots,\;E_{L}\:=\:{\sf E}_{\sf s k}(a_{L}),\ E_{1}^{\prime}\:=\:{\sf E}_{\sf s k}(b_{1}),\;\ldots,\;E_{\mu}^{\prime}\:=\:{\sf E}_{\sf s k}(b_{\mu})
$$
$$
(c_{i})
$$
$$
V=\mathsf{E v a l}(\{E_{i}^{\prime}\},\{c_{i}\},
$$
$$
i \in [ 1; \mu ]
$$
$$
(E_{i})_{i}
$$
$$
V^{\prime}=(1+\ \ {\mathcal N})^{Q(a_{1},\ldots,a_{L})}
$$
$$
\mathcal {N} ^ {2}
$$
$$
V^{\prime}
$$
$$
\mathcal{N}^{q r_{1}}\cdot\boldsymbol{r}_{0}^{\mathcal{N}}
$$
$$
:V\,=\,V^{\prime}\times(1+
$$
$$
r_{0},r_{1}
$$
$$
\mathcal{N}^{2}
$$
$$
c_{i}\in\mathcal{M}
$$
$$
i\in[1;\mu]
$$
$$
[ 0; 2 ^ {\lambda} L q ^ {2} ]
$$
$$
\ {V\cal=}\ \ \textstyle prod\boldsymbol E{}_{i}^{\prime c_{i}}=\boldsymbol{V}^{\prime}\!\times\!(1\!+\!\mathcal{N})^{q r_{1}}\!\cdot\!\boldsymbol{r}_{0}^{\mathcal{N}}
$$
$$
\mathcal {N} ^ {2}
$$
$$
c_{i}
$$
$$
E_{i}^{\prime}
$$
$$
\ \ -L q^{2};L q^{2}\rfloor,\ r_{1}q|\leq\mu L q^{3}
$$
$$
\nu^{\prime}\xleftarrow{\ }\|0;2^{\lambda}L q^{2}\|
$$
$
For the latter zero-knowledge proof, the prover chooses random *k*iZq, with additional
0$2$
noise [[0; 2 *Lq*]] and Z, to hide any extra information beyond the modulo *q* relation,
N
Qk0
i q N 2
and sets *D* = *E* (1 + *N*) mod *N*, gets a random challenge *e* (possibly derived from
i0
0
(*Q;*(*E*i)i*;* (*E*)i*;D*) in [[0; 2 1]] and outputs the proof = (*D;*(*s*i= *k*i*ec*imod *q*)i) *2*
i0
ZN2 Zq.
$$
k_{i}\xleftarrow{\S}\mathbb{Z}_{q}
$$
$$
\nu\nleftarrow{\mathbb{Z}}_{N}^{*}
$$
$$
D=\prod{E_{i}^{\prime}}_{k_{i}}\cdot(1+\mathcal{N})^{q\nu^{\prime}}\nu^{\mathcal{N}}
$$
$$
\ {\mathcal N}
$$
$$
\left(Q,(E_{i})_{i},(E_{i}^{\prime})_{i},D\right)
$$
$$
\left\{0;2^{\lambda^{\prime}}-1\right\}
$$
$$
\varPi = \left(D, \left(s _ {i} = k _ {i} - e c _ {i} \bmod q\right) _ {i}\right) \in
$$
$$
\mathbb{D}_{\mathcal{N}^{2}}\times\mathbb{D}_{q}^{\mu}
$$
00
For the moment, we use a dierent space [[0; 2 1]] for the challenge, with possibly
0
smaller than or log*"*s, in which case log*"*s*=* parallel repetitions should be performed for
correct soundness. One can check
$$
[ 0; 2 ^ {\lambda^ {\prime}} - 1 ]
$$
$$
\lambda \operatorname {o r} - \log \varepsilon_ {s}
$$
$$
- \log \varepsilon_ {s} / \lambda^ {\prime}
$$
$$
e\leftarrow\mathcal{H}(Q,(E_{i})_{i},(E_{i}^{\prime})_{i},D)\qquad D^{\prime}\leftarrow\prod E_{i}^{\prime s_{i}}\cdot(V^{\prime})^{e}\bmod\mathcal{N}^{2}\qquad\mathsf{D e c}(D/D^{\prime})\overset{?}{=}0\bmod q
$$
---
Indeed,
$$
\begin{array}{l} D ^ {\prime} = \prod E _ {i} ^ {\prime s _ {i}} \times \left(V ^ {\prime}\right) ^ {e} = \prod E _ {i} ^ {\prime s _ {i}} \times V ^ {e} \cdot \left(1 + \mathcal {N}\right) ^ {- e q r _ {1}} \cdot r _ {0} ^ {- e \mathcal {N}} \\ = \prod E _ {i} ^ {\prime k _ {i} - e c _ {i}} \times \prod E _ {i} ^ {\prime e c _ {i}} \times (1 + \mathcal {N}) ^ {- e q r _ {1}} \cdot r _ {0} ^ {- e \mathcal {N}} \\ = \prod E _ {i} ^ {\prime k _ {i}} \cdot \left(1 + \mathcal {N}\right) ^ {- e q r _ {1}} \cdot r _ {0} ^ {- e \mathcal {N}} = D \cdot \left(1 + \mathcal {N}\right) ^ {- q \left(e r _ {1} + \nu^ {\prime}\right)} \cdot \left(r _ {0} ^ {e} \nu\right) ^ {- \mathcal {N}} \bmod \mathcal {N} ^ {2}. \\ \end{array}
$$
One must make sure that 2*eqr₁ N*: with *N* 2*L tq³* (where *t* is the smallest prime
0
factor of q and 2 < t), there is no reduction modulo N before the reduction modulo q. The
zero-knowledge proof of scalars thus contains 2 log*N* + log*q* bits.
$$
2e q r_{1}\:\leq\:{\mathcal N}\ \colon
$$
$$
{\mathcal{N}}\,\geq\,2\mu L\cdot t q^{3}
$$
$$
q
$$
$$
2^{\lambda^{\prime}}i, the same challenge is used, and
the same (*k*i*;s*i), reducing the bit-size to 2 log*N*#Equations + log*q* #Secrets.
$$
\mu
$$
$$
c _ {i},
$$
$$
(k_{i},s_{i})
$$
$$
+\,\log q\!\times\!\!\neq\!\!\mathrm{S{}epsilon}
$$
## B.3 Proofs for a Hiding Commitment in R₂
$$
\mathcal{R}_{2}
$$
Let us illustrate on the proof of validity of a hiding commitment in *R₂*, as presented in Secn 1 N (2)
tion3.3. Commit (u*;* Zq[*X;Y*]), outputs the tuple *C* = (*E*u= (*E;E*)k*;*u), where for
k k
0k$0
all indices *k 2* [[1;*K*]] and *m 2* [[1;*M*]], withk*; M* andk*; 2* Z :
k N
Y
$$
\mathcal{R}_{2}
$$
$$
\ \cdot(\mathsf{u},\mathbb{Z}_{q}[X^{n-1},Y^{N}])
$$
$$
C ^ {*} = \left(E _ {\mathrm {u}} ^ {*} = \left(E _ {k} ^ {*}, E _ {k} ^ {(2 *)}\right) _ {k}, \Pi_ {\mathrm {u}} ^ {*}\right)
$$
$$
k\in[1;K]\!
$$
$$
\rho_{k},\rho_{k}^{\prime}\xleftarrow{\ }\mathcal{M}
$$
$$
\sigma_{k},\sigma_{k}^{\prime}\in\mathbb{Z}_{\mathcal{N}}^{*}:colon
$$
$$
m \in [ 1; M ]
$$
$$
E_{k}^{*}\leftarrow\prod_{j,i}E_{k,j,i}^{u_{j,i}}\times E_{k,0,0}^{\rho_{k}}\times\sigma_{k}^{\mathcal{N}}\bmod\mathcal{N}^{2}
$$
$$
E_{k}^{(2*)}\leftarrow\prod_{j,i}{E_{k,j,i}^{(2)}}^{u_{j,i}}\times E_{k,0,0}^{\rho_{k}^{\prime}}\times{\sigma_{k}^{\prime}}^{\mathcal{N}}\bmod{\mathcal{N}^{2}}
$$
(2) (2) (2)
with ZKLQCheck(*X₁ X₂ X₃;E;E;E*; *E*k;0;0*;E*) = true for which the verier can
k k k;0;0 k;0;0
(2)
compute the plaintexts in *E* and *E*, and then the quadratic relation *a*k, that should be
k k
0k (2)
*a*k= 1k*r* mod *q*:
k
$$
(X_{1}-X_{2}\cdot X_{3},E_{k}^{(2*)},E_{k}^{*},E_{k,0,0}^{(2)};E_{k,0,0},E_{k,0,0}^{(2)})=\mathsf{t r u e}
$$
$$
E_{k}^{(2*)}
$$
$$
E_{k}^{*}.
$$
$$
a_{k}.
$$
$$
a_{k}=\rho_{k}^{\prime}\times1-\rho_{k}\times r_{k}^{(2)}
$$
$$
q.
$$
$$
V_{k}^{\prime}=(1+\mathcal{N})^{a_{k}}=(1+\mathcal{N})^{\rho_{k}^{\prime}\times1-\rho_{k}\times r_{k}^{(2)}\bmod q}\bmod{\mathcal{N}}^{2}
$$
and the encodings in the proofu:
$$
\varPi_ {\mathrm {u}} ^ {*}
$$
$$
V_{k,m}^{*}\leftarrow(1+\mathcal{N})^{\mathsf{v}_{m}(s_{k},t_{k})+\rho_{k,m}\bmod q}\cdot\sigma_{k,m}^{\mathcal{N}}\bmod\mathcal{N}^{2}
$$
$$
W_{k,m}^{*}\leftarrow(1+\mathcal{N})^{\mathsf{w}_{m}(s_{k})+\rho_{k,m}^{\prime}\bmod q}\cdot{\sigma_{k,m}^{\prime}}^{\mathcal{N}}\bmod{\mathcal{N}^^{2}}
$$
0k;m$
for randomk;m; *M*, chosen by the prover for their privacy, and some unknown
0$
*k;m; 2* Z, using random *x*m*;y*mZqobtained by a hash function, and
k;m N
$$
\rho_{k,m},\rho_{k,m}^{\prime}\stackrel{\ }\\\ s\\\{\mathcal{M}
$$
$$
\sigma_{k,m},\sigma_{k,m}^{\prime}\in\mathbb{Z}_{\mathcal{N}}^{*}
$$
$$
x _ {m}, y _ {m} \leftarrow^ {\$} \mathbb {Z} _ {q}
$$
$$
E_{k}^{*},E_{k,1,0},V_{k,m}^{*},E_{k,0,1},W_{k,m}^{*};E_{k,0,0},E_{k,0,0},E_{k,1,0}^{(m)},E_{k,0,1}^{(m)})=\mathsf{t r u e}
$$
where
$$
E_{k,1,0}^{(m)}=E_{k,1,0}\cdot E_{k,0,0}^{-y_{m}}\bmod\mathcal{N}^{2}\qquad\qquad E_{k,0,1}^{(m)}=E_{k,0,1}\cdot E_{k,0,0}^{-x_{m}}\bmod\mathcal{N}^{2}
$$
Again, the verier can compute the plaintexts in the input encodings, and the plaintext *b*k;mto
0k;m
be proven, that should be *b*k;m=k+ u(*x*m*;y*m)k;m(*t*k*y*m) (*s*k*x*m) mod *q*. They
0
build *V* :
k;m
$$
b_{k,m}
$$
$$
b_{k,m}=\rho_{k}+\mathsf{u}(x_{m},y_{m})-\rho_{k,m}(t_{k}-y_{m})-\rho_{k,m}^{\prime}(s_{k}-x_{m})
$$
$$
V_{k,m}^{\prime}
$$
$$
V_{k,m}^{\prime}=(1+\mathcal{N})^{b_{k,m}}=(1+\mathcal{N})^{\rho_{k}+\mathfrak{u}(x_{m},y_{m})-\rho_{k,m}(t_{k}-y_{m})-\rho_{k,m}^{\prime}(s_{k}-x_{m})\bmod q}\bmod{\mathcal{N}^{2}}
$$
---
$$
u_{m}=\mathsf{u}(x_{m},y_{m})
$$
$$
\rho_{k}
$$
As the samekand the same *u*m= u(*x*m*;y*m) are used many times, the prover rst randomly
0$0$2$
chooses *T*k*;T;v*m*;T*k;m*;T* [[0;*q* 1]],*;* [[0; 2 *Lq* 1]],k*;*k;mZ and sets
k0 k;m k0 k;m N
$$
D_{k}=E_{k,0,0}^{T_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{-T_{k}}(1+\mathcal{N})^{q\nu_{k}^{\prime}}\nu_{k}^{\mathcal{N}}\bmod\mathcal{N}^{2}
$$
$$
D_{k,m}=E_{k,0,0}^{T_{k}}\times E_{k,0,0}^{v_{m}}\times E_{k,1,0}^{(m)}\mathrm{}{~-T_{k,m}}\times E_{k,0,1}^{(m)}\mathrm{}{~-T_{k,m}^{\prime}}(1+\mathcal{N})^{q\nu_{k,m}^{\prime}}\nu_{k,m}^{\mathcal{N}}\bmod{mathcal}N^{2}
$$
0$2
The huge range for*;* [[0; 2 *Lq* 1]] is to hide the random values even if then encodings
k0 k;m
come from *L*-linear combinations (which is not the case in this specic proof, but will be for
the relation (6), with v ).
$$
\nu_{k}^{\prime},\nu_{k.m}^{\prime}\xleftarrow{\ [;;2^{\ lambda}L q^{2}\!-\!1]}
$$
$$
\mathtt{V}_{\kappa})
$$
0
A challenge *e 2* [[0; 2 1]] is provided by the verier or drawn from a hash function evaluated
on the statement to be proven and all the (*D*k)kand (*D*k;m)k;m, and the proof eventually consists
0
of = ((*D*k)k*;* (*D*k;m)k;m; (*S*k*;S*)k*;* (*w*m)m*;* (*S*k;m*;S*)k;m), where
k0 k;m
$$
e\in[0;2^{\lambda^{\prime}}\!-\!1]
$$
$$
(D_{k}),
$$
$$
(D_{k,m})_{k,m}
$$
$$
\varPi = \left(\left(D _ {k}\right) _ {k}, \left(D _ {k, m}\right) _ {k, m}, \left(S _ {k}, S _ {k} ^ {\prime}\right) _ {k}, \left(w _ {m}\right) _ {m}, \left(S _ {k, m}, S _ {k, m} ^ {\prime}\right) _ {k, m}\right)
$$
$$
S_{k}=T_{k}-e\rho_{k}\bmod q\qquad\qquad\qquad\qquad S_{k}^{\prime}=T_{k}^{\prime}-e\rho_{k}^{\prime}\bmod q
$$
$$
w_{m}=v_{m}-e u_{m}\;\mathrm{m o d}\;q
$$
$$
S_{k,m}=T_{k,m}-e\rho_{k,m}\bmod q\qquad\qquad\qquad S_{k,m}^{\prime}=T_{k,m}^{\prime}-e\rho_{k,m}^{\prime}\bmod q
$$
It thus contains *K*(*M* + 1) ciphertexts (the number of equations), of 2 log *N* bits, and 2*K*(*M* +
1) + *M* scalars in [[0;*q* 1]] (the number of private masks), of less than log *q* bits.
$$
2K(M+
$$
The verier can rst compute the challenge *e*, and
$$
D_{k}^{\prime}=E_{k,0,0}^{S_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{-S_{k}}\times(V_{k}^{\prime})^{e}\bmod\mathcal{N}^{2}
$$
$$
D_{k,m}^{\prime}=E_{k,0,0}^{S_{k}}\times E_{k,0,0}^{w_{m}}\times E_{k,1,0}^{(m)}{}^{-S_{k,m}}\times E{_{k,0,1}^{(m)}}{}^{-S_{k,m}^{\prime}}\times(V_{k,m}^{\prime})^{e}\bmod\mathcal{N}^{2}
$$
0 0
They then decrypt all the *D*k*=D* and *D*k;m*=D*, that should be 0 modulo *q*, as there is no
k k;m
reduction modulo *N* before the reduction modulo *q*, thanks to the constraint on *N >* 2*L* 2 *q³*.
$$
q,
$$
$$
D_{k}/D_{k}^{\prime}
$$
$$
D_{k,m}/D_{k,m}^{\prime}
$$
$$
\mathcal{N}>2\mu L\!\cdot\!2^{\lambda}q^{3}
$$
0~0
*Soundness.* After a rewinding, with a dierent challenge ~*e 6*= *e*, such that *D* and D decrypt
k k
0~0
to the same value modulo q, and *D* and *D* decrypt to the same value modulo *q*, where
k;m k;m
$$
\tilde{e}\neq e,
$$
$$
D_{k}^{\prime}
$$
$$
\tilde{D}_{k}^{\prime}
$$
$$
D_{k,m}^{\prime}
$$
$$
q,
$$
$$
\check{D}_{k,m}^{\prime}
$$
$$
q,
$$
$$
D_{k}^{\prime}=E_{k,0,0}^{S_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{-S_{k}}\times(V_{k}^{\prime})^{e}\bmod\mathcal{N}^{2}
$$
$$
\tilde{D}_{k}^{\prime}=E_{k,0,0}^{\tilde{S}_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{-\tilde{S}_{k}}\times(V_{k}^{\prime})^{\tilde{e}}\bmod\mathcal{N}^{2}
$$
$$
D_{k,m}^{\prime}=E_{k,0,0}^{S_{k}}\times E_{k,0,0}^{w_{m}}\times E_{k,1,0}^{(m)\ {-S_{k,m}}}\times E_{k,0,1}^{(m)\ {-S_{k,m}^{\prime}}}\times(V_{k,m}^{\prime})^{e}\operatorname{m o d}\mathcal{N}^{2}
$$
$$
\tilde{D}_{k,m}^{\prime}=E_{k,0,0}^{\tilde{S}_{k}}\times E_{k,0,0}^{\tilde{w}_{m}}\times E_{k,1,0}^{(m)}\ {{-\tilde{S}_{k,m}}}\times\ E_{k,0,1}^{(m)}\ {{-\tilde{S}_{k,m}^{\prime}}}\times(V_{k,m}^{\prime})^{\tilde{e}}\operatorname{m o d}\mathcal{N}^{2}
$$
we have both
$$
A_{k}=E_{k,0,0}^{S_{k}^{\prime}-\tilde{S}_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{\tilde{S}_{k}-S_{k}}\times(V_{k}^{\prime})^{e-\tilde{e}}\bmod\mathcal{N}^{2}
$$
$$
A_{k,m}=E_{k,0,0}^{S_{k-}\tilde{S}_{k}}\times E_{k,0,0}^{w_{m}-\tilde{w}_{m}}\times E_{k,1,0}^{(m)}{^{\hat{S}_{k,m}-S_{k,m}}}\times E_{k,0,1}^{(m)}{^{\hat{S}_{k,m}^{\prime}-S_{k,m}^{\prime}}}\times(V_{k,m}^{\prime})^{c-\tilde{c}}\bmod{mathcal\mathcal N{}}^{2}
$$
0
decrypt to 0 modulo *q*, while the small size of the answers and the evaluation of *V* and *V* by
k0 k;m
30
the verier on small scalars guarantees no wrap-up modulo N : qk;qk;m< 2Lq + 2 q < N,
even with encodings generated from *L*-linear combinations in
$$
V_{k}^{\prime}
$$
$$
q\cdot
$$
$$
V_{k,m}^{\prime}
$$
$$
\mathcal {N}: q \alpha_ {k}, q \alpha_ {k, m} < 2 \mu L q ^ {3} + 2 ^ {\lambda^ {\prime}} q < \mathcal {N}
$$
$$
A_{k}=(1+\mathcal{N})^{q\alpha_{k}}\beta_{k}^{\mathcal{N}}\bmod\mathcal{N}^{2}\qquad\qquad A_{k,m}=(1+\mathcal{N})^{q\alpha_{k,m}}\beta_{k,m}^{\mathcal{N}}\bmod\mathcal{N}^{2}
$$
---
1
If we assume ~*e e* invertible modulo *q*, and set *"* = (~*e e*) mod *q*, we can compute
$$
\varepsilon=(\tilde{e}-e)^{-1}
$$
$$
q,
$$
$$
\tilde{e}-e
$$
$$
q\cdot
$$
$$
\rho_{k}^{\prime}\gets(S_{k}^{\prime}-\tilde{S}_{k}^{\prime})\cdot\varepsilon\bmod q\quad\quad\quad\quad\quad\quad\quad\rho_{k}\gets(S_{k}-\tilde{S}_{k})\cdot\varepsilon\bmod q
$$
$$
u_{m}\gets\left(w_{m}-\tilde{w}_{m}\right)\cdot\varepsilon\bmod q
$$
$$
\rho_{k,m}\gets(S_{k,m}-\tilde{S}_{k,m})\cdot\varepsilon\bmod q\qquad\qquad\rho_{k,m}^{\prime}\gets(S_{k,m}^{\prime}-\tilde{S}_{k,m}^{\prime})\cdot\varepsilon\bmod q
$$
all smaller than *q*
$$
\begin{aligned}{E_{k,0,^{\prime}}^{\rho_{k}^{\prime}}\cdot(E_{k,0,0}^{(2)})^{-\rho_{k}}}&{{}=V_{k}^{\prime}\cdot(1+\mathcal{N})^{q\alpha_{k}^{\prime}}\gamma_{k}^{\mathcal{N}}\bmod{mathcal}N^{2}}\\ {E_{k,0,0}^{\rho_{k}}\times E_{k,0,0}^{u_{m}}\times E_{k,1,0}^{(m)-\rho_{k,m}}\times E_{k,0,1}^{(m)-\rho_{k,m}^{\prime}}}&{{}=V_{k,m}^{\prime}\cdot(1+\mathcal{N})^{q\alpha_{k,m}^{\prime}}\gamma_{k,m}^{\mathcal{N}}\bmod\mathcal{N}^{2}}\\ \end{aligned}
$$
Eventually, if *N >* 2*Lq³*, all the exponents to (1 + *N*) remain smaller than *N*, which proves
0
the soundness, until ~*e e* is invertible: one can take 2 smaller than the smallest prime factor
of *q*, so that any non-trivial dierence will always be invertible, and iterate several times in
parallel with multiple challenges *e*, to increase soundness. For *N*, this is safe to take it larger
than 2*L*2 *q³*. As will always be smaller than 4, in each individual equations, we can take
+3
*N > L*2 *q³*.
$$
\mathcal{N}>2\mu L q^{3}
$$
$$
(1+{mathcal N))}
$$
$$
\ {\mathcal M}.
$$
$$
\tilde{e}-e
$$
$$
2^{\lambda^{\prime}}
$$
$$
q,
$$
$$
e,
$$
$$
\mathbf{N}
$$
$$
2\mu L2^{\lambda}q^{3}
$$
$$
\mu
$$
$$
\mathcal{N}>L2^{\lambda+3}q^{3}
$$
*Zero-Knowledge.* Thanks to the random masks in *M*, the plaintexts are statistically hidden. The
0
proofs contain tuples ((*D*k)k*;* (*D*k;m)k;m; (*S*k*;S*)k*;* (*w*m)m*;* (*S*k;m*;S*)k;m), where the cipherk0 k;m
texts statistically hide their representations modulo *q*, and the scalars are uniformly distributed
in [[0;*q* 1]]. Hence, a statistical zero-knowledge proof that guarantees the hiding property of
the commitments.
$$
{{}}_{({{}}(D_{k}){{}}_{k}){{}}_{k},{{}}(D_{k,m}){{}}_{k,m},{{}}(S_{k},{{}}S_{k}^{\prime}){{}}_{k},{{}}(w_{m}){{}}_{m},{{}}(S_{k,m},S{_{k,m}^{\prime}}){{}}_{k,m})}
$$
$$
q,
$$
$$
[ 0; q - 1 ]
$$
## C Commitments
## C.1 Commitments in Additional Subspaces
In our proof of inner product, we will use polynomials in multiple subspaces of *R* = Zq[*X;Y*].
n 1 N n 1 N 2N
In addition to *R₂* = Zq[*X;Y*], we will use *R₁* = Zq[*X*], *R₃* = Zq[*Y*], and Zq[*Y*]
N 2N nN
with no term in *Y*, denoted *R₄* = Zq[*Y*]. For this, we draw additional random elements
(1) (3) (4) $
*r;r;r* Zqfor *k 2* [[1;*K*]], and set:
k k k
$$
\mathcal{R}=\mathbb{Z}_{a}|X,Y|
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}]
$$
$$
\mathcal{R}_{1}=\mathbb{Z}_{q}[X^{n-1}],\,\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
$$
\bar{\mathbb{Z}}_{q}[Y^{2N}]
$$
$$
Y^{N}
$$
$$
\mathcal{R}_{4}\doteq\mathbb{Z}_{q}[Y^{2N\setminus N}]
$$
r (1) ;r (3) ;r (4) $ Z for k 2 [[1; K ]], and set: k k k q
$$
r_{k}^{(1)},r_{k}^{(3)},r_{k}^{(4)}\xleftarrow{\Phi}\mathbb{Z}_{q}^{*}
$$
$$
k\in[1;K]\!
$$
$$
\begin{array}{l} E _ {k, i} ^ {(1)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(1)} \cdot s _ {k} ^ {i}\right) \quad i \in [ 0; n - 1 ] \\ E _ {k, j} ^ {(3)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(3)} \cdot t _ {k} ^ {j}\right) \quad j \in [ 0; N ] \\ E _ {k, j} ^ {(4)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(4)} \cdot t _ {k} ^ {j}\right) \quad j \in [ 0; 2 N ] \backslash \{N \} \\ \end{array}
$$
and we extend
$$
E_{k,j,i}\gets\mathsf{E}(s_{k}^{i}\cdot t_{k}^{j})\qquad\qquad\qquad\quad i\in\ [0;n-1],j\in\big[0;2N\big]
$$
Note that *D* becomes max*fN* + *n* 1*;* 2*N g* = 2*N*, for *N n*. We then commit the polynomi-
N 2N nN
als Commit(u*;* Zq[*Y*]) or Commit(u*;* Zq[*Y*]) with appropriate twin encodings, that can be
veried as above: for each pair *k 6*= *k⁰* of valid encodings:
$$
\{N + n - 1, 2 N \} = 2 N
$$
$$
N\geq n
$$
$$
(\mathsf{u},\mathbb{Z}_{q}[Y^{N}])
$$
$$
\ \ (\mathsf{u},\mathbb{Z}_{q}[Y^{2N\setminus N}])
$$
$$
k\neq k^{\prime}
$$
$$
\mathsf{u}_{\mathsf{k}}(Y)-\mathsf{u}_{\mathsf{k}^{\prime}}(Y^{\prime})=\mathsf{u}(Y)-\mathsf{u}(Y^{\prime})=(Y-Y^{\prime})\cdot\mathsf{v}(Y,Y^{\prime})
$$
$
and so for a random *y*mZqchosen by the prover:
$$
y_{m}\xleftarrow{\mathfrak{S}}\mathbb{Z}_{q}
$$
$$
\mathsf{u}(Y)-\mathsf{u}(y_{m})=(Y-y_{m})\cdot\mathsf{v}(Y,y_{m})=(Y-y_{m})\cdot\mathsf{v}_{m},
$$ from
$$
\varPi_ {\mathrm {u}} = \left(u _ {m} \leftarrow \mathrm {u} \left(y _ {m}\right), \left(V _ {k, m} \leftarrow \mathrm {E} \left(\mathrm {v} _ {m} \left(t _ {k}\right)\right)\right) _ {k}\right) _ {m}
$$
as
$$
\mathsf{Q C h e c k}(\mathit{X}_{1}-\mathit{u}_{m}-(\mathit{X}_{2}-\mathit{y}_{m})\cdot\mathit{X}_{3},\mathit{E}_{k},\mathit{E}_{k,1,0},\mathit{V}_{k,m})=\mathsf{t r u e}
$$
and the rest of the proof follows as in Section3.2, with thusu= (*u*m*;* (*V*k;m)k)m, for *k 2* [[1;*K*]],
*m 2* [[1;*M*]].
$$
k\in[1;K]
$$
$$
\varPi_ {\mathrm {u}} = \left(u _ {m}, \left(V _ {k, m}\right) _ {k}\right) _ {m}
$$
$$
m \in [ 1; M ]
$$
## C.2 Univariate Hiding Commitments
P
N N j
Commit (u*;* Zq[*Y*]), the hiding commitment for a univariate polynomial u(*Y*) = *u*j*Y 2*
j=0
N (3)
*R₃* = Zq[*Y*], outputs the tuple *C* = (*E*u*;* (*E*k*;E*)k*;*u), where for all indices *k 2* [[1;*K*]] and
k
$
*m 2* [[1;*M*]] withk *M* :
$$
(\mathbf{u},\mathbb{Z}_{q}[\mathbf{Y}^{N}])
$$
$$
\mathsf{u}\big(Y\big)=\sum_{i=0}^{N}u_{j}Y^{j}\in
$$
$$
\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
$$
\ =(E_{\mathsf{u}},(E_{k},E_{k}^{(3*)})_{k},\varPi_{\mathsf{u}})
$$
$$
k\in[1;K]\!
$$
$$
m\in[1;M]
$$
$$
\rho_{k}\xleftarrow{\S}\ {mathcal M}.
$$
$$
\begin{array}{l} E _ {k} \leftarrow \operatorname {E v a l} \left(\left\{E _ {k, j, 0} \right\} _ {j}, \left\{F _ {k} \right\}, \left\{u _ {j} \right\} _ {j}, \left\{\rho_ {k} \right\}\right) = \mathrm {E} \left(\mathrm {u} \left(t _ {k}\right) + \rho_ {k} \cdot r _ {k}\right), \\ E _ {k} ^ {(3 *)} \leftarrow \operatorname {E v a l} \left(\left\{E _ {k, j, 0} ^ {(3 *)} \right\} _ {j}, \left\{F _ {k} ^ {(3 *)} \right\}, \left\{u _ {j} \right\} _ {j}, \left\{\rho_ {k} \right\}\right) = \mathrm {E} \left(r _ {k} ^ {(3 *)} \left(\mathrm {u} \left(t _ {k}\right) + \rho_ {k} \cdot r _ {k}\right)\right) \\ \text {w i t h Q C h e c k} \left(X _ {1} - X _ {2} \cdot X _ {3}, E _ {k} ^ {(3 *)}, E _ {k}, E _ {k, 0} ^ {(3 *)}\right) = \text {t r u e} \\ \end{array}
$$
$
and a proof, using random *y*mZqsent by the verier, of u(*Y*) u(*y*m) = (*Y y*m) vm(*Y*)
$
which can be checked withu= (*V*k;mE(vm(*t*k) +k;m*r*k))k;mfor randomk;mZq,
chosen by the prover for their privacy, and
$$
y_{m}\xleftarrow{\mathfrak{S}}\mathbb{Z}_{q}
$$
$$
\mathsf{u}(Y)-\mathsf{u}(y_{m})\,{=}\,(Y-y_{m})\cdot\mathsf{v}_{m}(Y)
$$
$$
\ Pi_{{\mathsf u}}\:=\:(V_{k,m}\:\leftarrow\:{\mathsf E}({\mathsf v}_{m}(t_{k})\ {\mathsf{}}+\ \rho_{k,m}\ {\mathsf{}}cdot\ {\mathsf{}}r_{k}))_{k,m}
$$
$$
\rho_{k,m}\xleftarrow{\mathfrak{S}}\mathbb{Z}_{q}^{*}
$$
$$
\mathsf{Z K L Q C h e c k}(X_{1}-(X_{2}-y_{m})\cdot X_{3},E_{k}^{*},E_{k,1,0},V_{k,m};E_{k,0,0},F_{k}^{(t)},F_{k})=\mathsf{t r u e}
$$
0k;m
where one proves the knowledge of the 3 scalars *u*m= u(*y*m), =k k;m*y*mandk;mso
that the above relation is equal to
$$
u_{m}=\mathsf{u}(y_{m}),\,\rho_{k,m}^{\prime}=\rho_{k}-\rho_{k,m}\cdot y_{m}
$$
$$
\rho_{k,m}
$$
$$
u_{m}\times1+\rho_{k,m}\times r_{k}\cdot t_{k}-\rho_{k,m}^{\prime}\times r_{k}\bmod q.
$$
The same analysis as for the *R₂* case can be done for the soundness of the proof, but with less
strict bounds, as degrees are lower.
## C.3 Complete Construction of the Commitment
$$
\mathcal{R}_{2}
$$
In the following, we are considering *q* = *p₁ ::: p*‘, a composite modulus *q*, with *‘* prime factors
n 1 2N
p₁ < ::: < p‘. We will work in subspaces of R = Zq[X;Y]. We will consider the subspaces
n 1 n 1 N N 2N nN
*R₁* = Zq[*X*], *R₂* = Zq[*X;Y*], *R₃* = Zq[*Y*], and *R₄* = Zq[*Y*], hence *D* = 2*N*, so
we will assume *t* 128*N‘*.
$$
q=p_{1}\cdot\ldots\cdot p_{\ell}
$$
$$
q,
$$
$$
p_{1}<\ldotsi)i) rst runs (pk⁰*;*vk⁰) Gen(1 ), chooses *K* tuples of
$ (1) (2) (3) (4) $
random elements *s*k*;t*kZq, as well as *K* tuples of random elements *r;r;r;r;* Zq,
k k k k
to limit the combinations of the bases. Then, for *k 2* [[1;*K*]], one sets
$$
{\sf S{t u t}}{\ }\mathsf{p}(1^{\lambda},\mathcal{R},(\mathcal{R}_{i})_{i})
$$
$$
(\mathsf{p k}^{\prime},\mathsf{v k}^{\prime})\leftarrow\mathsf{G e n}(1^{\lambda})
$$
$$
s_{k},t_{k}\xleftarrow{\circ}\mathbb{Z}_{q}^{*}
$$
$$
r_{k}^{(\dot{1})},r_{k}^{(2)},r_{k}^{(3)},r_{k}^{(4)},\xleftarrow{\ }\mathbb{Z}_{q}^{*}
$$
$$
k \in [ 1; K ]
$$
$$
\begin{array}{l} \mathcal {R} = \mathbb {Z} _ {q} [ X ^ {n - 1}, Y ^ {N} ] + \mathbb {Z} _ {q} [ Y ^ {2 N} ] E _ {k, j, i} \leftarrow \mathsf {E} \left(s _ {k} ^ {i} \cdot t _ {k} ^ {j}\right) (i, j) \in (\llbracket 0; n - 1 \rrbracket \times \llbracket 0; N \rrbracket) \\ \cup \left(\{0 \} \times \llbracket N + 1; 2 N \rrbracket\right) \\ \mathcal {R} _ {1} = \mathbb {Z} _ {q} [ X ^ {n - 1} ] E _ {k, i} ^ {(1)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(1)} \cdot s _ {k} ^ {i}\right) i \in \llbracket 0; n - 1 \rrbracket \\ \mathcal {R} _ {2} = \mathbb {Z} _ {q} [ X ^ {n - 1}, Y ^ {N} ] E _ {k, j, i} ^ {(2)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(2)} \cdot s _ {k} ^ {i} \cdot t _ {k} ^ {j}\right) i \in \llbracket 0; n - 1 \rrbracket , j \in \llbracket 0; N \rrbracket \\ \mathcal {R} _ {3} = \mathbb {Z} _ {q} [ Y ^ {N} ] E _ {k, j} ^ {(3)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(3)} \cdot t _ {k} ^ {j}\right) j \in \llbracket 0; N \rrbracket \\ \mathcal {R} _ {4} = \mathbb {Z} _ {q} [ Y ^ {2 N \backslash N} ] E _ {k, j} ^ {(4)} \leftarrow \mathsf {E} \left(r _ {k} ^ {(4)} \cdot t _ {k} ^ {j}\right) j \in \llbracket 0; 2 N \rrbracket \backslash \{N \} \\ \end{array}
$$
Then, the public key of the commitment scheme is set to pk⁰ with all these encodings, while the
n 1 N 2N
verication key is vk⁰. For *R*, we can limit to Zq[*X;Y*] + Zq[*Y*], with (*n* + 1) *N* + *n*
encodings in the public key, sent once for many proofs.
$$
\mathbb{Z}_{q}[X^{n-1},Y^{N}]+\mathbb{Z}_{q}[Y^{2N}]
$$
$$
(n+1)\times N+n
$$
---
Commitment Generation: there are two commitment algorithm, with or without the hiding
property.
n 1
*Non-Hiding Commitment.* We have dened commitments on specic subspaces: *R₁* = Zq[*X*],
n 1 N N 2N nN
*R₂* = Zq[*X;Y*], *R₃* = Zq[*Y*], and *R₄* = Zq[*Y*]:
(1)
$$
\mathcal{R}_{1}=\mathbb{Z}_{q}[X^{n-1}]
$$
$$
\mathcal{R}_{2}=\mathbb{Z}_{q}[X^{n-1},Y^{N}],\:\mathcal{R}_{3}=\mathbb{Z}_{q}[Y^{N}]
$$
n 1
Commit(u*;* Zq[*X*]): it outputs *C* = (*E*u= (*E*k*;E*)k*;*u), for *k 2* [[1;*K*]], where
k
$$
\mathcal{R}_{4}=\mathbb{Z}_{q}[Y^{2N\setminus N}]
$$
$$
: \left(\mathrm {u}, \mathbb {Z} _ {q} \left[ X ^ {n - 1} \right]\right)
$$
$$
C = \left(E _ {\mathrm {u}} = \left(E _ {k}, E _ {k} ^ {(1)}\right) _ {k}, \Pi_ {\mathrm {u}}\right)
$$
$$
k \in [ 1; K ]
$$
$$
E_{k}\leftarrow\mathsf{E}(\mathsf{u}(s_{k}))
$$
$$
E_{k}^{(1)}\leftarrow\mathsf{E}(r_{k}^{(1)}\cdot\mathsf{u}(s_{k})),
$$
$
and for all *m 2* [[1;*M*]]: *x*mZqchosen by the verier (or from a hash function for a
non-interactive proof), and then
$$
m\,\in\,[1;M]\colon\,x_{m}\,\overset{\&}{\leftarrow}\,\mathbb{Z}_{q}
$$
$$
\mathit{}mathit H\mathsf{u}=(u_{m}\leftarrow\mathsf{u}(x_{m}),(W_{k,m}\leftarrow\mathsf{E}(\mathsf{w}_{m}(s_{k})))_{k})_{m}
$$
where wmis such that u(*X*) *u*m= (*X x*m) wm(*X*): in total, these are 2*K* encodings,
plus *M* scalars and *KM* encodings for the proof.
n 1 N (2)
Commit(u*;* Zq[*X;Y*]): it outputs *C* = (*E*u= (*E*k*;E*)k*;*u), for *k 2* [[1;*K*]], where
k
$$
W_{m}
$$
$$
\mathsf{u}(X)-\mathbf{\mathit{u}}_{m}=\mathbf{\mathit{(}}X-\mathbf{\mathit{x}}_{m})\cdot\mathsf{w}_{m}(X)
$$
$$
:(\mathsf{u},\mathbb{Z}_{q}[X^{n-1},Y^{N}])
$$
$$
C = \left(E _ {\mathrm {u}} = \left(E _ {k}, E _ {k} ^ {(2)}\right) _ {k}, \Pi_ {\mathrm {u}}\right)
$$
$$
k\in[1;K]\!
$$
$$
E_{k}\leftarrow\mathsf{E}(\mathsf{u}(s_{k},t_{k}))\qquad\qquad\qquad\ E_{k}^{(2)}\leftarrow\mathsf{E}(r_{k}^{(2)}\cdot\mathsf{u}(s_{k},t_{k})),
$$
$2
and for all *m 2* [[1;*M*]]: (*x*m*;y*m) Zqchosen by the verier (or from a hash function for a
non-interactive proof), and then
$$
m \in [ 1; M ]: (x _ {m}, y _ {m}) \leftarrow^ {\$} \mathbb {Z} _ {q} ^ {2}
$$
$$
\small\begin{aligned}{\mathit\Pi{}_{\mathsf{u}}=(u_{m}\gets\mathsf{u}(x_{m},y_{m}),(V_{k,m}\gets\mathsf{E}(\mathsf{v}_{m}(s_{k},t_{k})),W_{k,m}\gets\mathsf{E}(\mathsf{w}_{m}(s_{k})))_{k})_{m}}\\ \end{aligned}
$$
where vmand wmare such that
$$
W_{m}
$$
$$
\mathrm{v}_{m}
$$
$$
\mathsf{u}(X,Y)-u_{m}=(Y-y_{m})\cdot\mathsf{v}_{m}(X,Y)+(X-x_{m})\cdot\mathsf{w}_{m}(X).
$$
In total, these are 2*K* encodings, plus *M* scalars and 2*KM* encodings for the proof.
N (3)
Commit(u*;* Zq[*Y*]): it outputs *C* = (*E*u= (*E*k*;E*)k*;*u), for *k 2* [[1;*K*]], where:
k
$$
(\mathsf{u},\mathbb{U}_{q}[Y^{N}])
$$
$$
C = \left(E _ {\mathrm {u}} = \left(E _ {k}, E _ {k} ^ {(3)}\right) _ {k}, \Pi_ {\mathrm {u}}\right)
$$
$$
k\in[1;K]\!
$$
$$
E_{k}\leftarrow\mathsf{E}(\mathsf{u}(t_{k}))\qquad\qquad\qquad\qquad E_{k}^{(3)}\leftarrow\mathsf{E}(r_{k}^{(3)}\cdot\mathsf{u}(t_{k})),
$$
$
and for all *m 2* [[1;*M*]]: *y*mZqchosen by the verier (or from a hash function for a
non-interactive proof), and then
$$
m\,\in\,[1;M]\colon\,y_{m}\,\xleftarrow{\S}\,\mathbb{Z}_{q}
$$
$$
\mathit{I}_{\mathbf{u}}=(u_{m}\leftarrow\mathsf{u}(y_{m}),(V_{k,m}\leftarrow\mathsf{E}(\mathsf{v}_{m}(t_{k})))_{k})_{m}
$$
where vmis such that u(*Y*) *u*m= (*Y y*m) vm(*Y*). In total, these are 2*K* encodings, plus
*M* scalars and *KM* encodings for the proof.
$$
\ _{}\ \ !
$$
$$
{\mathsf{U}}\big(Y\big)-u_{m}=\big(Y-y_{m}\big)\,{\cdot}\,{\mathsf{V}}_{m}\big(Y\big)
$$
2N nN (3) (4)
Commit(u*;* Zq[*Y*]): as the previous case but replacing *r* with *r* and analogously (3)
indices with (4) indices.
$$
\mathsf{t}(\mathsf{u},\mathbb{Z}_{q}[Y^{2N\setminus N}])
$$
$$
r^{(3)}
$$
$$
r^{(4)}
$$
$$
\ \mathcal{R}_{2}
$$
*Hiding Commitment.* We only focus on *R₂* and *R₃*:
$$
\mathcal{R}_{3}
$$
n 1 N (2)
Commit (u*;* Zq[*X;Y*]): it outputs *C* = (*E*u= (*E;E;*k)k*;*u), for *k 2* [[1;*K*]], where,
k k
0k$
withk*; M*, where *M* is the appropriate masking set:
$$
\vdots\big(\mathsf{u},\mathbb{Z}_{q}[X^{n-1},Y^{N}]\big)
$$
$$
\ \ C{}^{*}=\big(E_{\mathsf{u}}^{*}=(E_{k}^{*},E_{k}^{(2*)},\pi_{k})_{k},\varPi_{\mathsf{u}}^{*}\big)
$$
$$
k\in[1;K]\!
$$
$$
\rho_{k},\rho_{k}^{\prime}\xleftarrow{\ }\mathcal{M}
$$
$$
E _ {k} ^ {*} \leftarrow \operatorname {E v a l} \left(\left\{E _ {k, j, i} \right\} _ {j, i}, \left\{E _ {k, 0, 0} \right\}, \left\{u _ {j, i} \right\} _ {j, i}, \left\{\rho_ {k} \right\}\right) = \mathrm {E} \left(\mathrm {u} \left(s _ {k}, t _ {k}\right) + \rho_ {k}\right)
$$
$$
\mathrm{w i t h~}\pi_{k}=\{\mathsf{Z K L Q C h e c k}(X_{1}-X_{2}\cdot X_{3},E_{k}^{(2*)},E_{k}^{*},E_{k,0,0}^{(2)};E_{k,0,0},E_{k,0,0}^{(2)})=\mathsf{t r u e}\}
$$
---
$$
m \in [ 1; M ]: (x _ {m}, y _ {m}) \leftarrow^ {\$} \mathbb {Z} _ {q} ^ {2}
$$
$2
and for all *m 2* [[1;*M*]]: (*x*m*;y*m) Zqchosen by the verier (or from a hash function for a
0k;m$
non-interactive proof), and then for randomk;m; Zqchosen by the prover for their
privacy:
0
$$
\rho_{k,m},\rho_{k,m}^{\prime}\overset{\&}{\leftarrow}\mathbb{Z}_{q}^{*}
$$
$$
\varPi_{\mathsf{u}}^{*}=(V_{k,m}^{*}\leftarrow\mathsf{E}(\mathsf{v}_{m}(s_{k},t_{k})+\rho_{k,m}),W_{k,m}^{*}\leftarrow\mathsf{E}(\mathsf{w}_{m}(s_{k})+\rho_{k,m}^{\prime})_{k,m}
$$
where vmand wmare such that
$$
W_{m}
$$
$$
\mathrm{v}_{m}
$$
$$
\mathsf{u}(X,Y)-\mathsf{u}(x_{m},y_{m})=(Y-y_{m})\cdot\mathsf{v}_{m}+(X-x_{m})\cdot\mathsf{w}_{m}
$$
with
0k;m
*KM* additional zero-knowledge proofs of knowledge of 4 scalarsk;m,,k, and *u*m=
u(*x*m*;y*m). In total, this is 2*K* encodings, plus *KM* encodings for the proof, and *KM* zeroknowledge proofs of 4 scalars.
$$
\rho_{k,m},\,\rho_{k,m}^{\prime},\,\rho_{k}
$$
$$
\mathsf{u}(x_{m},y_{m})
$$
$$
u_{m}=
$$
N (3)
Commit (u*;* Zq[*Y*]): it outputs *C* = (*E*u= (*E;E;*k)k*;*u), for *k 2* [[1;*K*]], where, with
k k
0$
k*; M* :
*k*
$$
(\boldsymbol{\mathsf{u}},\mathbb{Z}_{q}[Y^{N}])
$$
$$
\mathcal{C}^{*}=\big(E_{\mathsf{u}}^{*}=(E_{k}^{*},E_{k}^{(3*)},\pi_{k})_{k},\varPi_{\mathsf{u}}^{*}\big)
$$
$$
k \in [ 1; K ]
$$
$$
\rho_{k},\rho_{k}^{\prime}\xleftarrow{\S}\mathcal\{M{}:
$$
$$
E_{k}\leftarrow\mathsf{E}(\mathsf{u}(t_{k})+\rho_{k})\qquad\qquad\qquad E_{k}^{(3*)}\leftarrow\mathsf{E}(r_{k}^{(3)}\cdot\mathsf{u}(t_{k})+\rho_{k}^{\prime})
$$
(3) (3) (3)
withk= *f*ZKLQCheck(*X₁ X₂ X₃;E;E;E*; Ek;0;0*;E*) = true*g*, and for all
k k k;0;0 k;0;0
$
*m 2* [[1;*M*]]: *y*mZqchosen by the verier (or from a hash function for a non-interactive
$
proof), and then for randomk;mZqchosen by the prover for their privacy:
$$
\pi_{k}\,=\,\{\mathsf{Z K L Q C h e k}(X_{1}-X_{2}\cdot X_{3},E_{k}^{(3*)},E_{k}^{*},E_{k,0,0}^{(3)};E_{k,0,0},E_{k,0,0}^{(3)})\,=\,\mathsf{t r u e}\}
$$
$$
m \in [ 1; M ]: y _ {m} \leftarrow^ {\$} \mathbb {Z} _ {q}
$$
$$
\rho_{k,m}\xleftarrow{\S}\mathbb{Z}_{q}^{*}
$$
$$
\varPi_{\mathsf{u}}^{*}=(V_{k,m}^{*}\gets\mathsf{E}(\mathsf{v}_{m}(t_{k})+\rho_{k,m}))_{k,m}
$$
for vmsuch that u(*Y*) u(*y*m) = (*Y y*m) vm(*Y*) with *KM* additional zero-knowledge
proofs of knowledge of 3 scalarsk;m,k, and *u*m= u(*y*m). In total, this is 2*K* encodings,
plus *KM* encodings for the proof, and *KM* zero-knowledge proofs of 3 scalars.
$$
\mathsf{v}_{m}
$$
$$
\mathsf{u}(Y)\:-\:\mathsf{u}(y_{m})\:=\:(Y\:-\:y_{m})\:\cdot\:\mathsf{v}_{m}(Y)
$$
$$
\rho_{k,m},\rho_{k}
$$
$$
u_{m}=\mathsf{u}(y_{m})
$$
Validity Check: it also depends on hiding or non-hiding commitments and on the space *R*.
$$
\mathcal{R}_{\pi}
$$
*Non-Hiding Commitment.* Validity(*C; R*) rst checks the twin encodings, for *k 2* [[1;*K*]]:
$$
(C,\mathcal{R}_{\pi})
$$
$$
k \in [ 1; K ]
$$
$$
\begin{array}{l} \mathcal {R} _ {1} \quad Q C \check {c h e c k} \left(X _ {1} - X _ {2} \cdot X _ {3}, E _ {k} ^ {(1)}, E _ {k}, E _ {k, 0} ^ {(1)}\right) = \mathrm {t r u e} \\ \mathcal {R} _ {2} \quad Q C \check {c h e c k} \left(X _ {1} - X _ {2} \cdot X _ {3}, E _ {k} ^ {(2)}, E _ {k}, E _ {k, 0, 0} ^ {(2)}\right) = \mathrm {t r u e} \\ \mathcal {R} _ {3}, \mathcal {R} _ {4} \quad Q C \check {c h e c k} \left(X _ {1} - X _ {2} \cdot X _ {3}, E _ {k} ^ {(3 / 4)}, E _ {k}, E _ {k, 0} ^ {(3 / 4)}\right) = \mathrm {t r u e} \\ \end{array}
$$
$$
m \in [ 1; M ]
$$
$$
k \in [ 1; K ]
$$
and then, for *k 2* [[1;*K*]] and *m 2* [[1;*M*]], either
$$
\begin{aligned}{}&{{}\mathcal{R}_{1}}&{\qquad}&{{}\mathsf{Q C h e c k}(X_{1}-u_{m}-(X_{2}-x_{m})\cdot X_{3},E_{k},E_{k,0,1},W_{k,m})=\mathsf{t r u e}}\\ {}&{{}\mathcal{R}_{2}}&{\qquad}&{{}\mathsf{Q C h e c k}(X_{1}-u_{m}-(X_{2}-y_{m})\cdot X_{3}-(X_{4}-x_{m})\cdot X_{5})}\\ {}&{{}\mathcal{R}_{3},\mathcal{R}_{4}}&{\qquad}&{{}E\_{k,1},E_{k,1},V_{k,m},E_{k,0},W_{k,m})=\mathsf{t r u e},}\\ {}&{{}\mathcal{R}_{3},\mathcal{R}_{4}}&{\qquad}&{{}\mathsf{Q C h e c k}(X_{1}-u_{m}-(X_{2}-y_{m})\cdot X_{3},E_{k,1},E_{k,1},V_{k,m})=\mathsf{t r u e}}\\ \end{aligned}
$$
---
*Hiding Commitment.* Validity (*C; R*) rst checks the twin encodings, for *k 2* [[1;*K*]]:
$$
(mathcal C\ \mathcal{R}_{\pi})
$$
$$
k \in [ 1; K ]
$$
$$
\begin{array}{r l r l}{\mathcal{R}_{2}}&{\qquad\qquad}&{\mathsf{Q C h e c k}(X_{1}-X_{2}\cdot X_{3},E_{k}^{(2*)},E_{k},E_{k,0,0}^{(2)})=\mathsf{t r u e}}&end{}\end{array}
$$
$$
\mathcal{R}_{3}\qquad\qquad\qquad\mathsf{Q C h e c k}(X_{1}-X_{2}\cdot X_{3},E_{k}^{(3*)},E_{k},E_{k,0}^{(3)})=\mathsf{t r u e}
$$
and then, for *k 2* [[1;*K*]] and *m 2* [[1;*M*]], the zero-knowledge proofs
$$
k\in[1;K]\!
$$
$$
m\in[1;M]
$$
$$
\mathcal{R}_{2}\ \ \ \ \ \ \ \mathsf{Z L Q C h e c k}(X_{1}-(X_{2}-y_{m})\cdot X_{3}-(X_{4}-x_{m})\cdot X_{5},
$$
$$
E_{k}^{*},E_{k,1,0},V_{k,m}^{*},E_{k,0,1},W_{k,m}^{*};E_{k,0,0},E_{k,0,0},E_{k,1,0}^{(m)},E_{k,0,1}^{(m)})=\mathsf{t r u e}
$$
$$
\mathcal{R}_{3}\qquad\mathsf{Z K L Q C h e c k}(X_{1}-(X_{2}-y_{m})\cdot X_{3},E_{k},E_{k,1,0},V_{k,m}^{*};E_{k,0,0},E_{k,1,0}^{(m)},E_{k,0,1}^{(m)})=\mathsf{t u u e}
$$
## D Proving Correct Noise
In the case of an honest choice of the rk’s by the sender, coecients of u follow a Gaussian
0 0
distribution on Z with standard deviation *Z*. For their privacy, the sender needs 10*Z*
2 *B⁰*, where *B⁰* is the maximal error in the clean ciphertext (d*;*d⁰). This bound is analysed
later.
$$
\ {mathsf r_{{k}}}^{\mathrm{~S~}}
$$
$$
Z\cdot\sigma^{\prime}
$$
$$
10Z\cdot\sigma^{\prime}\geq
$$
$$
2^{\lambda}\cdot B^{\prime}
$$
$$
B^{\prime}
$$
$$
(\mathsf{d},\mathsf{d}^{\prime})
$$
Eventually, the publication of the linear combination r reveals information about the rk’s,
and the larger is, the more information leaks. For the check on r to detect large coecients,
one should avoid similar coecients to compensate, and so with similar random coecients in
the linear combination: false negative will happen with probability bounded by 1*=*2. We can
reduce it to *"*s*=*3 with iterations: (1*=*2) *"*s*=*3, with log₂(3*="*s)*=*(1+log₂). On the other
hand, we need to make sure that enough entropy remains: entropy of Gaussian random variables
*p p*
0 0
*r*k;iis log₂( 2*e*), so globally there are *Z* log₂( 2*e*) bits of entropy revealed. With linear
*p*
0
combinations, one reveals log*q* bits for each index *i*. One would like to still have log2(Z 2e)
*p* p
0 0
bits remaining for true randomness in the noise: *Z* log₂( 2*e*) log₂ *q* + log₂(*Z* 2*e*):
$$
\mathrm {r} _ {k} ^ {\prime} \mathrm {s},
$$
$$
\theta
$$
$$
\varepsilon_{s}/3
$$
$$
\theta\geq\mathrm{l o g}_{2}(3/\varepsilon_{s})/(1+\mathrm{l o g}_{2}\eta)
$$
$$
(1/2\eta)^{\theta}\leq\varepsilon_{s}/3
$$
$$
r_{k,i}\,\mathrm{i s}\,\log_{2}(\sigma^{\prime}\sqrt{2\pi e})
$$
$$
Z\log_{2}(\sigma^{\prime}\ \sqrt{2\pi e})
$$
$$
\log_{2}(Z{\cdot}\!^{\prime}\!{\sqrt{2\pi e}})
$$
$$
Z \log_ {2} \left(\sigma^ {\prime} \sqrt {2 \pi e}\right) \geq \theta \log_ {2} q + \log_ {2} \left(Z \cdot \sigma^ {\prime} \sqrt {2 \pi e}\right)
$$
$$
\begin{aligned}{\theta=\operatorname{l o g}_{2}(3/\varepsilon_{s})/(1+\operatorname{l o g}_{2}\eta)}\end{aligned}
$$
On the other hand, for the correctness during the decryption, if u, e₁, and e₂ follow the same
0
process, we will need *q >* 2*t* 10*Z²* (2*nB* + 1), as the randomness in the decryption key is
likely bounded by *B* = 10. Hence, *q* 2 *Z* 2*tB⁰*(2*nB* + 1), where *B⁰* is the error bound in
the clean ciphertext (d*;*d⁰), after deterministic evaluation.
$$
\mathsf{u},\,\mathsf{e}_{1}
$$
$$
\mathbf{e_{2}}
$$
$$
q>2t\cdot10Z^{2}\cdot\sigma^{\prime}\eta\cdot(2n B+1)
$$
$$
B=10\sigma
$$
$$
q\geq2^{\lambda}\eta Z\times2t B^{\prime}(2n B+1)
$$
$$
B^{\prime}
$$
## E FHE Parameters
As explained in the preliminaries, we consider the Fan-Vercauteren Fully Homomorphic Encryption scheme [FV12].
n
Notations. Let *R* be the ring Z[*X*]*=*r(*X*), where r(*X*) = *X* + 1. Given a polynomial p *2R*,
we denote *k*p*k₁* the innity norm, *i.e.* the max of its coecients. We also dene the polynomial
multiplication expansion factor as
$$
\|\ {pm p}\|_{\infty}
$$
$$
{\mathsf{r}}(X)=X^{n}+1
$$
$$
{\mathcal{D}}[X]/{\mathfrak{r}}(X)
$$
$$
{\mathfrak{p}}\in{\mathcal{R}}
$$
$$
\delta
$$
$$
\delta=\operatorname*{m a x}_{\mathsf{c},\mathsf{d}\in\mathcal{R}}\{{\left\|{\mathsf{c}\cdot\mathsf{d}}\right\|}_{\infty}/(\left\|{\mathsf{c}}\right\|_{\infty}\cdot{\left\|{\mathsf{d}}\right\|}_{\infty})\}.
$$
n
By taking the cyclotomic polynomial r(*X*) = *X* + 1, the worst-case bound for this expansion
factor is = *n*.
$$
{\mathfrak{r}}(X)=X^{n}+1
$$
$$
\delta=n
$$
---
The Fan-Vercauteren FHE. We denote *R*t= Zt[*X*]*=*r(*X*) (with r *2* Zt[*X*] an irreducible
polynomial of degree *n*) the plaintext message space and *R*q= Zq[*X*]*=*r(*X*) the ciphertext
space, and we denote = *q=t*. We will denote the Gaussian distribution on Z with standard
deviation.
$$
\mathcal{R}_{t}=\mathbb{Z}_{t}[X]/{\mathsf{r}}(X)
$$
$$
\mathrm {r} \in \mathbb {Z} _ {t} [ X ]
$$
$$
\mathcal {R} _ {q} = \mathbb {Z} _ {q} [ X ] / \mathrm {r} (X)
$$
$$
\varDelta=q/t
$$
$$
\sigma.
$$
$$
\mathbb{Z}
$$
The FV encryption scheme [FV12] denes (p*;*p⁰) = ( (a s + e)*;*a) *2R²*qas the public key,
with the coecients of the secret key s and the error e taken from, thereafter reduced modulo
*q*. A fresh ciphertext of m *2R*tcan be written as
$$
{\bigl(}{\mathfrak{p}},{\mathfrak{p}}^{\prime}{\bigr)}={\bigl(}-{\bigl(}{\mathfrak{d}}\cdot{\mathfrak{s}}+{\mathfrak{e}}{\bigr)},{\mathfrak{d}}{\bigr)}\in\mathcal{R}_{q}^{2}
$$
$$
\chi,
$$
$$
\mathfrak{m}\in\mathcal{R}_{t}
$$
$$
(\mathsf{c},\mathsf{c}^{\prime})=\left(\mathsf{p}\cdot\mathsf{u}+\mathsf{e}_{1}+\varDelta\cdot\mathsf{m}\bmod q,\mathsf{p}^{\prime}\cdot\mathsf{u}+\mathsf{e}_{2}\bmod\ )\right.,
$$
with coecients of u*;*e₁*;*e₂ also taken from. In order to decrypt, using the secret key s, one
computes
$$
\mathsf{u},\mathsf{e}_{1},\mathsf{e}_{2}
$$
$$
{\mathsf{m}}^{\prime}=|{\mathsf{d}}/{\varDelta}|=|{(\Delta{\mathsf{\Delta}}\ {\mathsf{m}}+{\mathsf{v}})}/{\varDelta}|={\mathsf{m}}+|{\mathsf{v}}/{\varDelta}|\bmod t
$$
where v = e u + e₂ s + e₁ is the error term: m⁰ = m if *k*v*k₁ =*2.
$$
v = - e \cdot u + e _ {2} \cdot s + e _ {1}
$$
$$
\mathsf{m}^{\prime}=\mathsf{m}\;\mathrm{i f}\;\big\|\mathsf{v}\big\|_{\infty}\leq\varDelta/2.
$$
Assuming the coecients of the error polynomials and the secret key polynomial are bounded
by *B*, we just require *B* (2*nB* + 1) *=*2 for correct decryption. In particular, Pr[*k*e*k₁ >*
$128
10*;* e] 2.
$$
B\cdot(2n B+1)\leq\varDelta/2
$$
$$
\mathrm{P r}\big\|\mathbf{\hat{e}}\big\|_{\infty}>
$$
$$
10\cdot\sigma,\mathsf{e}\xleftarrow{\S}\chi]\leq2^{-128}
$$
Semantic Security. From [PRS17]], if 0 < 1 be some real, and the modulus q is such
that = *q* =*!*(1), then there is a polynomial quantum reduction from the SIVP problem with approximation factor (*n*) to the average-case decision Ring-LWE where (*n*)
*p p*
max*f!*( *n*log *n=*)*;* 2*ng*. For the SIVP problem to be hard, we need (*n*) to be polynomial
in *n*. And the semantic security of the FV scheme relies on the decision Ring-LWE problem.
*p p*
We can take = *q* = *n*, then we have (*n*) *q* log*n*, which will be polynomial in *n*, in our
case.
$$
0\,\leq\,\alpha\,<\,1
$$
$$
\sigma\,=\,\alpha q\,=\,\omega(1)
$$
$$
\gamma(n)
$$
$$
\gamma(n)\;\leq
$$
$$
\mathrm {k} \left\{\omega (\sqrt {n \log n} / \alpha), \sqrt {2} n \right\}
$$
$$
\gamma(n)
$$
$$
\sigma=\alpha q={\sqrt{n}}
$$
$$
\gamma(n)\leq q{\sqrt{\log n}}
$$
0i
Correctness Let ai*2 R*tbe *L* polynomials and (ci*;* c) be *L* ciphertexts generated with a
circuit of depth *d*, encrypting mi*2R*t. In order to decrypt the linear combination, we compute:
$$
\mathsf{a}_{i}\,\in\,\mathcal{R}_{t}
$$
$$
(\mathsf{c}_{i},\mathsf{c}_{i}^{\prime})
$$
$$
d,
$$
$$
\mathfrak{m}_{i}\in\mathcal{R}_{t}
$$
$$
\begin{array}{l} \sum_ {i = 1} ^ {L} a _ {i} \cdot c _ {i} + s \cdot \sum_ {i = 1} ^ {L} a _ {i} \cdot c _ {i} ^ {\prime} = \sum_ {i = 1} ^ {L} a _ {i} \left(c _ {i} + s \cdot c _ {i} ^ {\prime}\right) \\ = \sum_ {i = 1} ^ {L} a _ {i} \left(\Delta \cdot m _ {i} + v _ {i}\right) \bmod q = \Delta \cdot \sum_ {i = 1} ^ {L} a _ {i} \cdot m _ {i} + \sum_ {i = 1} ^ {L} a _ {i} \cdot v _ {i} \bmod q \\ \end{array}
$$
We have the required (*L;d*)-*R*tlinear homomorphism property if
$$
(L,d)\!{\ -\!{\mathcal{R}}_{t}}
$$
$$
{\left\|{\sum_{i=1}^{L}{\mathsf{a}}_{i}\cdot{\mathsf{v}}_{i}}\right\|}_{\infty}\leq\sum_{i=1}^{L}n{\left\|{{\mathsf{a}}_{i}}\right\|}_{\infty}\cdot{\left\|{{\mathsf{v}}_{i}}\right\|}_{\infty}\leq n t\sum_{i=1}^{L}{\left\|{{\mathsf{v}}_{i}}\right\|}_{\infty}\leq\varDelta/2.
$$
Using [LN14] noise derivation formula, the error noise growth after having evaluated a sequence
d d 1 d 1
of *d* multiplications with a fresh ciphertext is bounded by *C₁V* +*dC₁ C₂* = *C₁* (*C₁V* +*dC₂*),
where
$$
C_{1}^{d}V\!+\!d C_{1}^{d-1}C_{2}=C_{1}^{d-1}\!\cdot\!(C_{1}V+d{C_{2}})
$$
$$
C_{1}=n^{2}t B+4n t\qquad\quad C_{2}=n^{2}B(B+t^{2})+\frac{n\ell q^{2/\ell}B}{2}\qquad\quad V=B(2n B+1)
$$
where
$$
C_{1}\leq11t n^{5/2}\qquad\qquad\qquad C_{2}\leq20n^{\frac{3}{2}}t^{2}(n+\ell)\qquad\qquad\qquad V\leq201n^{2}
$$
---
$$
w=q^{2/\ell}\leq4t^{2}
$$
$$
n\geq5,\,\sigma=\sqrt{n},\,B=\ 100\cdot\sqrt{n}\leq t^{2}
$$
*p p*
2 2=‘ 2
assuming *n* 5, = *n*, *B* = 10 *n t*, and the basis for relinearization *w* = *q* 4*t*.
With the additional assumption *‘ n*, the initial error in the result is bounded by
d 1 =2 d
$$
\ell\leq n
$$
$$
L n t\cdot C_{1}^{d-1}\cdot\big(C_{1}V+d C_{2}\big)\leq L n t\cdot(11t n^{5/2})^{d}\cdot\big(201n^{2}+4d t\big).
$$
2 +4 =2 d
With our additional noise-ooding, the error is still bounded by 2 *Lnt* (11*tn⁵*) 201*n²*+
4*dt*. For this bound, we take the pessimistic situation of = 2 and *Z* = 16.
$$
2^{2\lambda+4}L n t\cdot\,(11t n^{5/2})^{d}\cdot\,(201n^{2}+
$$
$$
4d t]
$$
$$
\eta=2^{\lambda}
$$
$$
Z=16.
$$
2 +4 =2 d
With *dt* 201*n²*, it is sucient to have the condition: 5 2 *t²Lnd* (11*tn⁵*) *q=*2*t*.
‘
As t = p₁ < ::: < p‘, q t. We can thus take ‘ such that
2 =2 d ‘ 3 d
$$
d t\geq201n^{2}
$$
$$
5\,\cdot\,2^{2\lambda+4}\,\cdot\,t^{2}L n d\,\cdot\,(1t t t^{5/2})^{d}\,\leq\,q/2t
$$
$$
t=p_{1}<\ldots2 *Lnd*) to have the (*L;d*)-*R*tlinear
homomorphism property and noise-ooding. In particular, we will need the (*N;d*)-*R*tlinear
=2 2 1=d
homomorphism property: *t²* 11*n⁵* (160 2 *Nnd*), which will be satised as we already
d d =2 2 1=d
need *t* 64 24*‘N* 128*‘n*, with *S* = 5, *N* = *n*, and 11*n⁵* (160 2 *Nnd*) =
=2 2 1=d =2+1=d (2 +8)=d 5+(2 +8)=d 58
11*n⁷* (160 2 *nd*) 22*n⁷* 2 2 *n⁴* 2 *n⁴* when *d* 5 and
2 44 d 6 2 d 8
= 128. This is less than (128) 2 *n² n* (128) *n² t²* when *n* 2.
$$
\ell\,=\,3(d+1)
$$
$$
t ^ {2} \geq 1 1 n ^ {5 / 2} \cdot (1 6 0 \cdot 2 ^ {2 \lambda} \cdot L n d) ^ {1 / d}
$$
$$
(L,d)\!{\ -\!{\mathcal{R}}_{t}}
$$
$$
t^{2}\geq11n^{5/2}\cdot(160\cdot2^{2\lambda}\cdot N n d)^{1/d}
$$
$$
(N,d)\mathcal{R}_{t}
$$
$$
t\geq64\times24\ell N\geq128\ell n^{d}
$$
$$
S\,=\,5,\,N\,=\,n^{d}
$$
$$
11n^{5/2}\cdot(160\cdot2^{2\lambda}\cdot N n d)^{1/d}=
$$
$$
11n^{7/2}\cdot(160\cdot2^{2\lambda}\cdot n d)^{1/d}\,\leq\,22n^{7/2+1/d}\cdot\,2^{(2\lambda+8)/d}\,\leq\,2^{5+(2\lambda+8)/d}n^{4}\,\leq\,2^{58}n^{4}
$$
$$
d\geq5
$$
## F Python Script for Parameters
$$
n\geq2^{8}
$$
$$
\lambda=128
$$
$$
({128})^{2}\cdot2^{44}\cdot n^{2d}\cdot n^{-6}\leq({128})^{2}\cdot n^{2d}\leq t^{2}
$$
## F.1 Parameters Choice
In the application, we performed optimizations on the parameters that were not necessarily
detailed in the main paper description, but will be in this section to make all parameter choices
clearer.
{ The security parameter is set as 128, to have an 128-bit security;
30
{ The soundness parameter *"*sis chosen among standard values at 2 for interactive proofs
80 128
and 2 and 2 for non-interactive proofs;
$$
2^{-30}
$$
$$
\varepsilon_{s}
$$
$$
2^{-80}
$$
$$
2^{-128}
$$
{ The specic soundness parameter for commitments *"*cis taken to be less than *"*s*=*3c, where
*c*= 14 + 5 + 3*Z*, so that all the commitments are valid excepted with probability less
than *"*s*=*3, making up for a third of the possible soundness error.
$$
\varepsilon_{c}
$$
$$
\varepsilon_{s}/3\nu_{c}.
$$
$$
\nu_{c}=14\varLambda+5+3Z
$$
$$
\varepsilon_{s}/3
$$
{ The number =
l mof points, committed polynomials have to be evaluated in, is taken as
log2(24="s) S S
, where *S* is the margin length parameter given by *t* 2 2*D‘* = 2 4*N‘*.
S+1+log2(N=n)
This ensures that times the probability a quadratic relationship with polynomials in
S+1
is wrong, 2*‘n=t n=*(2 *N*), is less than *"*s*=*24, and as there are 8 relationships to check,
the error coming from these verications will not exceed *"*s*=*3, making up for a second third
of the possible soundness error;
$$
\varLambda=
$$
$$
\left\lceil\frac{\log_{2}(24/\varepsilon_{s})}{S+1+\log_{2}(N/n)}\right\rceil
$$
$$
t\geq2^{S}\cdot2\mathcal{D}\ell=2^{S}\cdot4N\ell
$$
$$
2\ell n/t\leq n/(2^{S+1}N)
$$
$$
\beta_{\kappa}
$$
$$
\varepsilon_{s}/24
$$
$$
\varepsilon_{s}/3
$$
{ We choose = 4 and *B* = 10 as the corresponding FHE parameters;
{ is the bound of the distribution of the scalarsk*2* [[;]] being multiplied with small errors
in the noise checks to prove (z*;*z⁰) is correct, where soundness error is also bounded by *"*s*=*3,
making up for the last third of the possible soundness error. Because of the noise ooding
l m
=(1+log2)
constraints, there are *Z* = 2 + of these scalars at each draw, = 2
log2()+1
l m
draws, and the noise ooding constraints add + log₂() + log₂(2 +) bits to *q*;
log2()+1
{ Getting the FHE parameters:
$$
\delta_{k}\in[-\eta;\eta]
$$
$$
(\mathbf{z}^{*},\mathbf{z}^{\prime*})
$$
$$
\varepsilon_{s}/3.
$$
$$
Z=2+\left\lceil\frac{\lambda}{\log_{2}(\eta)+1}\right\rceil
$$
$$
\theta=\left\lceil2^{\lambda/(1+\log_{2}\eta)}\right\rceil
$$
$$
\left[ \lambda + \log_ {2} (\eta) + \log_ {2} \left(2 + \frac {\lambda}{\log_ {2} (\eta) + 1}\right) \right]
$$
S S
{ *t* is taken to be the next prime above 2 2*D‘* = 2 4*N‘* such that *t* 8 mod 3, so that
*R*tbe a ring product of two large elds of degree *n=*2 each, and the probability of having a
false (b*;*b⁰) decoding to the right value be negligible;
$$
\ mathcal R,{}it
$$
$$
t\equiv8
$$
$$
2^{S}\cdot2\mathcal{D}\ell=2^{S}\cdot4N\ell
$$
$$
n/2
$$
{ the *‘* 1 next primes are then multiplied with *t* to obtain *q*;
{ the maximal error in FHE ciphertexts after *d* multiplications is then calculated, and we
check it remains small enough to ensure correctness;
{ the FHE security with these parameters is calculated using the external reference estimator [APS15].
---
RSAM
{ After these FHE parameters were calculated, a lower bound on the Paillier modulus (2),
8*nNq³*2 is given, so that we can be sure the Paillier encodings are never reduced modulo
*N*. We take *jNj* (RSAM) as the maximum of this bound and 2048 to ensure satisfactory
security (above 100-bit security).
$$
(2^{\mathsf{R S A M}})
$$
$$
8n{N}q^{3}2^{\lambda}
$$
Then we use the following numbers:
{ FHE ciphertexts are on 2*n*log*q* bits;
1=(d+1)
{ The receiver sends (*d*+ 1) (*N* + 1) of these, and this is how the Global FHE Ciphertexts Size is calculated;
l m
$$
(d\!+\!1)\lceil(N+1)^{1/(d+1)}\rceil
$$
log2(24="s)
{ The number of points is =;
S+1+log2(N=n)
$$
\varLambda=\left\lceil\frac{\log{_2}(24/\varepsilon_{s})}{S+1+\log{_2}(N/n)}\right\rceil
$$
{ The number of commitments,c= 14 + 3*Z* + 5;
$$
\nu_ {c} = 1 4 \Lambda + 3 Z + 5;
$$
{ The encoding parameters are then calculated for the commitments, depending on *c*, the
maximal number of prover-generated commitments they will be involved with in a single
quadratic check (see Figure3);
l m
log2(3 c="s)
{ The number of times a Zero-Knowledge Proof has to be repeated is taken as;
log2t
{ We need for commitments and equations involving *c* prover-generated commitments
$$
\left\lceil\frac{\operatorname{l o g}_{2}(3\nu_{c}/\varepsilon_{s})}{\operatorname{l o g}_{2}t}\right\rceil
$$
$$
\begin{array}{l l}{K\geq\operatorname{l o g}_{2}(3\nu_{c}/\varepsilon_{s})(c+1)/S}qquad&K geq\\({{\operatorname{l o g}_{2}(3\nu_{c}/\varepsilon_{s}))}+1)(c+1)/(S+1)}\\ {M\geq3({\operatorname{l o g}_{2}(3K\nu_{c}/\varepsilon_{s})}+2)/(S+1)}\\ \end{array}
$$
$$
K = \max \left\{\left[ (c + 1) \times \frac {\log_ {2} \left(\varepsilon_ {c}\right) + 1}{S + 1} \right]; \left[ (c + 1) \times \frac {\log_ {2} \left(3 \nu_ {e} / \varepsilon_ {s}\right)}{S} \right] \right\}
$$
l m l m l m
log2("c)+1 log2(3 e="s) 2+log2(" K c)
So we take *K* = max*f* (*c* + 1); (*c* + 1) *g* and *M* = 3.
S+1 S S+1
{ In the binding case, there are *M* scalars, with *K*(*M* + 2) encodings for the commitment
of a one variable polynomial and 2*K*(*M* + 1) encodings for a two variables polynomial.
$$
M=\left\lceil3\times\frac{2+\log{_22}(\varepsilon_{c}K)}{S+1}\right\rceil
$$
$$
K(M+2)
$$
{ In the hiding case, there are always *K*(*M* + 1) encodings and 2*K*(*M* + 1) + *M* scalars,
times the number of repetitions.
{ Each Paillier encoding holds on 4*jNj* bits;
{ Each proof holds on 2*jNj* + 4 log₂ *q* bits.
$$
2|\mathcal{N}|+4\log_{2}q
$$
{ All the sizes of the commitments given in gure4are then added up and the nal size of
the sender’s communications encompasses this and the size of the 6(1 +) elements of *R*q
directly sent to the receiver.
$$
\mathcal{R}_{q}
$$
| #Prover-Generated Commitments:c | | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| $\varepsilon_{c}=2^{-38}$ | K | 26 | 35 | 43 |
| $\varepsilon_{c}=2^{-38}$ | M(and binding case #Scalars) | 20 | 20 | 20 |
| $\varepsilon_{c}=2^{-38}$ | #Equations(hiding case) | 2184 | 2940 | 3612 |
| $\varepsilon_{c}=2^{-38}$ | #Secrets(hiding case) | 4448 | 5960 | 7304 |
| $\varepsilon_{c}=2^{-38}$ | #Encodings for 1v Pol. | 572 | 770 | 946 |
| $\varepsilon_{c}=2^{-38}$ | #Encodings for 2v Pol. | 1092 | 1470 | 1806 |
| $\varepsilon_{c}=2^{-136}$ | K | 75 | 100 | 125 |
| $\varepsilon_{c}=2^{-136}$ | M(and binding case #Scalars) | 62 | 62 | 63 |
| $\varepsilon_{c}=2^{-136}$ | #Equations(hiding case) | 18900 | 25200 | 32000 |
| $\varepsilon_{c}=2^{-136}$ | #Secrets(hiding case) | 38048 | 50648 | 64252 |
| $\varepsilon_{c}=2^{-136}$ | #Encodings for 1v Pol. | 4800 | 6400 | 8125 |
| $\varepsilon_{c}=2^{-136}$ | #Encodings for 2v Pol. | 9450 | 12600 | 16000 |
$$
\boxed{\varepsilon_{c}=2^{-38}~~K}
$$
8
Fig. 3. Parameters for Commitments with *t* 64*‘D*, four repetitions in the zero-knowledge proofs, *"s* = 2 *"c*,
and *e* = 11.
$$
t\geq64\ell\mathcal{D}
$$
$$
\varepsilon_{s}=2^{8}\cdot\varepsilon_{c},
$$
$$
\nu_{e}=11
$$
---
| #variables | c | Binding or Hiding | Polynomials | Domain | #commitments |
| --- | --- | --- | --- | --- | --- |
| 1v | 2 | B | yκ,y'κ | R4 | 2A |
| 1v | 2 | H | q*，q'*，q'*，q'*，z'*，z'* | R1 | 2(2A+1) |
| 1v | 3 | H | u'k，e'1,k，e'2,k | R1 | 3Z |
| 1v | 4 | B | vκ,v'κ | R3 | 2A |
| 1v | 4 | B | sκ,s'κ | R4 | 2A |
| 2v | 3 | B | u,u'，wκ，w'κ | R2 | 2(A+1) |
| 2v | 3 | H | f*，h'κ | R2 | A+1 |
| Total | | | | | 14A+5+3Z |
$$
{\mathcal R}_{4}
$$
$$
\underline{{\mathsf{y}_{\kappa}}},\mathsf{y}_{\kappa}^{\prime}
$$
$$
\overline{{\mathsf{q}^{*},\mathsf{q}^{\prime*},\:\mathsf{q}_{\kappa}^{*},\:\mathsf{q}_{\kappa}^{\prime*}}}
$$
$$
\ {mathsf{}}{\mathsf{{}}}{\mathsf{}}_{k}^{*},\:{{\mathsf{}}}{\mathsf{}}{\mathsf{}}_{1,k}^{*},\:{{\mathsf{}}}
$$
$$
\mathsf{v}_{\kappa},\mathsf{v}_{\kappa}^{\prime}
$$
$$
\ \mathcal{R}_{3}
$$
$$
\mathsf{s}_{\kappa},\mathsf{s}_{\kappa}^{\prime}
$$
$$
\mathcal{R}_{1}
$$
$$
{\mathcal R}_{4}
$$
$$
\overline{{\mathcal{R}_{1}}}
$$
$$
\overline{{\mathcal{R}}}_{3}
$$
$$
\mathsf{u},\mathsf{u}^{\prime},\mathsf{w}_{\kappa},\mathsf{w}_{\kappa}^{\prime}
$$
$$
\mathcal {R} _ {2}
$$
$$
2(\varLambda+1)
$$
$$
\overline{{\mathsf{f}^{*},\mathsf{h}_{\kappa}^{*}}}
$$
$$
\overline{{\mathrm{}{R}}}{\mathrm{}{R}}_{2}
$$
$$
\overline{{14\varLambda+5+3Z}}
$$
Fig. 4. Number of Commitments in the Global Proof, and Size in Number of Encodings, with = *d*(3 +
log₂(3*="s*))*=*(*S* + 1 + log₂(*N=n*))*e*
$$
\log_{2}(3/\varepsilon_{s}))/big(3+1+\log_{2}(N/n)\big)
$$
## F.2 Script
Here is the python script used to generate our gures, whose parameters are described above.
from sage.allimport ∗
import math,ssl
try:
load("estimator.py")#usethelocalscriptifyoudownloadeditbecauseitgainsalotoftime
except:
ssl. create default https context = ssl. create unveried context
load("https://bitbucket.org/malb/lwe-estimator/raw/HEAD/estimator.py")
#incasessldoesnotworkthislecanbedownloaded.
#load("estimator.py")
logging.getLogger("estimator").setLevel(logging.WARNING)
#Parameterstobetested
#MarginLengthfort:t *>* 2∗∗MarginLength ∗ D ∗ ell
Values = [#lN,ln,d,ell,MarginLengh
[20 , 14 , 4 , 14, 21],
#BEST20
[25 , 15 , 5 , 16, 16],
#BEST25
[30 , 14 , 5 , 16, 11],
[30 , 15 , 5 , 15, 20],
#BEST30
[35 , 15 , 5 , 15, 15],
[35 , 15, 5, 14, 25],
#BEST35
[40 , 15 , 5 , 15, 10],
#BEST40
]
secpar = 128#lambda
#Securityboundsforcommitments
Eps = [ 30, 80, 128 ]
EpsC = [ 38, 136 ]
log2 eta = 21
Z = 2 + ceil(secpar/(log2 eta+1))#numberofencodingsofzerocommittedbythesender
theta = ceil(2∗∗(secpar/(log2 eta+1)))#numberoftimeswedrawscalarstoprovethez^∗,z^∗’
addpar = log2 eta + math.log2(2+secpar/(log2 eta+1))#becauseofnoise−ooding
MB = 8∗1024∗1024#MBytes
MinMarginLength = 5#t *>* 32 ∗ 4Nell
sigma = 4
B = 10∗sigma
#calculatingthenumberofcommitments:nuc=AnbCmt∗Lambda+BnbCmt
AnbCmt = 14
BnbCmt = 5+3∗Z
nue = 11#numberofquadraticrelationsbetweencommitmentsthereceiverhastocheck def bitSizeOf(x):
try: return math.ceil(math.log2(x))
except: return 0
def security(n, alpha, q):
cost = estimate lwe(n, alpha, q)
min = 1000
for algo in cost.keys():
ifmin *>* bitSizeOf(cost[algo][’rop’]):
min = bitSizeOf(cost[algo][’rop’])
returnmin
#SecurityEvaluationofFHEParameters
def FHE(lN, ln, d, ell, MarginLength):
N = 2∗∗lN; n = 2∗∗ln; D = 2∗N
parameters = *f* ’logN’: lN, ’n’: n, ’d’:d*g*
parameters[’ell’] = ell
#CorrectnessFHE
#Selectionoftheprimenumbers
p=[0]∗ell
pmin = 2∗∗MarginLength ∗ 2 ∗ D ∗ ell
p[0]=next prime(pmin)
while (p[0] % 8) != 3: p[0] = next prime(p[0]+1)
t = p[0]
q = t
for i inrange(ell−1):
p[i+1] = next prime(p[i]+1); q = q∗p[i+1]
#Analysisofthenoise
C1 = n∗n∗t∗B + 4∗n∗t
w = q∗∗(2/ell); lw = math.oor(ell/2)+1
C2 = n∗n∗B∗(B+t∗t)+n∗lw∗w∗B; V = B∗(2∗n∗B+1)
error = N∗n∗t∗C1∗∗(d−1)∗(C1∗V+d∗C2)∗(2∗∗(secpar+addpar)); ratio = 2∗t∗error/q#addednoiseoodingerror
parameters[’ratio’] = ratio
#PrivacyFHE
sec = security(n, sigma/q, q)
parameters[’logMargin’] = MarginLength
parameters[’logpl’] = bitSizeOf(p[−1])
parameters[’logt’] = bitSizeOf(t)
parameters[’logq’] = bitSizeOf(q)
parameters[’sec’] = sec
parameters[’RSAM’] = max(2048,3+ln+lN+3∗bitSizeOf(q)+secpar)#greaterthan2048forsecurity
return parameters
#NumberofEncodings
def encodings(epsc, MarginLength, ZKrepetitions, epss, nue):
C = [2, 3, 4]#numberofprover−generatedencodingsinequation
SizeE = [*fg*]∗5
for c in C:
gamma = c+1
K = math.ceil(gamma ∗ max((epsc+ 1)/(MarginLength+1), (math.log2(3∗nue)+epss)/MarginLength))
M = math.ceil(3 ∗ (epsc +2 + math.log2(K) ) / (MarginLength+1))
SizeE[c] = *f* ’K’: K, ’M’: M,
’1vEB’: K∗(M+2), ’2vEB’: 2∗K∗(M+1), ’EH’: ZKrepetitions∗K∗(M+1),
’SB’: M, ’SH’: ZKrepetitions∗(2∗K∗(M+1)+M) *g*
return SizeE
def get application results():
print("Z: "+str(Z))
print("additional bits on q: "+ str(ceil(addpar+secpar)))
for val in Values:
print("\n**********")
param = FHE(val[0], val[1], val[2], val[3], val[4])
print("\n-----------\n RSA Modulus: "+str(param[’RSAM’]))
print("\n N = 2^"+str(param[’logN’]))
print(" n = 2^"+str(bitSizeOf(param[’n’])))
print(" d = "+str(param[’d’]))
print(" ell = "+str(param[’ell’]))
print(" S = "+str(param[’logMargin’])+" >=? "+str(MinMarginLength))
print(" t on "+str(param[’logt’])+" bits")
print(" p_ell on "+str(param[’logpl’])+" bits")
print(" q on "+str(param[’logq’])+" bits")
print(" ratio = "+str(param[’ratio’]))
if param[’ratio’] *>* 1:
---
print("Correctness error! Parameters not compatible")
else:
print(" Best attack against FHE: "+str(param[’sec’]))
RSAM = param[’RSAM’]
SizeFHE = 2∗param[’n’]∗param[’logq’]
GlobalFHECiphersSize = ceil((2∗∗(param[’logN’])+1)∗∗(1/(param[’d’]+1)))∗(param[’d’]+1)∗SizeFHE
print(" FHE Size: "+str(math.ceil(GlobalFHECiphersSize/MB))+" MB")
secInd=0
for epss in Eps:
secInd=secInd+1
Lambda = math.ceil((3+epss+math.log2(3))/(param[’logN’]+param[’logMargin’]+1−math.log2(param
*,!* [’n’])))
nuc = AnbCmt∗Lambda + BnbCmt#totalnumberofcommitments
ZKrepetitions = ceil((math.log2(3∗nuc)+epss)/param[’logt’])
epsc = epss + math.ceil(math.log2(3∗nuc))
SizeE = encodings(epsc, param[’logMargin’], ZKrepetitions, epss, nue)
SizeLOE = 4∗RSAM; SizeScalar = param[’logq’]
SizeProof = 2∗RSAM + 4∗param[’logq’]#AppendixB2,mu=4
v1c2B = 2∗Lambda∗(SizeLOE∗SizeE[2][’1vEB’] + SizeScalar∗SizeE[2][’SB’])#bindingwith1vandc=2
v1c2H = 2∗(2∗Lambda+1)∗(SizeLOE∗SizeE[2][’EH’] + SizeProof∗SizeE[2][’SH’])#1vc=2hiding
v1c3H = 3∗Z∗(SizeLOE∗SizeE[3][’EH’] + SizeProof∗SizeE[3][’SH’])#1vc=3hiding
v1c4B = 4∗Lambda∗(SizeLOE∗SizeE[4][’1vEB’] + SizeScalar∗SizeE[4][’SB’])#1vc=4binding
v1c4H = Lambda∗(SizeLOE∗SizeE[4][’EH’] + SizeProof∗SizeE[4][’SH’])#1vc=4hiding
v2c3B = 2∗(Lambda+1)∗(SizeLOE∗SizeE[3][’2vEB’] + SizeScalar∗SizeE[3][’SB’])#2vc=3binding
v2c3H = (Lambda+1)∗(SizeLOE∗SizeE[3][’EH’] + SizeProof∗SizeE[3][’SH’])#2vc=3hiding
GlobalEncodingsSize = v1c2B + v1c2H + v1c3H + v1c4B + v1c4H + v2c3B + v2c3H
GlobalBobComsSize = GlobalEncodingsSize + 6∗(1+theta)∗(bitSizeOf(param[’n’])+param[’logq’])#
*,!* addingsizeoftheb,b’,l,l’,d,d’,andthethetau∗,e1∗,e2∗ andrhocleartextsin *n*Rqsentby
*,!* Bob
print(" EPS_s: 2^{-"+str(epss)+"}--EPS_c: 2^{-"+str(epsc)+"}--Lambda: "+str(Lambda) + "
*,!*--#Commitments: "+ str(nuc)
+"--Bob Communic. Size: "+str(math.ceil(GlobalBobComsSize/MB))+" MB")
def get encodings g():
#gurewithnumberofencodingsandscalarspercommitment
print("\n**********\n Figure 1 data: \n")
for epsc in EpsC:
print("epsc = "+str(epsc))
SizeE = encodings(epsc, 6, 4, epsc+8, 11)
print("K: "+str(SizeE[2]["K"])+" & "+str(SizeE[3]["K"])+" & "+str(SizeE[4]["K"])+" \\\\ ")
print("M: "+str(SizeE[2]["M"])+" & "+str(SizeE[3]["M"])+" & "+str(SizeE[4]["M"])+" \\\\ ")
print("& \#Equations (hiding case) & "+ str(SizeE[2]["EH"]) +" & "+ str(SizeE[3]["EH"]) +" & "+ str(
*,!* SizeE[4]["EH"]) +" \\\\")
print("& \#Secrets (hiding case) & "+ str(SizeE[2]["SH"]) +" & "+ str(SizeE[3]["SH"]) +" & " + str(SizeE
*,!* [4]["SH"])+ " \\\\")
print("& \#Encodings for $1v$ Pol. & "+ str(SizeE[2]["1vEB"]) +" & "+ str(SizeE[3]["1vEB"]) +" & "+ str(
*,!* SizeE[4]["1vEB"]) + " \\\\")
print("& \#Encodings for $2v$ Pol. & "+ str(SizeE[2]["2vEB"]) +" & "+ str(SizeE[3]["2vEB"]) +" & " + str
*,!* (SizeE[4]["2vEB"]) + " \\\\")
get application results()
#get encodings g()