# LWR-Based Fully Homomorphic Encryption, Revisited

Authors: Fucai Luo; Fuqun Wang; Kunpeng Wang; Jie Li; Kefei Chen
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Very recently, Costache and Smart proposed a fully homomorphic encryption (FHE) scheme based on the Learning with Rounding (LWR) problem, which removes the noise (typically, Gaussian noise) sampling needed in the previous lattices-based FHEs. But their scheme did not work, since the noise of homomorphic multiplication is complicated and large, which leads to failure of decryption. More specifically, they chose LWR instances as a public key and the private key therein as a secret key and then used the tensor product to implement homomorphic multiplication, which resulted in a tangly modulus problem. Recall that there are two moduli in the LWR instances, and then the moduli will tangle together due to the tensor product. Inspired by their work, we built the first workableLWR-based FHE scheme eliminating the tangly modulus problem by cleverly adopting the celebratedapproximate eigenvector method proposed by Gentry et al. at Crypto 2013. Roughly speaking, we use a specific matrix multiplication to perform the homomorphic multiplication, hence no tangly modulus problem. Furthermore, we also extend theLWR-based FHE scheme to the multikey setting using the tricks used to constructLWE-based multikey FHE by Mukherjee and Wichs at Eurocrypt 2016. OurLWR-based multikey FHE construction provides an alternative to the existing multikey FHEs and can also be applied to multiparty computation with higher efficiency.


---

## Body

## 1. Introduction

Fully homomorphic encryption (FHE) is a cryptographic primitive that allows performing arbitrarily complex and efficiently computable evaluations over encrypted data without decrypting them. But the problem of how to construct a FHE scheme had been bothering cryptologists since it was initially introduced by Rivest et al. [1]. Until 2009, this conundrum was compromised due to Gentry’s first plausible candidate FHE construction based on ideal lattices [2]. Since then, a series of works [3–8] have been presented with much progress mainly in security assumptions and efficiencies.Gentry’s seminal work [2] showed for the first time that FHE can be based on cryptographic assumptions and put forward a remarkable “bootstrapping” theorem to achieve full homomorphism (which needs a “circular security” assumption). However, his scheme relies on relatively stronger cryptographic assumptions on ideal lattices (ideal lattices are a special breed that we know relatively little about) and can only evaluate “low degree” polynomials homomorphically without “bootstrapping.”TheLWE-based FHEs [5, 9–13] enjoy higher efficiency and stronger security compared to the previous schemes [2–4, 7] (following a similar framework to Gentry’s work), due to the simple algebraic structure of the well-studiedLWE [14] and classical (quantum) reduction from some apparently intractable lattice problems (e.g., GapSVP) toLWE [14, 15]. The firstLWE-based FHE was proposed by Brakerski and Vaikuntanathan [5] (henceforth, BV11b), who used a novelrelinearization technique to construct a “somewhat homomorphic” encryption scheme based onLWE problem and introduced a noveldimension-modulus reduction technique, without resorting to the “squashing paradigm” used in the previous schemes [2–4, 7]. The subsequent improved works mainly refer to Brakerski et al.’s [9] BGV12 and Brakerski’s [10] Bra12. In BGV12, Brakerski, Gentry, and Vaikuntanathan used thedimension reduction andmodulus reduction (which are originated from BV11b) iteratively and gradually, to construct a “leveled” FHE scheme (capable of evaluating arbitrary polynomial-depth circuits). Bra12 used thedimension reduction without themodulus reduction, to build a better leveled FHE scheme, which is superior to the previous best known in simplicity, noise management, and security. This is mainly because of their noise which only grows linearly (B→B·poly(n)) with every homomorphic multiplication, while in all previous works, the noise grows quadratically (B→B2·poly(n)) withoutmodulus reduction.In Crypto 2013, Gentry et al. [16] (henceforth, GSW13) presented a LWE-based FHE scheme of GSW style (which was improved by Alperin-Sheriff and Peikert [17], henceforth, AP14), using two novel techniques of so-calledapproximate eigenvector andflatten, where the ciphertext is a matrix rather than vector. For the most part, its homomorphic addition and multiplication are just matrix addition and multiplication, which avoids thekey switching,modulus switching, and the “evaluation” key used in previous schemes (e.g., BV11b, BGV12). It is important to note that, besides the fact that the scheme does not need an “evaluation” key, it has an interesting property of asymmetric noise growth because of its specific GSW style. Based on GSW13, a sequence of schemes was proposed, including bootstrapping schemes [11, 17], multikey schemes [6, 12, 13], and some other related schemes [18, 19] (these schemes mainly leverage the homomorphic operations of GSW13).Motivations. The above-mentionedLWE-based FHEs and related schemes suffered the complex and time-consuming Gaussian or sub-Gaussian noise sampling, due to the fact that the correspondingLWE problem needs a noise (error) vector sampled from a distribution, typically (discrete) Gaussian or sub-Gaussian distribution [5, 9, 10, 12, 16, 17]. In particular, some schemes (e.g., [6, 18]) based on theLWE problem have to sample Gaussian noise in the encryption process, which seriously weakens the schemes’ efficiencies. Moreover, it has been recently shown (e.g., [20, 21]) that the Gaussian sampling will create lots of potential side-channel vulnerabilities that result in complete leakage of the secret key. Although it is possible to design good implementations which protect against side-channel attacks, these implementations are often very complex.As a matter of course, this raises a question:can we cast away the Gaussian noise sampling in building a FHEscheme while maintaining the same (almost) security level as those based onLWEproblem? Indeed, this is valuable theoretically and practically and even pedagogically.Very recently, Costache and Smart [22] showed a FHE scheme based on the ring-LWR problem (orRLWR, a variant of Learning with Rounding (LWR) problem). Their scheme removes the Gaussian noise needed in the previousLWE-based FHEs and results in slightly smaller ciphertexts. Roughly speaking, they focused their attention on BGV12 and used the techniques ofrelinearization andmodulus switching to build aRLWR-based FHE scheme. However, theLWR (the definition ofLWR will be presented in Section 2.2), mainly leveraged by a scaled rounding function [23] including two different moduli q and p, makes the tensor product ⊗ used by them to implement homomorphic multiplication intractable. In more detail, they choseRLWR instances as a public key and the private key therein as a secret key, and the ciphertext was computed as a vector c=(v,w)∈Rq×Rp decrypting to message μ∈Rt, where Rq,Rp,Rt are quotient rings. Then, they used the tensor product ⊗ to implement homomorphic multiplication, which results in a product of two different elements belonging to different rings (i.e., two moduli are tangled together). This makes their analysis of the multiplication noise complicated and obscure. In fact, this “tangly modulus” problem brings a large multiplication noise to their decryption equation (in terms of ciphertext after homomorphic multiplication) and thus leads to failure of the decryption. Therefore, how to construct a FHE scheme based onLWR problem, we think, is still an open problem, while we focus our attention on this problem.Our Results. In this paper, we propose a workableLWR-based FHE scheme eliminating the tangly modulus problem by cleverly adopting the celebratedapproximate eigenvector method in GSW13. Roughly speaking, we use a specific matrix multiplication to perform the homomorphic multiplication, which avoids the tangly modulus problem, where the specific matrix multiplication involves a variant ofgadget matrix (which will be described in Section 2.3). The efficiency of our scheme is almost comparable to that of GSW13 and AP14 without counting the cost of Gaussian noise sampling, for the size of modulus q is almost the same as theirs which can be seen from Table 1 (our modulus q is larger; see Section 4.2). Indeed, it is mainly our larger security loss (up to a polynomial factor) that results in the larger modulus q (up to a polynomial factor). Our scheme can be seen as an alternative to the GSW13 and AP14.Table 1
Comparison withLWE-based FHEs: GSW13 and AP14.
FHE Modulusq Security loss Gaussian noise GSW13 and AP14 ( O ( n log ⁡ q ) ) L + O ( 1 ) O ( 1 ) Yes OurLWR-based FHE ( O ( n log ⁡ q ) ) L + O ( 1 ) O ( q n log ⁡ q ) No (1) We consider a leveled FHE scheme where the depth of circuits is polynomialL. The homomorphic evaluation capability, efficiency, and security of the FHE scheme mainly depend on modulus q, under the same dimension n. Note that the modulus q of AP14 is relatively smaller than that of GSW13, for the sub-Gaussian in AP14 results in a tighter noise growth than the Gaussian. Here, we ignore this little difference. (2) Here, the security loss is caused by the reduction between the security of the FHE scheme and the LWE problem. Since the security of our FHE scheme is directly based on the LWR problem, the security loss involves the reduction loss incurred by the reduction between LWE and LWR (see Theorem 7 in Section 2).Furthermore, we also extend theLWR-based FHE scheme to multikey setting using the tricks used to constructLWE-based multikey FHE by Mukherjee and Wichs [12] at Eurocrypt 2016. Again, we leverage the specific GSW style to avoid the tangly modulus problem. Interestingly, it seems that the method of [12] has been tailored to be employed in constructing ourLWR-based multikey FHE scheme, since it helps to avoid the tangly modulus problem when expanding the valid ciphertexts needed in multikey setting (see Section 5). Compared to Mukherjee and Wichs’s scheme, our scheme can also be applied to multiparty computation and is more efficient; again, this is largely for the reason that there is no Gaussian noise sampling. This can be also verified by Table 1 and by the fact that theLWE-based multikey FHE [12] is an extension of AP14.What is more, ourLWR-based FHE and its extended multikey FHE support bootstrapping procedures; this is due to the fact that the encryption and decryption processes in our schemes are very similar to those in AP14, except that there are two different moduli in our scheme (which will not tangle together because of our specific structure). We believe that it is straightforward to convert ourLWR-based scheme into aRLWR-based one.Our Techniques. In ourLWR-based FHE, we choose m pairs ofLWR instances as a public key and the private key therein as a secret key. The public key is assembled as a matrix (1)A=A¯b∈Zqn×m×Zpmsuchthats·A=emodp,where A¯∈Zqn×m, b∈Zpm, and the secret key is s=(-p/q·s′,1), where s′∈{0,1}n. Since there are two different moduli in a matrix, we use the symbol [×] (see Section 2) to differentiate from the conventional symbol ×.For a messageμ∈{0,1}, the ciphertext is computed as (2)C=A·R+μG∈Zqn×N×ZpN,where G∈Zqn×N[×]ZpN is a variant ofgadget matrix (see Section 2.3). To perform homomorphic multiplication (addition is very natural), do the following: given two ciphertexts C1,C2 decrypting to message μ1,μ2∈{0,1}, we have (3)Cmult≜C1·G-1C2∈Zqn×N×ZpN,since matrix G-1(C2)∈{0,1}N×N does not affect the structure of matrix C1·G-1(C2) (seeOperations in Section 2). Hence, we assert that the structures of ciphertexts remain unchanged after L levels of multiplication, so they can be properly decrypted. Indeed, our homomorphic multiplication will not cause the tangly modulus problem existent in Costache and Smart’s solution [22], because these two different modular operations (in terms of moduli q,p) can be partitioned by our matrix operation but cannot be by the tensor product used by them. We defer the details to Section 4.For the secret key,s=(-p/q·s′,1), where p,q are public and s′ is privately and uniformly chosen from {0,1}n instead of Zq for initial noise and efficiency. This is reasonable and secure relying on Theorem 7 in Section 2.2 and the hardness ofLWE problem with binary secret (which was proved at least as hard as the originalLWE problem by Brakerski et al. [24]).Organization. In Section 2, we give some preliminaries including theLWE problem,LWR problem, and a variant of gadget matrix. We describe a basicLWR-based encryption scheme and give its full security proof in Section 3. Section 4 goes into the core of ourLWR-based FHE scheme. In Section 5, we extend our main construction to theLWR-based multikey FHE. Finally, we conclude the paper in Section 6.


## 2. Preliminaries

As a preliminary matter, we give some explanations for some notations and operations throughout the paper.Notations. For an integer q, we define the set Zq≜(-q/2,q/2]∩Z, and all logarithms on q are to base 2. All arithmetics are performed over Z or Q when division is used, and for ease of use, we let [n]≜{1,…,n}. We denote vectors in bold lowercase (e.g., x) and matrices in bold uppercase (e.g., A). Let At (resp., xt) be the transpose of A (resp., x). For any x∈Q, we denote by x, ⌈x⌉, and x the rounding of x down, up, or to the nearest integer; these notations also apply to vector and matrix. We say that a function negl(n) is negligible if there are not any polynomial fractions smaller than the negl(n) for sufficiently large n. All vectors are treated as rows in the paper.Probability. We let x←rD denote that x is sampled uniformly at random from a distribution D and x←rS (e.g., Zq) denote that x is uniform over a set S.Operations. For an n-dimensional vector x={x1,…,xn}, we denote its norm by x≜max⁡xii∈[n], where xi refers to its magnitude. The multiplication between two vectors x, y over Zq is denoted by 〈x,y〉q (i.e., 〈x,y〉modq). What we want to particularly explain beforehand is the multiplication between two matrices.Given two different moduliq, p, and any integer n, m, for (n+1)×m matrix A, by abuse of notation, we let A∈Zqn×m[×]Zpm indicate that all row vectors of A are over Zqm but the last one (i.e., (n+1)-th) is over Zpm, and we state that we should be careful about, for example, multiplying a matrix A∈Zqn×m[×]Zpm by a matrix R∈{0,1}m×m (or a vector r∈{0,1}m). More precisely, we should multiply every row vector of A by the matrix R∈{0,1}m×m, that is, multiply each row vector of A by each column vector of R∈{0,1}m×m, and then take a modular operation (take the product modulo a modulus). Note that the last row vector of A is over Zpm, and thus the multiplications between this row vector and the matrix R∈{0,1}m×m are evaluated over Zpm (take the products modulo the modulus p), while all the other multiplications are evaluated over Zqm (take the products modulo the modulus q). (These two modular operations can be partitioned due to the matrix structure which, roughly speaking, avoids the tangly modulus problem existent in [22].) This principle also applies to addition between two matrices over Zqn×m[×]Zpm. Indeed, this is an important difference betweenLWE andLWR when performing addition and multiplication operations on matrices.In our security proof, we will use the following variant of the standard leftover hash lemma [25].Lemma 1 (see [5]).
Letλ, n, q, p, and m≥nlog⁡q+log⁡p+2λ be integers, and let y←rZqn×Zp. For matrix A←rZqn×m[×]Zpm, let r←r{0,1}m; one has (4)∆A,A·r,A,y≤12qn·p2m<2-λ, where ∆(X,Y) denotes the statistical distance between two distributions X,Y.


### 2.1. Learning with Errors (LWE)

The well-knownLWE problem has been enjoying fame for its applicability in constructions of lattice-based schemes conjectured to be secure in quantum setting, ever since Regev introduced it and showed a quantum reduction [14] from some worst-case hardness of the standard lattice problems toLWE problem (followed by classical reductions [15, 24]). It is defined as follows.Definition 2 (see [9]).
For positive integersn, q=q(n), m≥O(nlogq), a vector s∈Zqn, and an error distribution χ over Z (typically, a (discrete) Gaussian distribution with standard deviation αq for α=o(1)). Let An,q,m,χ be the distribution over Zqn+1 obtained by choosing m independent samples a←rZqn and an error term e←rχ and outputting m pairs (a,b=〈a,s〉q+e). Then, the (average-case) decision problem of theLWE, denoted by DLWEn,q,m,χ, is to distinguish, given arbitrarily many independent samples, the uniform distribution over Zqn+1 from An,q,m,χ, for a fixed s∈Zqn. The search problem of LWEn,q,m,χ is aim to find secret s given m independent samples from LWEn,q,m,χ(s) (for s∈Zqn). The LWEn,q,m,χ assumption is that the LWEn,q,m,χ problem is infeasible.Definition 3 (B-bounded distributions [16]).
A distribution ensemble{χn}n∈N, supported over the integers, is called B-bounded if (5)Pre←rχne>B=negln.


### 2.2. Learning with Rounding (LWR)

Learning with Rounding (LWR) problem, which was used to construct lossy trapdoor functions, reusable computational extractors, and deterministic encryption, was firstly proposed by Banerjee et al. [23] for improving the efficiency of pseudorandom generator (PRG) based on theLWE problem. Indeed, theLWR problem can be seen as a deterministic alternative toLWE problem, except that the noise inLWR is deterministic which derandomizes the Gaussian noise inLWE, and the noise inLWR resulted from the scale rounding function being smaller than that inLWE. Specifically, the noise inLWE is B-bounded (B>2n for security [14]), whereas it has magnitude of less than 1/2 inLWR. We recall the scaled rounding function ·p [23] which is defined as follows: for p<q, (6)·p:Zq⟶Zpa⟼pq·a.Similar to theLWE problem, we get the following analogous definition for theLWR problem.Definition 4 (see [23]).
For integersn, q>p, and m, sample uniformly at random an n-dimensional vector s from Zqn, and then theLWR distribution is defined as LWRn,q,p(s)≜{a,a,sqp∈Zqn×Zp∣a←rZqn}, where the pair (a,⌈a,s〉qp) isLWR sample (instance), and let LWRn,m,q,p(s) be the distribution comprised of m independent samples from LWRn,q,p(s). Then, the search LWRn,m,q,p problem is defined as finding secret s given m independent samples from LWRn,q,p(s), while the decision DLWRn,m,q,p problem is to distinguish m independent samples (with nonnegligible advantage) chosen from the distribution LWRn,m,q,p(s), for a fixed s←rZqn, from m samples chosen from uniform distribution over Zqn×Zp. The LWRn,m,q,p assumption is that the DLWRn,m,q,p problem is infeasible.As to the hardness of theLWR problem, Banerjee et al. [23] presented an efficient reduction from theLWE problem to theLWR problem for modulus q of superpolynomial size, followed by Alwen et al. [26], who gave a reduction that allowed for a polynomial modulus q, but restricted the number of samples and failed to apply to all values of the modulus q. In 2016, Bogdanov et al. [27] generalized the theorem of [26] by eliminating the theoretic restriction on the modulus q, but the number of samples was required to be less than O(q/Bp) (weaker than that of [26]), while Alperin-Sheriff and Apon [28] showed a dimension-preserving reduction fromLWE toLWR with a polynomial-sized modulus, which immediately implies improvements in parameters (i.e., security and efficiency) for all known applications of polymodulusLWR.Note that Brakerski et al. [24] proved that the bin-LWE (implies that the secret key is uniformly chosen from 0,1n) is at least as hard as the originalLWE problem (up to logarithmic loss). Hence, we can uniformly choose the secret s inLWR from {0,1}n under the hardness of bin-LWE and the following theorem (Theorem 5). Next, we recall the main theorem in [27] (it is sufficient for our schemes, though the number of samples was required to be less than O(q/Bp)). Then, by combining this theorem with Lemma 6 (it is a simple fact; here we present it as a lemma), we get our crucial Theorem 7 on which the proposed schemes’ security is based. Note that Theorem 7 concerns the search problem of bin-LWE, which is harder than the decision problem of bin-LWE.Theorem 5 (see [27]).
For everyε>0, n, m, q≥2mpB, and if there is an algorithm A such that (7)PrA,sAA,Asp=1-PrA,uAA,up=1≥ε,where A←rZqm×n, s←r{0,1}n, and u←rZqm, then there exists an efficient algorithm B that runs in time polynomial in n, m, the number of divisors of q, and the running time of A such that (8)PrA,sBA,As+e=s≥ε4qm-2npm2·11+2Bp/qmfor noise distribution e that is B-bounded and balanced in each coordinate.Lemma 6.
Ifp∣q, then the distribution up is uniform over Zpm for u←rZqm (i.e., the distribution up is equivalent to Zpm).Theorem 7.
For everyε>0, n, m, q≥2mpB, p∣q, and if there is an algorithm A such that (9)PrA,sAA,Asp=1-PrA,vAA,v=1≥ε,where A←rZqm×n, s←r{0,1}n, and v←rZpm, then there exists an efficient algorithm B that runs in time polynomial in n, m, the number of divisors of q, and the running time of A such that (10)PrA,sBA,As+e=s≥ε4qm-2npm2·11+2Bp/qmfor noise distribution e that is B-bounded and balanced in each coordinate.Proof of Sketch.
Note that there is no restriction on the conditionp∣q in Theorem 5. In other words, Theorem 5 holds even under the additional condition p∣q. Therefore, Theorem 7 is obvious by combining Lemma 6 which implies that the vector up is equivalent to v.We remark that the termPrA,s[A(A,Asp)=1]-PrA,v[A(A,v)=1] in Theorem 7 can be interpreted as the decision DLWRn,m,q,p problem, for the fixed s←r0,1n.


### 2.3. Variant of Gadget Matrix

The gadget matrix, which was proposed by [29], was used to build aLWE-based FHE scheme of GSW style by AP14, which extended the “flatten” skill in GSW13. Here, we construct a variant of gadget matrix which is specific to ourLWR-based FHE scheme.Since there are two moduliq, p in theLWR problem, a variant of gadget matrix G with invariant function is as follows: (11)G≔g⋱ggn+1∈Zqn×N×ZpN,where g≔(1,2,…,2⌈log⁡q⌉-1)∈Zq⌈log⁡q⌉, gn+1≔(1,2,…,2⌈log⁡p⌉-1)∈Zp⌈log⁡p⌉, and N=n⌈log⁡q⌉+⌈log⁡p⌉. We also define the deterministic inversion function G-1:Zqn×N[×]ZpN→{0,1}N×N, which is equal to bit decomposition that decomposes x into its bit representation over Zq or Zp and has the following property: for any matrix A∈Zqn×N[×]ZpN, it holds that G·G-1(A)=A. Note that G-1 is an expensively randomized inversion function in AP14, although it leads to a tighter noise analysis for its homomorphic operations.


## 2.1. Learning with Errors (LWE)

The well-knownLWE problem has been enjoying fame for its applicability in constructions of lattice-based schemes conjectured to be secure in quantum setting, ever since Regev introduced it and showed a quantum reduction [14] from some worst-case hardness of the standard lattice problems toLWE problem (followed by classical reductions [15, 24]). It is defined as follows.Definition 2 (see [9]).
For positive integersn, q=q(n), m≥O(nlogq), a vector s∈Zqn, and an error distribution χ over Z (typically, a (discrete) Gaussian distribution with standard deviation αq for α=o(1)). Let An,q,m,χ be the distribution over Zqn+1 obtained by choosing m independent samples a←rZqn and an error term e←rχ and outputting m pairs (a,b=〈a,s〉q+e). Then, the (average-case) decision problem of theLWE, denoted by DLWEn,q,m,χ, is to distinguish, given arbitrarily many independent samples, the uniform distribution over Zqn+1 from An,q,m,χ, for a fixed s∈Zqn. The search problem of LWEn,q,m,χ is aim to find secret s given m independent samples from LWEn,q,m,χ(s) (for s∈Zqn). The LWEn,q,m,χ assumption is that the LWEn,q,m,χ problem is infeasible.Definition 3 (B-bounded distributions [16]).
A distribution ensemble{χn}n∈N, supported over the integers, is called B-bounded if (5)Pre←rχne>B=negln.


## 2.2. Learning with Rounding (LWR)

Learning with Rounding (LWR) problem, which was used to construct lossy trapdoor functions, reusable computational extractors, and deterministic encryption, was firstly proposed by Banerjee et al. [23] for improving the efficiency of pseudorandom generator (PRG) based on theLWE problem. Indeed, theLWR problem can be seen as a deterministic alternative toLWE problem, except that the noise inLWR is deterministic which derandomizes the Gaussian noise inLWE, and the noise inLWR resulted from the scale rounding function being smaller than that inLWE. Specifically, the noise inLWE is B-bounded (B>2n for security [14]), whereas it has magnitude of less than 1/2 inLWR. We recall the scaled rounding function ·p [23] which is defined as follows: for p<q, (6)·p:Zq⟶Zpa⟼pq·a.Similar to theLWE problem, we get the following analogous definition for theLWR problem.Definition 4 (see [23]).
For integersn, q>p, and m, sample uniformly at random an n-dimensional vector s from Zqn, and then theLWR distribution is defined as LWRn,q,p(s)≜{a,a,sqp∈Zqn×Zp∣a←rZqn}, where the pair (a,⌈a,s〉qp) isLWR sample (instance), and let LWRn,m,q,p(s) be the distribution comprised of m independent samples from LWRn,q,p(s). Then, the search LWRn,m,q,p problem is defined as finding secret s given m independent samples from LWRn,q,p(s), while the decision DLWRn,m,q,p problem is to distinguish m independent samples (with nonnegligible advantage) chosen from the distribution LWRn,m,q,p(s), for a fixed s←rZqn, from m samples chosen from uniform distribution over Zqn×Zp. The LWRn,m,q,p assumption is that the DLWRn,m,q,p problem is infeasible.As to the hardness of theLWR problem, Banerjee et al. [23] presented an efficient reduction from theLWE problem to theLWR problem for modulus q of superpolynomial size, followed by Alwen et al. [26], who gave a reduction that allowed for a polynomial modulus q, but restricted the number of samples and failed to apply to all values of the modulus q. In 2016, Bogdanov et al. [27] generalized the theorem of [26] by eliminating the theoretic restriction on the modulus q, but the number of samples was required to be less than O(q/Bp) (weaker than that of [26]), while Alperin-Sheriff and Apon [28] showed a dimension-preserving reduction fromLWE toLWR with a polynomial-sized modulus, which immediately implies improvements in parameters (i.e., security and efficiency) for all known applications of polymodulusLWR.Note that Brakerski et al. [24] proved that the bin-LWE (implies that the secret key is uniformly chosen from 0,1n) is at least as hard as the originalLWE problem (up to logarithmic loss). Hence, we can uniformly choose the secret s inLWR from {0,1}n under the hardness of bin-LWE and the following theorem (Theorem 5). Next, we recall the main theorem in [27] (it is sufficient for our schemes, though the number of samples was required to be less than O(q/Bp)). Then, by combining this theorem with Lemma 6 (it is a simple fact; here we present it as a lemma), we get our crucial Theorem 7 on which the proposed schemes’ security is based. Note that Theorem 7 concerns the search problem of bin-LWE, which is harder than the decision problem of bin-LWE.Theorem 5 (see [27]).
For everyε>0, n, m, q≥2mpB, and if there is an algorithm A such that (7)PrA,sAA,Asp=1-PrA,uAA,up=1≥ε,where A←rZqm×n, s←r{0,1}n, and u←rZqm, then there exists an efficient algorithm B that runs in time polynomial in n, m, the number of divisors of q, and the running time of A such that (8)PrA,sBA,As+e=s≥ε4qm-2npm2·11+2Bp/qmfor noise distribution e that is B-bounded and balanced in each coordinate.Lemma 6.
Ifp∣q, then the distribution up is uniform over Zpm for u←rZqm (i.e., the distribution up is equivalent to Zpm).Theorem 7.
For everyε>0, n, m, q≥2mpB, p∣q, and if there is an algorithm A such that (9)PrA,sAA,Asp=1-PrA,vAA,v=1≥ε,where A←rZqm×n, s←r{0,1}n, and v←rZpm, then there exists an efficient algorithm B that runs in time polynomial in n, m, the number of divisors of q, and the running time of A such that (10)PrA,sBA,As+e=s≥ε4qm-2npm2·11+2Bp/qmfor noise distribution e that is B-bounded and balanced in each coordinate.Proof of Sketch.
Note that there is no restriction on the conditionp∣q in Theorem 5. In other words, Theorem 5 holds even under the additional condition p∣q. Therefore, Theorem 7 is obvious by combining Lemma 6 which implies that the vector up is equivalent to v.We remark that the termPrA,s[A(A,Asp)=1]-PrA,v[A(A,v)=1] in Theorem 7 can be interpreted as the decision DLWRn,m,q,p problem, for the fixed s←r0,1n.


## 2.3. Variant of Gadget Matrix

The gadget matrix, which was proposed by [29], was used to build aLWE-based FHE scheme of GSW style by AP14, which extended the “flatten” skill in GSW13. Here, we construct a variant of gadget matrix which is specific to ourLWR-based FHE scheme.Since there are two moduliq, p in theLWR problem, a variant of gadget matrix G with invariant function is as follows: (11)G≔g⋱ggn+1∈Zqn×N×ZpN,where g≔(1,2,…,2⌈log⁡q⌉-1)∈Zq⌈log⁡q⌉, gn+1≔(1,2,…,2⌈log⁡p⌉-1)∈Zp⌈log⁡p⌉, and N=n⌈log⁡q⌉+⌈log⁡p⌉. We also define the deterministic inversion function G-1:Zqn×N[×]ZpN→{0,1}N×N, which is equal to bit decomposition that decomposes x into its bit representation over Zq or Zp and has the following property: for any matrix A∈Zqn×N[×]ZpN, it holds that G·G-1(A)=A. Note that G-1 is an expensively randomized inversion function in AP14, although it leads to a tighter noise analysis for its homomorphic operations.


## 3. Building Block

As a warmup, in this section, we present a basic encryption scheme construction based onLWR which is adapted from the ring-LWR-based FHE scheme [22]. Then, based on the basic encryption scheme, we give ourLWR-based FHE scheme in the next section. We remark that the secret key is uniformly chosen from {0,1}n to keep the noise growing slower and speed up encryption and decryption processes, under the same (almost) security level as GSW13 and AP14. This can be guaranteed by Theorem 7 in Section 2.2 and the hardness of bin-LWE problem.


### 3.1. The Basic LWR-Based Encryption Scheme

The basic encryption scheme based onLWR is constructed as follows.(i)
Setup(1λ): choose parameters n=n(λ), l=l(λ), moduli q=q(λ), and p=p(λ) satisfying p∣q (this condition is needed for the security proof). Let params=(n,l,q,p).(ii)
KeyGen(params): choose uniformly at random a secret key s′←r{0,1}n. Choose uniformly at random l vectors ai←rZqn, and then compute(12)bi=ai,s′qp∈Zpfori∈[l], which results in l pairs ofLWR samples {(a1,b1),…,(al,bl)∈Zqn×Zp}. Assemble a matrix A¯∈Zqn×l by the l column vectors ait and set b=(b1,…,bl), and then let A=A¯b∈Zqn×l[×]Zpl. The final public key is pk≔A, and the secret key is sk:s=(-p/q·s′,1). For later use, we write ei=bi-p/q〈ai,s′〉q∈[-1/2,1/2] for i∈[l]. Then, according to (15), it holds that s·A=e mod p, where the noise e=(e1,…,el)∈[-1/2,1/2]l.(iii)
Enc(params,pk,μ): to encrypt a message μ∈{0,1}, choose a random vector r←r{0,1}l, and then output (13)c=A·rt+0,μ·p2t∈Zqn×Zp.(iv)
Dec(params,sk,c): given the ciphertext c∈Zqn×Zp, output (14)μ=1p/2·s,cmod2.Correctness. As long as the noise e≜e,r=∑i=1l‍ri·ei≤1/2·l<1/2·p/2, where ri∈{0,1} is the entry of the vector r, the aboveDec algorithm can rightly recover the message μ. We prove this by the following steps: For every column vector (ai,bi)t of the matrix A, it holds that(15)s·ai,bit=-pqs′,ai+bi=-pq·s′,aiq+kq+bi=-pqs′,aiq+bi-kp=ei-kp.Then, we have s·A=emodp, and it follows that (16)1p/2·s,c=1p/2·e,r+μ·p2-kp=μmod2,iff e,r≤1/2·l<1/2·p/2.


### 3.2. Security

We argue that the above basic encryption scheme is IND-CPA secure under Theorem7. In fact, the structure of our basic encryption scheme is identical to that of [14, 16, 17], and so is the strategy of security proof. In our paper, Theorem 7 guarantees the hardness of LWRn,m,q,p assumption (where s←r0,1n) assuming the bin-LWE problem; hence, we can base the security of our basic encryption scheme on theLWR problem. For completeness, we give a full security proof below.Theorem 8.
The above basicLWR-based encryption scheme is IND-CPA secure under the LWRn,m,q,p assumption.Proof.
We prove the theorem via a series of hybrid experiments. The analysis of probability is omitted here, since it is natural and very similar to that of [4, 14].(i)
Hybrid 0: this is the real system (we set l=m, where m=Onlog⁡q+log⁡p≥nlog⁡q+log⁡p+2λ).(ii)
Hybrid 1: this is the same as Hybrid 0 except that we use m pairs {(ai,bi)}i=1,…,m chosen uniformly from Zqn×Zp, instead of being chosen fromLWR samples in Hybrid 0, to assemble public key A. The ciphertext c is thus generated by encrypting μ using the public key A as per the encryption procedure in Hybrid 0.(iii)
Hybrid 2: this is the same as Hybrid 1 except that the ciphertext c∈Zqn×Zp is chosen from Zqn×Zp uniformly and independently of the public key.
Firstly, we claim that Hybrid 1 is indistinguishable from Hybrid 0, under theLWRn,m,q,p assumption. This is shown by a simple reduction: if any hypothetical adversary A can distinguish these two hybrids, then we can construct an algorithm B to break the LWRn,m,q,p assumption. Specifically, B simply collects its input samples (challenged samples) into the public key A and encrypts a message μ using the public key A to get a ciphertext c, and then it invokes A on (A,c), outputting the same accept/reject decision. It is clear that B perfectly simulates Hybrid 0 or Hybrid 1 depending on whether its input samples areLWR samples or uniform over Zqn×Zp; that is, if the input samples areLWR samples, then the ciphertext c is generated as per Hybrid 0; otherwise, the ciphertext c is generated as per Hybrid 1. Therefore, B and A have equal distinguishing advantages. Because B’s advantage must be negligible by hypothesis, so is A’s.
In the second place, we claim that Hybrid 1 is statistically indistinguishable from Hybrid 2; that is, even a computationally unbounded adversary has only negligible advantage in distinguishing them. This is easy to be justified by Lemma1 in Section 2. In more detail, by Lemma 1, the term A·r in Hybrid 1 is statistically indistinguishable from any element y∈Zqn×Zp. Hence, the ciphertext in Hybrid 1 is statistically indistinguishable from that of Hybrid 2, for adding any fixed vector (0,μ·p/2)t to A·r preserves its uniform distribution.
To sum up, we conclude that Hybrid 0 is indistinguishable from Hybrid 2, and the ciphertext in Hybrid 2 is independent of messageμ (regardless of μ=0 or μ=1), which completes the proof.


## 3.1. The Basic LWR-Based Encryption Scheme

The basic encryption scheme based onLWR is constructed as follows.(i)
Setup(1λ): choose parameters n=n(λ), l=l(λ), moduli q=q(λ), and p=p(λ) satisfying p∣q (this condition is needed for the security proof). Let params=(n,l,q,p).(ii)
KeyGen(params): choose uniformly at random a secret key s′←r{0,1}n. Choose uniformly at random l vectors ai←rZqn, and then compute(12)bi=ai,s′qp∈Zpfori∈[l], which results in l pairs ofLWR samples {(a1,b1),…,(al,bl)∈Zqn×Zp}. Assemble a matrix A¯∈Zqn×l by the l column vectors ait and set b=(b1,…,bl), and then let A=A¯b∈Zqn×l[×]Zpl. The final public key is pk≔A, and the secret key is sk:s=(-p/q·s′,1). For later use, we write ei=bi-p/q〈ai,s′〉q∈[-1/2,1/2] for i∈[l]. Then, according to (15), it holds that s·A=e mod p, where the noise e=(e1,…,el)∈[-1/2,1/2]l.(iii)
Enc(params,pk,μ): to encrypt a message μ∈{0,1}, choose a random vector r←r{0,1}l, and then output (13)c=A·rt+0,μ·p2t∈Zqn×Zp.(iv)
Dec(params,sk,c): given the ciphertext c∈Zqn×Zp, output (14)μ=1p/2·s,cmod2.Correctness. As long as the noise e≜e,r=∑i=1l‍ri·ei≤1/2·l<1/2·p/2, where ri∈{0,1} is the entry of the vector r, the aboveDec algorithm can rightly recover the message μ. We prove this by the following steps: For every column vector (ai,bi)t of the matrix A, it holds that(15)s·ai,bit=-pqs′,ai+bi=-pq·s′,aiq+kq+bi=-pqs′,aiq+bi-kp=ei-kp.Then, we have s·A=emodp, and it follows that (16)1p/2·s,c=1p/2·e,r+μ·p2-kp=μmod2,iff e,r≤1/2·l<1/2·p/2.


## 3.2. Security

We argue that the above basic encryption scheme is IND-CPA secure under Theorem7. In fact, the structure of our basic encryption scheme is identical to that of [14, 16, 17], and so is the strategy of security proof. In our paper, Theorem 7 guarantees the hardness of LWRn,m,q,p assumption (where s←r0,1n) assuming the bin-LWE problem; hence, we can base the security of our basic encryption scheme on theLWR problem. For completeness, we give a full security proof below.Theorem 8.
The above basicLWR-based encryption scheme is IND-CPA secure under the LWRn,m,q,p assumption.Proof.
We prove the theorem via a series of hybrid experiments. The analysis of probability is omitted here, since it is natural and very similar to that of [4, 14].(i)
Hybrid 0: this is the real system (we set l=m, where m=Onlog⁡q+log⁡p≥nlog⁡q+log⁡p+2λ).(ii)
Hybrid 1: this is the same as Hybrid 0 except that we use m pairs {(ai,bi)}i=1,…,m chosen uniformly from Zqn×Zp, instead of being chosen fromLWR samples in Hybrid 0, to assemble public key A. The ciphertext c is thus generated by encrypting μ using the public key A as per the encryption procedure in Hybrid 0.(iii)
Hybrid 2: this is the same as Hybrid 1 except that the ciphertext c∈Zqn×Zp is chosen from Zqn×Zp uniformly and independently of the public key.
Firstly, we claim that Hybrid 1 is indistinguishable from Hybrid 0, under theLWRn,m,q,p assumption. This is shown by a simple reduction: if any hypothetical adversary A can distinguish these two hybrids, then we can construct an algorithm B to break the LWRn,m,q,p assumption. Specifically, B simply collects its input samples (challenged samples) into the public key A and encrypts a message μ using the public key A to get a ciphertext c, and then it invokes A on (A,c), outputting the same accept/reject decision. It is clear that B perfectly simulates Hybrid 0 or Hybrid 1 depending on whether its input samples areLWR samples or uniform over Zqn×Zp; that is, if the input samples areLWR samples, then the ciphertext c is generated as per Hybrid 0; otherwise, the ciphertext c is generated as per Hybrid 1. Therefore, B and A have equal distinguishing advantages. Because B’s advantage must be negligible by hypothesis, so is A’s.
In the second place, we claim that Hybrid 1 is statistically indistinguishable from Hybrid 2; that is, even a computationally unbounded adversary has only negligible advantage in distinguishing them. This is easy to be justified by Lemma1 in Section 2. In more detail, by Lemma 1, the term A·r in Hybrid 1 is statistically indistinguishable from any element y∈Zqn×Zp. Hence, the ciphertext in Hybrid 1 is statistically indistinguishable from that of Hybrid 2, for adding any fixed vector (0,μ·p/2)t to A·r preserves its uniform distribution.
To sum up, we conclude that Hybrid 0 is indistinguishable from Hybrid 2, and the ciphertext in Hybrid 2 is independent of messageμ (regardless of μ=0 or μ=1), which completes the proof.


## 4. LWR-Based FHE Scheme

### 4.1. Our Construction

OurLWR-based FHE scheme is constructed as follows.(i)
Setup(1λ,1L): choose dimension parameter n=n(λ,L) and moduli q=q(λ,L) and p=p(λ,L) satisfying p∣q. Also, choose parameter m=m(λ,L)=O(nlog⁡q+log⁡p). Let params=(n,q,p,m). Let k1=⌈log⁡q⌉, k2=⌈log⁡p⌉, and N=n·k1+k2.(ii)
KeyGen(params): choose uniformly at random a secret key s′←r{0,1}n. As perKeyGen algorithm in Section 3, generate a matrix (17)A=A¯b∈Zqn×m×Zpm.The final public key ispk≔A, and the secret key is sk:s=(-p/q·s′,1). Note that it holds that s·A=e mod p, where the noise e=(e1,…,em)∈[-1/2,1/2]m.(iii)
Enc(params,pk,μ): to encrypt a message μ∈{0,1}, choose a random matrix R←r{0,1}m×N. Output the ciphertext (18)C=A·R+μG∈Zqn×N×ZpN,where the gadget matrixG is brought from Section 2.3. Since we should perform the above matrix multiplication as per the specific matrix operations described in Section 2, we give Algorithm 1 that makes the encryption algorithm more readable.(iv)
Dec(params,sk,C): given the ciphertext C∈Zqn×N[×]ZpN, choose a vector v≔(0,…,0,p/2)∈Zpn+1 and compute (19)v=s·C·G-1vt=e·R·G-1vt+μ·p2.Outputμ=1/p/2·v (mod 2). We also give Algorithm 2 that makes the decryption algorithm more readable.(v)
Add(C1,C2): given two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, output (20)CAdd≜C1+C2∈Zqn×N×ZpN.(vi)
Mult(C1,C2): for two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, the multiplication is defined as (21)Cmult≜C1·G-1C2∈Zqn×N×ZpN,whereG-1 is brought from Section 2.3. We give Algorithm 3 only for homomorphic multiplication, because homomorphic addition is trivial, and homomorphicNAND depends on homomorphic multiplication.(vii)
NAND(C1,C2): for two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, theNAND operation is defined as (22)CNAND≜G-C1·G-1C2∈Zqn×N×ZpN.Note that any Boolean circuit can be converted to use onlyNAND operation.(viii)
Eval(f,(C1,C2,…,Ct)): evaluate the Boolean function f:{0,1}t→{0,1} on t ciphertexts C1,C2,…,Ct by theNAND operation. Output a ciphertext Cf.Algorithm 1:Encryption algorithm.
Input: Parameters, a public-key matrix A∈Zqn×m[×]Zpm and a message μ∈{0,1}. Output: A ciphertext matrix C=A⋅R+μG∈Zqn×N[×]ZpN. (1) Generate a variant gadget matrix G according to the structure of gadget matrix given in Section 2.3. (2) Choose uniformly at random a matrix R←r0,1m×N. (3) Compute C=A⋅R+μG∈Zqn×N×ZpN as per our specific matrix operations described in Section 2.Algorithm 2:Decryption algorithm.
Input: Parameters, a secret key sk=s and a ciphertext matrix C∈Zqn×N[×]ZpN. Output: A binary value μ∈{0,1}. (1) Choose a vector v:=0,…,0,p/2∈Zpn+1, and compute a vector r∈{0,1}N, such that G⋅rt=v, i.e., rt=G-1(vt). (2) Compute v = s ⋅ C ⋅ r t = e ⋅ R ⋅ r t + μ ⋅ p 2 . (3) Output μ=1/p/2⋅v (mod 2).Algorithm 3:Homomorphic multiplication.
Input: Two ciphertext matrices C1,C2 decrypting to messages μ1,μ2, respectively. Output: A derived ciphertext matrix Cmult decrypting to message μ1μ2. (1) Compute a matrix X∈{0,1}N×N, such that G⋅X=C2, i.e., X=G-1(C2). (2) Output C m u l t = C 1 ⋅ G - 1 C 2 ∈ Z q n × N × Z p N .The IND-CPA security of the above scheme follows immediately from the security of the basic encryption scheme in Section3. The ciphertext matrix is just μG plus a matrix of N encryptions of 0 under the key s by the basic encryption in Section 3, which is pseudorandom by Theorem 8 and hence hides μG.


### 4.2. Correctness

In this subsection, we analyze the scheme’s correctness and the noise growth of each homomorphic operation. Moreover, we also give a more detailed analysis for homomorphic multiplication to illustrate that our proposed construction is practicable.Correctness. The correctness is obvious according to the correctness of the basic encryption scheme in Section 3, iff the magnitude of noise e∗≜e·R·G-1(vt) is less than 1/2·p/2. In fact, according to theDec, we have(23)s·C=μs·G+e·Rmodp,and then(24)s·C·G-1vt=μ·p2+e·R·G-1vtmodp,where e∗≜e·R·G-1vt<1/2m·⌈log⁡p⌉. Hence, the correctness holds iff 1/2m·⌈log⁡p⌉<1/2·p/2.Since the homomorphic addition is obvious, we mainly analyze homomorphic multiplication and NAND operation.Homomorphic Multiplication. To multiply two ciphertext matrices C1,C2∈Zqn×N×ZpN designated for messages μ1,μ2∈{0,1}, we have(25)s·MultC1,C2=s·C1·G-1C2=e1+μ1s·G·G-1C2=e1·G-1C2+μ1e2+μ2s·G=e1·G-1C2+μ1e2+μ1μ2s·G,where G-1(C2)∈{0,1}N×N and e1·G-1(C2)+μ1e2 is the total noise which is of magnitude (26)e1·G-1C2+μ1e2≤12mN+1,due to eii∈[2]≤1/2m by the correctness of our basic encryption scheme. Therefore, it is clear that the noise growth factor is N+1, and after L levels of homomorphic multiplication, the noise grows from initial magnitude of 1/2m to 1/2m(N+1)L. By comparison, in GSW13, the noise at L level is near m′B(N′+1)L, where m′=O(nlog⁡q), N′=(n+1)·⌈log⁡q⌉,B≥ω(log⁡n)·n.Homomorphic NAND. To performNAND operation on two ciphertext matrices C1,C2∈Zqn×N[×]ZpN designated for messages μ1,μ2∈{0,1}, we have (27)s·NANDC1,C2=s·G-C1·G-1C2=e1·G-1C2+μ1e2+1-μ1μ2s·G,where e1·G-1(C2)+μ1e2 is the noise of homomorphicNAND, which is identical to that of homomorphic multiplication. Therefore, the noise is also increased by a factor of at most N+1.Analysis for Homomorphic Multiplication. Given two ciphertext matrices C=A·R+μG,C′=A·R′+μ′G∈Zqn×N[×]ZpN designated for messages μ,μ′∈{0,1}, we let C=Cqcp, C′=Cq′cp′∈Zqn×N[×]ZpN. Recall that (28)G=1,…,2log⁡q-1⋱1,…,2log⁡q-11,…,2log⁡p-1∈Zqn×N×ZpN.Compute G-1(C′) and let X=G-1(C′), that is, G·X=C′, and then we have X=XqXp∈{0,1}N×N, where Xq∈{0,1}(N-⌈log⁡p⌉)×N and Xp∈{0,1}⌈log⁡p⌉×N. Then, we have(29)MultC,C′=C·G-1C′=A·R+μG·XqXp=A·R·XqXp+μC′=A·R·XqXp+A·μR′+μμ′G=A·R·X+μR′+μμ′G,where, as per the specific matrix multiplication described in Section 2, we can compute A·R·X∈Zqn×N[×]ZpN. Since s·A=e mod p, X=XqXp does not affect the correctness of s·(A·R·X)=e·R·X mod p (recall that s=(-p/q·s′,1)). Therefore, (25) holds.


### 4.3. Parameters and Comparisons

Compared to GSW13 and AP14, we conclude, from the above analysis, that our noise growth factor is alsoN+1 (identical to theirs) and the size of parameter q is almost the same as theirs. Hence, we claim that the efficiency of our scheme is almost comparable to theirs without considering the cost of the Gaussian noise sampling, since our encryption and decryption processes are identical to theirs. Concretely, we assume the depth ofNAND operation is L, and after L levels of homomorphicNAND operation, the noise is near 1/2m(N+1)L, and it holds that 1/2m(N+1)L<1/2·p/2 for decryption. Then, combining with the requirements of q≥2mpB in Theorem 7 in Section 2, and m=O(nlog⁡q+log⁡p), N=nlog⁡q+log⁡p in our scheme, we can set q=(O(nlog⁡q))L+O(1), p=(O(nlog⁡p))L+O(1) satisfying q≥2mpB. Compared to the parameter q of q=(O(nlog⁡q))L+O(1) (since q≥8m′B(N′+1)L) in GSW13 and AP14, our parameter q is larger (up to a polynomial factor); this is caused by the condition q≥2mpB needed for achieving the same (almost) security level as GSW13 and AP14. Therefore, in consideration of the cost (e.g., running time, memory) of Gaussian or sub-Gaussian noise sampling in GSW13 and AP14, our scheme has some advantages over them and thus can be seen as an alternative to them. Actually, with the development of reduction betweenLWE andLWR, the moduli can be reduced.Bootstrapping involves homomorphically evaluating the decryption function. Because our decryption process is identical to AP14, bootstrapping works on our proposed scheme as well. In more detail, similar to AP14, we can also directly evaluate the decryption function in an elementary and efficient arithmetic form, using just basic facts about cyclic groups, so as to achieve bootstrapping. In our scheme, the bootstrapping method also just results in polynomial noise, which allows the security to be based on theLWR problem with inverse-polynomial noise rates. Since the reduction fromLWE toLWR incurs a polynomial loss (O(qnlog⁡q)) according to Theorem 7 in Section 2, the security can be based onLWE problem with inverse-polynomial noise rates and hence on worst-case lattice problems (e.g., GapSVP) with polynomial approximation factors.


## 4.1. Our Construction

OurLWR-based FHE scheme is constructed as follows.(i)
Setup(1λ,1L): choose dimension parameter n=n(λ,L) and moduli q=q(λ,L) and p=p(λ,L) satisfying p∣q. Also, choose parameter m=m(λ,L)=O(nlog⁡q+log⁡p). Let params=(n,q,p,m). Let k1=⌈log⁡q⌉, k2=⌈log⁡p⌉, and N=n·k1+k2.(ii)
KeyGen(params): choose uniformly at random a secret key s′←r{0,1}n. As perKeyGen algorithm in Section 3, generate a matrix (17)A=A¯b∈Zqn×m×Zpm.The final public key ispk≔A, and the secret key is sk:s=(-p/q·s′,1). Note that it holds that s·A=e mod p, where the noise e=(e1,…,em)∈[-1/2,1/2]m.(iii)
Enc(params,pk,μ): to encrypt a message μ∈{0,1}, choose a random matrix R←r{0,1}m×N. Output the ciphertext (18)C=A·R+μG∈Zqn×N×ZpN,where the gadget matrixG is brought from Section 2.3. Since we should perform the above matrix multiplication as per the specific matrix operations described in Section 2, we give Algorithm 1 that makes the encryption algorithm more readable.(iv)
Dec(params,sk,C): given the ciphertext C∈Zqn×N[×]ZpN, choose a vector v≔(0,…,0,p/2)∈Zpn+1 and compute (19)v=s·C·G-1vt=e·R·G-1vt+μ·p2.Outputμ=1/p/2·v (mod 2). We also give Algorithm 2 that makes the decryption algorithm more readable.(v)
Add(C1,C2): given two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, output (20)CAdd≜C1+C2∈Zqn×N×ZpN.(vi)
Mult(C1,C2): for two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, the multiplication is defined as (21)Cmult≜C1·G-1C2∈Zqn×N×ZpN,whereG-1 is brought from Section 2.3. We give Algorithm 3 only for homomorphic multiplication, because homomorphic addition is trivial, and homomorphicNAND depends on homomorphic multiplication.(vii)
NAND(C1,C2): for two ciphertext matrices C1,C2 decrypting to messages μ1 and μ2, respectively, theNAND operation is defined as (22)CNAND≜G-C1·G-1C2∈Zqn×N×ZpN.Note that any Boolean circuit can be converted to use onlyNAND operation.(viii)
Eval(f,(C1,C2,…,Ct)): evaluate the Boolean function f:{0,1}t→{0,1} on t ciphertexts C1,C2,…,Ct by theNAND operation. Output a ciphertext Cf.Algorithm 1:Encryption algorithm.
Input: Parameters, a public-key matrix A∈Zqn×m[×]Zpm and a message μ∈{0,1}. Output: A ciphertext matrix C=A⋅R+μG∈Zqn×N[×]ZpN. (1) Generate a variant gadget matrix G according to the structure of gadget matrix given in Section 2.3. (2) Choose uniformly at random a matrix R←r0,1m×N. (3) Compute C=A⋅R+μG∈Zqn×N×ZpN as per our specific matrix operations described in Section 2.Algorithm 2:Decryption algorithm.
Input: Parameters, a secret key sk=s and a ciphertext matrix C∈Zqn×N[×]ZpN. Output: A binary value μ∈{0,1}. (1) Choose a vector v:=0,…,0,p/2∈Zpn+1, and compute a vector r∈{0,1}N, such that G⋅rt=v, i.e., rt=G-1(vt). (2) Compute v = s ⋅ C ⋅ r t = e ⋅ R ⋅ r t + μ ⋅ p 2 . (3) Output μ=1/p/2⋅v (mod 2).Algorithm 3:Homomorphic multiplication.
Input: Two ciphertext matrices C1,C2 decrypting to messages μ1,μ2, respectively. Output: A derived ciphertext matrix Cmult decrypting to message μ1μ2. (1) Compute a matrix X∈{0,1}N×N, such that G⋅X=C2, i.e., X=G-1(C2). (2) Output C m u l t = C 1 ⋅ G - 1 C 2 ∈ Z q n × N × Z p N .The IND-CPA security of the above scheme follows immediately from the security of the basic encryption scheme in Section3. The ciphertext matrix is just μG plus a matrix of N encryptions of 0 under the key s by the basic encryption in Section 3, which is pseudorandom by Theorem 8 and hence hides μG.


## 4.2. Correctness

In this subsection, we analyze the scheme’s correctness and the noise growth of each homomorphic operation. Moreover, we also give a more detailed analysis for homomorphic multiplication to illustrate that our proposed construction is practicable.Correctness. The correctness is obvious according to the correctness of the basic encryption scheme in Section 3, iff the magnitude of noise e∗≜e·R·G-1(vt) is less than 1/2·p/2. In fact, according to theDec, we have(23)s·C=μs·G+e·Rmodp,and then(24)s·C·G-1vt=μ·p2+e·R·G-1vtmodp,where e∗≜e·R·G-1vt<1/2m·⌈log⁡p⌉. Hence, the correctness holds iff 1/2m·⌈log⁡p⌉<1/2·p/2.Since the homomorphic addition is obvious, we mainly analyze homomorphic multiplication and NAND operation.Homomorphic Multiplication. To multiply two ciphertext matrices C1,C2∈Zqn×N×ZpN designated for messages μ1,μ2∈{0,1}, we have(25)s·MultC1,C2=s·C1·G-1C2=e1+μ1s·G·G-1C2=e1·G-1C2+μ1e2+μ2s·G=e1·G-1C2+μ1e2+μ1μ2s·G,where G-1(C2)∈{0,1}N×N and e1·G-1(C2)+μ1e2 is the total noise which is of magnitude (26)e1·G-1C2+μ1e2≤12mN+1,due to eii∈[2]≤1/2m by the correctness of our basic encryption scheme. Therefore, it is clear that the noise growth factor is N+1, and after L levels of homomorphic multiplication, the noise grows from initial magnitude of 1/2m to 1/2m(N+1)L. By comparison, in GSW13, the noise at L level is near m′B(N′+1)L, where m′=O(nlog⁡q), N′=(n+1)·⌈log⁡q⌉,B≥ω(log⁡n)·n.Homomorphic NAND. To performNAND operation on two ciphertext matrices C1,C2∈Zqn×N[×]ZpN designated for messages μ1,μ2∈{0,1}, we have (27)s·NANDC1,C2=s·G-C1·G-1C2=e1·G-1C2+μ1e2+1-μ1μ2s·G,where e1·G-1(C2)+μ1e2 is the noise of homomorphicNAND, which is identical to that of homomorphic multiplication. Therefore, the noise is also increased by a factor of at most N+1.Analysis for Homomorphic Multiplication. Given two ciphertext matrices C=A·R+μG,C′=A·R′+μ′G∈Zqn×N[×]ZpN designated for messages μ,μ′∈{0,1}, we let C=Cqcp, C′=Cq′cp′∈Zqn×N[×]ZpN. Recall that (28)G=1,…,2log⁡q-1⋱1,…,2log⁡q-11,…,2log⁡p-1∈Zqn×N×ZpN.Compute G-1(C′) and let X=G-1(C′), that is, G·X=C′, and then we have X=XqXp∈{0,1}N×N, where Xq∈{0,1}(N-⌈log⁡p⌉)×N and Xp∈{0,1}⌈log⁡p⌉×N. Then, we have(29)MultC,C′=C·G-1C′=A·R+μG·XqXp=A·R·XqXp+μC′=A·R·XqXp+A·μR′+μμ′G=A·R·X+μR′+μμ′G,where, as per the specific matrix multiplication described in Section 2, we can compute A·R·X∈Zqn×N[×]ZpN. Since s·A=e mod p, X=XqXp does not affect the correctness of s·(A·R·X)=e·R·X mod p (recall that s=(-p/q·s′,1)). Therefore, (25) holds.


## 4.3. Parameters and Comparisons

Compared to GSW13 and AP14, we conclude, from the above analysis, that our noise growth factor is alsoN+1 (identical to theirs) and the size of parameter q is almost the same as theirs. Hence, we claim that the efficiency of our scheme is almost comparable to theirs without considering the cost of the Gaussian noise sampling, since our encryption and decryption processes are identical to theirs. Concretely, we assume the depth ofNAND operation is L, and after L levels of homomorphicNAND operation, the noise is near 1/2m(N+1)L, and it holds that 1/2m(N+1)L<1/2·p/2 for decryption. Then, combining with the requirements of q≥2mpB in Theorem 7 in Section 2, and m=O(nlog⁡q+log⁡p), N=nlog⁡q+log⁡p in our scheme, we can set q=(O(nlog⁡q))L+O(1), p=(O(nlog⁡p))L+O(1) satisfying q≥2mpB. Compared to the parameter q of q=(O(nlog⁡q))L+O(1) (since q≥8m′B(N′+1)L) in GSW13 and AP14, our parameter q is larger (up to a polynomial factor); this is caused by the condition q≥2mpB needed for achieving the same (almost) security level as GSW13 and AP14. Therefore, in consideration of the cost (e.g., running time, memory) of Gaussian or sub-Gaussian noise sampling in GSW13 and AP14, our scheme has some advantages over them and thus can be seen as an alternative to them. Actually, with the development of reduction betweenLWE andLWR, the moduli can be reduced.Bootstrapping involves homomorphically evaluating the decryption function. Because our decryption process is identical to AP14, bootstrapping works on our proposed scheme as well. In more detail, similar to AP14, we can also directly evaluate the decryption function in an elementary and efficient arithmetic form, using just basic facts about cyclic groups, so as to achieve bootstrapping. In our scheme, the bootstrapping method also just results in polynomial noise, which allows the security to be based on theLWR problem with inverse-polynomial noise rates. Since the reduction fromLWE toLWR incurs a polynomial loss (O(qnlog⁡q)) according to Theorem 7 in Section 2, the security can be based onLWE problem with inverse-polynomial noise rates and hence on worst-case lattice problems (e.g., GapSVP) with polynomial approximation factors.


## 5. LWR-Based Multikey FHE Scheme

FHE has been studied extensively also due to its versatility in cryptography and industrial application, such as the problem of outsourcing computation to a third trust party (a remote server) without compromising its privacy [5] and secure multiparty computation problem [12, 30]. In Eurocrypt 2016, Mukherjee and Wichs [12] extended AP14 to multikey case and presented a multikey FHE scheme for implementing two round multiparty computations, which enabled performing homomorphic computation over encrypted data under different keys and satisfied threshold decryption. Their solution, however, relies on theLWE problem, the efficiency of which is retarded by the sub-Gaussian noise sampling. But the tricks in [12] inspire us to construct a multikey FHE scheme based onLWR. In fact, our construction also satisfies threshold decryption; we will describe it in Section 5.3. Here, we just present some necessary tools and our main construction, and we refer interested readers to [12] for the definitions of multikey FHE and multiparty computation, the security definition of multiparty computation protocol, and some other related concepts.


### 5.1. Overview of the Techniques

In this subsection, we will describe how to construct aLWR-based multikey FHE scheme (adapted from [12]); this helps readers understand our construction more easily. For simplicity, we consider a case of two keys, for it is natural to generalize to the case of any polynomial number of keys. According to (23) in Section 4.2, given two ciphertexts C1 and C2 decrypting to messages μ1 and μ2, we can perform homomorphic operations on these two ciphertexts, iff they satisfy the equation s·C=μis·G+ei for small noise ei, where i∈[2]. Hence, for the “combined secret key” s^=(s1,s2), where s1=(-p/q·s1′,1) and s2=(-p/q·s2′,1) which correspond to two different users, if we can construct two expanded ciphertexts C^1 and C^2, such that s^·C^1≈μ1s^·G^ and s^·C^2≈μ2s^·G^ (henceforth, ≈ is used for omitting the noise term e), where G^ is the expansion of G, then we can perform homomorphic operations on these two ciphertexts C^1 and C^2.Exactly as Mukherjee and Wichs [12] showed, we can create the expanded ciphertext as follows: (30)C^1≔C1X10C1,such that (31)s^·C^1≈μ1s^G^,iff(32)s1·X1+s2·C1≈μ1s2·G,where G^≔G00G. Similarly, we can also generate the ciphertext C^2. Here, we have made a big step forward; next, we proceed to analyze how to construct this X without revealing the secret key s2.Assume we are given a user-specific public keyA1=A¯b1, a secret key s1=(-p/q·s1′,1), and a ciphertext (33)C1=A1·R1+μG=A¯·R1b1·R1+μG,which is generated as perEnc algorithm in Section 4. Assume we are also given another user-specific public key A2=A¯b2 and secret key s2=(-p/q·s2′,1) (assume A¯ is the public shared parameter), such that s2·A2=emodp; then, we have(34)s2·C1=-pq·s2′·A¯·R1+b1·R1+μ1s2·G≈b1-b2·R1+μ1s2·G.Subtracting (34) from (32), we get s1·X1≈(b2-b1)·R1 over Zp. We proceed to use an important tool brought from [12] to construct such matrix X.Linear Combination. For a matrix R∈{0,1}m×N with mN entries {R[i,j]} for i∈[m], j∈[N], let C(i,j)∈Zqn×N[×]ZpN beLWR-based FHE encryption of R[i,j] under a secret key s=(-p/q·s′,1), where s′←r{0,1}n. Let b∈Zpm be a vector, where b[i] is its ith entry. Then, there is a polynomial time deterministic algorithm (35)Clc=LCombC1,1,…,Cm,N,b,which outputs Clc∈Zqn×N[×]ZpN such that s·Clc=b·R+e, where e∞≤1/2(mN)2.The algorithmLComb((C(1,1),…,C(m,N)),b) is implemented as follows:(1)
For eachi∈[m], j∈[N], define a matrix Zi,j∈Zpm×N as follows: (36)Zi,ja,b=biwhena=n,b=j,0otherwise.In other words,Zi,j will be 0 everywhere except the nth row and jth column where it has the value b[i].(2)
OutputClc∈Zqn×N[×]ZpN, where Clc=∑i=1,j=1m,N‍C(i,j)·G-1(Zi,j).Then, we analyze its correctness as follows:(37)s·Clc=s·∑i,jm,NCi,j·G-1Zi,j=∑i,jm,NRi,j·s·G+ei,j·G-1Zi,j=∑i,jm,NRi,j·s·Zi,j+ei,j′=s·∑i,jm,NRi,j·Zi,j+∑i,jm,Nei,j′=-pq·s′,1·0b·R+e′′=b·R+e′′,where ei,j is the noise contained in C(i,j) with magnitude of ei,j∞≤1/2m (according to Section 3), and then ei,j′=ei,j·G-1(Zi,j) has magnitude ei,j′∞≤1/2mN, and finally e′′=∑i,jm,N‍ei,j′ has magnitude e′′∞≤1/2(mN)2.


### 5.2. Construction of Two-Key FHE Scheme from LWR

For ease of description, here we just give a construction of two-key FHE scheme based onLWR, for everything extends naturally to any polynomial number of keys.Construction. Now, we describe the two-key FHE construction.(i)
TFHE.Setup(1λ,1L): run theSetup andKeyGen algorithms in Section 4 to generate the parameters: (38)params≔n,q,p,m,A¯.(ii)
TFHE.KeyGen(params): run theKeyGen algorithms in Section 4 to get (39)sk:si=-pq·si′,1,pk:Ai=A¯bi∈Zqn×m×Zpm,fori∈2.(iii)
TFHE.Enc(params,pki,μi): for i∈[2], run theEnc algorithm in Section 4 to get a ciphertext Ci and the corresponding random matrix Ri∈{0,1}m×N. For all entries {Ri[i,j]}i∈[m],j∈[N] of the uniform matrix Ri∈{0,1}m×N, we use the same secret key si to encrypt them, which leads to a helper set Hi={Ci(i,j)}i∈[m],j∈[N]. Output the ciphertext Ci and the helper set Hi.(iv)
TFHE.Expand(params,(pk1,pk2),Ci,Hi): given Ci and Hi, when i=1, run thelinear combination algorithm to generate a matrix X1=LComb((C1(1,1),…,C1(m,N)),b2-b1), such that(40)s1·X1=b2-b1·R1+eX1.Finally, output an expanded ciphertext:(41)C^1≔C1X10C1,where ciphertextC1 corresponds to the message μ1. Similarly, when i=2, output an expanded ciphertext C^2.(v)
TFHE.Eval(params,f,(C^1,C^2)): on inputting two expanded ciphertexts, runEval algorithm in Section 4, albeit with expanded dimensions n′=2n+2 and N′=2N, and the gadget matrix G^≔G00G. Output the ciphertext C^f.(vi)
TFHE.Dec(params,(sk1,sk2),C^f): on inputting a ciphertext C^f and two secret keys sk1 and sk2, parse sk1=s1 and sk2=s2, and then obtain a new secret key s^=(s1,s2). Finally, run theDec algorithm in Section 4 to get a plaintext f(μ1,μ2).Correctness. It is sufficient to verify that s^·C^1≈μ1s^·G^ and s^·C^2≈μ2s^·G^. Adding (34) and (40) up, that is, (42)s2·C1≈b1-b2·R1+μ1s2·Gplus(43)s1·X1=b2-b1·R1+eX1,results in (44)s^·C^1=s1·C1,s1·X1+s2·C1≈μ1s1·G,μ1s2·G=μ1s^·G^.This also applies to verify s^·C^2≈μ2s^·G^.Parameters and Security. Though ourLWR-based multikey FHE scheme does not need the sub-Gaussian noise sampling compared to Mukherjee and Wichs’s [12], the structure of our construction is identical to theirs. Indeed, we just cleverly use the scaled rounding function instead of their sub-Gaussian noise, to hide the message, and this is done thanks to our specific structure which helps us circumvent the tangly modulus problem that exists in [22]. Since theLWE-based multikey FHE [12] is an extension of AP14, while the parameter q in ourLWR-based FHE is almost identical to that of AP14 according to Section 4.2, hence theLWR-based multikey FHE which is the extension ofLWR-based FHE has almost the same parameter q as that of [12].As to the security, we remark that the main difference between multikey setting in this section and single key setting in Section4 is the number of ciphertexts. In multikey setting, there is an additional helper set H which involves mN ciphertexts, but the mN ciphertexts are encryptions of entries of the random matrix R∈0,1m×N, which are independent of other ciphertexts. In other words, the helper set H does not affect scheme’s security; therefore, ourLWR-based multikey FHE scheme has the same security level as theLWR-based FHE scheme in Section 4.


### 5.3. Threshold Decryption for Two-Key FHE Scheme

In [12], the main idea of designing a multiparty computation protocol is to leverage the property of “threshold decryption” of multikey FHE and rely on the “smudging lemma [31].” In the secure multiparty computation distributed protocol, the parties run a secure distributed protocol using their own secret key to decrypt the output ciphertext and finally recover the plaintext y. Specifically, each party will obtain partial information by operating their own secret key on the common ciphertext C^, and then they broadcast the information they get added by some medium-sized smudging noise from a uniform distribution (adding the noise is needed to “smudge out” any information about the noise contained in ciphertext C^ and is needed for security proof); finally, each party can sum up all the other partial information and get the final decryption y. We can achieve the construction of multiparty computation protocol as well, for ourLWR-based multikey FHE scheme also satisfies the threshold decryption. Compared to [12], our threshold decryption also needs the smudging noise, but the whole computation overhead is lower in that ourLWR-based multikey FHE scheme does not need the sub-Gaussian noise sampling. The threshold decryption follows. For simplicity, we again cover the case of two-key FHE.(i)
TFHE.PartDec(C^,(pk1,pk2),(sk1,sk2)): given the output (common) ciphertext C^ under two public keys pk1,pk2 and the secret keys sk1=s1,sk2=s2, do the following:
(1)
Parse the ciphertextC^ consisting of two submatrices C^(i) such that C^=C^(1)C^(2).(2)
Define a vectorv^∈Zp2n+2 as v^=(0,…,0,p/2).(3)
Fori∈[2], compute ϕi=siC^(i)·G^-1(v^t)∈Zp, and then compute τi=ϕi+ei∗∈Zp, where ei∗←r[-Bsmdgdec,Bsmdgdec] is random “smudging noise.” We can set Bsmdgdec=2Lλlog⁡λ. Note that the parameter Bsmdgdec=Bχ·2Lλlog⁡λ in [12], where Bχ>ω(log⁡n)·n.(ii)
TFHE.FinDec(τ1,τ2): given τ1,τ2, compute the sum τ=∑i=12‍τi. Finally, output μ′=1/p/2·τ.Correctness. Given the common ciphertext C^ designated for the message μ∈{0,1}, parse the parties’ keys as s^=(s1,s2). By the correctness ofLWR-based two-key FHE scheme, it holds that (45)s^·C^=∑i=12si·C^i=μs^·G^+e^modp.Then, we have (46)τ=∑i=12τi=∑i=12ϕi+∑i=12ei∗=∑i=12si·Ci·G^-1v^t+e∗=μs^·G^+e^·G^-1v^t+e∗=μ·p2+e′+e∗modp,where e′+e∗<1/2·p/2 holds under the appropriate parameters; for example, we can set p=2ω(Lλlog⁡λ). Therefore, the correctness holds.


## 5.1. Overview of the Techniques

In this subsection, we will describe how to construct aLWR-based multikey FHE scheme (adapted from [12]); this helps readers understand our construction more easily. For simplicity, we consider a case of two keys, for it is natural to generalize to the case of any polynomial number of keys. According to (23) in Section 4.2, given two ciphertexts C1 and C2 decrypting to messages μ1 and μ2, we can perform homomorphic operations on these two ciphertexts, iff they satisfy the equation s·C=μis·G+ei for small noise ei, where i∈[2]. Hence, for the “combined secret key” s^=(s1,s2), where s1=(-p/q·s1′,1) and s2=(-p/q·s2′,1) which correspond to two different users, if we can construct two expanded ciphertexts C^1 and C^2, such that s^·C^1≈μ1s^·G^ and s^·C^2≈μ2s^·G^ (henceforth, ≈ is used for omitting the noise term e), where G^ is the expansion of G, then we can perform homomorphic operations on these two ciphertexts C^1 and C^2.Exactly as Mukherjee and Wichs [12] showed, we can create the expanded ciphertext as follows: (30)C^1≔C1X10C1,such that (31)s^·C^1≈μ1s^G^,iff(32)s1·X1+s2·C1≈μ1s2·G,where G^≔G00G. Similarly, we can also generate the ciphertext C^2. Here, we have made a big step forward; next, we proceed to analyze how to construct this X without revealing the secret key s2.Assume we are given a user-specific public keyA1=A¯b1, a secret key s1=(-p/q·s1′,1), and a ciphertext (33)C1=A1·R1+μG=A¯·R1b1·R1+μG,which is generated as perEnc algorithm in Section 4. Assume we are also given another user-specific public key A2=A¯b2 and secret key s2=(-p/q·s2′,1) (assume A¯ is the public shared parameter), such that s2·A2=emodp; then, we have(34)s2·C1=-pq·s2′·A¯·R1+b1·R1+μ1s2·G≈b1-b2·R1+μ1s2·G.Subtracting (34) from (32), we get s1·X1≈(b2-b1)·R1 over Zp. We proceed to use an important tool brought from [12] to construct such matrix X.Linear Combination. For a matrix R∈{0,1}m×N with mN entries {R[i,j]} for i∈[m], j∈[N], let C(i,j)∈Zqn×N[×]ZpN beLWR-based FHE encryption of R[i,j] under a secret key s=(-p/q·s′,1), where s′←r{0,1}n. Let b∈Zpm be a vector, where b[i] is its ith entry. Then, there is a polynomial time deterministic algorithm (35)Clc=LCombC1,1,…,Cm,N,b,which outputs Clc∈Zqn×N[×]ZpN such that s·Clc=b·R+e, where e∞≤1/2(mN)2.The algorithmLComb((C(1,1),…,C(m,N)),b) is implemented as follows:(1)
For eachi∈[m], j∈[N], define a matrix Zi,j∈Zpm×N as follows: (36)Zi,ja,b=biwhena=n,b=j,0otherwise.In other words,Zi,j will be 0 everywhere except the nth row and jth column where it has the value b[i].(2)
OutputClc∈Zqn×N[×]ZpN, where Clc=∑i=1,j=1m,N‍C(i,j)·G-1(Zi,j).Then, we analyze its correctness as follows:(37)s·Clc=s·∑i,jm,NCi,j·G-1Zi,j=∑i,jm,NRi,j·s·G+ei,j·G-1Zi,j=∑i,jm,NRi,j·s·Zi,j+ei,j′=s·∑i,jm,NRi,j·Zi,j+∑i,jm,Nei,j′=-pq·s′,1·0b·R+e′′=b·R+e′′,where ei,j is the noise contained in C(i,j) with magnitude of ei,j∞≤1/2m (according to Section 3), and then ei,j′=ei,j·G-1(Zi,j) has magnitude ei,j′∞≤1/2mN, and finally e′′=∑i,jm,N‍ei,j′ has magnitude e′′∞≤1/2(mN)2.


## 5.2. Construction of Two-Key FHE Scheme from LWR

For ease of description, here we just give a construction of two-key FHE scheme based onLWR, for everything extends naturally to any polynomial number of keys.Construction. Now, we describe the two-key FHE construction.(i)
TFHE.Setup(1λ,1L): run theSetup andKeyGen algorithms in Section 4 to generate the parameters: (38)params≔n,q,p,m,A¯.(ii)
TFHE.KeyGen(params): run theKeyGen algorithms in Section 4 to get (39)sk:si=-pq·si′,1,pk:Ai=A¯bi∈Zqn×m×Zpm,fori∈2.(iii)
TFHE.Enc(params,pki,μi): for i∈[2], run theEnc algorithm in Section 4 to get a ciphertext Ci and the corresponding random matrix Ri∈{0,1}m×N. For all entries {Ri[i,j]}i∈[m],j∈[N] of the uniform matrix Ri∈{0,1}m×N, we use the same secret key si to encrypt them, which leads to a helper set Hi={Ci(i,j)}i∈[m],j∈[N]. Output the ciphertext Ci and the helper set Hi.(iv)
TFHE.Expand(params,(pk1,pk2),Ci,Hi): given Ci and Hi, when i=1, run thelinear combination algorithm to generate a matrix X1=LComb((C1(1,1),…,C1(m,N)),b2-b1), such that(40)s1·X1=b2-b1·R1+eX1.Finally, output an expanded ciphertext:(41)C^1≔C1X10C1,where ciphertextC1 corresponds to the message μ1. Similarly, when i=2, output an expanded ciphertext C^2.(v)
TFHE.Eval(params,f,(C^1,C^2)): on inputting two expanded ciphertexts, runEval algorithm in Section 4, albeit with expanded dimensions n′=2n+2 and N′=2N, and the gadget matrix G^≔G00G. Output the ciphertext C^f.(vi)
TFHE.Dec(params,(sk1,sk2),C^f): on inputting a ciphertext C^f and two secret keys sk1 and sk2, parse sk1=s1 and sk2=s2, and then obtain a new secret key s^=(s1,s2). Finally, run theDec algorithm in Section 4 to get a plaintext f(μ1,μ2).Correctness. It is sufficient to verify that s^·C^1≈μ1s^·G^ and s^·C^2≈μ2s^·G^. Adding (34) and (40) up, that is, (42)s2·C1≈b1-b2·R1+μ1s2·Gplus(43)s1·X1=b2-b1·R1+eX1,results in (44)s^·C^1=s1·C1,s1·X1+s2·C1≈μ1s1·G,μ1s2·G=μ1s^·G^.This also applies to verify s^·C^2≈μ2s^·G^.Parameters and Security. Though ourLWR-based multikey FHE scheme does not need the sub-Gaussian noise sampling compared to Mukherjee and Wichs’s [12], the structure of our construction is identical to theirs. Indeed, we just cleverly use the scaled rounding function instead of their sub-Gaussian noise, to hide the message, and this is done thanks to our specific structure which helps us circumvent the tangly modulus problem that exists in [22]. Since theLWE-based multikey FHE [12] is an extension of AP14, while the parameter q in ourLWR-based FHE is almost identical to that of AP14 according to Section 4.2, hence theLWR-based multikey FHE which is the extension ofLWR-based FHE has almost the same parameter q as that of [12].As to the security, we remark that the main difference between multikey setting in this section and single key setting in Section4 is the number of ciphertexts. In multikey setting, there is an additional helper set H which involves mN ciphertexts, but the mN ciphertexts are encryptions of entries of the random matrix R∈0,1m×N, which are independent of other ciphertexts. In other words, the helper set H does not affect scheme’s security; therefore, ourLWR-based multikey FHE scheme has the same security level as theLWR-based FHE scheme in Section 4.


## 5.3. Threshold Decryption for Two-Key FHE Scheme

In [12], the main idea of designing a multiparty computation protocol is to leverage the property of “threshold decryption” of multikey FHE and rely on the “smudging lemma [31].” In the secure multiparty computation distributed protocol, the parties run a secure distributed protocol using their own secret key to decrypt the output ciphertext and finally recover the plaintext y. Specifically, each party will obtain partial information by operating their own secret key on the common ciphertext C^, and then they broadcast the information they get added by some medium-sized smudging noise from a uniform distribution (adding the noise is needed to “smudge out” any information about the noise contained in ciphertext C^ and is needed for security proof); finally, each party can sum up all the other partial information and get the final decryption y. We can achieve the construction of multiparty computation protocol as well, for ourLWR-based multikey FHE scheme also satisfies the threshold decryption. Compared to [12], our threshold decryption also needs the smudging noise, but the whole computation overhead is lower in that ourLWR-based multikey FHE scheme does not need the sub-Gaussian noise sampling. The threshold decryption follows. For simplicity, we again cover the case of two-key FHE.(i)
TFHE.PartDec(C^,(pk1,pk2),(sk1,sk2)): given the output (common) ciphertext C^ under two public keys pk1,pk2 and the secret keys sk1=s1,sk2=s2, do the following:
(1)
Parse the ciphertextC^ consisting of two submatrices C^(i) such that C^=C^(1)C^(2).(2)
Define a vectorv^∈Zp2n+2 as v^=(0,…,0,p/2).(3)
Fori∈[2], compute ϕi=siC^(i)·G^-1(v^t)∈Zp, and then compute τi=ϕi+ei∗∈Zp, where ei∗←r[-Bsmdgdec,Bsmdgdec] is random “smudging noise.” We can set Bsmdgdec=2Lλlog⁡λ. Note that the parameter Bsmdgdec=Bχ·2Lλlog⁡λ in [12], where Bχ>ω(log⁡n)·n.(ii)
TFHE.FinDec(τ1,τ2): given τ1,τ2, compute the sum τ=∑i=12‍τi. Finally, output μ′=1/p/2·τ.Correctness. Given the common ciphertext C^ designated for the message μ∈{0,1}, parse the parties’ keys as s^=(s1,s2). By the correctness ofLWR-based two-key FHE scheme, it holds that (45)s^·C^=∑i=12si·C^i=μs^·G^+e^modp.Then, we have (46)τ=∑i=12τi=∑i=12ϕi+∑i=12ei∗=∑i=12si·Ci·G^-1v^t+e∗=μs^·G^+e^·G^-1v^t+e∗=μ·p2+e′+e∗modp,where e′+e∗<1/2·p/2 holds under the appropriate parameters; for example, we can set p=2ω(Lλlog⁡λ). Therefore, the correctness holds.


## 6. Conclusions

We present the first workableLWR-based FHE scheme. Our FHE scheme erases the expensive Gaussian noise sampling and thus can be seen as an alternative to the existingLWE-based FHEs. Furthermore, based on our main construction, we give the firstLWR-based multikey FHE scheme, which is an alternative to the existing multikey FHEs that can also be applied to multiparty computation. However, neither ourLWR-based multikey FHE scheme nor Mukherjee and Wichs’s can be used to construct multiparty computation protocol without the smudging lemma (which means that the corresponding modulus has to be set exponentially in security parameter). Therefore, it remains an open problem to construct multiparty computation protocol via multikey FHEs without the smudging lemma.



---

*Source: 5967635-2018-04-23.xml*