Efficient Homomorphic Conversion Between (Ring) LWE Ciphertexts

Abstract

In the past few years, significant progress on homomorphic encryption (HE) has been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE). In this work, we present new conversion algorithms that switch between different (R)LWE-based HE schemes to take advantage of them. Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption. Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.

1 Introduction

In recent years, there have been remarkable advances in cryptographic primitives for secure computation without compromising data privacy. Specifically, homomorphic encryption (HE) [28] has been considered as one of the most attractive solutions due to its conceptual simplicity and efficiency. HE is a cryptosystem which supports arithmetic operation on encrypted data, so that any computational task can be outsourced to a public cloud while data provider does not need to either perform a large amount of work or stay online during the protocol execution. In addition, the concrete efficiency of HE has been improved rapidly by theoretic and engineering optimizations [4, 15, 41]. Recent studies demonstrated that this technology shows reasonable performance in real-world tasks such as biomedical analysis and machine learning [20, 33, 34].

Currently, all the best-performing HE schemes, such as BGV [8], BFV [6, 23], TFHE [18] and CKKS [16], are based on the hardness of Learning with Errors (LWE) or its ring variant (RLWE). In particular, ring-based HE systems have shown remarkable performance in real-world applications due to the efficient use of the ciphertext packing technique [43]. Each HE scheme has its own pros and cons, but it has been relatively less studied how to take advantage of various HE schemes by converting ciphertexts of different types [5].

Our Contribution. In this paper, we provide a toolkit to transform (R)LWE-based ciphertexts and generate another ciphertext under a new key or of a different structure. Specifically, we present three conversion methods: (1) to perform a new key-switching (KS) operation between LWE ciphertexts; (2) to transform an LWE ciphertext into an RLWE-based ciphertext; and (3) to merge multiple LWE ciphertexts into a single RLWE ciphertext. The first two conversions (from LWE to LWE/RLWE) have quasi-linear complexity $\tilde{O}(N)$ where N denotes the dimension of (R)LWE. The last packing algorithm is a generalization of LWE-to-RLWE conversion which achieves a better amortized complexity. Our algorithms are almost optimal in the sense that their complexities are quasi-linear with respect to the size of input ciphertext(s). Moreover, there is no reduction of ciphertext level (modulus) because all building blocks (e.g. homomorphic automorphism) are depth-free. The proposed methods have wide applications in the literature: For example, our KS algorithm can replace the old KS method in the FHEW and TFHE schemes [18, 22], and our LWEs-to-RLWE packing method can improve the performance of [5, 10] which present a hybrid framework between different HE schemes. In addition, the proposed methods can be easily generalized to design better key-switching methods between (R)LWE ciphertexts with different dimensions, or more generally, Module LWE [8, 35] based schemes with different parameters.

Finally, we present experimental results to show that our techniques achieve better asymptotic and concrete performance than previous methods. Moreover, we provide a secure outsourcing solution of storage and computation to a cloud with low communication cost. A client encrypts data via an LWE-based symmetric encryption on a lightweight device. On receiving LWE ciphertexts, the public server transforms or packs them into RLWE encryptions to provide better functionality for homomorphic arithmetic. Compared to prior works based on block or stream ciphers [3, 9, 21, 27, 37], our approach has advantages in terms of flexibility, functionality and efficiency.

Technical Overview. Let N be the dimension and q the modulus of an LWE problem. An LWE ciphertext with secret $\mathbf{s}\in {\mathbb Z}^N$ is of the form $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ and its phase is defined as $\mu =b+\langle \mathbf {a},\mathbf{s}\rangle \pmod q$. Typically, the phase is a noisy encoding of some underlying plaintext. Performing homomorphic operations on a ciphertext will increase this noise and thus the phase will be changed, but as long as the noise is below a given threshold, the underlying plaintext is preserved. Similarly, in the case of RLWE over $R={\mathbb Z}[X]/(X^N+1)$ and its residue ring $R_q=R/qR$, the phase of an RLWE ciphertext $(b,a)\in R_q^2$ of secret s is defined as $\mu =b+as \pmod q$.

Suppose that we are given some ciphertexts of a cryptosystem (which is not necessarily an HE scheme) and wish to publicly transform them into ciphertexts of another HE scheme for secure computation. In general, this task can be done by evaluating the decryption circuit of the initial cryptosystem using an HE system if a homomorphically encrypted secret key is given. Furthermore, the conversion can be more efficient if input ciphertexts are encrypted by an LWE-based cryptosystem because it suffices to homomorphically evaluate the phase, instead of performing the full decryption which usually includes expensive (non-arithmetic) operations such as bit extraction or rounding [12, 26].

We remark that this approach can be still inefficient in some cases. For example, if we aim to convert an LWE encryption $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ under secret $\mathbf{s}\in {\mathbb Z}^N$ into an RLWE ciphertext, the secret key owner should generate and publish an RLWE ‘encryption’ of $\mathbf{s}$ as the evaluation key, and the conversion can be done by computing the LWE phase $\mu =b+\langle \mathbf {a},\mathbf{s}\rangle$ homomorphically over an RLWE-based HE system. In fact, the evaluation key consists of N key-switching keys from individual $\mathbf{s}[i]$ to the RLWE secret and the conversion requires N RLWE KS operations. Consequently, the total complexity grows quadratically with the security parameter. The techniques we present in this work do not follow the existing framework of the phase evaluation.

Our first idea is to embed elements of ${\mathbb Z}_q^N$ or ${\mathbb Z}_q$ into $R_q$. Given an LWE ciphertext $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ of the phase $\mu _0=b+\langle \mathbf {a},\mathbf{s}\rangle$, we consider the RLWE ciphertext $\mathsf {ct}=(b,a)\in R_q^2$ for $a=\sum _{i\in [N]} \mathbf {a}[i]\cdot X^i$ and the secret $s=\sum _{i\in [N]}\mathbf{s}[i]\cdot X^{-i} \in R$. The ciphertext $\mathsf {ct}$ is not a completely valid RLWE ciphertext but its phase $\mu =b+as \pmod q$ contains $\mu _0=\mu [0]$ in its constant term. We use this idea to accelerate the KS procedure between LWE ciphertexts. For another LWE secret $\mathbf{s}'$, we first perform a RLWE KS procedure from s to $s'=\sum _{i\in [N]}\mathbf{s}'[i]\cdot X^{-i}$. Then the phase of the output ciphertext is approximately equal to $\mu$ in R, so it is enough to extract an LWE ciphertext from the ciphertext.

Our second algorithm is an efficient conversion from LWE to RLWE. In the example above, the RLWE ciphertext $\mathsf {ct}$ cannot be directly used for further homomorphic computation because the phase $\mu$ contains invalid values in its coefficients except the constant term. We observe that the field trace function $\text {Tr}_{K/{\mathbb Q}}$ of the number field $K={\mathbb Q}[X]/(X^N+1)$ zeroizes all the monomials $X^i$ for $0\ne i\in [N]$ but keeps the constant term (scaled by a factor of N). We homomorphically evaluate the trace function to obtain an RLWE ciphertext whose phase is approximately equal to the constant polynomial $N\cdot \mu _0$ (the extra factor N can be easily removed). To minimize the conversion complexity, we present a recursive algorithm that includes only $\log N$ automorphism evaluations, based on the tower of number fields. Furthermore, our algorithm reduces the number of key-switching keys to $\log N$ compared to N of the previous method.

Finally, we present a packing algorithm that takes at most N LWE ciphertexts as the input and returns a single RLWE ciphertext. Suppose that we are given $n\le N$ input ciphertexts of phases $\mu _j\in {\mathbb Z}_q$. A naive solution is to perform our LWE-to-RLWE conversion on each LWE ciphertext and adds up the output RLWE ciphertexts into a single ciphertext, which requires $n \log N$ homomorphic automorphisms. We can improve the complexity by performing the FFT-style ciphertext packing algorithm. The first step is a tree-based algorithm which generates an RLWE ciphertext of phase $\mu \in R_q$ such that $\mu [(N/n)\cdot j] \approx n\cdot \mu _j$ for all $j\in [n]$, i.e., it collects the phases $\mu _j$’s in an element $\sum _{j\in [n]}\mu _j\cdot Y^j$ of $K_n={\mathbb Z}[Y]/(Y^n+1)$. In the following step, we evaluate the field trace $\text {Tr}_{K/K_n}$ to annihilate the useless coefficients $\mu [i]$ for $(N/n) \not \mid i$ and finally return an RLWE ciphertext of phase $\approx N\cdot \sum _{j\in [n]} \mu _j\cdot Y^j$. The whole process requires $(n-1)+\log (N/n)$ homomorphic automorphisms, so we achieve an amortized complexity of $< 1+ n^{-1}\cdot \log N$ automorphisms per an LWE ciphertext.

Table 1. Computational costs (number of scalar operations) and storage (number of ${\mathbb Z}_q$ elements to store a switching key) of conversion algorithms. N denotes the dimension of (R)LWE, n denotes the number of input LWE ciphertexts to be packed in an RLWE ciphertext, and d denotes the gadget decomposition degree.

Related Works. In [25, 26], the authors presented a method to switch the underlying field of HE ciphertexts. In these works, ciphertexts were taken as the input of the trace function to reduce the dimension of the base ring dynamically during computation purely for efficiency reasons. Meanwhile, in our LWE(s)-to-RLWE algorithm, we utilize the trace function in a totally different way for a different purpose. We homomorphically evaluate the field trace on plaintexts (phases) to generate a valid RLWE ciphertext over a larger ring $R_q$ from LWE ciphertexts over ${\mathbb Z}_q$.

It has been studied in [17, 39] how to convert multiple LWE ciphertexts into a single RLWE ciphertext. Given n LWE ciphertexts $\left\{ (b_j,\mathbf {a}_j)\right\} _{j\in [n]}$, it vertically stacks the i-th entries of all ciphertexts in a polynomial by $b= \sum _{j\in [n]} b_j \cdot X^j$ and $a_i = \sum _{j\in [n]} \mathbf {a}_{j}[i]\cdot X^j$ for $i\in [N]$. Then it homomorphically evaluates $b + \sum _i a_i \cdot s_i$ over an RLWE-based HE scheme. Different from our packing algorithm, this method has a fixed complexity of N RLWE KS operations, independently from the number n of input ciphertexts. This implies that it needs to pack $\Omega (N)$ many ciphertexts to achieve minimal amortized complexity.

Boura et al. [5] presented various transformations between ciphertexts of different RLWE-based HE schemes. Our work is in an orthogonal direction to [5] as we aim to switch the secret key or change the type of ciphertexts (e.g. LWE, RLWE) while preserving their phases (encoded plaintexts). In addition, the performance of [5] can be improved by replacing the underlying KS methods by our conversion algorithms.

Cheon and Kim [13] considered converting an ElGamal-like public key encryption scheme to an HE scheme. This involves evaluating the decryption circuit homomorphically, which consumes at least 10 levels, while our approach is almost depth-free.

In Table 1, we provide the performance of previous works and analyze the computational costs of our algorithms. Our LWE-to-RLWE conversion consists of several iterations in which we evaluate an automorphism and add the resulting ciphertext to the original input. There have been proposed a few algorithms [11, 12, 14, 31] which are technically similar to our conversion algorithm. However, to the best of our knowledge, this is the first study to reinterpret and apply this building block to the KS (conversion) of HE ciphertexts.

Recently, Gentry and Halevi [24] and Brakerski et al. [7] presented a new framework that compresses multiple HE ciphertexts into a single ciphertext with the nearly optimal rate of $1-o(1)$. Our approach solves an associated but fundamentally different problem. In our application, we could build a lightweight and low-latency communication from the client to the cloud because fresh ciphertexts are high-rate and extremely small. However, they should be packed or converted into an RLWE ciphertext before computation. Meanwhile, previous works [7, 24] aim to compress HE ciphertexts after computation and thereby minimize the communication cost from the cloud to the client.

2 Background

We denote vectors in bold, e.g. $\mathbf {u}$, and the i-th entry of a vector $\mathbf {u}$ will be denoted by $\mathbf {u}[i]$. For simplicity, we identify ${\mathbb Z}\cap (-q/2,q/2]$ as a set of representatives of ${\mathbb Z}_q$ and write the index set $[N]=\{0,1,\dots ,N-1\}$. For a finite set S, U(S) denotes the uniform distribution on S.

2.1 Cyclotomic Field

Let $\zeta =\exp (\pi i/N)$ for a power-of-two integer N. We denote by $K={\mathbb Q}(\zeta )$ the 2N-th cyclotomic field and $R={\mathbb Z}[\zeta ]$ the ring of integers of K. We will identify K (resp. R) with ${\mathbb Q}[X]/(X^N+1)$ (resp. ${\mathbb Z}[X]/(X^N+1)$) with respect to the map $\zeta \mapsto X$. The residue ring of R modulo an integer q is denoted by $R_{q}=R/q R$. For $a,b \in {\mathbb Z}$ (or R, $R_{q}$), we informally write $a \approx b \pmod q$ if $a=b+e$ for some small $e\in {\mathbb Z}$ (or R).

An element of K (resp. R, $R_q$) can be uniquely represented as a polynomial of degree less than N with coefficients in ${\mathbb Q}$ (resp. ${\mathbb Z}$, ${\mathbb Z}_q$). The i-th coefficient of a polynomial a(X) will be denoted by a[i]. We use the map $\iota :\mathbf {a}\mapsto \sum _{i\in [N]}\mathbf {a}[i]\cdot X^i$ to identify a polynomial and the vector of its coefficients.

2.2 (Ring) Learning with Errors

Given the dimension N, modulus q and error distribution $\psi$ over ${\mathbb Z}$, the LWE distribution with secret $\mathbf{s}\in {\mathbb Z}^N$ is a distribution over ${\mathbb Z}_q^{N+1}$ which samples $\mathbf {a}\leftarrow U({\mathbb Z}_q^N)$ and $e\leftarrow \psi$, and returns $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ where $b=\langle \mathbf {a},\mathbf{s}\rangle +e \pmod q$. The (decisional) LWE assumption of parameter $(N,q,\chi ,\psi )$ is that it is computationally infeasible to distinguish the LWE distribution of a secret $\mathbf{s}\leftarrow \chi$ from the uniform distribution $U({\mathbb Z}_q^{N+1})$.

The RLWE problem [36] is a variant of LWE which has been widely used to design HE schemes, e.g. [8, 16, 18, 23]. The key s is chosen from the key distribution $\chi$ over R, and an RLWE sample $(b,a)\in R_q^2$ by sampling random a and noise e from $U(R_q)$ and the error distribution $\psi$ over R and computing $b=as+e \pmod q$. The RLWE assumption with parameter $(N,q,\chi ,\psi )$ is that the RLWE distribution of a secret $s\leftarrow \chi$ and $U(R_q^2)$ are computationally indistinguishable.

2.3 Gadget Decomposition

Let q be an integer and $\mathbf {g}=(g_0,\dots ,g_{d-1})$ be an integral vector. A gadget decomposition [38], denoted by $\mathbf {g}^{-1}:{\mathbb Z}_q\rightarrow {\mathbb Z}^d$, is a map satisfying $\langle \mathbf {g}^{-1}(a),\mathbf {g}\rangle =a \pmod q$ for all $a\in {\mathbb Z}_q$. We can naturally extend its domain and define $\mathbf {g}^{-1}:R_q\rightarrow R^d$ by $a=\sum _{i\in [N]} a_i\cdot X^i\mapsto \sum _{i\in [N]}\mathbf {g}^{-1}(a_i)\cdot X^i$.

The base (digit) decomposition [6, 8] and prime decomposition [4, 15] are typical examples. This technique has been widely used to control the noise growth during homomorphic computation such as key-switching, which will be described in the next section.

2.4 Key Switching

We describe a well known KS method for RLWE ciphertexts. The goal of KS procedure is to transform a ciphertext into another ciphertext under a different secret key while approximately preserving its phase.

$\bullet ~\texttt {KSKeyGen}(s\in R, s'\in R):$ Sample $\mathbf {k}_1\leftarrow U(R_{q}^d)$ and $\mathbf {e}\leftarrow \chi ^d$. Compute $\mathbf {k}_0=-s'\cdot \mathbf {k}_1+s\cdot \mathbf {g}+\mathbf {e}\pmod {q}$ and return the KS key $\mathbf {K}=[\mathbf {k}_0|\mathbf {k}_1]\in R_{q}^{d\times 2}$.

$\bullet ~\texttt {KeySwitch}(\mathsf {ct}; \mathbf {K}):$ Given an RLWE ciphertext $\mathsf {ct}=(c_0,c_1)\in R_{q}^{2}$ and a KS key $\mathbf {K}\in R_q^{d\times 2}$, compute and return the ciphertext $\mathsf {ct}'=(c_0,0)+\mathbf {g}^{-1}(c_1)\cdot \mathbf {K}\pmod {q}$.

Roughly speaking, a KS key consists of d RLWE ‘encryptions’ of $s\cdot g_i$ under $s'$, i.e., $\mathbf {K}\cdot (1,s')\approx s\cdot \mathbf {g}\pmod q$. For an RLWE ciphertext $\mathsf {ct}\in R_q^2$ and a KS key $\mathbf {K}\leftarrow \texttt {KSKeyGen}(s,s')$, the output $\mathsf {ct}'\leftarrow \texttt {KeySwitch}(\mathsf {ct};\mathbf {K})$ satisfies that

$$\begin{aligned} \langle \mathsf {ct}',(1,s')\rangle&=c_0+\mathbf {g}^{-1}(c_1)\cdot \mathbf {K}\cdot (1,s') \nonumber \\&=c_0+\langle \mathbf {g}^{-1}(c_1),s\cdot \mathbf {g}+\mathbf {e}\rangle = \langle \mathsf {ct},(1,s)\rangle +e_{ks} \pmod q \end{aligned}$$

(1)

for the KS noise $e_{ks}=\langle \mathbf {g}^{-1}(c_1),\mathbf {e}\rangle \in R$.

2.5 Galois Group and Evaluation of Automorphisms

We recall that $K\ge Q$ is a Galois extension and its Galois group $\text {Gal}(K/{\mathbb Q})$ consists of the automorphisms $\tau _d:\zeta \mapsto \zeta ^d$ for $d\in {\mathbb Z}_{2N}^\times$, the invertible residues modulo 2N. The automorphisms $\tau _d\in \text {Gal}(K/{\mathbb Q})$ gives some distinctive functionalities to the HE system. For example, many of RLWE-based schemes such as BGV [8], BFV [6, 23] and CKKS [16] utilize the Discrete Fourier Transform (DFT) to encode multiple plaintext values in a single polynomial, so that the slots of a ciphertext can be permuted by evaluating an automorphism.

We describe a well-known method to homomorphically evaluate an automorphism $\tau _d: a(X) \rightarrow a(X^d)$.

$\bullet ~\texttt {AutoKeyGen}(d \in {\mathbb Z}_{2N}^\times ; s\in R):$ Run $\mathbf {A}_d\leftarrow \texttt {KSKeyGen}(\tau _d(s),s)$.

$\bullet ~\texttt {EvalAuto}\left( \mathsf {ct}\in R_q^2, d \in {\mathbb Z}_{2N}^\times ; \mathbf {A}_d\right) :$ Given a ciphertext $\mathsf {ct}=(c_0,c_1)\in R_q^2$, an integer $d\in {\mathbb Z}_{2N}^\times$ and an automorphism key $\mathbf {A}_d$, compute and return the ciphertext $\mathsf {ct}'\leftarrow \texttt {KeySwitch}\left( (\tau _d(c_0), \tau _d(c_1));\mathbf {A}_d\right)$.

Security. The homomorphic automorphism algorithm is a simple application of KS, so its security basically relies on the hardness of RLWE for $\texttt {KSKeyGen}$. Moreover, an additional circular security assumption should be made because $\mathbf {A}_d$ is a special encryption of $\tau _d(s)$ with secret s.

Correctness. Suppose that $\mathsf {ct}\in R_q^2$ is an RLWE ciphertext such that $\mu =\langle \mathsf {ct},(1,s)\rangle \pmod q$ and $\mathbf {A}_d\leftarrow \texttt {AutoKeyGen}(d; s)$ is an automorphism key. Then the output ciphertext $\mathsf {ct}'\leftarrow \texttt {EvalAuto}(\mathsf {ct},d; \mathbf {A}_d)$ satisfies that

$$\begin{aligned} \langle \mathsf {ct}',(1,s)\rangle \approx \langle (\tau _d(c_0),\tau _d(c_1)),(1, \tau _d(s))\rangle = \tau _d\left( \langle \mathsf {ct},(1,s)\rangle \right) =\tau _d(\mu ) \pmod q, \end{aligned}$$

from the property of $\texttt {KeySwitch}$.

In the rest of this paper, we simply write $\texttt {EvalAuto}(\mathsf {ct},d;\mathbf {A}_d)=\texttt {EvalAuto}(\mathsf {ct},d)$ by assuming that an automorphism key $\mathbf {A}_d\leftarrow \texttt {AutoKeyGen}(d;s)$ is properly generated and implicitly taken as input of the $\texttt {EvalAuto}$ algorithm. We remark that homomorphic automorphism has almost the same complexity as the KS procedure because the computation of $\tau _d(c_i)$ is very cheap.

3 Conversion Algorithms

This section presents core ideas and their application to efficient conversion between HE ciphertexts of different secret keys or algebraic structures.

3.1 Functionality of Automorphisms on Coefficients

We examine how the elements of ${\text {Gal}}(K/{\mathbb Q})$ act on the coefficients of an input polynomial. Let us define the sets $I_k=\left\{ i\in [N]: 2^k~\Vert ~i\right\}$¹ for $0\le k<\log N$ and $I_{\log N}=\{0\}$. Then, the index set [N] can be written as the disjoint union $\bigcup _{0\le k\le \log N}I_k$. We are interested in how the automorphism $\tau _d(\cdot )$ acts on the monomials for $d=2^\ell +1$, $1\le \ell \le \log N$. We note that the map $i\mapsto i\cdot d \pmod N$ is a signed permutation on $I_k$, i.e., if $i\in I_k$, then $\tau _d(X^i)=\pm X^j$ for some $j\in I_k$. In particular, we see that

$$\begin{aligned} \tau _d(X^i)&= X^i \quad \text {for} \quad i \in \bigcup _{k>\log N-\ell } I_k, \nonumber \\ \tau _d(X^i)&= -X^i \quad \text {for} \quad i \in I_{\log N-\ell }. \end{aligned}$$

(2)

In other words, the map $\mu \mapsto \mu +\tau _d(\mu )$ doubles the coefficients $\mu [i]$ if $2^{\log N-\ell +1}|~i$, but zeroizes the coefficients $\mu [i]$ if $2^{\log N-\ell }\Vert ~i$.

3.2 LWE to LWE

Let $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ be an LWE ciphertext under a secret $\mathbf{s}\in {\mathbb Z}^N$ with phase $\mu _0=b+\langle \mathbf {a},\mathbf{s}\rangle \pmod q$. We aim to design an efficient LWE-to-LWE conversion, which replaces the secret of the ciphertext into another secret $\mathbf{s}'\in {\mathbb Z}^N$ while almost preserving the phase $\mu _0$.

Our first idea is to embed ${\mathbb Z}_q^N$ and ${\mathbb Z}_q$ into $R_q$ to utilize the ring structure. We consider the two polynomials

$$\begin{aligned} a&:=\iota (\mathbf {a})=\sum _{i\in [N]} \mathbf {a}[i]\cdot X^i\in R_q, \\ s&:=\tau _{-1}\circ \iota (\mathbf{s})=\sum _{i\in [N]} \mathbf{s}[i]\cdot X^{-i}\in R, \end{aligned}$$

and we define the polynomial pair $\mathsf {ct}=(b,a)\in R_q^2$. We remark that $\mathsf {ct}$ can be viewed as an RLWE ciphertext with secret s satisfying $\langle \mathsf {ct},(1,s)\rangle [0] = (b+as)[0] = \mu _0$, i.e., its phase $\mu =\langle \mathsf {ct},(1,s)\rangle \pmod q$ of $\mathsf {ct}$ stores $\mu [0]=\mu _0$ in the constant term but all other coefficients, $\mu [i]$ for $0\ne i\in [N]$, have no valid values.

Though $\mathsf {ct}$ is not a valid RLWE ciphertext, we can still apply the KS algorithm. If we perform the KS procedure from s to $s'=\tau _{-1}\circ \iota (\mathbf{s}')$, then the output ciphertext also includes a valid value in its constant term from the property of KS. Finally, we can extract an LWE ciphertext with secret $\mathbf{s}'$.

$\bullet ~\texttt {LWE-to-LWE}\left( (b,\mathbf {a}), \mathbf {K}\right) :$ Given an LWE ciphertext $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ and a KS key $\mathbf {K}\in R_q^{L\times 2}$, set the RLWE ciphertext $\mathsf {ct}\leftarrow (b,a)\in R_q^2$ where $a=\iota (\mathbf {a})$. Compute $\mathsf {ct}'=(b',a')\leftarrow \texttt {KeySwitch}(\mathsf {ct},\mathbf {K})\in R_q^2$ and let $\mathbf {a}'=\iota ^{-1}(a')$. Return the ciphertext $(b'[0],\mathbf {a}')\in {\mathbb Z}_q^{N+1}$.

Correctness. We claim that, if $\mathbf {K}\leftarrow \texttt {KSKeyGen}(s, s')$ is a KS key from s to $s'$, then $(b'[0],\mathbf {a}')$ is an LWE ciphertext under $\mathbf{s}'$ whose phase is approximately equal to the phase of $(b,\mathbf {a})$ under $\mathbf{s}$. It can be shown by

$$\begin{aligned} b'[0]+\langle \mathbf {a}',\mathbf{s}'\rangle =(b'+a's')[0] \approx (b+as)[0] = b+\langle \mathbf {a},\mathbf{s}\rangle \pmod q, \end{aligned}$$

where the approximate equality is derived from the property of $\texttt {KeySwitch}$ (see Eq. (1)).

3.3 LWE to RLWE

Our next goal is to design a conversion algorithm from LWE to RLWE. As explained above, if we set an RLWE ciphertext $(b,a=\iota (\mathbf {a}))\in R_q^2$ from an LWE ciphertext $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$, then its phase has the valid value only in the constant term. Hence, the key question is how to annihilate useless coefficients of $\mu$ except the constant term $\mu [0]$ to generate a valid RLWE ciphertext.

We remark that the field trace $\text {Tr}_{K/{\mathbb Q}}:K\rightarrow {\mathbb Q}$, $a\mapsto \sum _{\tau \in {\text {Gal}}(K/{\mathbb Q})}\tau (a)$ has the required property, i.e., $\text {Tr}_{K/{\mathbb Q}}(1) = N$ and $\text {Tr}_{K/{\mathbb Q}}(X^i)=0$ for all $0\ne i\in [N]$. Therefore, conversion from LWE into RLWE can be done by evaluating the field trace homomorphically. A naive solution is to evaluate each automorphism $\tau (\cdot )$ and add up all the resulting ciphertexts, and therefore it requires N KS operations. We now describe a recursive algorithm that uses an algebraic structure of cyclotomic fields for reducing the conversion complexity. To be precise, for the tower of finite fields $K=K_N\ge K_{N/2}\ge \dots \ge K_1={\mathbb Q}$, where $K_n$ denotes the (2n)-th cyclotomic field for a power-of-two integer n, the field trace can be expressed as a composition $\text {Tr}_{K/{\mathbb Q}}=\text {Tr}_{K_2/K_1}\circ \dots \circ \text {Tr}_{K_N/K_{N/2}}$ of $\log N$ field traces and each Galois group ${\text {Gal}}\left( K_{2^\ell }/K_{2^{\ell -1}}\right)$ has a (unique) nontrivial element $\tau _{2^\ell +1}|_{K_{2^\ell }}$ for $\ell =1,\dots , \log N$. Therefore, the evaluation of $\text {Tr}_{K_{2^\ell }/K_{2^{\ell -1}}}$ requires only one homomorphic rotation.

See Algorithm 1 for a description of homomorphic trace evaluation $\text {Tr}_{K_N/K_n}$ for any power-of-two integer $n\le N$. We use the parameter $n=1$ in the following LWE-to-RLWE conversion algorithm.

$\bullet ~\texttt {LWE-to-RLWE}\left( (b,\mathbf {a})\in {\mathbb Z}_q\times {\mathbb Z}_q^N\right) :$ Set the RLWE ciphertext $\mathsf {ct}\leftarrow (b,a)\in R_q^2$ where $a=\iota (\mathbf {a})$. Then, run Algorithm 1 and return the ciphertext $\mathsf {ct}'\leftarrow \texttt {EvalTr}_{N/1}(\mathsf {ct})\in R_q^2$.

The phase of the input LWE ciphertext $(b,\mathbf {a})$ is multiplied by N by the trace evaluation. We will explain in the next section how to remove the constant N by adding a pre-processing step.

Correctness. We will prove the correctness of Algorithm 1 for an arbitrary $n\le N$. Let $\mu =\langle \mathsf {ct},(1,s)\rangle \pmod q$ be the phase of an input $\mathsf {ct}$. We inductively show that the phase $\mu '=\langle \mathsf {ct}',(1,s)\rangle \pmod q$ satisfies

$$\begin{aligned} \mu '\approx \text {Tr}_{K_N/K_{N/2^{k}}}(\mu )=2^{k}\cdot \sum _{2^{k}|i\in [N]}\mu [i]\cdot X^i \pmod q \end{aligned}$$

(3)

at iteration k. For the base case $k=0$, the statement is trivially true since $\mu '=\mu$. Now we assume that (3) is true for $k-1$. In the next k-th iteration, we evaluate the map $\mu '\mapsto \mu '+\tau _d(\mu ')$ for $d=2^{\log N-k+1}+1$. We recall from (2) that $\tau _d(X^i)=X^i$ for $2^{k}~|~i\in [N]$ and $\tau _d(X^i)=-X^i$ for $i\in [N]$ such that $2^{k-1}~\Vert ~i$. From the induction hypothesis,

$$\begin{aligned} \mu '&\approx 2^{k-1}\cdot \sum _{2^{k-1}|i}\mu [i]\cdot X^i \\&= 2^{k-1}\cdot \sum _{2^{k}| i} \mu [i]\cdot X^i + 2^{k-1}\cdot \sum _{2^{k-1}\Vert i}\mu [i]\cdot X^i \pmod q,\\ \tau _d(\mu ')&\approx 2^{k-1}\cdot \sum _{2^{k}| i} \mu [i]\cdot X^i - 2^{k-1}\cdot \sum _{2^{k-1}\Vert i}\mu [i]\cdot X^i \pmod q, \end{aligned}$$

and thereby $\mu '+\tau _d(\mu ')\approx 2^{k}\cdot \sum _{2^{k}|i}\mu [i]\cdot X^i$. Finally, we obtain

$$\mu '\approx \text {Tr}_{K_N/K_n}(\mu )=(N/n)\cdot \sum _{(N/n)|i\in [N]}\mu [i]\cdot X^i \pmod q$$

after $k=\log (N/n)$ iterations. We remark that the noise does not blow up much during the evaluation since $\tau _d(\cdot )$ preserves the size of elements in R.

The correctness of $\texttt {LWE-to-RLWE}$ is directly derived from this result with a parameter $n=1$. Given an RLWE encryption $\mathsf {ct}=(b,a)$, we homomorphically compute the field trace $\text {Tr}_{K_N/{\mathbb Q}}$ and the phase $\mu '=\langle \mathsf {ct}',(1,s)\rangle$ of the output ciphertext is approximately equal to $\text {Tr}_{K_N/{\mathbb Q}}(b+as) = N\cdot (b+as)[0] = N\cdot (b+\langle \mathbf {a},\mathbf{s}\rangle )$, as desired.

3.4 LWEs to RLWE

An LWE ciphertext has a phase in ${\mathbb Z}_q$, which can store only one scalar message, so our LWE-to-RLWE conversion algorithm aims to generate an RLWE ciphertext whose phase $\mu$ contains an approximate value of an initial LWE phase in its constant term. However, in general, an RLWE ciphertext can store at most N scalars in the coefficients of its phase. So a natural question is how to efficiently merge multiple LWE ciphertexts into a single RLWE ciphertext.

Suppose that we are given n LWE ciphertexts $\{(b_j,\mathbf {a}_j)\}_{j\in [n]}$ for some $n=2^\ell \le N$ and let $\mu _j\in {\mathbb Z}_q$ be the phase of $(b_j,\mathbf {a}_j)$ under the same secret $\mathbf{s}\in {\mathbb Z}^N$. A naive answer for the question above is to run $\mathsf {ct}_j'\leftarrow \texttt {LWE-to-RLWE}\left( (b_j,\mathbf {a}_j)\right) \in R_q^2$ for all $j\in [n]$ and take their linear combination $\mathsf {ct}'=\sum _{j\in [n]}\mathsf {ct}_j'\cdot Y^j$ for $Y=X^{N/n}$. Then the phase of $\mathsf {ct}'$ is approximately equal to $N\cdot \sum _{j\in [n]}\mu _j\cdot Y^j$, which is an element of the ring of integers of $K_{n}$. However, this method is not optimal in terms of both complexity and noise growth.

In this section, we present a generalized version of our previous algorithm which takes multiple LWE encryptions as input and returns a single RLWE ciphertext. This conversion consists of two phases: packing and trace evaluation. The first step (Algorithm 2) is an FFT-style algorithm which merges $n=2^\ell$ multiple RLWE ciphertexts into one. The phase $\mu$ of an output ciphertext stores the constant terms of input phases in its coefficients $\mu [i]$ for (N/n) | i. All valid values are now packed into an element of $R_n$, so in the next step, we use the idea of the previous section to evaluate the field trace $\text {Tr}_{K_N/K_n}$ and zeroize useless coefficients.

$\bullet ~\texttt {LWEs-to-RLWE}\left( \left\{ (b_j,\mathbf {a}_j)\right\} _{j\in [n]}\right) :$ Given $n=2^\ell$ LWE ciphertexts $(b_j,\mathbf {a}_j)\in {\mathbb Z}_q^{N+1}$, do the following:

• 1. Set $\mathsf {ct}_j\leftarrow (b_j,a_j)\in R_q^2$ for each $j\in [n]$ where $a_j=\iota (\mathbf {a}_j)$.

• 2. Run Algorithm 2 to get $\mathsf {ct}\leftarrow \texttt {PackLWEs}\left( \{\mathsf {ct}_j\}_{j\in [n]}\right)$.

• 3. Compute and return the ciphertext $\mathsf {ct}'\leftarrow \texttt {EvalTr}_{N/n}(\mathsf {ct})$.

The packing algorithm and the subsequent field trace evaluation for $n=2^\ell$ ciphertexts require $(n-1)$ and $\log (N/n)$ homomorphic automorphisms, respectively. Hence the total complexity of $\texttt {LWEs-to-RLWE}$ is $(n-1)+\log (N/n)<n+\log N$ automorphisms, yielding an amortized complexity less than $(1+n^{-1}\cdot \log N)$ automorphisms per an input LWE ciphertext. We remark that this conversion algorithm achieves the asymptotically optimal amortized complexity (O(1) automorphisms) when $n=\Omega (\log N)$. Similar to the LWE-to-RLWE conversion, the phase of input ciphertexts are multiplied by the factor of N which can be removed by a pre-processing step described below.

Correctness. We first show the correctness of our packing algorithm. For $j\in [2^\ell ]$, let $\mathsf {ct}_j$ be input ciphertexts of Algorithm 2 such that $\mu _j=\langle \mathsf {ct}_j,(1,s)\rangle [0] \pmod q$. For the output ciphertext $\mathsf {ct}\leftarrow \texttt {PackLWEs}\left( \{\mathsf {ct}_j\}_{j\in [2^\ell ]}\right)$, we claim that its phase satisfies

$$\begin{aligned} \mu \left[ (N/2^{\ell })\cdot j\right] \approx 2^\ell \cdot \mu _j \pmod q \quad \text {for all} \quad j \in [2^\ell ]. \end{aligned}$$

(4)

We again use the induction on $\ell \ge 0$. The base case $\ell =0$ is trivial since $\mu [0]=\mu _0$. Suppose that our statement is true for some $0\le \ell -1<\log N$. For $2^\ell$ input ciphertexts, Algorithm 2 first divides them into two groups of size $2^{\ell -1}$ and runs $\texttt {PackLWEs}$ twice (in lines 5 and 6). From the induction hypothesis, the output ciphertexts $\mathsf {ct}_{even}, \mathsf {ct}_{odd}$ have phases $\mu _{even}, \mu _{odd}$ such that

$$\begin{aligned} \mu _{even}\left[ (N/2^{\ell -1})\cdot j\right]&\approx 2^{\ell -1}\cdot \mu _{2j} \pmod q,\\ \mu _{odd}\left[ (N/2^{\ell -1})\cdot j\right]&\approx 2^{\ell -1}\cdot \mu _{2j+1} \pmod q, \end{aligned}$$

for all $j\in [2^{\ell -1}]$. Then, we compute and return the ciphertext $\mathsf {ct}$ whose phase is

$$\begin{aligned} \mu&\approx (\mu _{even}+X^{N/2^\ell }\cdot \mu _{odd}) + \tau _d\left( \mu _{even}-X^{N/2^\ell }\cdot \mu _{odd}\right) \\&= \mu _{even}' + X^{N/2^\ell }\cdot \mu _{odd}', \end{aligned}$$

for $\mu _{even}'=\mu _{even}+\tau _d(\mu _{even})$ and $\mu _{odd}'=\mu _{odd}+\tau _d(\mu _{odd})$, which satisfies that

$$\begin{aligned} \mu _{even}'\left[ (N/2^{\ell })\cdot (2j)\right] \approx 2^\ell \cdot \mu _{2j}, \quad \mu _{even}'\left[ (N/2^{\ell })\cdot (2j+1)\right] \approx 0 \pmod q,\\ \mu _{odd}'\left[ (N/2^{\ell })\cdot (2j)\right] \approx 2^\ell \cdot \mu _{2j+1}, \quad \mu _{odd}'\left[ (N/2^{\ell })\cdot (2j+1)\right] \approx 0 \pmod q \end{aligned}$$

for all $j\in [2^{\ell -1}]$. Therefore, their linear combination $\mu =\mu _{even}'+X^{N/2^\ell }\cdot \mu _{odd}'$ has coefficients $\mu \left[ (N/2^\ell )\cdot j\right] \approx 2^\ell \cdot \mu _j$ for all $j\in [2^{\ell }]$, as desired.

Now let us discuss the $\texttt {LWEs-to-RLWE}$ algorithm. After running the packing algorithm, the phase $\mu$ of $\mathsf {ct}\leftarrow \texttt {PackLWEs}\left( \{\mathsf {ct}_j\}_{j\in [n]}\right)$ has $n\cdot \mu _j$ in its coefficients $\mu [i]$ such that (N/n) | i. So we homomorphically evaluate the field trace $\text {Tr}_{K_N/K_{n}}$ on the ciphertext $\mathsf {ct}$ to zeroize all other coefficients. It follows from the property of Algorithm 1 that the final output $\mathsf {ct}'\leftarrow \texttt {EvalTr}_{N/n}(\mathsf {ct})$ satisfies

$$\begin{aligned} \langle \mathsf {ct}',(1,s)\rangle&\approx \text {Tr}_{K_N/K_{n}}(\mu ) = (N/n)\cdot \sum _{(N/n)|i\in [N]} \mu [i]\cdot X^{i} \\&\approx (N/n)\cdot \sum _{j\in [n]} (n\cdot \mu _j)\cdot X^{(N/n)\cdot j} = N\cdot \sum _{j\in [n]} \mu _j\cdot Y^j\pmod q \end{aligned}$$

where $Y=X^{N/n}$, as desired.

Removing the Leading Term. Let $\{\mathsf {ct}_j\}_{j\in [n]}$ be n LWE input encryptions of our LWEs-to-RLWE algorithm and $\mathsf {ct}'$ the output RLWE ciphertext. We denote their phases by $\mu _j=\langle \mathsf {ct}_j,(1,\mathbf{s})\rangle \pmod q$ and $\mu '=\langle \mathsf {ct}',(1,s)\rangle \pmod q$, respectively. As shown in their correctness proofs, our algorithms converting one or more LWE encryptions into an RLWE ciphertext introduce the additional term N into the phase of output RLWE ciphertext.

We present a pre-processing technique to remove this constant. We multiply the constant $N^{-1} \pmod q$ to the input LWE ciphertexts so that their phases $\mu _j$ are also multiplied by the same factor. If we run the same algorithm on the ciphertexts of phases $N^{-1}\cdot \mu _j \pmod q$, then the leading term N is naturally cancelled out and the phase of the output RLWE ciphertext will be approximately equal to $N\cdot \sum _{j\in [n]}(N^{-1}\cdot \mu _j)\cdot Y^j=\sum _{j\in [n]}\mu _j\cdot Y^j$, as desired.

We note that this method is depth-free and does not incur extra noise growth. It requires the ciphertext modulus q to be co-prime to the dimension N, but it is not a strong assumption in practice².

Further Computation on a Packed Ciphertext. In a plaintext level, our conversion algorithm computes the function ${\mathbb Z}_q^n\rightarrow R_q$, $(\mu _j)_{j\in [n]}\mapsto \sum _{j\in [n]}\mu _j\cdot Y^j$, which is not a multiplicative homomorphism. However, it is often required to pack multiple values in plaintext slots, instead of coefficients, so that parallel computation (e.g. element-wise addition or multiplication) is allowed over an encrypted vector of plaintexts.

It has been studied in several researches about HE bootstrapping [12, 14, 26, 32] how to represent values from coefficients to slots and vice versa. In the case of BGV, BFV or CKKS, the transformation can be done by evaluating the encoding or decoding functions of the underlying scheme, which are expressed as linear transformations over plaintext vectors. We do not consider it here because this coefficients-to-slots conversion is scheme-dependent. Moreover, its computational cost is cheaper than the main part, so that the total/amortized complexities do not change much even if we add this extra step at the end.

4 Implementation

4.1 Experimental Results

We provide a proof-of-concept implementation to show the performance of our conversion algorithms. Our source code is developed in C++ by modifying Microsoft SEAL version 3.5.1 [42]. All experiments are performed on a desktop with an Intel Core i7-4770K CPU running a single thread at 3.50 GHz, compiled with Clang 9.0.0 (-O3)³.

We set the secret distribution as the uniform distribution over the set of ternary polynomials in R coefficients in $\{0,\pm 1\}$. Each coefficient/entry of (R)LWE error is drawn according to the discrete Gaussian distribution centered at zero with standard deviation $\sigma =3.2$. The selected parameter sets provide at least 128-bit of security level according to the LWE estimator [2] and HE security standard white paper [1].

Table 2 presents timing results and noise growth of our conversion algorithms. The ciphertext moduli q of three parameter sets are products of 2, 4, and 8 distinct primes, respectively. We use an RNS-friendly decomposition method [4] and exploit an efficient NTT in order to optimize the basic polynomial arithmetic. As discussed in Sect. 3.4, the LWEs-to-RLWE conversion algorithm achieves a better amortized running time as the number n of input LWE ciphertexts increases. For comparison, we implemented the old KS method using the same parameter sets and decomposition method, and it took 203ms and 1628ms when $(N,\log q)=(2^{12},72)$ and $(2^{13},174)$, respectively, compared to 1.0ms and 4.8ms of our method. We refer the reader to Appendix A which provides noise analysis of our conversion algorithms. The noise variances of the LWE-to-LWE and LWE(s)-to-RLWE conversions are O(N) and $O(N^3)$, respectively, which align very well with our experimental results.

Table 2. Concrete performance of our conversion algorithms measured by total running time (amortized timing per ciphertext) and noise growth (an upper bound on the bit size of coefficients of conversion errors). n stands for the number of input LWE ciphertexts.

We did not specify the underlying HE scheme or its plaintext space as the performance of our conversion algorithms depends only on the parameters N, $\log q$ and n. Since the bit-size of a conversion noise is only $O(\log N)$ bits, the rest of the space can be used to store a plaintext or be left empty to provide more homomorphic functionality after conversion. For example, if we use the BFV scheme with the second parameter set $(N,\log q)=(2^{13},174)$, then our conversion algorithms work correctly as long as the bit-size of its plaintext modulus is $\le 152$.

4.2 Lightweight Communication with Homomorphic Functionality

HE is a useful cryptographic technology for secure outsourced computation on the cloud, however, its applications have some common issues in practice. Since HE schemes are comparably expensive, a client must have enough memory and computing power. Moreover, the ciphertext expansion rate can be reasonably small only when we pack a large number of values in a single RLWE ciphertext. Therefore, the total communication cost may blow up much when the client sends a small amount of information.

To mitigate this issue, Naehrig et al. [40] came up with a blueprint that the client sends data, encrypted by a light-weight symmetric encryption scheme, as well as a homomorphically encrypted secret key of the cryptosystem. Then, the cloud homomorphically evaluates its decryption circuit to get homomorphically encrypted data. In this scenario, the main challenge is to construct a symmetric encryption with low communication cost (expansion rate) and conversion complexity. After the first attempt by Gentry et al. [27] which evaluated the AES-128 circuit using the BGV scheme, there has been a line of studies (e.g. LowMC [3], Kreyvium [9], FLIP [37], Rasta [21]) to design HE-friendly symmetric encryption schemes. These block/stream ciphers made progresses in communication cost and encryption time, but the transformation of ciphertexts results in a considerable computational overhead on the cloud side.

In this work, we present a new solution that the client uses an LWE-based symmetric encryption on the edge device. On receiving the LWE ciphertexts, the cloud transforms them into RLWE encryptions using our conversion algorithm. In addition, we adapt the idea of Coron et al. [19] to reduce the size of LWE ciphertexts and communication cost. To be precise, a symmetric key LWE encryption of secret $\mathbf{s}$ is of the form $(b,\mathbf {a})\in {\mathbb Z}_q^{N+1}$ for a random vector $\mathbf {a}\leftarrow U({\mathbb Z}_q^N)$ and $b=-\langle \mathbf {a},\mathbf{s}\rangle +\mu \pmod q$ where $\mu$ is the phase from the input which is a randomized encoding of the plaintext. Since the second component $\mathbf {a}$ is purely random over ${\mathbb Z}_q^N$, we can modify the encryption algorithm such that it samples a seed $\mathsf {se}$ and takes it as the input of a pseudo-random number generator $f:\{0,1\}^*\rightarrow {\mathbb Z}_q^N$ to generate $\mathbf {a}=f(\mathsf {se})$. As a result, a ciphertext can be represented as a pair $(b,\mathsf {se})$, and this variant remains semantically secure in the random oracle model. Moreover, when a client sends multiple LWE ciphertexts to the cloud, the same seed can be reused by computing the random part of the i-th ciphertext by $\mathbf {a}_i=f(\mathsf {se};i)$. Hence, the communication cost per an LWE ciphertext is only $\log q$ bits.

Our approach has advantages in computational efficiency compared to prior works based on block/stream ciphers. Prior works have several minutes’ latency for the transformation (e.g. 4.1, 63.1, 29.3, 0.65 and 15.2 min of AES-128, LowMC v1, Kreyvium, FLIP, and Rasta, respectively⁴), and have to collect a number of ciphertexts to achieve the minimal amortized complexity. Meanwhile, our method has significantly better conversion latency and amortized timings (several milliseconds), and enables a smooth trade-off between them via the packing algorithm. As discussed in Sect. 3.4, it requires to collect only $\Omega (\log N)$ LWE ciphertexts to obtain a nearly optimal amortized complexity.

Our method is generic in the sense that it preserves the phases of input ciphertexts approximately regardless of the type of HE schemes or a plaintext space. Therefore, it is allowed to use the BGV/BFV scheme with a non-binary plaintext space, or CKKS for approximate computation. Moreover, we provide a flexible parameter setting that enables us to achieve an almost optimal expansion rate of $1+o(1)$ even when a client sends only a small amount of information at a time. For example, as shown in Table 2, the expansion rate can be reduced down to $174/(174-21)\approx 1.14$ or $389/(389-23)\approx 1.06$ when $(N,\log q)=(2^{13},174)$ or $(2^{14},389)$, respectively.

A Noise analysis

The key switching procedure described in Sect. 2.4 is the only source of an extra noise during our conversion algorithms. Recall that the key-switching procedure $\texttt {KeySwitch}(\mathsf {ct}=(c_0,c_1);\mathbf {K})$ introduces the noise $e_{ks}=\langle \mathbf {g}^{-1}(c_1),\mathbf {e}\rangle$ where $\mathbf {e}$ is the noise of the KS key $\mathbf {K}$. We make a heuristic assumption (which has been widely used in HE researches, e.g. [17, 27, 30]) such that a KS noise behaves as if its coefficients are sampled independently from a Gaussian distribution with a fixed variance, which will be denoted by $V_{ks}$. For a random variable $a=\sum _{i \in [N]}a_i\cdot X^i$ over R, we denote by $\mathsf {Var}(a)$ the maximum among the variances of its coefficients $\{\mathsf {Var}(a_i):0\le i<N\}$.

In practice, we need to specify the gadget decomposition method to compute $V_{ks}$. For example, suppose that the ciphertext modulus $q=\prod _{0\le i<d} q_i$ is a product of relatively co-prime integers and the gadget decomposition is defined as $R_q \rightarrow \prod _{i \in [d]} R_{q_i}, a\mapsto \mathbf {g}^{-1}(a)=(a\pmod {q_i})_{0\le i<d}$⁵. Then, the coefficients of $e_{ks}=\langle \mathbf {g}^{-1}(c_1),\mathbf {e}\rangle$ have the common variance $V_{ks}\le \frac{1}{12}N\sigma ^2\cdot \sum _{i \in [d]}q_i^2$ where $\sigma ^2$ is the variance of RLWE error distribution.

1.1 A.1 LWE to LWE

Technically, our LWE-to-LWE conversion includes only one KS procedure between RLWE ciphertexts and then we extract an LWE ciphertext from the output ciphertext. As shown in the correctness proof in Sect. 3.2, the additional noise in the final LWE ciphertext is equal to the constant term of the KS noise, whose variance is $V_{ks}$.

1.2 A.2 LWE to RLWE

We will analyze the noise of homomorphic trace evaluation ($\texttt {EvalTr}_{N/n}$ in Algorithm 1) since the LWE-to-RLWE conversion is a special case where $n=1$.

We showed that if $\mu =b+as \pmod q$ is the phase of the input ciphertext $\mathsf {ct}$, then the phase of $\mathsf {ct}'$ is $\text {Tr}_{K_N/K_{N/2^k}}(\mu )+e_k$ for some error $e_k$ after k iterations. We will estimate the variance of $e_k$ using the induction on k.

If $k=0$, we have $e_0=0$. For $1\le k\le \log (N/n)$, we denote by $e_k'\in R$ the additional noise from the homomorphic automorphism at the k-th iteration. Then, we get $e_{k}=e_{k-1}+\tau _d(e_{k-1})+e_{k}'$ for $d=2^{\log N-k+1}+1$ and its variance is bounded by $\mathsf {Var}(e_k)\le 4\cdot \mathsf {Var}(e_{k-1})+V_{ks}$. Therefore, the noise of the output ciphertext from Algorithm 1 is bounded by $\mathsf {Var}(e_{k})\le (1+4+\dots +4^{k-1})\cdot V_{ks} \le \frac{1}{3}\left( (N/n)^2-1\right) \cdot V_{ks}$.

Our LWE-to-RLWE algorithm is the case of $n=1$ (or equivalently $k=\log N$) which returns a ciphertext whose phase is $\text {Tr}_{K/{\mathbb Q}}(\mu )+e_{\log N}$ for some $e_{\log N}$ such that $\mathsf {Var}(e_{\log N})\le \frac{1}{3}(N^2-1)\cdot V_{ks}$.

1.3 A.3 LWEs to RLWE

We first analyze the noise growth of Algorithm 2. We showed that if $\{\mathsf {ct}_j=(b_j,a_j)\}_{j\in [2^\ell ]}$ are the input RLWE ciphertexts such that $\mu _j=(b_j+a_j\cdot s)[0]$, then the phase $\mu$ of output ciphertext satisfies that $\mu [(N/2^\ell )\cdot j]=2^\ell \cdot \mu _j + e_{\ell , j}\pmod q$ for all $j\in [2^\ell ]$ and for some $e_{\ell ,j} \in {\mathbb Z}$. If $\ell =0$, then there is no extra noise from the packing algorithm. In the case of $\ell >0$, we divide the input ciphertexts into two groups and run the packing algorithm on each subgroup separately. Suppose that the phases of $\mathsf {ct}_{even}$ and $\mathsf {ct}_{odd}$ satisfy

$$\begin{aligned} \mu _{even}[(N/2^{\ell -1})\cdot j]&=2^{\ell -1}\cdot \mu _{2j}+e_{\ell -1,2j} \pmod q, \\ \mu _{odd}[(N/2^{\ell -1})\cdot j]&=2^{\ell -1}\cdot \mu _{2j+1}+e_{\ell -1,2j+1} \pmod q \end{aligned}$$

for some errors $e_{\ell -1,2j}, e_{\ell -1,2j+1}\in {\mathbb Z}$. Let $e_{\ell }'(X)$ be the additional noise from the evaluation of automorphism $\texttt {EvalAuto}(\mathsf {ct}_{even} - X^{N/2^\ell }\cdot \mathsf {ct}_{odd},2^\ell +1)$ and $e_{\ell ,j}'$ the $(N/2^{\ell )})\cdot j$-th coefficient of $e_\ell '(X)$ for $j\in [2^\ell ]$. Then, we get a relation $e_{\ell ,j}=2e_{\ell -1,j}+e_{\ell ,j}'$ between errors from the equation $\mu =\mu _{even}'+X^{N/2^\ell }\cdot \mu _{odd}'+e_{\ell }'(X)$ for all $j\in [2^\ell ]$. Since $e_{\ell ,j}'$ has a fixed variance $V_{ks}$ for all $\ell$ and j, we have $\mathsf {Var}(e_{\ell ,j})=4\cdot \mathsf {Var}(e_{\ell -1,j})+V_{ks}$. Finally, we use the induction on $\ell$ and show that $\mathsf {Var}(e_{\ell ,j})= (1+4+\dots +4^{\ell -1})\cdot V_{ks}=\frac{1}{3}(n^2-1)\cdot V_{ks}$ when $n=2^{\ell }$.

In our LWEs-to-RLWE conversion, the packing algorithm is followed by the trace evaluation $\texttt {EvalTr}_{N/n}$ whose noise growth is analyzed above. Hence, the phase of the output ciphertext from the LWEs-to-RLWE conversion satisfies that $\mu =(N/n)\cdot \left( \sum _{j\in [n]}(n\mu _j + e_{\ell , j}) \cdot X^{(N/n)\cdot j}\right) + e_{k}(X) \pmod q$ where $e_k$ denotes the noise from trace evaluation and $k=\log (N/n)$. Therefore, the variance of total noise $(N/n)\cdot \left( \sum _{j\in [n]}e_{\ell ,j}\cdot X^{(N/n)\cdot j}\right) +e_k(X)$ is bounded by $(N/n)^2 \cdot \mathsf {Var}(e_{\ell ,j}) + \mathsf {Var}(e_k) \le \frac{1}{3} (N^2-1)\cdot V_{ks}$.