MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

;3;4;4 Malika Izabachene¹, Anca Nitulescu², Paola de Perthuis¹, and David Pointcheval³

¹ Cosmian

² Protocol Labs

³ DIENS, Ecole normale superieure, CNRS, PSL University, Paris, France ⁴ 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 c_iof the remaining powers m of m ⁱn order to evaluate a ciphertext of f(m) by a simple inner product with the vector of the coecients. The computation of the ciphertexts c_i 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 c_iinstead. Our scheme MyOPE requires the prover/sender to (compactly) commit the vector of ciphertexts (c_i)_iand prove it indeed coincides with the correct values. To check this, the receiver asks for a random linear combination of the c_i’s. Since the vector (c_i)_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 c_i’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₁;:::;xNg owned by the prover and Y = fy₁*;:::;yKg* 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 Z_t[X]=r(X), where r(X) = X +1, iⁿto the ciphertext ring Z_q[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 2nlogq bits long, and the underlying 30 plaintexts nlogt 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= Z_t[X]*=r(X) the plaintext message space and R_q= Z_q[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 kv*k₁ =*2.

$$ v = - e \cdot u + e _ {2} \cdot s + e _ {1} $$

$$ \ {\mathfrak{m}}^{\prime}={\mathfrak{m}} $$

0i 0f Eval(pk*;f;* (c_i; c)_i=1;:::;‘)! (c_f; c): Given pk, an arithmetic circuit f with bounded multiplica- 0i 0f tive depth and ‘ ciphertexts (c_i; c)_i=1_;:::;‘output the ciphertext (c_f; 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*;(c_f;* c)) should return f (m₁;:::;m‘) 0_i where Dec(sk*;(c_i;* 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 E_sk(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 Eval_pk(E₁;:::;E_L;c₁;:::;c_L), on input public information pk, encodings E₁ = E^sk(a₁), . . . , E^L= E^sk(a^L), and coecients c₁;:::;c^L2 R, P L outputs an encoding of c_ia_i; i₌₁

$$ \ \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 QCheck_vk(Q;E₁;:::;E_L), on input the verication key vk, a quadratic polynomial Q 2 R[X₁;:::;X_L] and encodings E₁ = E_sk(a₁), . . . , E_L= E_sk(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 Verify_vk(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 Ext_Asuch 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*_iE_sk(a_i), for i = 1*;:::;n,* and (E;c₁;:::;c_n) (AjjExt_A)(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_ia_i, for extractable elements c_i2 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 = Z_q). Then, Zero-Knowledge proofs will be needed for Quadratic root verications with private linear 0 combinations: ZKLQCheck_vk(Q;E₁;:::;E_L;E₁;:::;E⁰), on input a quadratic polynomial Q 2 0 R[X₁;:::;X_L] and encodings E₁ = E_sk(a₁), . . . , E_L= E_sk(a_L), E₁ = E_sk(b₁), . . . , E⁰ = E_sk(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_ib_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)) E_sk(a): A Paillier ciphertext of a scalar x 2 Z_Nis E = (1 + N) N 2$ r mod N, for some random r Z. An encoding is thus 4 logN 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 Z_N, but in order to get the L- linear homomorphism over Z_q, 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 Z_qon 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 > 2L 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 Z_q, 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} $$

{ Commit_pk(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 $$

{ Validity_vk(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} $$

{ Quadratic_vk(Q;C₁;:::;C_‘), for valid commitments C_iof (unknown) polynomials u_iand 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 Ext_Asuch that for any valid commitment C generated by A, Ext_Aoutputs 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ⁱE 0 (s). Then, the public key of the sk commitment scheme is pk = (pk⁰; fEig*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 = uⁱX 2 R₁ R of degree at most n 1, Pi=0 i outputs E = Eval(fE_ig_i; fu_ig_i) = E( u_is) = 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)) $$

{ Validity_vk(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₀;:::;En 1), one can extract (ci) such that E is an encoding of P n 1 i c₀ + c₁s + :::c_{n 1}s in R, and thus of the polynomial c = c_iX _in R. Our above comi mitment scheme o_n 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 = Z_q, 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 Z_q[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 Z_pj[X]. Under the Schwartz-Zippel lemma [Sch80,Zip79], this probability is bounded by 2n=p_jfor each j, as the total degree of the relation is at most 2n. Hence, the probability over s to have a false positive is bounded by 2n‘=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 (2n‘=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 Z_qfor 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 Z_q[X;Y]: u(X;Y) = Y u_j(X) = u_j;iX 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* = Z_q[X; Y]; R₂ = Z_q[X; Y]) rst runs (pk⁰*;sk⁰;vk⁰) Gen(1 ), chooses $ K tuples of random elements s_k;t*_kZ_qand, for k 2 [[1;K]], i 2 [[0;n 1]], and j 2 [[0;N]], sets ik j n 1 N Ek;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 Z_q. 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₂ = Z_q[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₂ = Z_q[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*;* Z_q[X; Y]), for a polynomial u = u_j;_iX Y ⁱ_n R₂ = Z_q[X;Y], j=0 i=0 (2) outputs C = (E_u= (E_k;E)_k;_u), for k 2 [[1;K]], with_udetailed 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 = Z_q[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₂ = Z^q[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 proof_u(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*=*3_cfor commitments, where_cwill 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_mZ_q, 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 v_k;m, w_k;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 2M=3 indices m. Then, for any k⁰ 6= k, that correspond to valid encodings E_kand Ek0, at least M=3 common values (xm;ym) satisfy both relations in k and k⁰, hence uk(xm*;ym) = u_k0 (x_m;y*_m) = u_m. As a consequence, as the polynomials ukand u_k0 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= uk0, excepted with probability upper-bounded by (‘D=t) ². A false acceptance for (S+1)M=3 some pair (k;k⁰) of consecutive valid encodings is upper-bounded by 2K 2. Globally, the probability of having a false positive among the valid encodings E_kis bounded by 2K (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= (E^k;E)^k, k after having received (or seen) (x_m;y_m)_m, one completes the commitment with the proofs_u, 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) Z_q, there exists a polynomial u 2 R₂ such that at least 4K=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 +2K 2, Q ‘ ^S where q = p_i, 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 2K 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 iⁿ Z_q[X] thus consist of 2K + KM = K(M + 2) enn 1 N codings, and M scalars in Z_qwhile commitments in Z_q[X;Y] coⁿsist of 2K + 2KM = 2K(M + 1) encodings, and M scalars in Z_q.

$$ \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 4K=5 valid encodings. When other values of c in f2; 3*;* 4g, 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₂ = Z_q[X;Y]. Iⁿ AppendixC, we also detail the case of R₃ = Z_q[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*;* Z_q[X; Y]), the hiding commitment for a bivariate polynomial u(X;Y) = P P₍₂₎ N n 1 i _{j n 1 N} u_j;iX Y 2R₂ = Z_q[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]], with_k; 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 1_kr, with private scalars_kand, and a k $ proof, using random x_m;y_mZ_qsent 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 random_k;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 to_k+ u(x_m;y_m)_k;m(t_ky_m) (s_kx_m). One thus proves their knowledge of the 4 private scalars,_k2M (the same as above), u_m= u(x_m;y_m) 2 R 0k;m (the same for all the k’s), and_k;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 i_n Z_q[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 2K(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 2K(M + 1) + M scalars in Z_q, iterated log(3_c="_s)=logt 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 factors_k;_k2 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 to_k1_kd, where_kand_kare 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=*3_e, where_eis 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₁ = Z_q[X], R₂ = Z_q[X;Y], R₃ = Z_q[Y], and Z_q[Y] with no N 2N nN S term in Y, denoted R₄ = Z_q[Y], hence D = 2N, so we will assume t 2 4N‘. 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}<\ldots<p_{\ell} $$

$$ q_{\gamma} $$

$$ \mathcal{R}=\mathbb{Z}_{a}|X^{n-1},Y^{2N}| $$

$$ \mathcal{R}{1}=\mathbb{Z}{q}[X_{\dots\dots}^{n-1}],\mathcal{R}{2}=\mathbb{Z}{q}[X^{n-1},Y^{N}],\mathcal{R}{3}=\mathbb{Z}{q}[Y^{N}], $$

$$ Y^{N} $$

$$ \mathbb{Z}_{q}[Y^{2N}] $$

$$ \mathcal{R}{4}=\mathbb{Z}{q}[Y^{2N\setminus N}] $$

$$ \mathcal{D}=2N $$

$$ t\geq2^{S}\times4N\ell $$

4 Veriable Inner Product

We now have the tools to allow the receiver/verier with their private input message m to learn in a veriable way the inner product of the vector (m) = ( (m*;0);(m;1);:::;(m;N*)) with a private vector F = (f^j)^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 (f_j)_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 Z_t[X]=r(X), where r = X + 1, iⁿto R_q= Z_q[X]=r(X) for q = p₁ ::: p_‘, with 2 4N‘ 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}<\ldots<p_{\ell} $$

The receiver encrypts the input m 2R^tunder 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 = (f_j)_j2[[0;N]]2R_t, committed by the sender, with a proof of correct value (d*;d⁰) = Enc(h (m);* Fi) 2R²_q, that thereafter decrypts to h (m); Fi2R_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 (u_j;* 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 ~⁰ and d = d⁰ + z⁰ so that (d*;* d) decrypts to h (m); Fi. 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 (u_j; 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 a_i; u_i2R_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 (c_i; c) 2R²_qis an encryption of u_iobtained 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₁ = Z_q[X]. The sender’s vector F 2 Rtcan be committed P P N j n 1 i using the polynomial f = f_jY in R_t[Y], where f_j= 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₂ = Z_q[X;Y] as f = f_j;iX Y (w_ith 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 ¹ Z_q[X]. The iⁿner products must be proven, which is the goal of the second part, after we 0j have proven the correct computation of the (u_j;* 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 (u_j; 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₂ = Z_q[X;Y] iⁿto 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]], (u_j; u) = Enc( (m*;j*)), or more precisely that the decryptions 0j Dec(u_j; 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 n_j= n = n_j;iX _in R_t, for all j 2 [[0;N]], and commit them in R₂ = Z_q[X;Y] as i=0 P P N n 1 _{i N} j t = n_j;iX Y (w_ith reverse order coecients) into T. Then, the prover computes j=0 i=0 P 0 N 0j 2 and sends (b*;* b) = n_j(u_j; 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 n_ju_j= b + l r, that they both commit as L in R₁ = Z_q[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 Z_q, for 2 [[1;]]. They will dene v_;j= u_j() 2 Z_qfor 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₃ = Z_q[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₂ = Z_q[X;Y] aⁿd 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) = n_j() 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 Z_q, 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_{0<i\neq j<N}v_{\kappa,i}\cdot{\mathsf{n}}{j}(\beta{\kappa})\cdot Y^{N+i-j}={\mathsf{y}}_{\kappa}(Y) $$

(2)

$$ \mathcal{R}{4}=\mathbb{Z}{q}[Y^{2N\setminus N}] $$

$$ Y_{\kappa} $$

2N nN N with a commitment Y of y in R₄ = Z_q[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, u_jn_j= 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⁼⁰ 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 Z_p[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 (2p + 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 ² 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 ²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 d_j)_jand z*;q . The same should be done for d 0j with respect to all (u)_jand z⁰;q⁰, but for the same (f_j)_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 (f_j)_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_;jY in R₃ = Z_q[Y], where g_;j= f_j(), j=0 n N and the hiding commitment of h (X;Y) in R₂ = Z_q[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)

$$ \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 Z_qthat 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₄ = Z_q[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 + 3Z. We explain the 3Z commitments in the next section to build (z*;z⁰). We thus need to take "^c"^s=(3^c) = "^s=(3(14 + 5 + 3Z*)).

$$ 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 d0 ~⁰ Indeed, after all these steps, on both d, one gets the proof that, in R_q, (d*;* d) is a ciphertext of h (m); Fi, 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 r_k, 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 P_kP 0 ri=_kr_k;ithat follow a Gaussian distribution on Z with standard deviationk. kPk ₀ 128 They should thus be smaller than 1₀k(excepted with probability 2). One can kP 0 0 thus check that. When true, this at least proves that jr_k;ij 10k1₀Z, with _k P$ 0 0 overwhelming probability. We can thus dene u = r_k, for random scalars f 1; 1g. We k k k 0 then know that kuk₁* 1₀Z². We will then have to consider this bound for 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 (¹="_s), we have = 5. We can then take Z = 8, = 2 B⁰=80, and q 2 2tB⁰(2nB+1). 128 This increases the initial size of q by + 3 + log more bits. With = ¹²⁸, "_s= 2, and ²¹ = 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*)) = (u_i; 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 The sender can generate (z*;* z) = (p u + e₁*;* p u + e₂ mod q), and send the k k k;k k;k ~ ~0 resulting 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 the_k(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 Z_qg, 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 ⁰ 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²_qg, 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 hF*;*(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 ~ ~⁰ (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₊₁ d i ₁) e. Then, any k 2 [[0;N]] can be written in basis b as x_ib, w_ith x_i2 [[0;b 1]]. Hence, i=0 x bi from the ciphertexts of all the powers m_ifor 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 and the noise, then we have (n) q logn, 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 2n elements in Z_q: 6(d + 1) nlogn bits each. The verier rst 1=d+1 d=d+1 2 1=d+1 sends (d + 1) (N + ¹) dn ciphertexts, so approximately 6d(d + ¹) n² logn ~(=d bits, which is in O(n² logn) = 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_ag of cardinality #X, the sender a set Y = fy₁;:::;y_bg 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 h_i) committed once for all in i=1 P, where the values h_i2R_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 4N‘. 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_Ng 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 an_d j = j_kb, where the k=0 k=0 _k;j_k2 [[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 Fp 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 Ext_Asuch 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 th^at c = g. The only way to compute ^c being to gener^ate (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₂;* G_T;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 Z_q: the encoding function E_skis E_sk(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}<\ldots<p_{\ell} $$

$$ \ell\neq1 $$

$$ q=p_{1}\cdot\ldots\cdot p_{\ell} $$

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

$$ G,=,e(g,{\mathfrak{g}}) $$

$$ ={\mathfrak{g}}^{\alpha} $$

$$ \mathsf{E_{s k}} $$

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

$$ \mathrm {E} _ {\mathrm {s k}} (a) = \left(g ^ {a}, g ^ {\alpha \cdot a}, \mathfrak {g} ^ {a}\right) \in \mathbb {G} _ {1} ^ {2} \times \mathbb {G} _ {2} $$

$$ g^{a} $$

$$ Q=X_{1}\cdot X_{2}-X_{3} $$

$$ a{}_{3}. $$

$$ \mathbf{g}^{a} $$

$$ {\it e}(g^{a_{1}},{\tt g}^{a_{2}}){\it\cdot}{\it e}(g^{-a_{3}},{\tt g}){\it=}\ {\it e}(g,{\tt g})^{Q(a_{1},a_{2},a_{3})} $$

$$ a_{1},,a_{2} $$

$$ e(g^{a},{\mathfrak{g}})=e(g,{\mathfrak{g}}^{a}) $$

$$ e\big(g^{a},{\mathsf{v k}}\big)=e\big(g^{\alpha\cdot a},{\mathfrak{g}}\big) $$

To hide the content of an encoding, one just needs the encoding E⁰ = (g;g;g) of 1, multiplied by a private random factor in M = Zq. To prove the existence of such private coecients P c_isuch that Q(a₁;:::;a_L) = c_ib_imod q is satised, one has to prove the knowledge of (c_i)_i such that Y Q(a1;:::;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 E_sk(b_i), as V = e(g; g) c^an be computed thanks to the pairing. Using the Fiat-Shamir paradigm[FS87], this proof can $Q biki be non-interactive: with random exponents k_iZ_q, 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_iec_imod qg;e) 2 Z_q[[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; fE_sk(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²₁G₂, and a zero-knowledge proof of scalars contains elements from Z_qand 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 Z_qwhere 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 Z_qonto C, for any integer q, one chooses a $ random private element Z_q, 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 E_skis E_sk(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 Z^Nis E = (1 + N) r mod N, for r Z. The ciphertext space N is thus C = Z₂. 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 { Verify_vk(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 Z_q, 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 Z_q. 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 Ei= (1 + N) rⁱNmod N, for riZ, one can compute the lⁱnear QNPQ ⁱ cixi i ^N combination with coecients smaller than q, E = (1 + N) ( r), wh_ich is an P P_icP_ic encryption of ciximod N. It decodes to cixiif j cixij < N =2: we thus have to take N > 2L 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 > 2L 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_i2M such that Q(a₁;:::;a_L) = c_ib_imod q is satised, on the encodings E₁ = 0 E_sk(a₁), . . . , E_L= E_sk(a_L), E₁ = E_sk(b₁), . . . , E⁰ = E_sk(b), one has to prove the knowledge of (cⁱ) in V = Eval(fE g; fcⁱ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 = ₍₁ + N_{) mod} N². 0 0 One wants to prove that V and V decrypt to the same value modulo q: V = V (1 + ^qr1N 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 Qc i 0 qr1N 2 2 V = E = V (₁+N) r₀ mod N. The c_i’s are the masks in [[0; ₂ 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_iZ_q, with additional 0$2^$ noise [[⁰; ² 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 [[₀; 2 1]] and outputs the proof = (D;(s_i= k_iec_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 [[⁰; 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 2eqr₁ N: with N 2L 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 logN + logq bits.

$$ 2e q r_{1}:\leq:{\mathcal N}\ \colon $$

$$ {\mathcal{N}},\geq,2\mu L\cdot t q^{3} $$

$$ q $$

$$ 2^{\lambda^{\prime}}<t) $$

$$ q. $$

$$ {\mathcal{N}}+\mu\times\log q $$

In case of multiple equations involving the same secret c_i, the same challenge is used, and the same (k_i;s_i), reducing the bit-size to 2 logN#Equations + logq #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*;* Z_q[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]], with_k; M and_k; 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= 1_kr 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 proof_u:

$$ \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 random_k;m; M, chosen by the prover for their privacy, and some unknown ⁰$ k;m; 2 Z, using random xm*;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_ky_m) (s_kx_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 same_kand 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 [[⁰;q 1]],; [[⁰; ² 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*;* [[⁰; ² 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 [[⁰; 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 2K(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 > 2L 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} $$

00 Soundness. After a rewinding, with a dierent challenge ~e 6= e, such that D and D decrypt k k 00 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 k⁰ _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 > 2Lq³, 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 2L2 q³. As will always be smaller than 4, in each individual equations, we can take ⁺³ N > L2 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 = Z_q[X;Y]. n 1 N n 1 N 2N In addition to R₂ = Z_q[X;Y], we will use R₁ = Z_q[X], R₃ = Z_q[Y], and Z_q[Y] N ^2N nN with no term in Y, denoted R₄ = Z_q[Y]. For this, we draw additional random elements (1) (3) (4) ^$ r;r;r Z_qfor 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 maxfN + n 1*;* 2N g = 2N, for N n. We then commit the polynomi- N 2N nN als Commit(u*;* Z_q[Y]) or Commit(u*;* Z_q[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_mZ_qchosen 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 thus_u= (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*;* Z_q[Y]), the hiding commitment for a univariate polynomial u(Y) = u_jY 2 ^j=0 N (3) R₃ = Z_q[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]] with_k 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_mZ_qsent by the verier, of u(Y) u(y_m) = (Y y_m) v_m(Y) $ which can be checked with_u= (V_k;mE(v_m(t_k) +_k;mr_k))_k;mfor random_k;mZ_q, 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_mand_k;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₁ = Z_q[X], R₂ = Z_q[X;Y], R₃ = Z_q[Y], and R₄ = Z_q[Y], hence D = 2N, so we will assume t 128N‘.

$$ q=p_{1}\cdot\ldots\cdot p_{\ell} $$

$$ q, $$

$$ p_{1}<\ldots<p_{\ell} $$

$$ \mathcal{R}=\mathbb{Z}_{q}[X^{n-1},Y^{2N}] $$

$$ \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}] $$

$$ \mathcal{R}{4}\doteq\mathbb{Z}{q}[Y^{2N\setminus N}] $$

$$ t\geq128N\ell $$

Setup of the System: Setup(1*; R;(R_i)_i) rst runs (pk⁰;vk⁰) Gen(1 ), chooses K tuples of $ (1) (2) (3) (4) $ random elements s^k;t*^kZ^q, as well as K tuples of random elements r;r;r;r; Z_q, _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 Z_q[X;Y] + Z_q[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₁ = Z_q[X], ^{n 1} N N 2N nN R₂ = Z_q[X;Y], R₃ = Z_q[Y], and R₄ = Z_q[Y]: (¹)

$$ \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*;* Z_q[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_mZ_qchosen 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 w_mis such that u(X) u_m= (X x_m) w_m(X): in total, these are 2K encodings, plus M scalars and KM encodings for the proof. n 1 N (2) Commit(u*;* Z_q[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) Z_qchosen 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 v_mand w_mare 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 2K encodings, plus M scalars and 2KM encodings for the proof. N (3) Commit(u*;* Z_q[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_mZ_qchosen 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 v_mis such that u(Y) u_m= (Y y_m) v_m(Y). In total, these are 2K 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*;* Z_q[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*;* Z_q[X;Y]): it outputs C = (E_u= (E;E;_k⁾_k;_u), for k 2 [[1;K]], where, k k 0k$ with_k; 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) Z_qchosen by the verier (or from a hash function for a 0k;m$ non-interactive proof), and then for random_k;m; Z_qchosen 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 v_mand w_mare 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 scalars_k;m,,_k, and u_m= u(x_m;y_m). In total, this is 2K 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*;* Z_q[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) with_k= fZKLQCheck(X₁ X₂ X₃;E;E;E; E_k;_0;0;E⁾ = trueg, and for all k k k;0;0 _k;0;0 $ m 2 [[1;M]]: y_mZ_qchosen by the verier (or from a hash function for a non-interactive $ proof), and then for random_k;mZ_qchosen 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 v_msuch that u(Y) u(y_m) = (Y y_m) v_m(Y) with KM additional zero-knowledge proofs of knowledge of 3 scalars_k;m,_k, and u_m= u(y_m). In total, this is 2K 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 r_k’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 10Z 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 r_k’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 rk;iis log₂( 2e*), so globally there are Z log₂( 2e) bits of entropy revealed. With linear p 0 combinations, one reveals logq 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₂( 2e) log₂ q + log₂(Z 2e):

$$ \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 > 2t 1⁰Z² (2nB + 1), as the randomness in the decryption key is likely bounded by B = 10. Hence, q 2 Z 2tB⁰(2nB + 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 kpk₁ 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= Z_t[X]*=r(X) (with r 2 Z_t[X] an irreducible polynomial of degree n) the plaintext message space and R_q= Z_q[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 kv*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 (2nB + 1) =2 for correct decryption. In particular, Pr[kek₁ > $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 maxf!( nlog n=); 2ng. 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 logn, 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 a_i2 R_tbe L polynomials and (c_i; c) be L ciphertexts generated with a circuit of depth d, encrypting m_i2R_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 4t. 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 ² Lnt (11tn⁵) ²01n²+ 4dt. 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 201n², it is sucient to have the condition: 5 ² t²Lnd (11tn⁵) q=²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}<\ldots<p_{\ell},,q\geq t^{\ell} $$

$$ 160\cdot2^{2\lambda}\cdot L n d\cdot(11n^{5/2})^{d}\leq t^{\ell-3-d}. $$

=2 2 1=d With ‘ = 3(d + 1), we need t² 11n⁵ (160 ² 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² 11n⁵ (160 ² 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, an^d 11n⁵ (160 ² Nnd) = =2 2 ^1=d =2+1=d (2 +8)=d 5+(2 +8)=d 58 11n⁷ (160 ² nd) ²2n⁷ 2 2 n⁴ 2 n⁴ when d 5 and 2 44 d 6 2 d 8 = 128. This is less than (128) ² n² n (1²8) 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=3_c, where c= 14 + 5 + 3Z, 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 2D‘ = 2 4N‘. _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 scalars_k2 [[;]] 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, = ₂ log²₍⁾+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 2D‘ = 2 4N‘ 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), 8nNq³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 2nlogq bits;

1=(d+1) { The receiver sends (d+ 1) ⁽N + ¹) 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 i^s =; ^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 + 3Z + 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 a_s; ^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 = maxf (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 2K(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 2K(M + 1) + M scalars, times the number of repetitions.

{ Each Paillier encoding holds on 4jNj bits;

{ Each proof holds on 2jNj + 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} $$

$$ \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 $$

$$ {\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’:dg 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 nRqsentby ,! 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()