# New Secret Keys for Enhanced Performance in (T)FHE

Loris Bergerat, Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, Adeline Roux-Langlois, Samuel Tap

► To cite this version:

Loris Bergerat, Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, Adeline Roux-Langlois, et al. New Secret Keys for Enhanced Performance in (T)FHE. CCS '24: ACM SIGSAC Conference on Computer and Communications Security, Oct 2024, Salt Lake City UT, United States. pp.2547-2561, 10.1145/3658644.3670376. hal-04990120

HAL Id: hal-04990120

https://hal.science/hal-04990120v1

Submitted on 13 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
New Secret Keys for Enhanced Performance in
(T)FHE

Loris Bergerat*¹,², Ilaria Chillotti$\parallel$, Damien Ligier$\parallel$, Jean-Baptiste Orfila†¹, Adeline Roux-Langlois‡², and Samuel Tap§¹

¹Zama, Paris, France - https://zama.ai/

²Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC
14000 Caen, France

Abstract

Fully Homomorphic Encryption has known impressive improvements in the last 15 years, going from a technology long thought to be impossible to an existing family of encryption schemes able to solve a plethora of practical use cases related to the privacy of sensitive information. Recent results mainly focus on improving techniques within the traditionally defined framework of GLWE-based schemes, but the recent CPU implementation improvements are mainly incremental.; To keep improving this technology, one solution is to modify the aforementioned framework, by using slightly different hardness assumptions. In this paper, we identify two limitations with (T)FHE: (i) there is no fine-grained control over the size of a GLWE secret key, which is traditionally composed of $k$ polynomials with $N = 2^\alpha > 1$ coefficients; (ii) for security reasons one cannot use a noise variance smaller than a certain $\sigma_{\min}$ so, for all ciphertext modulus $q \in \mathbb{N}$, there exists an integer $n_{\text{plateau}}$ such that, with any secret key of size $k \cdot N \ge n_{\text{plateau}}$, one cannot control their level of security, resulting in unnecessary big security levels. To overcome the aforementioned limitations, we introduce two new types of secret keys for GLWE-based cryptosystems, that can be used separately or together. We explain why these new secret keys are as secure as the traditional ones and we detail all the improvements that they bring to existing FHE algorithms alongside new algorithms especially efficient with these new keys. We provide many comparisons with state-of-the-art TFHE techniques with traditional secret keys, and some benchmarks showing computational speed-ups between 1.3 and 2.4 while keeping the same level of security and failure probability (correctness). Furthermore, the size of the key switching and bootstrapping keys is also reduced with this contribution by factors ranging from 1.5 to 2.7.

<footnote>This work was done when Ilaria Chillotti and Damien Ligier were working at Zama</footnote>

<footnote>*loris.bergerat@zama.ai</footnote>

<footnote>†jb.orfila@zama.ai</footnote>

<footnote>‡ adeline.roux-langlois@cnrs.fr</footnote>

<footnote>§samuel tap@zama.ai</footnote>
# Contents

<table><tr><td>1 Introduction</td><td>3</td></tr><tr><td>2 Preliminaries</td><td>6</td></tr><tr><td>3 Partial GLWE Secret Key</td><td>9</td></tr><tr><td>3.1 Hardness of Partial GLWE</td><td>10</td></tr><tr><td>3.2 Advantages and applications of Partial GLWE Secret Keys</td><td>13</td></tr><tr><td>3.2.1 Advantage with Sample Extraction</td><td>13</td></tr><tr><td>3.2.2 Advantage with GLWE Key Switch</td><td>15</td></tr><tr><td>3.2.3 Advantage with Secret Product GLWE Key Switch</td><td>16</td></tr><tr><td>3.2.4 Advantage with External Product</td><td>17</td></tr><tr><td>3.2.5 LWE-to-LWE Key Switch</td><td>17</td></tr><tr><td>4 Shared Randomness Secret Keys</td><td>18</td></tr><tr><td>4.1 Hardness of Shared Randomness Secret Keys</td><td>19</td></tr><tr><td>4.2 Advantages of Shared Randomness Secret Keys</td><td>21</td></tr><tr><td>4.2.1 Advantages with LWE-to-LWE Key Switch</td><td>21</td></tr><tr><td>4.2.2 Stair Key Switch</td><td>23</td></tr><tr><td>5 Combining Both Techniques &amp; Their Applications</td><td>25</td></tr><tr><td>5.1 Combining Both Techniques</td><td>25</td></tr><tr><td>5.2 Some Higher Level Applications</td><td>27</td></tr><tr><td>6 Parameters &amp; Benchmarks</td><td>28</td></tr><tr><td>6.1 Partial GLWE Secret Key</td><td>28</td></tr><tr><td>6.2 Shared Randomness Secret Keys</td><td>29</td></tr><tr><td>6.3 Combining Both</td><td>30</td></tr><tr><td>7 Conclusion</td><td>30</td></tr><tr><td>A Comparison between usual secret key types in FHE</td><td>36</td></tr><tr><td>B Proofs</td><td>36</td></tr><tr><td>C Algorithms From Literature</td><td>46</td></tr><tr><td>D Algorithms in Details</td><td>47</td></tr><tr><td>E Parameter Sets</td><td>47</td></tr><tr><td>E.1 Size of Public Material</td><td>47</td></tr><tr><td>E.2 Parameter Sets</td><td>47</td></tr></table>
# 1 Introduction

Fully homomorphic encryption (FHE) is a technology allowing to perform computations over encrypted data, which makes it a great solution for many practical use cases aiming to protect the privacy of sensitive information. After the first solution proposed in 2009 by Gentry [Gen09], the field has received a significant amount of interest and has experienced a drastic improvement in the following decade. Gentry introduced a technique called bootstrapping, able to reduce the noise inside ciphertexts. Indeed, ciphertexts contain noise for security reasons, and most of the time, when an homomorphic operation is performed, the noise level grows. If not controlled, too much noise will eventually compromise the message.

Nowadays, practical FHE schemes are all inspired by Gentry's solution and are based on the Learning With Errors (LWE) problem [Reg05], its Ring variants (RLWE) [SSTX09, LPR10] and the General approach (GLWE also called Module LWE) [LS15, BGV12]. One of these schemes is called TFHE [CGGI20], and will be the focus of this paper. Most of the existing FHE schemes, for example BGV [BGV12], BFV [Bra12, FV12], and CKKS [CKKS17], prefer to avoid using bootstrapping and adopt a levelled approach. On the contrary, TFHE features a particularly efficient bootstrapping which is used to reduce the noise and can homomorphically evaluate an univariate function represented as a look-up table (LUT) on small messages. This operation is often referred to as functional bootstrapping or programmable bootstrapping (PBS). For efficiency reasons, the bootstrapping is paired with a keyswitch operation. In general, a keyswitch is an homomorphic operation which transforms an encryption under the secret key $s^{(1)}$ to an encryption of the same value under the secret key $s^{(0)}$. When the keyswitch is applied before the PBS, it reduces the dimension of the secret key, and thus the dimension of the input ciphertext for the PBS. A smaller secret key implies less operations during the bootstrapping which results in a faster computational time and a better noise reduction. Although it seems counterintuitive, performing a keyswitch (which is a costly operation) followed by a PBS remains less expensive than performing a PBS alone (as studied [BBB$^{+}$22]). The cost and the correctness of these operations are directly linked to the parameter sets, and changing one of them has a huge impact.

Even if the most recent results on FHE schemes show a huge improvement of this technology, for the last few years the scientific improvements observed are mainly incremental. Larger factors of improvement have been obtained for instance by using dedicated hardware, but on CPU only small factors are observed. Even if small, every little factor is extremely important, because a combination of small factors can lead to a significant improvement. But the ideas start exhausting if we only consider approaches that are traditionally for GLWE-based schemes. Thinking outside of the box might be beneficial at this point, and some alternative ideas need to be considered. An interesting approach in this direction is the new FHE scheme proposed in the FINAL paper [BIP$^{+}$22], which is very similar to TFHE. The hardness of this scheme relies on a combination between LWE and NTRU [HPS98]. This solution is very efficient for very small precisions of messages (one or two bits),
but it becomes very inefficient compared to TFHE for larger precisions, due to the security constraints imposed by the NTRU parameters.

An alternative approach, within the GLWE framework, would be to use slightly different hardness assumptions. In this paper, we explore this direction.

**TFHE's Plateau** TFHE, as many other RLWE based schemes, works with a cyclotomic ring $R_{q,N} = \mathbb{Z}_q[X] / \langle X^N + 1 \rangle$, with $N$ a power of 2. In TFHE's implementations, $q$ is often chosen equal to $2^{32}$ or $2^{64}$, in order to be able to work with 32 or 64 bit integers, respectively, since they are native types in the majority of machines used nowadays. The polynomial size $N$ strongly depends on the precision of the messages that we want to bootstrap. $N$ generally belongs in $[2^9, 2^{10}, \dots, 2^{16}]$ for 1 to 10 bits of precision. Roughly, the rule is to double its size for every additional bit of precision. The GLWE ciphertexts, which are a generalization of RLWE and LWE ciphertexts, use secret keys that are composed of $k$ polynomials in $R_{q,N}$. So the size of the secret key is $n = kN$, which is the parameter that is used for the security estimates. In order to keep the same security level when increasing $n$, we can reduce the variance $\sigma^2$ of the noise. But the value of $q$ imposes a lower bound on the variance, meaning that starting from a certain point - that we call *plateau* - we can not reduce the variance anymore, otherwise we lose security. Notice that a small increase of the value of $n$ allows for a small decrease of the value of $\sigma^2$. But when working with polynomials, moving to a bigger power of 2 for $N$ will lead to a large increase of the size of the secret key, from $kN$ to $k \cdot 2N$, and so a large decrease of $\sigma^2$ when allowed. For the same security reason mentioned above, at some point we reach a limit where we cannot reduce the variance $\sigma^2$ of the noise anymore. The consequence is that to avoid having no security at all, we end up with a security level way higher than desired. In this paper, we explore a new type of secret key that overcomes this existing limitation and improve the efficiency of most homomorphic computations.

**Our Contributions.** In this paper, we explore a new type of secret key that takes advantages of this plateau to improve the efficiency of most homomorphic computations. As a consequence, we reduce the size of public keys and the cost of some homomorphic algorithms. Furthermore, we present a theoretical analysis which provides arguments to understand the security of our new types of secret keys and allow us to pick secure parameters. We also provide benchmarks using parameters secure against known attacks.

In detail, we propose two new types of secret keys that we describe separately but can be used together. We call these two new distributions *partial secret keys* and *shared randomness secret keys*. The first kind, the partial secret keys, consists in allowing a GLWE secret key, traditionally containing $kN$ random elements (sampled from a distribution $\mathcal{D}$), to contain only $\phi$ random elements and set the rest to zeros. Intuitively, it allows using a smaller key of size $\phi$ while keeping a larger $N$, and the underlying security of the GLWE assumption is now relying on the parameter $\phi$ instead of the dimension $N$.
The second kind, the shared randomness secret keys, consists in reusing the
randomness from a bigger key (for example the input key of the keyswitch algorithm)
inside a smaller key (its output), instead of generating it independently as done
traditionally. For instance, we can consider two integers $1 < n_0 < n_1$ and a secret
key $\mathbf{s}^{(1)} \in \mathbb{Z}_q^{n_1}$ generated in the traditional manner (either sampled from an uniform
binary/ternary, or a small Gaussian). Let us write it as a concatenation of two
vectors: $\mathbf{s}^{(1)} = \mathbf{r}^{(0)} || \mathbf{r}^{(1)}$. We can now build a smaller secret keys out of $\mathbf{s}^{(1)}$ such
that the smaller one will be included in the bigger one, in its first coefficients:
$\mathbf{s}^{(0)} = \mathbf{r}^{(0)} \in \mathbb{Z}_q^{n_0}$ and $\mathbf{s}^{(1)} = \mathbf{r}^{(0)} || \mathbf{r}^{(1)} \in \mathbb{Z}_q^{n_1}$. The question is then to study if the
link between the two keys will impact the security.

Our two contributions reduce the size of the secret key, and then has a huge
impact in the size of public keys, including key-switching keys and bootstrapping
keys. It also has an impact on the operations on which these keys are used, i.e.,
keyswitching and bootstrapping. Key-switching keys and bootstrapping keys are in
practice encryptions of the elements of the secret key, and they are used inside some
linear combinations: roughly speaking, if a part of the key is set to zero or duplicated,
this part is not used inside the linear combination, with the direct consequence of
improving the overall operation in terms of computational cost and noise growth.

**Practical Speed-up from our Contributions.** One way to use TFHE in practice is to consider a graph of homomorphic operations over ciphertexts composed for example of key switchings, programmable bootstrapping (PBS) or linear combination of ciphertexts. This recipe was indeed used in the gate bootstrapping [CGGI20] technique to homomorphically evaluate any Boolean circuit, but it can also be used for message precision bigger than a single bit [CJP21]. As explained in [BBB+22], an efficient way to optimize parameters for this use-case is to consider the smallest sequence of FHE operators, composed for example of a ciphertext linear combination followed by a keyswitch and followed by a PBS. This sequence (introduced in [CJP21]), has been formalized as the notion of CJP Atomic Pattern (denoted CJP in what follows) in [BBB+22]). This optimization strategy consider both the cost and the noise growth for all the homomorphic operators involved in the sequence at once to infer efficient parameters. This means that if one improves an operator by reducing its noise growth and/or reducing its cost, the overall cost of the sequence will be decreased. As explained above, in this paper we improve both the cost and the noise growth of the keyswitch operator and we also improve the noise growth of the PBS, resulting in a big improvement in terms of cost and size of the needed public material. These results are confirmed by practical experiments, showing a speed up between 1.3 and 2.4 times, while keeping the same level of security and failure probability. Furthermore, the use of these new key types allows to reduce the size of the public material (i.e., key switching and bootstrapping keys) by a factor between 1.5 and 2.7. We share benchmarks comparing the running time needed with and without the new secret keys. Our simulations are done with the optimization tool proposed in [BBB+22] and show that the use of these new secret keys improve the state of the art for all message precisions.
**Related Works.** To the best of our knowledge, there are no mentions of such GLWE secret keys or something similar in the prior art. The closest work we can mention is by Lee and Yoon [LY23] where the server can publicly transform a bootstrapping key encrypted under a traditional secret key to an extended version encrypted under a secret key containing zeros between each secret coefficients. This extended bootstrapping key allows the authors to bootstrap messages with bigger precision, but it does not improve the noise growth. All this contribution only involves traditional GLWE secret keys for encryption. In some of the proofs, we use the morphism introduced in [LNPS21, LY23].

**Concurrent Works.** Lee et al. [LMSS23] introduced new types of secret keys. They call it *block binary keys*, which are different from our contribution but concurrently exploit the advantage of having nested secret keys, re-using their randomness, as we also introduce in this paper as *shared randomness secret keys*.

**Paper Organization.** In Section 2, we recall some mathematical definition along with FHE notations and security notions. In Section 3, we introduce and study the security of *partial GLWE secret keys* as well as all the FHE algorithms that benefit from them either in terms of noise growth or in terms of cost. Section 4 follows the same pattern, but it is dedicated to *shared randomness secret keys*. In Section 5, we detail how to take advantage of combining both partial and shared randomness secret keys, and along with some applications. In Section 6, we focus on the gains of using these techniques by comparing them to the state of the art. Finally, in Section 7, we conclude and introduce potential future work.

# 2 Preliminaries

In this section we clarify the notations we will use in this paper and introduce the notions needed to understand our contributions.

**Notations.** Let $q$ be a positive integer and $N$ be a power of 2. In this paper we mostly work with the rings $\mathbb{Z}_q$ (which refers to $\mathbb{Z}/q\mathbb{Z}$) and $R_{q,N} = \mathbb{Z}_q[X] / \langle X^N + 1 \rangle$. For error distributions, we note $\chi$ for a generic distribution and $N_{\sigma^2}$ for a Gaussian distribution with a mean set to zero and a standard deviation set to $\sigma$. We note by $\mathcal{U}(S)$ a uniform distribution in the generic set $S$ and by $\mathcal{D}(S)$ a generic probability distribution in the generic set $S$. We use the symbol $||$ for vector concatenation. Upper cases (e.g. $M, A, S, B, E$) designate polynomials and lower cases (e.g., $m, a, s, b, e$) scalars. We use bold characters to note vectors of polynomials (e.g., $\mathbf{A}, \mathbf{S}$) and vectors of coefficients (e.g. $\mathbf{a}, \mathbf{s}$). When we write $\mathrm{Var}(\mathbf{S})$ (resp. $\mathbb{E}(\mathbf{S}))$, we refer to the variance (resp. the expectation) of $\mathcal{D}$ (either a uniform binary distribution, uniform ternary distribution, Gaussian distribution or small uniform distribution). When $\mathcal{D}$ is a uniform binary distribution, $\mathrm{Var}(\mathbf{S}) = 1/4$ and $\mathbb{E}(\mathbf{S}) = 1/2$.
**Definition 1 (General Learning With Errors (GLWE) Decision Problem)**

Let $\mathbf{S} = (S_0, \dots, S_{k-1}) \in \mathbb{R}_{q,N}^k$ be a secret, where $S_i = \sum_{j=0}^{N-1} s_{i,j} X^j$ is sampled from a given distribution $\mathcal{D}(R_{q,N})$ for all $0 \le i < k$, and let $\chi$ be an error distribution. We define $(\mathbf{A}, \mathbf{B} = \sum_{i=0}^k A_i \cdot S_i + E) \in \mathbb{R}_{q,N}^{k+1}$ to be a sample from the general learning with errors (GLWE$_{N,k,\chi}$) distribution, such that $\mathbf{A} = (A_0, \dots, A_{k-1}) \leftarrow \mathcal{U}(R_{q,N})^k$, meaning that all the coefficients of $A_i$ are sampled uniformly from $\mathbb{Z}_q$, and the error (noise) polynomial $E \in \mathbb{R}_{q,N}$ is such that all the coefficients are sampled from $\chi$.

The decisional GLWE$_{N,k,\chi}$ problem [LS15, BGV12] consists in distinguishing $m$ independent samples from $\mathcal{U}(R_{q,N})^{k+1}$ from the same amount of samples from GLWE$_{N,k,\chi}$, where $\mathbf{S} \in \mathbb{R}_{q,N}^k$ follows a given distribution $\mathcal{D}$.

In general, the secret key distribution $\mathcal{D}(R_{q,N})$ is such that the polynomial coefficients are usually either sampled from a uniform binary distribution, a uniform ternary distribution or a Gaussian distribution ([BJRLW23, ACPS09]). Starting from the GLWE problem, we can define GLWE ciphertexts.

**Definition 2 (GLWE Ciphertexts)** A GLWE ciphertext of a plaintext $M \in \mathbb{R}_{q,N}$ under the secret key $\mathbf{S} \in \mathbb{R}_{q,N}^k$ is defined as follows:

$$ \text{CT} = \left( \mathbf{A}, \mathbf{B} = \sum_{i=0}^{k-1} A_i \cdot S_i + M + E \right) \in \text{GLWE}_{\mathbf{S}}(M) \subseteq \mathbb{R}_{q,N}^{k+1} $$

such that $\mathbf{A} = (A_0, \dots, A_{k-1}) \leftarrow \mathcal{U}(R_{q,N})^k$ and $E \in \mathbb{R}_{q,N}$ is such that all its coefficients are sampled from a gaussian distribution $\mathcal{N}_{\sigma^2}$.

**Remark 1 (LWE and RLWE)** We recall that, when $N = 1$, the GLWE problem (resp. ciphertext) becomes the LWE problem (resp. ciphertext): $\text{GLWE}_{1,k,\chi} = \text{LWE}_{n=k,\chi}$. In this case we consider the parameter $n = k$ to be the size of the LWE secret key and we denote the ciphertext, the message and the secret with a lower case: $\text{ct} \in \text{LWE}_{\mathbf{s}}(m)$. When $k = 1$, the GLWE problem (resp. ciphertext) becomes the RLWE problem (resp. ciphertext): $\text{GLWE}_{N,1,\chi} = \text{RLWE}_{N,\chi}$. In this case, since we are still working with polynomials, we keep upper cases for ciphertexts, messages and secret key: $\text{CT} \in \text{RLWE}_{\mathbf{s}}(M)$.

**Definition 3 (Flattened Representation of a GLWE Secret Key)** A

$\text{GLWE secret key S} = (S_0 = \sum_{j=0}^{N-1} s_{0,j} X^j, \dots, S_{k-1} = \sum_{j=0}^{N-1} s_{k-1,j} X^j) \in \mathbb{R}_{q,N}^k$ can be flattened into an LWE secret key $\bar{\mathbf{s}} = (\bar{s}_0, \dots, \bar{s}_{kN-1}) \in \mathbb{Z}^{kN}$ in the following manner: $\bar{s}_{iN+j} := s_{i,j}$, for $0 \le i < k$ and $0 \le j < N$.

In TFHE, apart from LWE, RLWE and GLWE ciphertexts, there are two additional constructions that are used, that are called GLev [CLOT21] and GGSW [GSW13]. A GLev ciphertext is a collection of GLWE ciphertexts, while a GGSW is a collection of GLev ciphertexts. In the same way as GLWE can be specialized as LWE and as RLWE ciphertext, GLev and GGSW can be specialized as Lev and GSW respectively, and as RLev and RGSW. We give the general definition below.
**Definition 4 (GLev Ciphertexts [CLOT21])** Given a decomposition base $\beta \in \mathbb{N}^*$ and a decomposition level $\ell \in \mathbb{N}^*$, a GLev ciphertext of a plaintext $M \in R_{q,N}$ under a GLWE secret key $\mathbf{S} \in R_{q,N}^k$ is defined as follows:

$$ \overline{CT} = (CT_0, \dots, CT_{\ell-1}) \in \text{GLEV}_{\mathbf{S}}^{(\beta, \ell)}(M) \subseteq R_{q,N}^{\ell \times (k+1)} \\ \text{such that } CT_j \in \text{GLWE}_{\mathbf{S}}\left(\frac{q}{\beta^{j+1}}M\right) \subseteq R_{q,N}^{k+1} \text{ for } 0 \le j < \ell. $$

**Definition 5 (GGSW Ciphertexts [GSW13, CLOT21])** Given a decomposition base $\beta \in \mathbb{N}^*$ and a decomposition level $\ell \in \mathbb{N}^*$, a GGSW ciphertext of a plaintext $M \in R_{q,N}$ under a GLWE secret key $\mathbf{S} \in R_{q,N}^k$ (with $S_k = -1$) is defined as follows:

$$ \overline{CT} = (\overline{CT}_0, \dots, \overline{CT}_k) \in \text{GGSW}_{\mathbf{S}}^{(\beta, \ell)}(M) \subseteq R_{q,N}^{(k+1) \times \ell \times (k+1)} \\ \text{such that } \overline{CT}_i \in \text{GLEV}_{\mathbf{S}}^{(\beta, \ell)}(-S_i \cdot M) \subseteq R_{q,N}^{\ell \times (k+1)} \text{ for } 0 \le i \le k. $$

**Programmable Bootstrapping (PBS).** We call Programmable Bootstrapping [CGGI20, CJL$^+$20, CJP21], or PBS, any FHE operator that enables to reset the noise in a ciphertext to a fixed level (when certain conditions are fulfilled) and to evaluate, at the same time, a lookup-table homomorphically on the encrypted message. Such an operator takes as input an LWE ciphertext encrypting a message $m$, a bootstrapping key BSK (i.e., a list of GGSW ciphertexts encrypting the elements of the secret key used to encrypt the message $m$), an encryption of a lookup table $L$, and outputs an LWE ciphertext with a fixed level of noise encrypting the message $L[m]$ with a probability $1 - p_{\text{fail}}$.

**Remark 2 (FFT Error)** Polynomial multiplications in the PBS are performed with an FFT. While very efficient, this introduces a noise due to the casting of the bootstrapping key (64-bit integers) into floating points (double with 53-bits mantissa) and the accumulation of the error along the computation in the Fourier domain. We use the corrective formula from [BBB$^+$22] to model this noise which is added to the one from the external product.

$$ \text{FftError}_{k,N,\beta,\ell} = 2^{\omega_1} \cdot \ell \cdot \beta^2 \cdot N^2 \cdot (k+1) $$

with $\omega_1 \approx 22 - 2.6$, the GLWE dimension $k$, the polynomial size $N$ and the decomposition parameters $(\beta, \ell)$.

**Attacks on LWE.** We quickly recall some known attacks against LWE which are important to consider in the selection of secure parameters. These attacks are the ones used in the lattice estimator [APS15]. This tool is used$^1$ to find out the smallest noise variance $\sigma^2$ guarantying the desired level of security $\lambda$.

<footnote>$^1$https://github.com/zama-ai/concrete/tree/main/tools/parameter-curves</footnote>
The first well known kind of attacks is the so called LWE primal attacks. This attack was first formulated in [ADPS16] and improved in [AGVW17, DSDGR20, PV21]. It consists in using lattice reduction to solve an instance of uSVP (unique Shortest Vector Problem) generated from LWE samples. The most common way to perform this reduction is to use the BKZ algorithm [SE94] to reduce a lattice basis by using an SVP (Shortest Vector Problem) oracle. So, based on this attack, the security of an LWE instance is based on the cost of lattice reduction for solving uSVP. In the paper [ADPS16], the authors propose to analyze the hardness of RLWE as an LWE problem. All the research on this attack tend to find the best cost of solving uSVP in order to find the closest model of security for LWE and by extension for RLWE.

The second type of attack is the LWE dual attacks. This attack is explained in [MR09] and upgraded with the dual hybrid attacks in [Alb17]. It consists in solving an instance of the SIS (Short Integer Solution) problem in the dual lattice of the lattice formed by LWE samples. As for the first type of attacks, the security of an LWE instance is based on the cost of solving the problem SIS.

The third well known kind of attacks is the coded-BKW attacks, which are based on the algorithm BKW (Blum, Kalai and Wasserman [BKW03]). This attack is explained in [GJS15, KF15]. The BKW algorithm is a recursive dimension reduction for LWE instances. In [GJS15], the authors make use of these attacks against RLWE. To do that, the RLWE problem is seen as a sub problem of LWE.

**Attacks on RLWE/GLWE.** In the last decade, some attacks (for example [CDW17, PMHS19, BRL20, BLNRL23]) tried to take advantage of the structure of RLWE and GLWE to solve the id-SVP (ideal-Shortest Vector Problem). However, none of these attacks is as efficient as the LWE attacks presented before. Thus, to efficiently break GLWE, one actually uses LWE attacks: the security of GLWE ∈ $R_{N,q}^{k+1}$ is then estimated as the LWE ∈ $\mathbb{Z}_q^{kN+1}$ one.

**Other Attacks.** Some other attacks are not based on a reduction to a classical problem but on the leakage of some fraction of the coordinates of the NTT transform of the RLWE secret. It is the case of the article [DSGKS18] which proposes a more direct attack against RLWE under this leakage assumption.

## 3 Partial GLWE Secret Key

As presented in the introduction, the partial GLWE secret key is composed of two parts, the first one contains secret random elements (sampled from a distribution $\mathcal{D}$) and the second part is filled with zeros at known positions. As a simple example, we can define the following partial GLWE secret key: $\mathbf{S} = (S_0, S_1) \in \mathbb{Z}_{q,N}^2$ with $S_0 = \sum_{j=0}^{N-1} s_{0,j}X^j$ and $S_1 = \sum_{j=0}^{N/2-1} s_{1,j}X^j$ where $s_{0,0}, \cdots, s_{0,N-1}$ and $s_{1,0}, \cdots, s_{1, \frac{N}{2}-1}$ are sampled from $\mathcal{D}$, and the other coefficients are publicly known to be set to zero. We recall the two limitations of TFHE (already mentioned in Section 1):
1. There is no fine-grained control over the size of a GLWE secret key, it is of the form $kN$ with $N$ a power of two;

2. When one increases $n$ (or $kN$), a plateau in terms of noise variance is reached. Concretely, $n_{\text{plateau}}$ is the first value of this plateau i.e., for larger value of $n$, the minimal standard deviation of the noise is constant. We evaluated its value to be 2443 for 128 bits of security and $q = 2^{64}$ by using the formula for the noise oracle of [BBB$^{+}$22].

Thanks to these new types of secret keys, these limitations are overcome. These new keys are beneficial to the noise growth during some operations (for instance, the external product) over RLWE and GLWE ciphertexts. As the bootstrapping is a chain of external products, partial secret keys will also be beneficial to its noise growth. After the sample extract, we can discard the mask elements associated with the positions of the zeros ending up with smaller LWE dimension than with a traditional secret key. This smaller LWE dimension will likely improve the cost of the next key switch.

In this section, we first formally define the notion of partial secret key, and then study the hardness of the underlying problem. Finally, we list the different advantages and improvements which they offer.

**Definition 6 (GLWE Partial Secret Key)** A Partial GLWE secret key is a vector $\mathbf{S}^{[\phi]} \in \mathbb{R}_{q,N}^k$ associated with its filling amount $\phi$ such that $0 \le \phi \le kN$. This key will have $\phi$ random coefficients sampled from a distribution $\mathcal{D}$ and $kN - \phi$ known zeros. Both the locations of the random elements and the zeros are public. By convention, the coefficients start at coefficient $s_{0,0}$, then $s_{0,1}$ and so on. When the first polynomial is entirely filled, the second polynomial starts with $s_{1,0}$ and so on, until $\phi$ coefficients are determined, up to $s_{k-1,N-1}$.

We now define the flattened representation.

**Definition 7 (Flattened Representation of a Partial GLWE Secret Key)**

A partial GLWE secret key $\mathbf{S}^{[\phi]} = (S_0 = \sum_{j=0}^{N-1} s_{0,j} X^j, \dots, S_{k-1} = \sum_{j=0}^{N-1} s_{k-1,j} X^j) \in \mathbb{R}_{q,N}^k$ (Definition 6) can be viewed as a flattened LWE secret key $\bar{\mathbf{s}} = (\bar{s}_0, \dots, \bar{s}_{\phi-1}) \in \mathbb{Z}^{\phi}$ in the following manner: $\bar{s}_{iN+j} := s_{i,j}$, for $0 \le j < N$ and $0 \le i < k$ with $iN + j < \phi$. This flattened representation contains only $\phi$ unknown coefficients.

Before checking the security in detail, this type of keys seem to be a secure solution, taking into account the plateau limitation (Limitation 2).

## 3.1 Hardness of Partial GLWE

The GLWE partial secret key problem $\mathbf{S}^{[\phi]} \in \mathbb{R}_{q,N}^k$ from Definition 6, seems to be at least as hard as a GLWE problem in a ring of dimension $\phi$. First, we present the GLWE alternate partial secret key, a key where the secret elements are separated by $2^{\nu} - 1$ known zeros. We prove the security of such secret key distribution by proving that the GLWE problem in $\mathbb{R}_{q,N/2^{\nu}}^{k+1}$ is equivalent to the GLWE problem in $\mathbb{R}_{q,N}^{k+1}$ instantiated with alternate partial GLWE secret keys.
**Definition 8 (Alternate Partial GLWE Secret Key)** An alternate partial GLWE ($\text{P-GLWE}_{N,k,\chi}$) secret, is a GLWE secret where the key alternates between one unknown element and $2^{\nu} - 1$ known elements. This key has of $\frac{N}{2^{\nu}}$ random coefficients sampled from a distribution $\mathcal{D}$ and $N - \frac{N}{2^{\nu}}$ known zero coefficients. As for the partial GLWE secret key (Definition 6), both the locations of the random elements and the known zeros are public. The binary version of partial secret keys in $R_{q,N}$ is defined by $S = \sum_{k=0}^{N/2^{\nu}-1} s_k \cdot X^{k \cdot 2^{\nu}}$, with $s_i \leftarrow \mathcal{U}(\{0,1\})$.

The Theorem 1 shows that the alternate partial GLWE problem (Def. 8) on the ring $R_{q,N}$ is at least as hard as the GLWE problem on the ring $R_{q,N/2^{\nu}}$.

**Theorem 1 (Hardness of P-GLWE)** For any $\nu \in \mathbb{Z}$, the $\text{P-GLWE}_{N,k,\chi}$ sample in $R_{q,N}^{k+1}$ is as least as hard as $2^{\nu} \text{GLWE}_{N/2^{\nu},k,\chi}$ samples in $R_{q,N/2^{\nu}}^{k+1}$.

**Proof 1 (Theorem 1)** The idea of this proof is to pack $2^{\nu}$ $\text{GLWE}_{N/2^{\nu},k,\chi}$ samples in one $\text{P-GLWE}_{N,k,\chi}$ sample. To do so, we differentiate the $2^{\nu}$ samples from $\text{GLWE}_{N/2^{\nu},k,\chi}$ in $R_{N/2^{\nu},q}^{k+1}$, by noting them $\text{GLWE}_{\mathcal{S}(X)}^w$ with $w \in [0, 2^{\nu}]$. Observe that all of them are encrypted under the same secret key $\mathcal{S} = (S_0, \dots, S_{k-1}) \in R_{q,N/2^{\nu}}^k$, with $S_i = \sum_{j=0}^{N/2^{\nu}-1} s_{i,j} X^j$, with $i \in [0, k]$.

Each one of the $k$ polynomials composing the $\text{GLWE}_{\mathcal{S}(X)}^w$ sample is noted with an exponent $w$: $A_i^w = \sum_{j=0}^{N/2^{\nu}-1} a_{i,j}^w X^j$, with $i \in [0, k]$. Starting from these $2^{\nu}$ samples, we define a new sample from $\text{P-GLWE}_{N,k,\chi}$. First, for each sample $\text{GLWE}_{\mathcal{S}(X)}^w \in R_{q,N/2^{\nu}}^{k+1}$, we need to evaluate each polynomial in $X^\nu$:

$$R_{q,N/2^{\nu}} \to R_{q,N}, \\ A_i^w(X) = \sum_{j=0}^{N/2^{\nu}-1} a_{i,j}^w \cdot X^j \mapsto A_i^w(X^{2^{\nu}}) = \sum_{j=0}^{N/2^{\nu}-1} a_{i,j}^w \cdot X^{j \cdot 2^{\nu}}.$$

So, for each sample $\text{GLWE}_{\mathcal{S}(X)}^w$ in $R_{q,N/2^{\nu}}^{k+1}$, we obtain a new sample $\widetilde{\text{GLWE}}_{\mathcal{S}(X^{2^{\nu}})}^w$ in $R_{q,N/2}^{k+1}$. We notice that for each polynomial, each coefficient is separated from the other by $2^{\nu} - 1$ zeros. Following the previous definition of P-GLWE (Definition 8), the secret key is in the desired shape. But the $A_i^w(X^{2^{\nu}})$ polynomials are not uniform anymore, only the coefficients of degree multiple of $2^{\nu}$ are. So we can't already define $\widetilde{\text{GLWE}}_{\mathcal{S}(X^{2^{\nu}})}^w$ as a sample of $\text{P-GLWE}_{N,k,\chi}$. For each $\widetilde{\text{GLWE}}_{\mathcal{S}(X^{2^{\nu}})}^w$ we now rotate all the $A_i^w$ and the $B^w$ polynomials by $X^w$: We now sum all of them together to obtain the expected sample from $\text{P-GLWE}_{N,k,\chi} \in \mathbb{R}_{q,N}^{k+1}$:

$$\sum_{w=0}^{2^{\nu}-1} (A_0^w(X^{2^{\nu}})X^w, \dots, A_{k-1}^w(X^{2^{\nu}})X^w, B^w(X^{2^{\nu}})X^w) \\ = (A_0, \dots, A_{k-1}, B) \in \text{P-GLWE}_{N,k,\chi}$$
with:

$$S_i = \sum_{j=0}^{N/2^{\nu}-1} s_{i,j} \cdot X^{j \cdot 2^{\nu}} = \sum_{j=0}^{N-1} \tilde{s}_{i,j} \cdot X^j \quad \text{for } i \in [0, k]$$

$$A_i = \sum_{w=0}^{2^{\nu}-1} A_i^w(X^{2^{\nu}})X^w = \sum_{w=0}^{2^{\nu}-1} \sum_{j=0}^{N/2^{\nu}-1} a_{i,j}^w X^{j \cdot 2^{\nu}+w} = \sum_{j=0}^{N-1} \tilde{a}_{i,j} X^j \quad \text{for } i \in [0, k]$$

$$B = \sum_{w=0}^{2^{\nu}-1} B^w(X^{2^{\nu}})X^w = \sum_{w=0}^{2^{\nu}-1} \sum_{j=0}^{N/2^{\nu}-1} b_j^w X^{j \cdot 2^{\nu}+w} = \sum_{j=0}^{N-1} \tilde{b}_j X^j$$

Lets focus on how $b_j^w$ evolve all along the reduction:

$$b_j^w = \sum_{i=0}^{k-1} \left( \sum_{\tau=0}^{j} a_{i,\tau}^w \cdot s_{i,j-\tau} - \sum_{\tau=j+1}^{N/2^{\nu}-1} a_{i,\tau}^w \cdot s_{i,N+\tau} \right) + e_j^w \\ = \sum_{i=0}^{k-1} \left( \sum_{\tau=0}^{j2^{\nu}+w} \tilde{a}_{i,\tau} \cdot \tilde{s}_{i,j2^{\nu}+w-\tau} - \sum_{\tau=j2^{\nu}+w+1}^{N-1} \tilde{a}_{i,\tau} \cdot \tilde{s}_{i,2^{\nu}(N+j)+w-\tau} \right) + \tilde{e}_{j2^{\nu}+w} = \tilde{b}_{j2^{\nu}+w}$$

Each coefficient is correctly decrypted and each $\tilde{b}_{j2^{\nu}+w}$ is equal to $b_j^w$. Moreover, the polynomials $A_i$ of the new P-GLWE$_{N,k,\chi}$ sample follows the same distribution as the polynomials $A_i^w$, we can make the same remark for the polynomial B. To conclude, we have packed several GLWE$_{N/2^{\nu},k,\chi}$ ciphertext in one P-GLWE$_{N,k,\chi}$ ciphertext by increasing the dimension of this new ciphertext without changing the noise distribution $\chi$.

**Remark 3 (Security of Partial Secret Key)** The reduction presented in Theorem 1 proves that the partial alternate secret keys (Definition 8) problem in $R_{q,N}^k$ is at least as hard as a GLWE problem in $R_{q,N/2^{\nu}}^k$, i.e., when $\phi = N/2^{\nu}$. So adding zeros at specific places in the secret key and increasing the dimension from $N/2^{\nu}$ to $N$ allows keeping the same security level. We assume this result is generalizable to any $\phi < N$.

Now, if we take two GLWE samples such that the first one is encrypted under an alternate partial key (Definition 8) and the second one is encrypted under a secret partial key (Definition 6) which have the same amount of unknown coefficients, this two samples should be indistinguishable.

We recall that in LWE samples, the security depends on the dimension and the noise (increasing one could allow to reduce the other one). Intuitively, the security of GLWE samples, encrypted under a partial key with $\phi$ random elements, is linked to the relation of $\phi$ and the noise $\sigma$ (instead of $N$ and $\sigma$). A bigger $\phi$ will lead to a smaller noise $\sigma$. To sum up, to guarantee a given level of security for GLWE samples encrypted under a partial secret key with $\phi$ random elements, we use the noise parameter given for LWE samples of dimension $n = \phi$ with the same level of security.
**Impact of Partial Key on the Noise Distribution.** Regarding the security of the partial secret key and the different attacks presented in Section 2, we can use the lattice estimator to find out the smallest noise variance $\sigma^2$ for an LWE $\in \mathbb{Z}_q^{\phi+1}$ guarantying the desired level of security $\lambda$. By using this same $\sigma^2$ for GLWE $\in R_{q,N}^{k+1}$ with partial secret key $S^{[\phi]}$ we obtain the same level of security $\lambda$. For instance, for RLWE in the ring $R_1 = R_{q=2^{64},N=1024}$ (resp. $R_2 = R_{q=2^{64},N=2048}$) with traditional uniform binary secret key $S_1 \in R_1$ (resp. $S_2 \in R_2$), we use a standard deviation $\sigma_1 = 2^{39.6}$ (resp. $\sigma_2 = 2^{12.6}$) which gives a security $\lambda_1 = 128.2$ (resp. $\lambda_2 = 128.0$) according to the lattice estimator. For our partial keys with the ring $R_2$, we now can mix the two previous contexts and keep the standard deviation of the smaller ring $R_1$. Indeed, with the ring $R_2 = R_{q=2^{64},N=2048}$ and a partial uniform binary secret key RLWE $S \in R_2$ with only 1024 secret coefficients, we will use a standard deviation $\sigma_1 = 2^{39.6}$ (from ring $R_1$) and this will offer at least 128 bits of security as well.

## 3.2 Advantages and applications of Partial GLWE Secret Keys

Partial GLWE secret keys enable to reduce the computational cost and/or the noise growth for some algorithms. For a given failure probability and security level, the parameter sets obtained after optimization will lead to better timings for the functionality (more details in Section 6). Moreover, partial GLWE secret keys can be used to design a new and more efficient LWE-to-LWE key switching that is FFT-based (Algorithm 1). The idea is an adaptation of [CDKS20] but now exploits the use of partial GLWE secret keys. First we cast the input LWE ciphertext into a GLWE ciphertext (Algorithm 3) so we can apply a GLWE-to-GLWE key switching to go to a partial GLWE secret key. This leverages the speed-up coming from the FFT. Finally, we compute a sample extraction (Algorithm 2). In Algorithm 1, two variants are described: a first one relying on the [GLWE-to-GLWE key switching] and a second one relying on the [secret product GLWE-to-GLWE key switching]. In what follows, we describe all advantages of using partial secret keys by describing each step of the Algorithm 1, which is studied more in details in Section 3.2.5.

### 3.2.1 Advantage with Sample Extraction

A sample extraction is the method to transform one coefficient of a GLWE ciphertext into an LWE ciphertext. The complete algorithm is described in 2, and can trivially be adapted in the context of partial GLWE secret keys. They are generalizations of the same algorithm used for “traditional” secret keys. Indeed, a traditional secret key is captured when $\phi = k \times N$.

**Noise and Cost of Sample Extraction** A sample extraction, whether it includes a partial secret key or not, does not add any noise to the plaintext. The cost of the sample extraction is also roughly the same and it is negligible.
<table><caption>**Algorithm 1:** ct<sub>out</sub> ← [FftLweKeySwitch] SecretProductFftLweKeySwitch (ct<sub>in</sub>, KSK)</caption>
  <tbody>
    <tr>
      <td>Context:</td>
      <td>
        <div>S<sub>in</sub><sup>[φ<sub>in</sub>]</sup> ∈ R<sub>q,N</sub><sup>k<sub>in</sub></sup>: the input partial secret key (Definition 6)</div>
        <div>S<sub>in</sub><sup>[φ<sub>in</sub>]</sup> = (S<sub>in,0</sub>, ..., S<sub>in,k<sub>in</sub>-1</sub>)</div>
        <div>S<sub>out</sub><sup>[φ<sub>out</sub>]</sup> ∈ R<sub>q,N</sub><sup>k<sub>out</sub></sup>: the output partial secret key (Definition 6)</div>
        <div>(k<sub>in</sub> - 1)N &lt; φ<sub>in</sub> ≤ k<sub>in</sub>N and (k<sub>out</sub> - 1)N &lt; φ<sub>out</sub> ≤ k<sub>out</sub>N</div>
        <div>Q = &sum;<sub>i=0</sub><sup>N-1</sup> Q<sub>i</sub>X<sup>i</sup> ∈ R<sub>q,N</sub></div>
        <div>CT<sub>i,j</sub> ∈ GLWE<sub>S<sub>out</sub><sup>[φ<sub>out</sub>]</sup></sub> (<sup>q</sup>/<sub>β<sup>j</sup></sub> &middot; Q &middot; S<sub>in,i</sub>), for 0 ≤ i ≤ k<sub>in</sub> - 1 and 0 ≤ j ≤ l - 1</div>
        <div>CT<sub>k<sub>in</sub>,j</sub> ∈ GLWE<sub>S<sub>out</sub><sup>[φ<sub>out</sub>]</sup></sub> (<sup>q</sup>/<sub>β<sup>j</sup></sub> &middot; Q), for 0 ≤ j ≤ l - 1</div>
        <div>l ∈ N: the number of levels in the decomposition</div>
        <div>β ∈ N: the base in the decomposition</div>
      </td>
    </tr>
    <tr>
      <td>Input:</td>
      <td>
        <div>ct<sub>in</sub> ∈ LWE<sub>s<sub>in</sub></sub>(p) ⊆ Z<sub>q</sub><sup>n<sub>in</sub>+1</sup>, with p ∈ Z<sub>q</sub></div>
        <div>KSK = {K<sub>i</sub> = (CT<sub>i,0</sub>, ..., CT<sub>i,l-1</sub>)}</div>
      </td>
    </tr>
    <tr>
      <td>Output:</td>
      <td>
        <div>ct<sub>out</sub> ∈ LWE<sub>s<sub>out</sub></sub>(Q<sub>0</sub> &middot; p) ⊆ Z<sub>q</sub><sup>n<sub>out</sub>+1</sup></div>
      </td>
    </tr>
    <tr>
      <td colspan="2" style="text-align: left;">/* Inverse of a constant sample extraction (Algorithm 3) */</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Set CT = (A<sub>0</sub>, ..., A<sub>k<sub>in</sub>-1</sub>, B) &larr; ConstantSampleExtraction<sup>-1</sup>(ct<sub>in</sub>, k<sub>in</sub>, N) ∈ R<sub>q,N</sub><sup>k<sub>in</sub>+1</sup></td>
    </tr>
    <tr>
      <td colspan="2" style="text-align: left;">/* Updating B for [Public] or [Secret] key switch */</td>
    </tr>
    <tr>
      <td>2</td>
      <td>[Set CT' := (0, ..., 0, B) ∈ R<sub>q,N</sub><sup>k<sub>out</sub>+1</sup>]</td>
    </tr>
    <tr>
      <td colspan="2" style="text-align: left;">Set CT' := &lt;K<sub>k<sub>in</sub></sub>, Decom<sup>(β,l)</sup>(B) &gt;</td>
    </tr>
    <tr>
      <td>3</td>
      <td>for i ∈ [0; k<sub>in</sub> - 1] do</td>
    </tr>
    <tr>
      <td>4</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;/* Decompose the mask */</td>
    </tr>
    <tr>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;Update CT' = CT' - &lt;K<sub>i</sub>, Dec<sup>(β,l)</sup>(A<sub>i</sub>) &gt;</td>
    </tr>
    <tr>
      <td colspan="2" style="text-align: left;">/* Constant sample extraction (Algorithm 2) */</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Set ct<sub>out</sub> &larr; ConstantSampleExtract(CT') ∈ Z<sub>q</sub><sup>n<sub>out</sub>+1</sup></td>
    </tr>
    <tr>
      <td>6</td>
      <td>return ct<sub>out</sub></td>
    </tr>
  </tbody>
</table>

**Inverse Constant Sample Extraction** An LWE ciphertext of size $n + 1$ can trivially be cast into a GLWE ciphertext of size $k + 1$ and with polynomials of size $N$. For completeness, the process is detailed in Alg. 3.

We obviously need $n \le kN$. If $n = kN$, the output is a GLWE ciphertext under a traditional secret key, otherwise it is a GLWE ciphertext under a partial GLWE secret key. Note that the constant term of the output GLWE plaintext is exactly the plaintext of the input LWE ciphertext, however the rest of the coefficients of the output GLWE ciphertext are filled with uniformly random values. We have the property that for all $p \in \mathbb{Z}_q$, for all $s \in \mathbb{Z}_q^n$, for all $ct \in \text{LWE}_s(p) \subseteq \mathbb{Z}_q^{n+1}$ and for all $(k, N) \in \mathbb{N}^2$ s.t. $n \le kN$:

$$ \text{ct} = \text{ConstantSampleExtract}(\text{ConstantSampleExtract}^{-1}(\text{ct}, k, N)) $$
<caption>**Algorithm 2:** ct<sub>out</sub> ← ConstantSampleExtract(CT<sub>in</sub>)</caption>

Context:
$$
\begin{cases}
\mathbf{S}^{[\phi]} \in \mathbb{R}_{q,N}^k : \text{a partial secret key (Definition 6)} \\
(k-1)N+1 \le \phi \le kN : \text{filling amount of the partial secret key} \\
\bar{s} \in \mathbb{Z}^\phi : \text{the flattened version of } \mathbf{S}^{[\phi]} \text{ (Definition 7)} \\
P := \sum_{i=0}^{N-1} p_i X^i \in \mathbb{R}_{q,N} \\
\text{CT}_{\text{in}} = \left( \sum_{i=0}^{N-1} a_{0,i} X^i, \dots, \sum_{i=0}^{N-1} a_{k-1,i} X^i, \sum_{i=0}^{N-1} b_i X^i \right) \in \mathbb{R}_{q,N}^{k+1}
\end{cases}
$$

**Input:** $\text{CT}_{\text{in}} \in \text{GLWE}_{\mathcal{S}^{[\phi]}}(P)$ : a GLWE encryption of the plaintext $P$

**Output:** $\text{ct}_{\text{out}} \in \text{LWE}_{\bar{s}}(p_0)$ : an LWE encryption of the plaintext $p_0$

1. **for** $i \in [0; \phi - 1]$ **do**

2. &nbsp;&nbsp;&nbsp;&nbsp;set $\alpha := \lfloor \frac{i}{N} \rfloor$, $\beta := (N - i) \mod N$ and $\gamma := 1 - (\beta == 0)$

3. &nbsp;&nbsp;&nbsp;&nbsp;set $a_{\text{out},i} := (-1)^\gamma \cdot a_{\alpha,\beta}$

4. **return** $\text{ct}_{\text{out}} := (a_{\text{out},0}, \dots, a_{\text{out},\phi-1}, b_0) \in \mathbb{Z}_q^{\phi+1}$

### 3.2.2 Advantage with GLWE Key Switch

A GLWE-to-GLWE key switching with $N \ne 1$, as described in Lines 1 and 2 of Alg. 1 takes as input a GLWE ciphertext $\text{CT}_{\text{in}} \in \mathbb{R}_{q,N}^{k_{\text{in}}+1}$ encrypting the plaintext $P \in \mathbb{R}_{q,N}$ under the secret key $\mathbf{S}^{[\phi_{\text{in}}]} \in \mathbb{R}_{q,N}^{k_{\text{in}}}$, and outputs $\text{CT}_{\text{out}} \in \mathbb{R}_{q,N}^{k_{\text{out}}+1}$ encrypting the plaintext $P + E_{\mathcal{K}_S} \in \mathbb{R}_{q,N}$ under the secret key $\mathbf{S}^{[\phi_{\text{out}}]} \in \mathbb{R}_{q,N}^{k_{\text{out}}}$.

The noise $E_{\mathcal{K}_S}$ added during this procedure, is composed of a rounding error plus a linear combination of the noise from the key switching key ciphertexts. The larger $\phi_{\text{in}}$, the more significant the rounding error.

**Theorem 2 (Noise of GLWE Key Switch)** After performing a key switching (Alg. 1) taking as input a GLWE ciphertext $\text{CT}_{\text{in}} \in \mathbb{R}_{q,N}^{k_{\text{in}}+1}$ under the secret key $\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]} \in \mathbb{R}_{q,N}^{k_{\text{in}}}$ and a key switching key with noise variance $\sigma_{\mathcal{K}_S}^2$, and outputting a GLWE ciphertext $\text{CT}_{\text{out}} \in \mathbb{R}_{q,N}^{k_{\text{out}}+1}$ under the secret key $\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]} \in \mathbb{R}_{q,N}^{k_{\text{out}}}$.

Let $\beta$ and $\ell$ be a decomposition base and level respectively. The variance of the noise of each coefficient of the output can be estimated by

$$ \text{Var}(\text{CT}_{\text{out}}) = \sigma_{\text{in}}^2 + \phi_{\text{in}} \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \text{Var}(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}) + \mathbb{E}^2(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}) \right) \\ + \frac{\phi_{\text{in}}}{4} \text{Var}(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}) + \ell k_{\text{in}} N \sigma_{\mathcal{K}_S}^2 \frac{\beta^2 + 2}{12}. $$

The proof of Th. 2 is a classical noise analysis of the result of the operation. Note that when $\phi_{\text{in}} = k_{\text{in}} \cdot N$ we end up with the same formula given in [CLOT21].

**Remark 4 (Cost of a GLWE Key Switch)** We recall that the cost of a GLWE-to-GLWE key switching, which remains the same whether it involves partial secret keys or not, is

$$ \begin{aligned} \mathcal{C}(\text{FftLweKeySwitch}) = & k_{\text{in}}\ell \cdot \mathcal{C}(\text{FFT}_N) + (k_{\text{out}} + 1) \cdot \mathcal{C}(\text{iFFT}_N) \\ & + Nk_{\text{in}}\ell \cdot (k_{\text{out}} + 1) \cdot \mathcal{C}(\times_{\mathbb{C}}) + N \cdot (k_{\text{in}}\ell - 1) \cdot (k_{\text{out}} + 1) \cdot \mathcal{C}(+_{\mathbb{C}}) \end{aligned} $$
<caption>**Algorithm 3:** $CT_{\text{out}} \leftarrow \text{ConstantSampleExtract}^{-1}(\text{ct}_{\text{in}}, k, N)$</caption>

```
Context: 
    s ∈ Z_q^n: the input LWE secret key
    S^{[n]} ∈ R_{q,N}^k: a partial secret key (Definition 6)
    such that its flattened version is s (Definition 7)
    R := Σ_{i=1}^{N-1} r_i · X^i ∈ R_{q,N}, where r_i are uniformly random
    ct_{in} = (a_0, ..., a_{N-1}, b) ∈ Z_q^{N+1}
    p ∈ Z_q

Input: 
    ct_{in} ∈ LWE_s(p): an LWE encryption of the plaintext p
    k ∈ N: the output GLWE dimension
    N ∈ N: the output polynomial size

Output: $CT_{\text{out}} \in \text{GLWE}_{S^{[n]}}(p_0 + R)$: a GLWE encryption

/* put the b part in a polynomial */
1 set B' := b ∈ R_{q,N}

/* put the rest in polynomials */
2 for i ∈ [0; k · N] do
3     set α := ⌊i/N⌋, β := (N - i) mod N and γ := 1 - (β == 0)
4     if i ≤ φ - 1 then
5         set a'_{α,β} := (-1)γ · a_i
6     else
7         set a'_{α,β} := 0

s return $CT_{\text{out}} := (A'_0 := \sum_{j=0}^{N-1} a'_{0,j} X^j, \dots, A'_{k-1} := \sum_{j=0}^{N-1} a'_{k-1,j} X^j, B') \in R_{q,N}^{k+1}$
```

where $+_{\mathbb{C}}$ and $\times_{\mathbb{C}}$ represent a double-complex addition and multiplication (in the FFT domain) respectively, and $\text{FFT}_N$ (resp. $\text{iFFT}_N$) the Fast Fourier Transform (resp. inverse FFT).

### 3.2.3 Advantage with Secret Product GLWE Key Switch

A GLWE-to-GLWE key switch also computing a product with a secret polynomial as described in Lines 1 and 2 of Alg. 1 follows the exact same definition than above, except that the output ciphertext encrypts $Q \cdot P + E_{\mathbb{K}S}$ where $Q \in R_{q,N}$ is the secret polynomial hidden in the key switching key. The added noise $E_{\mathbb{K}S}$ also depends on the input secret key $S^{[\phi_{\text{in}}]}$ and its filling amount $\phi_{\text{in}}$. Indeed, this term is the product between the rounding term (dependent on $\phi_{\text{in}}$) and the polynomial $Q$.

**Theorem 3 (Noise of Secret-Product GLWE Key Switch)** After performing a Secret-Product key switching (Algorithm 1), taking as input a GLWE ciphertext $CT_{\text{in}} \in R_{q,N}^{k_{\text{in}}+1}$ under the secret key $S_{\text{in}}^{[\phi_{\text{in}}]} \in R_{q,N}^{k_{\text{in}}}$ and a key switching key with noise variance $\sigma_{\mathbb{K}SK}^2$ encrypting a secret message $M_2$, and outputting a GLWE ciphertext $CT_{\text{out}} \in R_{q,N}^{k_{\text{out}}+1}$ under the secret key $S_{\text{out}}^{[\phi_{\text{out}}]} \in R_{q,N}^{k_{\text{out}}}$, the noise variance of
each coefficient of the output can be estimated by

$$ \mathrm{Var}(\mathrm{CT}_{\mathrm{out}}) = \ell(k_{\mathrm{in}} + 1)N\sigma_{\mathrm{KSK}}^2 \frac{\beta^2 + 2}{12} + ||M_2||_2^2 \cdot \left( \sigma_{\mathrm{in}}^2 + \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( 1 + \phi_{\mathrm{in}} \left( \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \mathbb{E}^2(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right) \right) + \frac{\phi_{\mathrm{in}}}{4} \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right). $$

The proof is detailed in the extended version of the paper.

### 3.2.4 Advantage with External Product

A GLWE external product is a special case of a secret-product GLWE-to-GLWE key switch where the input secret key and the output secret key are the same. It is pretty easy to compute the noise this procedure will add. The cost to compute a GLWE external product whether it includes a partial secret key or not, is the same.

**Theorem 4 (Noise of GLWE External Product)** The external product algorithm is the same as the algorithm of secret-product GLWE key switch (Alg. 1). The only difference is that the external product uses the same key $S^{[\phi]} \in R_{q,N}^k$ as input and as output, and the key switching key is now seen as a GGSW ciphertext of message $M_2$ encrypted with noise variance $\sigma_2^2$. For each coefficient of the output $\mathrm{CT}_{\mathrm{out}}$, the noise variance can be estimated by

$$ \mathrm{Var}(\mathrm{CT}_{\mathrm{out}}) = \ell(k + 1)N\sigma_2^2 \frac{\beta^2 + 2}{12} + ||M_2||_2^2 \cdot \left( \sigma_{\mathrm{in}}^2 + \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( 1 + \phi \left( \mathrm{Var}(S^{[\phi]}) + \mathbb{E}^2(S^{[\phi]}) \right) \right) + \frac{\phi}{4} \mathrm{Var}(S^{[\phi]}) \right). $$

**Proof 2 (Theorem 4)** This proof is the same than the proof of Theorem 3 with $k = k_{\mathrm{in}} = k_{\mathrm{out}}$ and $S^{[\phi]} = S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} = S_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}$. $\square$

**Noise Advantage with TFHE's PBS.** Using a partial GLWE secret key to encrypt a bootstrapping key for TFHE's programmable bootstrapping enables two convenient features: first to have a smaller output LWE ciphertext with less than $k \cdot N + 1$ coefficients, and second to reduce the noise growth in each external product. External product is the main operation used in the CMuxes of the blind rotation), as explained above. The direct consequence of having smaller output ciphertexts is the fact that we can perform smaller LWE-to-LWE key switchings before the next PBS. Furthermore, when $k \cdot N$ is large enough to reach the noise plateau (as explained in Limitation 2), partial secret keys enable to avoid adding unnecessary noise to the bootstrapping.

### 3.2.5 LWE-to-LWE Key Switch

Finally, we study the complete algorithm to compute and LWE-to-LWE keyswitch. We assume using the GLWE-to-GLWE key switch, but the formulae can easily be adapted to the private product one.
**Theorem 5 (Noise & Cost of FFT-Based LWE Key Switch)** We consider the new LWE-to-LWE key switch as described in Algorithm 1. Its cost is the same as the cost of a GLWE-to-GLWE key switch as introduced in Remark 4 i.e., $\mathcal{C}(\text{FftLweKeySwitch}) = \mathcal{C}(\text{GlweKeySwitch})$.

The output noise can be expressed from the noise formula of the GLWE-to-GLWE key switch (Theorem 2). To sum up, the output noise is:

$$ \mathrm{Var}(\text{FftLweKeySwitch}) = \mathrm{FftError}_{k_{\max}, N, \beta, \ell} + \mathrm{Var}(\text{GlweKeySwitch}) $$

with $\phi_{\text{in}} = n_{\text{in}}$, $\phi_{\text{out}} = n_{\text{out}}$, $k_{\max} = \max(k_{\text{in}}, k_{\text{out}})$ and $\text{FftError}_{k_{\max}, N, \beta, \ell}$ being the error added by the FFT conversions.

**Proof 3 (Theorem 5)** Expressing the cost is quite straight forward, since we can neglect the complexity of the sample extraction and its inverse. The estimation of the variance of the error is immediate as well. We use the corrective formula introduced in Remark 2 to estimate an upper bound on the FFT error. Indeed, it is easy to see that the FFT-based LWE key switch with $k_{\text{in}}$ and $k_{\text{out}}$ is a special case of an external product with $k_{\max} = \max(k_{\text{in}}, k_{\text{out}})$ where some of the ciphertexts composing the GGSW are trivial encryptions of 0 or 1 (no noise, all mask elements set to zero and the plaintext put in the b/B part).

**Practical Improvement.** The use of partial secret keys brings a practical significant improvement to homomorphic computations. Table 1 presents a comparison of our techniques and the state of the art [CJP21]. More details on the experiments are reported in Section 6.1.

# 4 Shared Randomness Secret Keys

To use FHE schemes, one needs to generate several secret keys of different sizes. Our main observation is that instead of sampling those keys independently, we can generate a list of $\alpha$ nested GLWE keys with the same level of security $\lambda$.

As a simple example we consider three integers $1 < n_0 < n_1 < n_2$ and a secret key $\mathbf{s}^{(2)} = \mathbf{r}^{(0)}||\mathbf{r}^{(1)}||\mathbf{r}^{(2)} \in \mathbb{Z}_q^{n_2}$ generated in the traditional manner. We can now build two smaller secret keys out of $\mathbf{s}^{(2)}$ such that for all pair of keys, the smaller one will be included in the bigger one, in its first coefficients: $\mathbf{s}^{(0)} = \mathbf{r}^{(0)} \in \mathbb{Z}_q^{n_0}$ and $\mathbf{s}^{(1)} = \mathbf{r}^{(0)}||\mathbf{r}^{(1)} \in \mathbb{Z}_q^{n_1}$. With this new secret keys, the cost and the noise of a keyswitch between $\mathbf{s}^{(1)}$ and $\mathbf{s}^{(0)}$ will no longer depend on $n_0$ and $n_1$ but on $n_1 - n_0$ and $n_0$. If we want to keyswitch from $\mathbf{s}^{(0)}$ to $\mathbf{s}^{(1)}$, the key switch will come for free: it will add no noise and will have no cost. Note that each of those secret keys use a different variance for the noise added during encryption: the smaller the secret key, the bigger the variance, so they can all guarantee the same level of security $\lambda$.

In this section, we first define the shared randomness secret key. We then study the impact of these keys on the security of the underlying LWE problems. Finally, we list the different advantages and improvements which they offer.
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of simplified key switch procedures between three shared randomness LWE secret keys.</figcaption></figure>

**Definition 9 (GLWE Shared Randomness Secret Keys)** *Two GLWE secret keys $\mathbf{S} \in \mathbb{R}_{q,N}^k$ and $\mathbf{S}' \in \mathbb{R}_{q,N'}^{k'}$, with $kN \le k'N'$, are said to share randomness if we have that for all $0 \le i < kN$, $\bar{s}_i = \bar{s}'_i$, where $\bar{s}_i$ and $\bar{s}'_i$ respectively come from the flattened view (Definition 3) of $\mathbf{S}$ and $\mathbf{S}'$. We note by $\mathbf{S} \prec \mathbf{S}'$ this relationship between secret keys.*

**4.1 Hardness of Shared Randomness Secret Keys**

Let us consider different samples of GLWE with shared randomness. By taking independently the samples under the same secret key, all the samples are secure and have the same level of security. We now study the level of security of several samples of GLWE considered together with shared secret keys.

First, we present the decisional LWE problem with shared randomness and prove that, under certain conditions, this problem can be reduced to a LWE problem. Next we show that the new operations offered by the shared randomness secret key can not impact the security. Indeed, with this new secret keys using shared randomness, it becomes possible to combine two ciphertexts encrypted under different secret keys.

**Definition 10 (Shared Randomness Secret Key Decisional Problem)**

Let $n_1 > n_0$. Given a secret key $\mathbf{s}^{(0)} \in \mathbb{Z}_q^{n_0}$ following a given distribution $\mathcal{D}$, a secret $\mathbf{r} \in \mathbb{Z}_q^{n_1-n_0}$ following the same distribution $\mathcal{D}$, and two errors distribution $\chi_0$ and $\chi_1$, we define the LWE with shared randomness secret samples – and we note sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ – the pairs $((\mathbf{a}_0, b_0 = \langle \mathbf{a}_0, \mathbf{s}^{(0)} \rangle + e_0), (\mathbf{a}_1, b_1 = \langle \mathbf{a}_1, \mathbf{s}^{(1)} \rangle + e_1)) \in \mathbb{Z}_q^{n_0+1} \times \mathbb{Z}_q^{n_1+1}$, where $\mathbf{s}^{(1)} = \mathbf{s}^{(0)}|_{\mathbf{r}}, \mathbf{a}_0 \leftarrow \mathcal{U}(\mathbb{Z}_q)^{n_0}, \mathbf{a}_1 \leftarrow \mathcal{U}(\mathbb{Z}_q)^{n_1}, e_0 \leftarrow \chi_0 \text{ and } e_1 \leftarrow \chi_1$.

The decision sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ problem consist of distinguishing $m$ independent samples from $\mathcal{U}(\mathbb{Z}_q^{n_0+1} \times \mathbb{Z}_q^{n_1+1})$ from $m$ independent samples $((\mathbf{a}_0, b_0), (\mathbf{a}_1, b_1)) \in \text{LWE}_{n_0,\chi_0} \times \text{LWE}_{n_1,\chi_1} \subseteq \mathbb{Z}_q^{n_0+1} \times \mathbb{Z}_q^{n_1+1}$ as defined above.

**Theorem 6 (Hardness of sh-LWE)** *If we have three random distributions $\chi_0, \chi_1$ and $\chi'$ such that, if we sample $e_1 \leftarrow \chi_1$ and $e' \leftarrow \chi'$, $e_1 + e'$ follows the distribution $\chi_0$. Then sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ with $m$ samples is at least as hard than LWE$_{n_0,\chi_1}$ with $2m$ samples.*

**Remark 5 (Error Distribution $\chi$)** *In GLWE-based FHE schemes, $\chi$ usually follows a discrete normal distribution. The condition for Theorem 6 is then always*
verified. In the following, the goal is to use a noise variance $\sigma_0$ for $\chi_0$ and a noise variance $\sigma_1$ for $\chi_1$ such that $n_0 < n_1$ and $\sigma_0 > \sigma_1$.

**Proof 4 (Theorem 6)** We define an instance of LWE$_{n_0,\chi_1}$ where the samples are encrypted under a secret key $\mathbf{s}^{(0)} \in \mathbb{Z}_q^{n_0}$ which follows a given distribution $\mathcal{D}$, and where for the given distribution $\chi_1$ it exists a distribution $\chi'$ such that, for any $e_1 \leftarrow \chi_1$ and for any $e' \leftarrow \chi'$, we have that $e_1 + e'$ follows a distribution $\chi_0$.

We now prove that solving the problem sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ is at least as hard than solving the problem LWE$_{n_0,\chi_1}$. To do so, we consider an oracle that can solve the decision sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ problem and show that a such oracle can solve the decisional LWE$_{n_0,\chi_1}$ instance.

Observe that, starting from an LWE$_{n_0,\chi_1}$ sample, we can easily create either an LWE$_{n_0,\chi_0}$ sample or an LWE$_{n_1,\chi_1}$ sample. To create an LWE$_{n_0,\chi_0}$ sample ($\mathbf{a}_0, b_0 = \langle \mathbf{a}_0, \mathbf{s}^{(0)} \rangle + e_0) \in \mathbb{Z}_q^{n_0+1}$, with $e_0$ coming from a distribution $\chi_0$, from an LWE$_{n_0,\chi_1}$ sample ($\mathbf{a}_1, b_1 = \langle \mathbf{a}_1, \mathbf{s}^{(0)} \rangle + e_1) \in \mathbb{Z}_q^{n_0+1}$, with $e_1$ coming from a distribution $\chi_1$, we only need to take $\mathbf{a}_0 = \mathbf{a}_1$ and modify the noise. Following the above condition, it is sufficient to sample $e' \leftarrow \chi'$ and then take $b_0 = b_1 + e'$, to make the noise in $b_0$ be equal to $e_1 + e'$. This now follows the distribution $\chi_0$.

To create an LWE$_{n_1,\chi_1}$ sample ($\mathbf{a}_1, b_1 = \langle \mathbf{a}_1, \mathbf{s}^{(1)} \rangle + e_1) \in \mathbb{Z}_q^{n_1+1}$ from a LWE$_{n_0,\chi_1}$ sample ($\mathbf{a}_0, b_0 = \langle \mathbf{a}_0, \mathbf{s}^{(0)} \rangle + e_1) \in \mathbb{Z}_q^{n_0+1}$, we start by generating an random key $r \in \mathbb{Z}_q^{n_1-n_0}$, which follows the same distribution $\mathcal{D}$ than $\mathbf{s}^{(0)}$, as well as a new vector $\mathbf{a}' \in \mathcal{U}(\mathbb{Z}_q^{n_1-n_0})$. Then, we take $\mathbf{a}_1 = \mathbf{a}_0 || \mathbf{a}'$ and $b_1 = b_0 + \langle \mathbf{a}', \mathbf{r}' \rangle$, which give us an LWE$_{n_1,\chi_1}$ sample as expected.

Following what just described, we observe that given 2m LWE$_{n_0,\chi_1}$ samples, we can generate m LWE$_{n_0,\chi_0}$ samples and m LWE$_{n_1,\chi_1}$ samples. Now we can provide all the valid samples of LWE$_{n_0,\chi_0} \times LWE_{n_1,\chi_1}$ to the oracle. Otherwise, when the decisional LWE$_{n_0,\chi_1}$ problem send uniform samples in $\mathbb{Z}_q^{n_0}$, the two transformations proposed before also return uniform samples in $\mathbb{Z}_q^{n_0}$ or in $\mathbb{Z}_q^{n_1}$. As the oracle can solve the decision sh-LWE$_{n_0,\chi_0,n_1,\chi_1}$ problem, we can solve the decisional LWE$_{n_0,\chi_1}$ problem.

**Remark 6 (Security with more than two shared Keys)** The Proof 4, can easily be adapted to more than only two shared keys.

**Operations Under Shared Randomness** Any known homomorphic operation (that we know) that makes two or more ciphertexts interact (encrypted under the same key or different keys) will have as a result a ciphertext with a level of security at least as high as the input with the lowest security level. In light of the common existing attacks, the level of security of a set of GLWE samples encrypted under shared randomness secret keys is then lower bounded by the level of security of the GLWE having the smallest level of security.

As for the partial secret keys, this new type of keys may lead to new unknown attacks and the level of security could be impacted. But at the current state of the art, no attacks seem to have an impact on shared randomness secret key. However, if one of the key sets is compromised, the other key sets will be impacted consequently.
## 4.2 Advantages of Shared Randomness Secret Keys

Using shared randomness secret keys enable to speed up homomorphic computations and reduce the amount of noise added by these operations. This is particularly useful for LWE-to-LWE key switch procedures.

### 4.2.1 Advantages with LWE-to-LWE Key Switch

Shared randomness secret keys enable to key switch more efficiently and add less noise during the procedure. Figure 1 illustrates key switching processes between three LWE shared randomness secret keys. A key switch to a bigger key is represented with dotted arrows and is called enlarging key switch. A key switch to a smaller key is represented with solid arrows and is called shrinking key switch.

**Enlarging Key Switch.** When we consider a ciphertext $ct_{in} = (a_0, \dots, a_{n_1-1}, b) \in \text{LWE}_{s^{(1)}}(m) \subseteq \mathbb{Z}_q^{n_1+1}$ under the secret key $s^{(1)} \in \mathbb{Z}_q^{n_1}$ and want to key switch it to the secret key $s^{(2)} \in \mathbb{Z}_q^{n_2}$, where $s^{(1)} \prec s^{(2)}$, the algorithm translates into simply adding zeros at the end of the ciphertext:

$$ \text{ct}_{\text{out}} := (a_0, \dots, a_{n_1-1}, 0, \dots, 0, b) \in \text{LWE}_{s^{(2)}}(m) \subseteq \mathbb{Z}_q^{n_2+1} $$

Algorithm 4 describes this procedure in detail. In this paper we only use this algorithm with LWE ciphertexts, but it can trivially be extended to GLWE ciphertexts.

<table><caption>**Algorithm 4:** $ct_{out} \leftarrow \text{EnlargingKeySwitch}(ct_{in})$</caption><tr><td>Context:</td><td>
  <div style="font-family: monospace; white-space: pre; text-align: left; margin: 0; padding: 0;">
    <pre><code>s<sub>in</sub> &isin; Z<sub>q</sub><sup>n<sub>in</sub></sup> : the input secret key<br>
s<sub>out</sub> &isin; Z<sub>q</sub><sup>n<sub>out</sub></sup> : the output secret key<br>
s<sub>in</sub> &prec; s<sub>out</sub> : shared randomness secret keys (Definition 9)<br>
p &isin; Z<sub>q</sub><br>
ct<sub>in</sub> = (a<sub>0</sub>, &hellip;, a<sub>n<sub>in</sub>-1</sub>, b) &isin; Z<sub>q</sub><sup>n<sub>in</sub>+1</sup>
  </pre></div>
</td></tr><tr><td>Input:</td><td>$ct_{in} \in \text{LWE}_{s_{in}}(p)$</td></tr><tr><td>Output:</td><td>$ct_{out} \in \text{LWE}_{s_{out}}(p)$</td></tr><tr><td colspan="2" style="border-bottom: 1px solid black; padding: 0; height: 1em;"></td></tr><tr><td colspan="2" style="padding: 0;">
  /* Pad with zeros between the mask and the b part
  */
</td></tr><tr><td>1</td><td>Set $ct_{out} := (a_0, \dots, a_{n_1-1}, 0, \dots, 0, b) \in Z<sub>q</sub><sup>n<sub>out</sub>+1</sup></td></tr><tr><td>2</td><td>return $ct_{out}$</td></tr></table>

To sum up, with shared randomness secret keys, the enlarging key switchings are basically zero-cost operations and do not require the use of a public key. They also add no noise, instead of adding a linear combination of freshly encrypted ciphertexts under $s^{(2)}$. The proof of next theorem is trivial.

**Theorem 7 (Cost & Noise of Enlarging Key Switching)** When working with shared randomness secret keys, the cost of an enlarging key switching (Algorithm 4) is reduced to zero, and the noise in the output is the same as the one in the input (no noise is added).
**Shrinking Key Switch.** When we consider a ciphertext $ct_{in} = (a_0, \dots, a_{n_2-1}, b) \in \mathbb{Z}_q^{n_2+1}$ under the secret key $\mathbf{s}^{(2)} \in \mathbb{Z}_q^{n_2}$ and we want to key switch it to the secret key $\mathbf{s}^{(1)} \in \mathbb{Z}_q^{n_1}$, where $\mathbf{s}^{(1)} \prec \mathbf{s}^{(2)}$ and $\mathbf{s}^{(2)} = \mathbf{s}^{(1)} \| \mathbf{r}^{(2)}$, the algorithm is simplified precisely because of the shared randomness:

1. the parts $(a_0, \dots, a_{n_1-1})$ and $b$ do not need to be processed but simply reorganized into a temporary ciphertext: $ct = (a_0, \dots, a_{n_1-1}, b) \in \mathbb{Z}_q^{n_1+1}$,

2. the part $(a_{n_1}, \dots, a_{n_2-1})$ has to be key switched, which can be viewed as a traditional key switching algorithm: i.e., key switching the ciphertext $(a_{n_1}, \dots, a_{n_2-1}, 0) \in \mathbb{Z}_q^{n_2-n_1+1}$ with a key switching key going from the secret key $\mathbf{r}^{(2)}$ to $\mathbf{s}^{(1)}$, and at the end, adding it to $ct$ and returning the result.

Algorithm 5, describes this procedure in detail. In this paper we only use this algorithm with LWE ciphertexts, but it can be also trivially extended to GLWE ciphertexts.

<table><caption>**Algorithm 5:** $ct_{out} \leftarrow \text{ShrinkingKeySwitch}(ct_{in}, \text{KSK})$</caption><tr><td>Context:</td><td><pre><code>  s<sub>in</sub> = (s<sub>0</sub>, ..., s<sub>n<sub>in</sub>-1</sub>) &isin; Z<sub>q</sub><sup>n<sub>in</sub></sup> : the input secret key<br>
  s<sub>out</sub> &isin; Z<sub>q</sub><sup>n<sub>out</sub></sup> : the output secret key<br>
  n<sub>out</sub> &lt; n<sub>in</sub><br>
  s<sub>out</sub> &prec; s<sub>in</sub> : shared randomness secret keys (Definition 9)<br>
  p &isin; Z<sub>q</sub><br>
  ct<sub>in</sub> = (a<sub>0</sub>, ..., a<sub>n<sub>in</sub>-1</sub>, b) &isin; Z<sub>q</sub><sup>n<sub>in</sub>+1</sup><br>
  l &isin; N: the number of levels in the decomposition<br>
  &beta; &isin; N: the base in the decomposition</code></pre></td></tr><tr><td>Input:</td><td><pre><code>  ct<sub>in</sub> &isin; LWE<sub>s<sub>in</sub></sub>(p)<br>
  KSK = {KSK<sub>i</sub>}<sub>n<sub>out</sub> &le; i &lt; n<sub>in</sub></sub>, with KSK<sub>i</sub> &isin; LEV<sub>s<sub>out</sub></sub><sup>(&beta;,l)</sup> (s<sub>in,i</sub>) : a key switching key</code></pre></td></tr><tr><td>Output:</td><td><pre><code>  ct<sub>out</sub> &isin; LWE<sub>s<sub>out</sub></sub>(p)</code></pre></td></tr><tr><td colspan="2" style="text-align: left;">/* Keep the beginning of the mask and the B part */</td></tr><tr><td>1</td><td>Set ct<sub>out</sub> := (a<sub>0</sub>, ..., a<sub>n<sub>out</sub>-1</sub>, b) &isin; Z<sub>q</sub><sup>n<sub>out</sub>+1</sup></td></tr><tr><td>2</td><td>for i &isin; [n<sub>out</sub>; n<sub>in</sub> - 1] do</td></tr><tr><td>3</td><td>&nbsp;&nbsp; /* Decompose the rest of the mask */<br>&nbsp;&nbsp; Update ct<sub>out</sub> = ct<sub>out</sub> - &lt;KSK<sub>i</sub>, Dec<sup>(&beta;,l)</sup>(a<sub>i</sub>)&gt;</td></tr><tr><td>4</td><td>return ct<sub>out</sub></td></tr></table>

To sum up, with shared randomness secret keys, the shrinking key switching requires smaller key switching keys: their size becomes proportional to $n_2 - n_1$ instead of $n_2$. As a consequence, the computation is faster, equivalent to key switch a ciphertext of size $n_2 - n_1 + 1$ instead of $n_2 + 1$. Finally, the noise in the output is also smaller because the algorithm involves a smaller linear combination of freshly encrypted ciphertexts under $\mathbf{s}^{(1)}$. The details of the proof of next theorem can be found in the extended version of the paper.

**Theorem 8 (Cost & Noise of Shrinking Key Switching)** Consider two shared randomness secret keys $\mathbf{s}^{(0)} \prec \mathbf{s}^{(1)}$ with $\mathbf{s}^{(0)} \in \mathbb{Z}_q^{n_0}$, $\mathbf{s}^{(1)} \in \mathbb{Z}_q^{n_1}$ and
1 < n₀ < n₁. Let β ∈ ℝ* and ℓ ∈ ℝ* be the decomposition base and level used in key switching. The cost of our shrinking key switching (Algorithm 5) is ℓ(n₁ - n₀)(n₀ + 1) integer multiplications and (ℓ(n₁ - n₀) - 1)(n₀ + 1) integer additions. The noise added by the procedure satisfies

$$ \mathrm{Var}(\mathrm{ShrinkingKeySwitch}) = (n_1 - n_0) \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \mathrm{Var}(\mathbf{s}_{\mathrm{in}}) + \mathbb{E}^2(\mathbf{s}_{\mathrm{in}}) \right) \\ + \frac{(n_1 - n_0)}{4} \mathrm{Var}(\mathbf{s}_{\mathrm{in}}) + \ell \cdot (n_1 - n_0) \cdot \frac{\beta^2 + 2}{12} \sigma_{\mathrm{KSK}}^2. $$

### 4.2.2 Stair Key Switch

In Section 4.2.1, we saw that when one uses different secret keys within an FHE use case, it is convenient to make use of shared randomness secret keys. However, this concept can also be used locally inside a key switch procedure to explore a cost/noise trade-off.

For simplicity, let's consider an FHE use case where there are only two LWE secret keys, and only a key switch from the big one to the small one. We start by setting the two secret keys as shared randomness. The idea here is to add one or several shared randomness secret keys, only during the key switch procedure.

For example, let's assume a fixed decomposition base $β$, a fixed number of levels $ℓ$ and let $\mathbf{s}^{(2)}$ be our big secret key and $\mathbf{s}^{(0)}$ be our small (as defined in Section 4.2.1). To key switch from $\mathbf{s}^{(2)}$ to $\mathbf{s}^{(0)}$, we will add one intermediate shared randomness secret key $\mathbf{s}^{(1)}$ and compute first a key switch from $\mathbf{s}^{(2)}$ to $\mathbf{s}^{(1)}$ and then another from $\mathbf{s}^{(1)}$ to $\mathbf{s}^{(0)}$. This algorithm will be more costly, because its first part will be a linear combination of $(n_2 - n_1)$ ciphertexts of size $n_1 + 1$, and its second part a linear combination of $(n_1 - n_0)$ ciphertexts of smaller size $n_0 + 1$, instead of having a single linear combination of $n_2 - n_0$ ciphertexts of size $n_0 + 1$: so the total number of ciphertexts in the linear combination and in the key switching key has not changed $(n_2 - n_1 + n_1 - n_0 = n_2 - n_0$ as in the key switching from $\mathbf{s}^{(2)}$ to $\mathbf{s}^{(0)}$), but the linear combinations are slightly more costly and the ciphertexts composing the key switching keys slightly larger. However, this algorithm produces less noise: indeed its first part has ciphertexts with lower noise because they are encrypted under a bigger secret key.

Here is the trade-off we want to study. The extreme is to go from $\mathbf{s}^{(\mathrm{nb})}$ to $\mathbf{s}^{(0)}$ by key switching one element of the key in each key switching, meaning that we will have a total number of $\mathrm{nb} = n_{\mathrm{nb}} - n_0$ shrinking key switching (Algorithm 5) to perform. So $\mathrm{nb}$ corresponds to the steps in the stair. This means considering a total number of shared keys equal to $\mathrm{nb} + 1$, including the secret keys $\mathbf{s}^{(\mathrm{nb})}$ and $\mathbf{s}^{(0)}$ which are the end points of the stair. We call the added keys between $\mathbf{s}^{(\mathrm{nb})}$ and $\mathbf{s}^{(0)}$ intermediate secret keys, so we have a total of $\mathrm{nb} - 1$ intermediate secret keys. In practice, we start with coefficient $a_{n_{\mathrm{nb}}-1}$ and key switch it to the secret key with $n_{\mathrm{nb}} - 1$ elements, add it to the rest, and do the same with the next last element, and so on until we reach the desired secret key, one coefficient at a time. The other extreme case is when we key switch directly from $\mathbf{s}^{(1)}$ and $\mathbf{s}^{(0)}$ without intermediary
key switchings, so $nb = 1$.

Algorithm 6 gives details about this procedure. It is important to point out that there are now nb couples of decomposition parameters $(\beta_{\alpha}, \ell_{\alpha})$ for $0 \le \alpha \le nb - 1$, one for each step of the stairs. Note that we could also allow to have more than one such couple per step as well.

<table><caption>**Algorithm 6:** $ct_{\text{out}} \leftarrow \text{StairKeySwitch}(ct_{\text{in}}, \{\text{KSK}_{\alpha}\}_{0 \le \alpha \le nb-1})$</caption><tr><td>Context:</td><td>
    <div>nb &isin; N: the number of steps in the algorithm</div>
    <div>n<sub>0</sub> &lt; n<sub>1</sub> &lt; &hellip; &lt; n<sub>nb</sub></div>
    <div>s<sup>(nb)</sup> &isin; Z<sup>n<sub>nb</sub></sup>: the input secret key</div>
    <div>s<sup>(0)</sup> &isin; Z<sup>n<sub>0</sub></sup>: the output secret key</div>
    <div>s<sup>(&alpha;)</sup> &isin; Z<sup>n<sub>&alpha;</sub></sup>, &forall;1 &le; &alpha; &le; nb &minus; 1: intermediate secret keys</div>
    <div>s<sup>(0)</sup> &lt; s<sup>(1)</sup> &lt; &hellip; &lt; s<sup>(nb)</sup>: shared randomness secret keys (Definition 9)</div>
</td></tr><tr><td>Input:</td><td>
    <div>ct<sub>in</sub> &isin; LWE<sub>s<sup>(nb)</sup></sub>(p) &sube; Z<sup>n<sub>nb+1</sub></sup>, with p &isin; Z<sub>q</sub></div>
    <div>{KSK<sub>&alpha;</sub>}<sub>0&le;&alpha;&le;nb&minus;1</sub>: intermediate key switching key as in Algorithm 5</div>
    <div>where KSK<sub>&alpha;</sub> switches from s<sup>(&alpha;+1)</sup> to s<sup>(&alpha;)</sup></div>
</td></tr><tr><td>Output:</td><td>ct<sub>out</sub> &isin; LWE<sub>s<sup>(0)</sup></sub>(p) &sube; Z<sup>n<sub>0</sub>+1</sup></td></tr><tr><td colspan="2">/* Set the counter to go from nb &minus; 1 to 0 */</td></tr><tr><td>1</td><td>Set &alpha; := nb &minus; 1</td></tr><tr><td colspan="2">/* Set the initial ciphertext */</td></tr><tr><td>2</td><td>Set ct := ct<sub>in</sub></td></tr><tr><td>3</td><td>while &alpha; &gt;= 0 do</td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp; /* Call to Algorithm 5 */</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp; Update ct &leftarrow; ShrinkingKeySwitch(ct, KSK<sub>&alpha;</sub>) &isin; LWE<sub>s<sup>(&alpha;)</sup></sub>(p) &sube; Z<sup>n<sub>&alpha;</sub>+1</sup></td></tr><tr><td>6</td><td>return ct<sub>out</sub> := ct</td></tr></table>

**Theorem 9 (Cost & Noise of Stair Shrinking Key Switching)**

Consider the stair key switch as detailed in Algorithm 6. Its cost amounts to $\sum_{\alpha=0}^{nb-1} \ell_{\alpha} (n_{\alpha+1} - n_{\alpha}) (n_{\alpha} + 1)$ integer multiplications and $\sum_{\alpha=0}^{nb-1} (\ell_{\alpha} (n_{\alpha+1} - n_{\alpha}) - 1) (n_{\alpha} + 1)$ integer additions. The noise added by the procedure satisfies

$$ \mathrm{Var}(\text{StairShrinkKS}) = \sum_{\alpha=0}^{nb-1} (n_{\alpha+1} - n_{\alpha}) \left( \frac{q^2 - \beta_{\alpha}^{2\ell_{\alpha}}}{12\beta_{\alpha}^{2\ell_{\alpha}}} \right) \left( \mathrm{Var}(\mathbf{s}^{(\alpha+1)}) + \mathbb{E}^2(\mathbf{s}^{(\alpha+1)}) \right) \\ + \frac{(n_{\alpha+1} - n_{\alpha})}{4} \mathrm{Var}(\mathbf{s}^{(\alpha+1)}) + \ell_{\alpha} \cdot (n_{\alpha+1} - n_{\alpha}) \cdot \frac{\beta_{\alpha}^2 + 2}{12} \sigma_{\text{KSK}_{\alpha}}^2. $$

**Proof 5 (Theorem 9)** The cost and noise of the stair shrinking key switching can be trivially deduced from the Theorem 8. Indeed, at step $\alpha$ of the loop in Algorithm 6, the cost of the shrinking key switching is $\ell_{\alpha} (n_{\alpha+1} - n_{\alpha}) (n_{\alpha} + 1)$ integer multiplications and $(\ell_{\alpha} (n_{\alpha+1} - n_{\alpha}) - 1) (n_{\alpha} + 1)$ integer additions.
The variance of the noise added at the step $\alpha$ is:

$$ \mathrm{Var}(\mathrm{ShrinkKS}_{\alpha}) = (n_{\alpha+1} - n_{\alpha}) \left( \frac{q^2 - \beta_{\alpha}^{2\ell_{\alpha}}}{12\beta_{\alpha}^{2\ell_{\alpha}}} \right) \left( \mathrm{Var}(\mathbf{s}^{(\alpha+1)}) + \mathbb{E}^2(\mathbf{s}^{(\alpha+1)}) \right) \\ + \frac{(n_{\alpha+1} - n_{\alpha})}{4} \mathrm{Var}(\mathbf{s}^{(\alpha+1)}) + \ell_{\alpha} \cdot (n_{\alpha+1} - n_{\alpha}) \cdot \frac{\beta_{\alpha}^2 + 2}{12} \sigma_{\mathrm{KSK}_{\alpha}}^2. $$

To obtain the total cost of the algorithm and the total variance of the noise added, we simply iterate from $\alpha = 0, \dots, nb - 1$.

**Remark 7 (Stairs in the Blind Rotation.)** A similar process can be introduced in the blind rotation algorithm. The idea would be, during the blind rotation, to progressively use GLWE partial secret keys (Definition 6) with a smaller filling amount $\phi$ which will reduce the output noise of the blind rotate. As with the stair shrinking key switch, we could use different bases and levels in the external products thus offering potentially an overall speed-up. We leave this problem as a topic for future work.

**Practical Improvement.** The use of shared secret keys brings a practical significant improvement to homomorphic computations: Table 1, presents a comparison of our techniques to the state of the art [CJP21]. More detailed experiments are reported in Section 6.2.

# 5 Combining Both Techniques & Their Applications

In this section, we start by providing details on FHE algorithms that benefit from having secret keys that are both partial and shared randomness. Later on, we describe some nice applications of these new types of secret keys.

## 5.1 Combining Both Techniques

Shared randomness partial GLWE secret keys are simply a list of partial GLWE secret keys (Section 3) with some public knowledge about shared coefficients in the exact same way as in Section 4. This type of keys is a combination of shared randomness and partial secret keys, offering advantages of both types.

It is possible to design a faster shrinking key switch (Algorithm 1) which uses partial secret keys (Definition 6). This means that for this faster algorithm, we use both partial secret keys and shared randomness secret keys. Details about this new procedure is given in Algorithm 7.

**Theorem 10 (Noise & Cost of the FFT-Based Shrinking Key Switch)**

We consider the FFT-based LWE shrinking key switching as detailed in Algorithm 7. Its cost can be expressed from the cost of a GLWE-to-GLWE
<caption>**Algorithm 7:** ct<sub>out</sub> ← FftShrinkingKeySwitch(ct<sub>in</sub>, KSK)</caption>

Context:
$$
\left\{
\begin{array}{l}
n_{\text{out}} < n_{\text{in}}, \ n_{\text{in}} - n_{\text{out}} \le k_{\text{KSK,in}} \cdot N_{\text{KSK}} \text{ and } n_{\text{out}} \le k_{\text{KSK,out}} \cdot N_{\text{KSK}} \\
s_{\text{out}} \prec s_{\text{in}} : \text{shared randomness secret keys (Definition 9)} \\
s_{\text{out}} \in \mathbb{Z}_{q}^{n_{\text{out}}} : \text{the output LWE secret key} \\
s = (s_{n_{\text{out}}}, \dots, s_{n_{\text{in}}-1}) \in \mathbb{Z}_{q}^{n_{\text{in}}-n_{\text{out}}} \\
s_{\text{in}} = s_{\text{out}} \parallel s \in \mathbb{Z}_{q}^{n_{\text{in}}} : \text{the input LWE secret key}
\end{array}
\right.
$$
Input:
$$ \text{ct}_{\text{in}} = (a_0, \dots, a_{n_{\text{in}}-1}, b) \in \text{LWE}_{s_{\text{in}}}(p) \subseteq \mathbb{Z}_{q}^{n_{\text{in}}+1}, \text{ where } p \in \mathbb{Z}_{q} \\ \text{KSK} : \text{ the key switching key suited for Algorithm 1} $$
Output:
$$ \text{ct}_{\text{out}} \in \text{LWE}_{s_{\text{out}}}(p) $$
/* Split the input LWE ciphertext into two parts: one related to } s_{\text{out}}, \text{ and} \\ \text{the rest} */
1. Set } ct_0 := (a_0, \dots, a_{n_{\text{out}}-1}, b) \in \mathbb{Z}_q^{n_{\text{out}}+1} \text{ Set } ct_1 := (a_{n_{\text{out}}}, \dots, a_{n_{\text{in}}-1}, 0) \in \mathbb{Z}_q^{n_{\text{in}}-n_{\text{out}}+1} \text{ Set } ct'_1 \leftarrow \text{FftLweKeySwitch}(ct_1, \text{KSK}) \in \mathbb{Z}_q^{n_{\text{out}}+1} \text{ return } ct_0 = ct_0 + ct'_1 */
2.
3.
4.

key switch (Remark 4) since we neglect the costs of sample extraction and its inverse. The cost is then $\mathcal{C}(\text{FftShrinkingKeySwitch}) = \mathcal{C}(\text{GlweKeySwitch})$. Note that $k_{\text{in}}$ is smaller thanks to the shared randomness property of the secret keys, which leads to a faster procedure. The added noise can be expressed from the noise formula of the GLWE-to-GLWE key switch (Theorem 2) which gives $\text{Var}(\text{FftShrinkingKeySwitch}) = \text{FftError}_{k_{\text{max}},N,\beta,\ell} + \text{Var}(\text{GlweKeySwitch})$ with $\phi_{\text{in}} = n_{\text{out}} - n_{\text{in}}$ and $k_{\text{max}} = \max(k_{\text{in}}, k_{\text{out}})$.

**Proof 6 (Theorem 10)** *The estimation of the variance of the error is immediate.*
*For the FFT error, we refer to Remark 2 and Proof 3.*

Alg. 8 summarizes the process to compute a keyswitch when both approaches are mixed.

**Theorem 11 (Noise of GLWE Key Switching With Partial & Shared Randomness Keys)** Perform a key switching (Algorithm 8) from $\text{CT}_{\text{in}} \in R_{q,N}^{k_{\text{in}}+1}$ under the secret key $S_{\text{in}}^{[\phi_{\text{in}}]} \in R_{q,N}^{k_{\text{in}}}$, to $\text{CT}_{\text{out}} \in R_{q,N}^{k_{\text{out}}+1}$ under the secret key $S_{\text{out}}^{[\phi_{\text{out}}]} \in R_{q,N}^{k_{\text{out}}}$, where the key are shared and partial, i.e., $S_{\text{out}}^{[\phi_{\text{out}}]} \prec S_{\text{in}}^{[\phi_{\text{in}}]}$. Each coefficient of the output has added noise estimated as

$$ \text{Var}(\text{GlweKeySwitch}') = (\phi_{\text{in}} - \phi_{\text{out}}) \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \text{Var}(S_{\text{in}}^{[\phi_{\text{in}}]}) + \mathbb{E}^2(S_{\text{in}}^{[\phi_{\text{in}}]}) \right) \\ + \frac{\phi_{\text{in}} - \phi_{\text{out}}}{4} \text{Var}(S_{\text{in}}^{[\phi_{\text{in}}]}) + \ell(k_{\text{in}} - k_{\text{out}}) N \sigma_{\text{ksk}}^2 \frac{\beta^2 + 2}{12}. $$

The proof of this theorem can be found in the extended version of the paper.
## 5.2 Some Higher Level Applications

Through Sections 3.2, 4.2 and 5.1, we discussed the many advantages of using partial and/or shared randomness secret keys. We now discuss the advantages at a somewhat higher level.

**Key Switching Key Compression.** When one deploys an FHE instance using the shared randomness property, the total amount of public material for key switching is smaller than usual. Indeed, this only requires to generate all the shrinking key switching keys (Algorithm 5), from the largest key to the smallest. All of these shrinking key switching keys are way smaller than the sum of all the traditional key switching keys that are usually needed. Note that it is possible to provide more levels in some of the key switching keys, and only use the ones that are needed at a moment for a given noise constraint.

**Compressed Bootstrapping Key.** Similarly, with shared randomness secret keys, the amount of public material for bootstrapping keys can be reduced. A bootstrapping key is a list of GGSW ciphertexts, each one encrypting a secret key coefficient of the input LWE secret key. Then, giving the GGSW ciphertexts for the largest LWE secret key of the instance is enough. Whenever bootstrapping an LWE ciphertext with a smaller dimension is required, one will only use the first part of the bootstrapping key. In the same spirit, additional levels can be added, and only used when strictly needed.

**Easier Parameter Set Conversion.** In $[BBB^{+22}]$, the authors consider use-cases where there are a couple of coexisting parameter sets, and it is necessary to move from one to the other. Using shared (and partial) secret keys helps converting more efficiently ciphertexts between two (or more) parameter sets. This is due to the removing of some key switchings and limiting the noise growth.

**Multikey Compatibility.** Both the partial and shared randomness properties are preserved in the MK-FHE (such as $[KKL^{+22}, KMS22]$) and in threshold-FHE approaches. Indeed, summing two partial secret keys results in another partial secret key, and summing two pairs of shared randomness secret keys together results in a new pair of shared randomness secret keys. Those new secret keys could improve the performance of MK-FHE and threshold-FHE, which are in general less efficient than the ones of (single key) FHE, as well as reduce the total size of the public material.

**Other FHE Schemes.** Partial and shared randomness secret keys could be used in other FHE schemes such as FHEW [DM15] or NTRU-based schemes (such as $[BIP^{+22}]$). This types of keys could also be used in BFV [Bra12, FV12] or CKKS [CKKS17] when larger polynomials are required for the same modulus $q$, for instance.
**Combination With Fixed Hamming Weight.** Both partial and shared randomness secret keys could be instantiated with a fixed Hamming weight We do not explore this topic any further here.

**LWE Encryption Public Key With GLWE Material.** If one wants to take advantage of the FFT to encrypt fresh LWE ciphertexts with a secret key $\mathbf{s} \in \mathbb{Z}_q^n$, and/or shrink the size of ciphertexts with partial GLWE secret key, it is possible to provide a GLWE encryption public key for a partial GLWE secret key $\mathbf{S}^{[\phi=n]} \in \mathbb{R}_{q,N}^k$ such that its flattened version is actually $\mathbf{s}$. In this case, one uses GLWE encryption and applies a sample extract right after that to obtain the desired LWE ciphertext.

# 6 Parameters & Benchmarks

In this section, we describe how to generate FHE parameters for all our experiments. We use the procedure introduced in [BBB+22] to compare the different approaches. To demonstrate the impact of partial and/or shared randomness secret keys, we use the Atomic Pattern (AP) called CJP in [BBB+22] (the name coming from the paper [CJP21]). After recalling its definition, we explain how to optimize parameters for the different experiments and show the different improvements (both in computational time and size of public material) brought forward by each of the new procedures introduced in this paper.

Real life applications use additions and multiplications by public integers (i.e. a dot product) between two consecutive bootstrappings. Formally, given a list of ciphertexts $\{ct_i\}_{i \in [1, \alpha]} \in (\text{LWE}_{s_{in}})^\alpha$ (with independent noise values) and a list of integers $\{\omega_i\}_{i \in [1, \alpha]} \in \mathbb{Z}^\alpha$, one computes $\sum_{i=1}^\alpha \omega_i \cdot ct_i$. In that case, we have $\nu^2 = \sum_{i=1}^\alpha \omega_i^2$ and $\nu$ is used to fully describe the noise growth during a dot product following the formalization of [BBB+22]. In this paper, we set $\nu = 2^p$ where $p$ is the precision of the message. For every experiment below, the probability of failure is set to $p_{fail} \le 2^{-13.9}$. Note that with the FHE parameter generation process used in this paper, any other probability can be chosen. In what follows, we use the CJP atomic pattern which denotes the chaining of a dot product, a keyswitch and a PBS.

All of the experiments presented in this paper have been carried out on AWS with a m6i.metal instance Intel Xeon 8375C (Ice Lake) at 3.5 GHz, with 128 vCPUs and 512.0 GiB of memory using the TFHE-rs library [Zam22]<fnref n="2" />. In Supplementary Material E.2 (Tables 4, 5, 6 and 7), we give the parameter sets used for the experiments reported in Table 2 along with benchmarks and public material sizes.

## 6.1 Partial GLWE Secret Key

We conduct three experiments with partial GLWE secret keys (Definition 6) that are displayed in Table 1. This shows the cost estimated by the optimizer (divided by $10^6$) in function of the precision.

<footnote n="2">²https://github.com/zama-ai/tfhe-rs/tree/artifact_ccs_2024</footnote>
Our baseline is CJP. The first experiment focuses on the CJP atomic pattern where the GLWE secret key could be partial with a filling amount $\phi$. During optimization, we set $\phi$ to the minimum between $k \cdot N$ and the value $n_{\text{plateau}}$ discussed in limitation 2. As expected, this is mostly better with larger precisions, starting at $p = 6$ where the plateau is reached.

The second experiment considers the CJP atomic pattern where the traditional LWE-to-LWE key switch is replaced with the FFT-base LWE key switch introduced in Algorithm 1. During the optimization, we had to introduce new FHE parameters for this particular key switch: an input GLWE dimension $k_{\text{in}}$, an output GLWE dimension $k_{\text{out}}$ and a polynomial size $N_{\text{KS}}$. We observe a significant improvement for all precisions when using this key switch, but it is more visible with smaller precisions, between 1 and 6.

The third and last experiment is the combination of the two first ones: we allow the GLWE secret key to be partial (when the plateau is reached) and use the FFT-based LWE key switch (Algorithm 1). As expected, this last experiment outperforms the other two. We can see a significant improvement for all precisions.

Note that there is no way to build an LWE-to-LWE key switch based on the FFT without partial secret keys, so no comparison with our results can be done.

## 6.2 Shared Randomness Secret Keys

We conduct two experiments with shared randomness secret keys (Definition 9), and we display the results predicted by an optimizer in Table 1.

The first experiment is the CJP atomic pattern where we allow the secret keys to share their randomness using the shrinking LWE key switch described in Algorithm 5. We observe a significant improvement with small precisions, up to $p = 6$.

The second and last experiment is the CJP atomic pattern where we allow the secret keys to share their randomness, so we can use the 2-step stair LWE key switch from Algorithm 6. We see a significant improvement at all precisions. Note that if one tries to trivially have a 2-step stair key switch without any shared randomness, the computational cost is basically the same as in CJP.

<table><caption>Table 1: Comparison in terms of estimated execution time, between traditional CJP, our baseline, two variants of CJP based on shared randomness secret keys and three variants based on partial secret keys.</caption><thead><tr><th rowspan="2">Precision & 2-norm</th><th colspan="2">1</th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th><th colspan="2">6</th><th colspan="2">8</th><th colspan="2">10</th></tr><tr><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th><th>Cost</th><th>Gain</th></tr></thead><tbody><tr><td>CJP</td><td>31</td><td>-</td><td>42</td><td>-</td><td>63</td><td>-</td><td>78</td><td>-</td><td>118</td><td>-</td><td>347</td><td>-</td><td>2351</td><td>-</td><td>20813</td><td>-</td></tr><tr><td>Partial: BSK</td><td>31</td><td>-0%</td><td>42</td><td>-0%</td><td>63</td><td>-0%</td><td>78</td><td>-0%</td><td>118</td><td>-0%</td><td>318</td><td>-8%</td><td>1934</td><td>-18%</td><td>16449</td><td><b>-21%</b></td></tr><tr><td>Partial: FFT-KS</td><td>25</td><td>-18%</td><td>33</td><td>-21%</td><td>41</td><td><b>-35%</b></td><td>62</td><td>-21%</td><td>92</td><td>-22%</td><td>298</td><td>-14%</td><td>2053</td><td>-12%</td><td>18841</td><td>-9%</td></tr><tr><td>Partial: BSK + FFT-KS</td><td>25</td><td>-18%</td><td>33</td><td>-21%</td><td>41</td><td><b>-35%</b></td><td>62</td><td>-21%</td><td>92</td><td>-22%</td><td>285</td><td>-17%</td><td>1879</td><td>-20%</td><td>16426</td><td>-21%</td></tr><tr><td>Shared: Shrinking-KS</td><td>29</td><td>-9%</td><td>39</td><td>-8%</td><td>49</td><td><b>-23%</b></td><td>72</td><td>-8%</td><td>105</td><td>-11%</td><td>336</td><td>-3%</td><td>2331</td><td>-0.8%</td><td>20785</td><td>-0.1%</td></tr><tr><td>Shared: Stair-KS</td><td>27</td><td>-15%</td><td>35</td><td>-17%</td><td>42</td><td><b>-32%</b></td><td>66</td><td>-17%</td><td>94</td><td>-20%</td><td>316</td><td>-9%</td><td>2057</td><td>-12%</td><td>16624</td><td>-20%</td></tr></tbody></table>
## 6.3 Combining Both

We conduct two experiments with both partial (Definition 6) and shared randomness secret keys (Definition 9), we display the results in Table 2.

The first experiment is the CJP atomic pattern where we allow the secret keys to be partial and to share their randomness. We use the 2-step stair LWE key switch from Algorithm 6 and we allow the GLWE secret key to be partial when the plateau is reached.

The second and last experiment also focuses on the CJP atomic pattern where we allow secret keys to be partial and to share their randomness. We allow the GLWE secret key to be partial (when the plateau is reached), and use the FFT-based LWE key switch (Algorithm 7) since our secret keys also share randomness.

Both the stair key switch experiments and the FFT shrinking key switch experiment are faster than our baseline, and we have even better results with the FFT shrinking key switch than expected. Note that at precision $p = 3$ we have a 2.4 speed-up factor compared to the baseline.

Our new secret key generation also has the advantage to reduce the key sizes. For those experiments, we plot the size of the public material needed in Figure 2 in Supplementary Material, to demonstrate their benefit in this matter. For instance, the storage needed for the public material when $p = 3$ is going from approximately 105 MB with the CJP method, to 50 MB with the FFT-based approach.

<table><caption>Table 2: Comparison in terms of computational time (in ms) of the traditional CJP, our baseline, with two variants of CJP based on both partial secret keys and shared randomness secret keys.</caption><thead><tr><th rowspan="2">Precision & 2-norm</th><th colspan="2">1</th><th colspan="2">2</th><th colspan="2">3</th><th colspan="2">4</th><th colspan="2">5</th><th colspan="2">6</th><th colspan="2">8</th><th colspan="2">10</th></tr><tr><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th><th>Time</th><th>Gain</th></tr></thead><tbody><tr><td>CJP</td><td>5.43</td><td>-</td><td>8.75</td><td>-</td><td>12.2</td><td>-</td><td>12.6</td><td>-</td><td>20.0</td><td>-</td><td>55.6</td><td>-</td><td>415</td><td>-</td><td>4710</td><td>-</td></tr><tr><td>All + Stair-KS</td><td>3.78</td><td>-30%</td><td>6.28</td><td>-28%</td><td>6.22</td><td><b>-49%</b></td><td>9.35</td><td>-25%</td><td>13.8</td><td>-31%</td><td>44.3</td><td>-20%</td><td>323</td><td>-22%</td><td>3620</td><td>-23%</td></tr><tr><td>All + FFT shrinking-KS</td><td>3.27</td><td>-39%</td><td>5.32</td><td>-39%</td><td>5.12</td><td><b>-58%</b></td><td>7.38</td><td><b>-41%</b></td><td>11.0</td><td><b>-45%</b></td><td>41.1</td><td>-26%</td><td>306</td><td>-26%</td><td>3603</td><td>-23%</td></tr></tbody></table>

## 7 Conclusion

To sum up, the traditional way of generating GLWE secret keys leads to unnecessary computation, larger noise growth and bigger public material. In this paper we introduced two (as secure) new ways to generate GLWE secret keys: partial and/or shared randomness. The benefits are indeed non negligible as demonstrated in practical experiments covering a wide range of message precisions. In this paper, we also described several applications exploiting such secret keys.

As future work, optimizing the step number, the size and the decomposition parameters of the (shrinking) stair key switch seems promising. Also, it could be interesting to generalize our approaches to other secret key distributions, like ternary or Gaussian.
References

[ACPS09] Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In *Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings*, pages 595-618. Springer, 2009.

[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange-a new hope. In *USENIX security symposium*, volume 2016, 2016.

[AGVW17] Martin R Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the expected cost of solving usvp and applications to lwe. In *Advances in Cryptology-ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23*, pages 297-322. Springer, 2017.

[Alb17] Martin R Albrecht. On dual lattice attacks against small-secret lwe and parameter choices in helib and seal. In *Advances in Cryptology-EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30-May 4, 2017, Proceedings, Part II*, pages 103-129. Springer, 2017.

[APS15] Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. *Journal of Mathematical Cryptology*, 9(3):169-203, 2015.

[BBB$^{+22}$] Loris Bergerat, Anas Boudi, Quentin Bourgerie, Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Parameter optimization & larger precision for (t)fhe. 2022. https://eprint.iacr.org/2022/704.

[BGV12] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In *ITCS*, 2012.

[BIP$^{+22}$] Charlotte Bonte, Ilia Iliashenko, Jeongeun Park, Hilder V. L. Pereira, and Nigel P. Smart. FINAL: faster FHE instantiated with NTRU and LWE. In Shweta Agrawal and Dongdai Lin, editors, *Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part II*, volume 13792 of *Lecture Notes in Computer Science*, pages 188-215. Springer, 2022.
[BJRLW23] Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen. On the hardness of module learning with errors with short distributions. *Journal of Cryptology*, 36(1):1, 2023.

[BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. *Journal of the ACM (JACM)*, 50(4):506-519, 2003.

[BLNRL23] Olivier Bernard, Andrea Lesavourey, Tuong-Huy Nguyen, and Adeline Roux-Langlois. Log-s-unit lattices using explicit stickelberger generators to solve approx ideal-svp. In *Advances in Cryptology-ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part III*, pages 677-708. Springer, 2023.

[Bra12] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. *IACR Cryptology ePrint Archive*, 2012.

[BRL20] Olivier Bernard and Adeline Roux-Langlois. Twisted-phs: Using the product formula to solve approx-svp in ideal lattices. In *Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II*, pages 349-380. Springer, 2020.

[CDKS20] Hao Chen, Wei Dai, Miran Kim, and Yongsoo Song. Efficient homomorphic conversion between (ring) LWE ciphertexts. *IACR Cryptol. ePrint Arch.*, 2020.

[CDW17] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short stickelberger class relations and application to ideal-svp. In *Advances in Cryptology-EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30-May 4, 2017, Proceedings, Part I*, pages 324-348. Springer, 2017.

[CGGI20] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: fast fully homomorphic encryption over the torus. *J. Cryptol.*, 2020.

[CJL+20] Ilaria Chillotti, Marc Joye, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Concrete: Concrete operates on ciphertexts rapidly by extending TfhE. In *WAHC 2020*, 2020.

[CJP21] Ilaria Chillotti, Marc Joye, and Pascal Paillier. Programmable bootstrapping enables efficient homomorphic inference of deep neural networks. In *CSCML 2021*. Springer, 2021.
[CKKS17] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In *ASIACRYPT 2017*, 2017.

[CLOT21] Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for tfhe. In *ASIACRYPT 2021*. Springer, 2021.

[DM15] Léo Ducas and Daniele Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In *EUROCRYPT 2015*, 2015.

[DSDGR20] Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. Lwe with side information: attacks and concrete security estimation. In *Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II*, pages 329–358. Springer, 2020.

[DSGKS18] Dana Dachman-Soled, Huijing Gong, Mukul Kulkarni, and Aria Shahverdi. Partial key exposure in ring-lwe-based cryptosystems: Attacks and resilience. Cryptology ePrint Archive, Paper 2018/1068, 2018. https://eprint.iacr.org/2018/1068.

[FV12] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. *IACR Cryptology ePrint Archive*, 2012.

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In *STOC 2009*, 2009.

[GJS15] Qian Guo, Thomas Johansson, and Paul Stankovski. Coded-bkw: Solving lwe using lattice codes. In *Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I*, pages 23–42. Springer, 2015.

[GSW13] Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In *CRYPTO 2013*. Springer, 2013.

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Joe Buhler, editor, *Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings*, volume 1423 of *Lecture Notes in Computer Science*, pages 267–288. Springer, 1998.

[KF15] Paul Kirchner and Pierre-Alain Fouque. An improved bkw algorithm for lwe with applications to cryptography and lattices. In *Advances in Cryptology–CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I*, pages 43–62. Springer, 2015.
[KKL$^{+22}$] Taechan Kim, Hyesun Kwak, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. Asymptotically faster multi-key homomorphic encryption from homomorphic gadget decomposition. *IACR Cryptol. ePrint Arch.*, page 347, 2022.

[KMS22] Hyesun Kwak, Seonhong Min, and Yongsoo Song. Towards practical multi-key TFHE: parallelizable, key-compatible, quasi-linear complexity. *IACR Cryptol. ePrint Arch.*, page 1460, 2022.

[LMSS23] Changmin Lee, Seonhong Min, Jinyeong Seo, and Yongsoo Song. Faster tfhe bootstrapping with block binary keys. In *ACM ASIACCS 2023*, 2023.

[LNPS21] Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plançon, and Gre-gor Seiler. Shorter lattice-based group signatures via “almost free” en-cryption and other optimizations. In *International Conference on the Theory and Application of Cryptology and Information Security*, pages 218–248. Springer, 2021.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In *EUROCRYPT 2010*. Springer, 2010.

[LS15] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. *Designs, Codes and Cryptography*, 75(3):565–599, 2015.

[LY23] Kang Hoon Lee and Ji Won Yoon. Discretization error reduction for high precision torus fully homomorphic encryption. In *Public-Key Cryptography–PKC 2023: 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7–10, 2023, Proceedings, Part II*, pages 33–62. Springer, 2023.

[MR09] Daniele Micciancio and Oded Regev. Lattice-based cryptography. *Post-quantum cryptography*, pages 147–191, 2009.

[PMHS19] Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé. Approx-svp in ideal lattices with pre-processing. In *Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part II 38*, pages 685–716. Springer, 2019.

[PV21] Eamonn W Postlethwaite and Fernando Virdia. On the success proba-bility of solving unique svp via bkz. In *Public-Key Cryptography–PKC 2021: 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10–13, 2021, Proceedings, Part I*, pages 68–98. Springer, 2021.
[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In *STOC 2005*. ACM, 2005.

[SE94] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. *Mathematical programming*, 66:181–199, 1994.

[SSTX09] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In *ASIACRYPT 2009*. Springer, 2009.

[Zam22] Zama. TFHE-rs: A Pure Rust Implementation of the TFHE Scheme for Boolean and Integer Arithmetics Over Encrypted Data, 2022. https://github.com/zama-ai/tfhe-rs.
# Supplementary Material

## A Comparison between usual secret key types in FHE

**Secret Keys With Fixed Hamming Weight (FHW).** A fixed-Hamming-weight (FHW) binary (resp. ternary) GLWE secret key of hamming weight $h \in \mathbb{N}$ is a GLWE secret key such that its polynomial coefficients are in $\{0,1\}$ (resp. $\{-1,0,1\}$) and contains exactly $h$ non-zero coefficients. We note these two distributions $\mathcal{FHW}(h, \{0,1\})$ and $\mathcal{FHW}(h, \{-1,0,1\})$ respectively. Such keys come along with public knowledge: the dimension $k$, the polynomial ring $R_{q,N}$ (including the polynomial degree $N$), the distribution (binary or ternary), the hamming weight $h$. This type of secret keys is in use in FHE schemes such as CKKS [CKKS17], because it offers a smaller value for the worst-case noise growth. Table 3 summarizes public knowledge for these different secret key types.

## B Proofs

In this section we provide some useful proofs.

**Proof 7 (Correctness for Constant Sample Extraction)** As in algorithm 2, we consider a GLWE ciphertext $CT_{in} := (A_0, \dots, A_{k-1}, B) \in \text{GLWE}_{\mathcal{S}[\phi]}(P) \subseteq R_{q,N}^{k+1}$ where $P = \sum_{i=0}^{N-1} p_i X^i \in R_{q,N}$ and for all $0 \le i \le k-1$ we have $A_i = \sum_{j=0}^{N-1} a_{i,j} X^j$ and $B = \sum_{j=0}^{N-1} b_j X^j$. The GLWE secret key is noted $\mathcal{S}^{[\phi]} = (S_0, \dots, S_{k-1}) \in R_{q,N}^k$ and follows Definition 6. By definition of GLWE ciphertexts, it means that it exists an error polynomial $E = \sum_{i=0}^{N-1} e_i X^i \in R_{q,N}$ such that $B - \sum_{i=0}^{k-1} A_i \cdot S_i = P + E$.

Following Algorithm 2, the constant sample extraction outputs the following LWE ciphertext: $ct_{out} = (a_{out,0}, \dots, a_{out,\phi-1}, b_{out}) \in \text{LWE}_{\bar{s}}(p_0) \subseteq \mathbb{Z}_q^{\phi+1}$ encrypted under the LWE secret key $\bar{s} = (\bar{s}_0, \dots, \bar{s}_{\phi-1}) \in \mathbb{Z}_q^{\phi}$ obtained as defined in Definition 7.

First we define two index functions, the first one is $\iota: i \mapsto (\lfloor \frac{i}{N} \rfloor, i \bmod N)$ and the second one is $\tilde{\iota}: i \mapsto (\lfloor \frac{i}{N} \rfloor, (N-i) \bmod N)$. We also need to define a last function $\gamma: i \mapsto 1 - ((i \bmod N) == 0)$
$$
\begin{align}
b_{\text{out}} - \sum_{i=0}^{\phi-1} a_{\text{out},i} \cdot \bar{s}_i &= b_0 - \sum_{i=0}^{\phi-1} a_{\text{out},i} \cdot \bar{s}_i - \underbrace{\sum_{i=\phi}^{kN-1} (-1)^{\gamma(i)} \cdot a_{\tilde{l}(i)} \cdot s_{\iota(i)}}_{\text{null since all } s_{\iota(i)}=0 \text{ because it is a partial key}} \nonumber \\
&= b_0 - \sum_{i=0}^{\phi-1} \underbrace{(-1)^{\gamma(i)} \cdot a_{\tilde{l}(i)} \cdot s_{\iota(i)}}_{\text{lines 2 and 3 in Algorithm 2}} - \sum_{i=\phi}^{kN-1} (-1)^{\gamma(i)} \cdot a_{\tilde{l}(i)} \cdot s_{\iota(i)} \tag{1} \\
&= b_0 - \sum_{i=0}^{kN-1} (-1)^{\gamma(i)} \cdot a_{\tilde{l}(i)} \cdot s_{\iota(i)} = b_0 - \sum_{i=0}^{k-1} \sum_{j=0}^{N-1} a_{i,N-j} \cdot s_{i,j} \nonumber \\
&= b_0 - \sum_{i=0}^{k-1} \sum_{j=0}^{N-1} a_{i,(N-j) \bmod N} X^{(N-j) \bmod N} \cdot s_{i,j} X^j \nonumber
\end{align}
$$

This quantity is what we have on the constant term of the polynomial resulting from the de-
cryption of $\text{CT}_{\text{in}}$:

$$
\begin{align}
B - \sum_{i=0}^{k-1} A_i \cdot S_i &= B - \sum_{i=0}^{k-1} \sum_{j=0}^{N-1} \sum_{j'=0}^{N-1} a_{i,j} X^j \cdot s_{i,j'} X^{j'} \nonumber \\
&= X^0 \cdot \left( b_0 - \sum_{i=0}^{k-1} \sum_{j=0}^{N-1} a_{i,(N-j) \bmod N} X^{(N-j) \bmod N} \cdot s_{i,j} X^j \right) \tag{2} \\
&\qquad + X^1 \cdot (b_1 - \dots) + \dots + X^{N-1} \cdot (b_{N-1} - \dots) \nonumber \\
&\underbrace{\qquad \qquad \qquad \qquad \text{constant coefficient with the same quantity}} \nonumber \\
&\underbrace{\qquad \qquad \qquad \qquad \text{non-constant coefficients}} \nonumber
\end{align}
$$

<figure><img src="image_3.png" /></figure>

**Proof 8 (Correctness for Sample Extraction)** We follow the context and inputs of Algorithm 11. It is trivial to show that the $\alpha$-th coefficient of the decryption of $\text{CT}_{\text{in}}$ is equal to what is in the constant coefficient of $X^{-\alpha} \cdot \text{CT}_{\text{in}}$.

**Proof 9 (Theorem 2)** *The inputs of a GLWE-to-GLWE key switching (Algorithm 9) are:*

* The input GLWE ciphertext: $\text{CT}_{\text{in}} = (\mathbf{A}_{\text{in}}, B_{\text{in}}) \in \text{GLWE}_{S_{\text{in}}^{[\phi_{\text{in}}]}}(\Delta \cdot M) \subseteq R_{q,N}^{k_{\text{in}}+1}$, where $B_{\text{in}} = \sum_{i=0}^{k_{\text{in}}-1} A_{\text{in},i} \cdot S_{\text{in},i} + \Delta \cdot M + E_{\text{in}}$, $A_{\text{in},i} = \sum_{j=0}^{N-1} a_{i,j} \cdot X^j \leftarrow \mathcal{U}(R_{q,N})$ for all $i \in [0, k]$ and $E_{\text{in}} = \sum_{j=0}^{N-1} e_j \cdot X^j$, and $e_j \leftarrow \mathcal{N}_{\sigma_{\text{in}}^2}$ for all $j \in [0, N-1]$.

* The key switch key: $\text{KSK} = (\text{KSK}_0, \dots, \text{KSK}_{k_{\text{in}}-1})$, where $\text{KSK}_i \in \text{GLEV}_{S_{\text{out}}^{[\phi_{\text{out}}]}}^{(\beta, \ell)}(S_{\text{in},i}) = (\text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta}S_{\text{in},i}), \dots, \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^\ell}S_{\text{in},i}))$ for all $0 \le i < k_{\text{in}}$. We note by $\text{KSK}_{i,j} = (\mathbf{A}_{i,j}, B_{i,j}) \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^{j+1}}S_{\text{in},i})$, for all $0 \le i < k_{\text{in}}$ and for all $0 \le j < \ell$, where $B_{i,j} = \sum_{\tau=0}^{k_{\text{out}}-1} A_{i,j,\tau} \cdot S_{\text{out},\tau}^{[\phi_{\text{out}}]} + \frac{q}{\beta^{j+1}}S_{\text{in},i} + E_{\text{ksk},i,j}$, and $E_{\text{ksk},i,j} = \sum_{\tau=0}^{N-1} e_{\text{ksk},i,j,\tau} \cdot X^\tau$ and $e_{\text{ksk},i,j,\tau} \leftarrow \mathcal{N}_{\sigma_{\text{ksk}}^2}$.
The output of this algorithm is: $CT_{out} = (\mathbf{A}_{out}, B_{out}) \in \text{GLWE}_{\mathbf{S}_{\text{out}}^{[\phi_{out}]}}(\Delta \cdot M) \subseteq R_{q,N}^{k_{out}+1}$. By definition, in the decomposition described in Supplementary Material C, we have that $\text{Dec}^{(\beta, \ell)}(A_{\text{in},i}) = (\tilde{A}_{\text{in},i,0}, \dots, \tilde{A}_{\text{in},i,\ell-1})$ such that $\tilde{A}_{\text{in},i} = \sum_{j=0}^{\ell-1} \frac{q}{\beta^{j+1}} \tilde{A}_{\text{in},i,j}$, for all $0 \le i < k_{\text{in}}$.

Let define $\bar{A}_{\text{in},i} = A_{\text{in},i} - \tilde{A}_{\text{in},i}$, $|\bar{a}_{i,\tau}| = |a_{i,\tau} - \tilde{a}_{i,\tau}| < \frac{q}{2\beta^\ell}$, $\bar{a}_{i,\tau} \in \left[ \frac{-q}{2\beta^\ell}, \frac{q}{2\beta^\ell} \right]$ for all $0 \le \tau < N$. So we have that their expectations and variances are respectively $\mathbb{E}(\bar{a}_{i,\tau}) = -\frac{1}{2}$, $\text{Var}(\bar{a}_{i,\tau}) = \frac{q^2}{12\beta^{2\ell}} - \frac{1}{12}$, $\mathbb{E}(\tilde{a}_{i,\tau}) = -\frac{1}{2}$ and $\text{Var}(\tilde{a}_{i,\tau}) = \frac{\beta^2-1}{12}$.

Now, we can decrypt:

$$ 
\begin{aligned}
B_{\text{out}} - \langle \mathbf{A}_{\text{out}}, \mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]} \rangle &= \langle (\mathbf{A}_{\text{out}}, B_{\text{out}}), (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= \left\langle (0, B_{\text{in}}) - \sum_{i=0}^{k_{\text{in}}-1} \text{Dec}^{(\beta, \ell)}(A_{\text{in},i}) \cdot \text{KSK}_i, (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \right\rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \langle \text{KSK}_{i,j}, (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \left( \frac{q}{\beta^{j+1}} S_{\text{in},i} + E_{\text{ksk},i,j} \right) \\
&= B_{\text{in}} - \underbrace{\sum_{i=0}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} S_{\text{in},i}}_{(I)} - \underbrace{\sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{\text{ksk},i,j}}_{(II)}
\end{aligned}
$$

Now let's focus on the $w^{th}$ coefficient of part (I):

$$ 
\begin{aligned}
b_{\text{in},w} - \sum_{i=0}^{k_{\text{in}}-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{\text{in},i,w-\tau} \cdot s_{\text{in},i,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{\text{in},i,N+w-\tau} \cdot s_{\text{in},i,\tau} \right) \\
&= b_{\text{in},w} - \sum_{i=0}^{k_{\text{in}}-1} \left( \sum_{\tau=0}^{w} (a_{\text{in},i,w-\tau} - \bar{a}_{\text{in},i,w-\tau}) \cdot s_{\text{in},i,\tau} \right. \\
& \qquad \left. - \sum_{\tau=w+1}^{N-1} (a_{\text{in},i,N+w-\tau} - \bar{a}_{\text{in},i,N+w-\tau}) \cdot s_{\text{in},i,\tau} \right) \\
&= \Delta m_w + e_w + \sum_{i=0}^{k_{\text{in}}-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{\text{in},i,w-\tau} \cdot s_{\text{in},i,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{\text{in},i,N+w-\tau} \cdot s_{\text{in},i,\tau} \right)
\end{aligned}
$$

Now let's focus on the $w^{th}$ coefficient of part (II):

$$ \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{\text{in},i,j,w-\tau} \cdot e_{\text{ksk},i,j,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{\text{in},i,j,N+w-\tau} \cdot e_{\text{ksk},i,j,\tau} \right) $$

We can now isolate the output error for the $w^{th}$ coefficient and remove the message
coefficient. We obtain that the output error is:

$$e'_w = e_w + \underbrace{\sum_{i=0}^{k_{in}-1} \left( \sum_{\tau=0}^{w} \bar{a}_{in,i,w-\tau} \cdot s_{in,i,\tau} - \sum_{\tau=w+1}^{N-1} \bar{a}_{in,i,N+w-\tau} \cdot s_{in,i,\tau} \right)}_{(*)} \\ + \sum_{i=0}^{k_{in}-1} \sum_{j=0}^{\ell-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{in,i,j,w-\tau} \cdot e_{\text{ksk},i,j,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{in,i,j,N+w-\tau} \cdot e_{\text{ksk},i,j,\tau} \right)$$

Observe that in the term (*) there are $k_{in}N - \phi_{in}$ terms of type $\bar{a}_{in,i,\cdot} \cdot s_{in,i,\cdot}$ that are equal to 0. So we have:

$$\begin{aligned} \mathrm{Var}(e'_w) &= \mathrm{Var}(e_w) + \phi_{\mathrm{in}} \cdot \mathrm{Var}(\bar{a}_{\mathrm{in},i,\cdot} \cdot s_{\mathrm{in},i,\cdot}) + k_{\mathrm{in}} \cdot \ell \cdot N \cdot \mathrm{Var}(\tilde{a}_{\mathrm{in},i,j,\cdot} \cdot e_{\mathrm{ksk},i,j,\cdot}) \\ &= \sigma_{\mathrm{in}}^2 + \phi_{\mathrm{in}}(\mathrm{Var}(\bar{a}_{\mathrm{in},i,\cdot}) \mathrm{Var}(s_{\mathrm{in},i,\cdot}) + \mathrm{Var}(\bar{a}_{\mathrm{in},i,\cdot}) \mathbb{E}^2(s_{\mathrm{in},i,\cdot}) \\ &\quad + \mathbb{E}^2(\bar{a}_{\mathrm{in},i,\cdot}) \mathrm{Var}(s_{\mathrm{in},i,\cdot}) \\ &\quad + \ell k_{\mathrm{in}} N (\mathrm{Var}(\tilde{a}_{\mathrm{in},i,j,\cdot}) \mathrm{Var}(e_{\mathrm{ksk},i,j,\cdot}) + \mathbb{E}^2(\tilde{a}_{\mathrm{in},i,j,\cdot}) \mathrm{Var}(e_{\mathrm{ksk},i,j,\cdot}) \\ &\quad + \mathrm{Var}(\tilde{a}_{\mathrm{in},i,j,\cdot}) \mathbb{E}^2(e_{\mathrm{ksk},i,j,\cdot})) \\ &= \sigma_{\mathrm{in}}^2 + \phi_{\mathrm{in}} \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \mathrm{Var}(\mathbf{S}_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \mathbb{E}^2(\mathbf{S}_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right) \\ &\quad + \frac{\phi_{\mathrm{in}}}{4} \mathrm{Var}(\mathbf{S}_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \ell k_{\mathrm{in}} N \frac{\beta^2 + 2}{12} \sigma_{\mathrm{ksk}}^2. \end{aligned}$$

**Proof 10 (Theorem 3)** This proof is similar to the proof proposed for the key switch with partial key (proof 9).

The inputs of secret-product GLWE key switch (Algorithm 10) are:

* The input GLWE ciphertext: $\mathrm{CT}_{\mathrm{in}} = (\mathbf{A}_{\mathrm{in}}, \mathbf{B}_{\mathrm{in}}) \in \mathrm{GLWE}_{\mathbf{S}_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}}(\Delta \cdot M_1) \subseteq \mathbf{R}_{q,N}^{k_{\mathrm{in}}+1}$, where $\mathbf{B}_{\mathrm{in}} = \sum_{i=0}^{k_{\mathrm{in}}-1} \mathbf{A}_{\mathrm{in},i} \cdot \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]} + \Delta \cdot M_1 + \mathbf{E}_{\mathrm{in}}$, $\mathbf{A}_{\mathrm{in},i} = \sum_{j=0}^{k-1} a_{i,j} \cdot X^j \leftarrow \mathcal{U}(R_{q,N})$ for all $i \in [0, k]$ and $\mathbf{E}_{\mathrm{in}} = \sum_{j=0}^{k-1} e_j \cdot X^j$, and $e_j \leftarrow \mathcal{N}_{\sigma_{\mathrm{in}}^2}$ for all $j \in [0, N-1]$.

* The secret product key switch key: $\mathrm{KSK} = (\mathrm{KSK}_0, \dots, \mathrm{KSK}_{k_{\mathrm{in}}})$, where $\mathrm{KSK}_i \in \mathrm{GLEV}_{\mathbf{S}_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}}^{(\beta, \ell)}(-M_2 \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]}) = (\mathrm{GLWE}_{\mathbf{S}_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}}(-\frac{qM_2}{\beta} \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]}), \dots, \mathrm{GLWE}_{\mathbf{S}_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}}(-\frac{qM_2}{\beta^\ell} \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]})$ for all $0 \le i \le k_{\mathrm{in}}$ (for this proof, we define $\mathbf{S}_{k_{\mathrm{in}}} = -1$). We note by $\mathrm{KSK}_{i,j} = (\mathbf{A}_{i,j}, \mathbf{B}_{i,j}) \in \mathrm{GLWE}_{\mathbf{S}_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}}(-\frac{qM_2}{\beta^{j+1}} \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]})$, for all $0 \le i < k_{\mathrm{in}}$ and for all $0 \le j < \ell$, where $\mathbf{B}_{i,j} = \sum_{\tau=0}^{k_{\mathrm{out}}-1} \mathbf{A}_{i,j,\tau} \cdot \mathbf{S}_{\mathrm{out},\tau}^{[\phi_{\mathrm{out}}]} + \frac{qM_2}{\beta^{j+1}} \mathbf{S}_{\mathrm{in},i}^{[\phi_{\mathrm{in}}]} + \mathbf{E}_{\mathrm{ksk},i,j}$, and $\mathbf{E}_{\mathrm{ksk},i,j} = \sum_{\tau=0}^{N-1} e_{\mathrm{ksk},i,j,\tau} \cdot X^\tau$ and $e_{\mathrm{ksk},i,j,m} \leftarrow \mathcal{N}_{\sigma_{\mathrm{ksk}}^2}$.

In output we obtain: $\mathrm{CT}_{\mathrm{out}} = (\mathbf{A}_{\mathrm{out}}, \mathbf{B}_{\mathrm{out}}) \in \mathrm{GLWE}_{\mathbf{S}_{\mathrm{out}}^{[\phi_{\mathrm{out}}]}}(\Delta \cdot M_1 \cdot M_2) \subseteq \mathbf{R}_{q,N}^{k_{\mathrm{out}}+1}$.

By definition, for any random polynomial $\mathbf{A}_i$, we have $\mathbf{A}_i = \sum_{j=0}^{N-1} a_{i,j} \cdot X^j$ where $a_{i,j} \sim \mathcal{U}(\mathbb{Z}_q)$, ($a_{i,j} \in [\frac{-q}{2}, \frac{q}{2}]$).

By definition, for the decomposition (describe in Annex C), we have $\mathrm{Dec}^{(\beta, \ell)}(\mathbf{A}_i) = (\tilde{\mathbf{A}}_{i,0}, \dots, \tilde{\mathbf{A}}_{i,\ell-1})$ such that $\tilde{\mathbf{A}}_i = \sum_{j=0}^{\ell-1} \frac{q}{\beta^{j+1}} \tilde{\mathbf{A}}_{i,j}$.

Let define $\tilde{\mathbf{A}}_i = |\mathbf{A}_i - \tilde{\mathbf{A}}_i|$, $\mathbf{a}_{i,j} = |a_{i,j} - \tilde{a}_{i,j}| < \frac{q}{2\beta^\ell}$; $\tilde{\mathbf{a}}_{i,j} \in [\frac{-q}{2\beta^\ell}, \frac{q}{2\beta^\ell}]$. Finally we obtain: $\mathbb{E}(\tilde{\mathbf{a}}_i) = -\frac{1}{2}$; $\mathrm{Var}(\tilde{\mathbf{a}}_i) = \frac{q^2}{12\beta^{2\ell}} - \frac{1}{12}$; $\mathbb{E}(\tilde{\mathbf{a}}_{i,j}) = -\frac{1}{2}$; $\mathrm{Var}(\tilde{\mathbf{a}}_i) = \frac{\beta^2-1}{12}$.

As $\mathbf{B}_{\mathrm{in}}$ is seen as an uniform polynomial, we obtain the same results for the variance and the expectation for $\tilde{\mathbf{B}}_{\mathrm{in}}$ (resp. $\tilde{\mathbf{B}}_{\mathrm{in}}$) than $\tilde{\mathbf{A}}_i$ (Resp. $\tilde{\mathbf{A}}_i$). In the next calculations, $\tilde{\mathbf{B}}_{\mathrm{in},j} \cdot \mathbf{E}_j$ will be write as $-\tilde{\mathbf{A}}_{\mathrm{in},k_{\mathrm{in}},j} \cdot \mathbf{E}_{k_{\mathrm{in},j}}$.
Now, we can compute the decryption:

$$
\begin{align*}
B_{\text{out}} - \langle \mathbf{A}_{\text{out}}, \mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]} \rangle &= \langle (\mathbf{A}_{\text{out}}, B_{\text{out}}); (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= \langle \mathbf{Dec}^{(\beta, \ell)} (B_{\text{in}}) \cdot \text{KSK}_{k_{\text{in}}} + \sum_{i=0}^{k_{\text{in}}-1} \mathbf{Dec}^{(\beta, \ell)} (A_{\text{in},i}) \cdot \text{KSK}_i; (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= M_2 \left( \tilde{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} \cdot S_{\text{in},i} \right) - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{i,j} \\
&= M_2 \left( \Delta M_1 + E_{\text{in}} + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \bar{A}_{\text{in},i} \cdot S_{\text{in},i} \right) - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \bar{A}_{\text{in},i,j} \cdot E_{i,j} \\
&= \Delta M_2 \cdot M_1 + M_2 \left( E_{\text{in}} + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \bar{A}_{\text{in},i} \cdot S_{\text{in},i} \right) - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \bar{A}_{\text{in},i,j} \cdot E_{i,j}
\end{align*}
$$

By following the same idea as the proof for the key switch (proof 9), we can isolate the noise and compute his variance. We obtain:

$$
\begin{align*}
\mathrm{Var} \left( M_2 \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \tilde{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) - \sum_{i=0}^{k_{\mathrm{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\mathrm{in},i,j} \cdot E_{i,j} \right) \\
= \|M_2\|_2^2 \cdot \mathrm{Var} \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \tilde{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) + \mathrm{Var} \left( \sum_{i=0}^{k_{\mathrm{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\mathrm{in},i,j} \cdot E_{i,j} \right)
\end{align*}
$$

where

$$
\begin{align*}
\mathrm{Var} \left( E + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} \cdot S_{\text{in},i} \right) \\
&= \sigma_{\text{in}}^2 + \left( \frac{q^2}{12\beta^2\ell} - \frac{1}{12} \right) + \phi_{\text{in}} \left( \frac{q^2}{12\beta^2\ell} - \frac{1}{12} \right) \left( \mathrm{Var}(S_{\text{in}}^{[\phi_{\text{in}}]}) + \mathbb{E}^2(S_{\text{in}}^{[\phi_{\text{in}}]}) \right) + \frac{\phi_{\text{in}}}{4} \mathrm{Var}(S_{\text{in}}^{[\phi_{\text{in}}]}) \\
&= \sigma_{\text{in}}^2 + \left( \frac{q^2 - \beta^2\ell}{12\beta^2\ell} \right) \left( 1 + \phi_{\text{in}} \left( \mathrm{Var}(S_{\text{in}}^{[\phi_{\text{in}}]}) + \mathbb{E}^2(S_{\text{in}}^{[\phi_{\text{in}}]}) \right) \right) + \frac{\phi_{\text{in}}}{4} \mathrm{Var}(S_{\text{in}}^{[\phi_{\text{in}}]})
\end{align*}
$$

and

$$
\mathrm{Var} \left( \sum_{i=0}^{k_{\mathrm{in}}} \sum_{j=0}^{\ell-1} \tilde{A}_{\mathrm{in},i,j} \cdot E_{i,j} \right) = \ell(k_{\mathrm{in}} + 1) N \sigma_{\mathrm{KSK}}^2 \frac{\beta^2 + 2}{12}
$$

**Proof 11 (Noise Eternal Product in Bootstrapping)** *The Theorem 2 gave us the following noise for an external product:*

$$
\begin{align*}
\mathrm{Var} \left( M_2 \left( E + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} \cdot S_{\text{in},i} \right) - \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{i,j} \right) \\
= \|M_2\|_2^2 \cdot \mathrm{Var} \left( E + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} \cdot S_{\text{in},i} \right) + \mathrm{Var} \left( \sum_{i=0}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{i,j} \right)
\end{align*}
$$
where

$$
\begin{align*}
& \mathrm{Var} \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) \\
&= \sigma_{\mathrm{in}}^2 + \left( \frac{q^2}{12\beta^{2\ell}} - \frac{1}{12} \right) + \phi_{\mathrm{in}} \left( \frac{q^2}{12\beta^{2\ell}} - \frac{1}{12} \right) \left( \mathrm{Var} \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right) + \mathbb{E}^2 \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right) \right) + \frac{\phi_{\mathrm{in}}}{4} \mathrm{Var} \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right) \\
&= \sigma_{\mathrm{in}}^2 + \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( 1 + \phi_{\mathrm{in}} \left( \mathrm{Var} \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right) + \mathbb{E}^2 \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right) \right) \right) + \frac{\phi_{\mathrm{in}}}{4} \mathrm{Var} \left( S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]} \right)
\end{align*}
$$

and

$$
\mathrm{Var} \left( \sum_{i=0}^{k_{\mathrm{in}}} \sum_{j=0}^{\ell-1} \tilde{A}_{\mathrm{in},i,j} \cdot E_{i,j} \right) = \ell(k_{\mathrm{in}} + 1) N \sigma_{\mathrm{in}}^2 \frac{\beta^2 + 2}{12}
$$

In TFHE, we use binary key to perform the bootstrap. So we have $M \in \{0, 1\}$ which represent a bit of the binary key. $\mathrm{Var}(M_2) = \frac{1}{4}$ and $\mathbb{E}(M_2) = \frac{1}{2}$. Let focus on the part with the message:

$$
\begin{align*}
& \mathrm{Var} \left( M_2 \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) \right) \\
&= (\mathrm{Var}(M_2) + \mathbb{E}^2(M_2)) \mathrm{Var} \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) \\
&\quad + \mathrm{Var}(M_2) \mathbb{E}^2 \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) \\
&= \frac{1}{2} \mathrm{Var} \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right) \\
&\quad + \frac{1}{4} \mathbb{E}^2 \left( E + \bar{B}_{\mathrm{in}} - \sum_{i=0}^{k_{\mathrm{in}}-1} \bar{A}_{\mathrm{in},i} \cdot S_{\mathrm{in},i} \right)
\end{align*}
$$

We have:

$$
\begin{align*}
\mathbb{E}^2 \left( E + \bar{B}_{\text{in}} - \sum_{i=0}^{k_{\text{in}}-1} \bar{A}_{\text{in},i} \cdot S_{\text{in},i} \right) &= \left( \mathbb{E}(E) + \mathbb{E}(\bar{B}_{\text{in}}) - \mathbb{E} \left( \sum_{i=0}^{k_{\text{in}}-1} \bar{A}_{\text{in},i} \cdot S_{\text{in},i} \right) \right)^2 \\
&= \left( 0 - \frac{1}{2} - \phi_{\text{in}} \mathbb{E} (\bar{a}_{\text{in},i}) \mathbb{E} (s_{\text{in},i}) \right)^2 \\
&= \frac{1}{4} \left( -1 + \phi_{\text{in}} \mathbb{E} (S_{\text{in}}^{[\phi_{\text{in}}]}) \right)^2
\end{align*}
$$

Finally, for each coefficient after one external product in the bootstrapping, we obtain the following formula for the noise variance:

$$
\begin{align*}
& \frac{\sigma_{\text{in}}^2}{2} + \left( \frac{q^2 - \beta^{2\ell}}{24\beta^{2\ell}} \right) \left( 1 + \phi_{\text{in}} \left( \text{Var}\left(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}\right) + \mathbb{E}^2\left(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}\right)\right) \right) + \frac{\phi_{\text{in}}}{8} \text{Var}\left(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}\right) \\
& \qquad + \frac{1}{16} \left( -1 + \phi_{\text{in}} \mathbb{E}\left(\mathbf{S}_{\text{in}}^{[\phi_{\text{in}}]}\right)^2 \right) + \ell(k_{\text{in}} + 1) N \sigma_{\text{in}}^2 \frac{\beta^2 + 2}{12}
\end{align*}
$$
**Proof 12 (Theorem 8)** The proof of this theorem follows the same footprint as the other key switching proofs presented in this paper (e.g., Theorem 2). We generalize the proof of this theorem to the GLWE case: the LWE result presented in the theorem follows by taking $k_0 = n_0$, $k_1 = n_1$ and $N = 1$.

We consider two shared randomness GLWE secret keys $\mathbf{S}^{(0)} \prec \mathbf{S}^{(1)}$ with $\mathbf{S}^{(0)} = (S_0^{(0)}, \dots, S_{k_0-1}^{(0)}) \in R_{q,N}^{k_0}$, $\mathbf{S}^{(1)} = (S_0^{(1)}, \dots, S_{k_1-1}^{(1)}) \in R_{q,N}^{k_1}$, $1 < k_0 < k_1$ and $S_i^{(1)} = S_i^{(0)}$ for all $0 \le i < k_0$. We take in input:

* A GLWE ciphertext: $\text{CT}_{\text{in}} = (\mathbf{A}_{\text{in}}, B_{\text{in}}) \in \text{GLWE}_{\mathbf{S}^{(1)}}(\Delta M) \subseteq R_{q,N}^{k_1+1}$, where $B_{\text{in}} = \sum_{i=0}^{k_1-1} A_{\text{in},i} \cdot S_i^{(1)} + \Delta M + E_{\text{in}}$, $A_{\text{in},i} = \sum_{j=0}^{N-1} a_{i,j} \cdot X^j \leftarrow \mathcal{U}(R_{q,N})$ for all $i \in [0, k]$ and $E_{\text{in}} = \sum_{j=0}^{N-1} e_j \cdot X^j$, and $e_j \leftarrow \mathcal{N}_{\sigma_1^2}$ for all $j \in [0, N-1]$.

* The key switching key: $\text{KSK} = (\text{KSK}_0, \dots, \text{KSK}_{k_1-k_0-1})$, where $\text{KSK}_i \in \text{GLEV}_{\mathbf{S}^{(0)}}^{(\beta, \ell)}(S_{k_0+i}^{(1)}) = (\text{GLWE}_{\mathbf{S}^{(0)}}(\frac{q}{\beta}S_{k_0+i}^{(1)}), \dots, \text{GLWE}_{\mathbf{S}^{(0)}}(\frac{q}{\beta^\ell}S_{k_0+i}^{(1)})$ for all $0 \le i < k_1$. We note by $\text{KSK}_{i,j} = (\mathbf{A}_{i,j}, B_{i,j}) \in \text{GLWE}_{\mathbf{S}^{(0)}}(\frac{q}{\beta^{j+1}}S_{k_0+i}^{(1)})$, for all $0 \le i < k_1$ and for all $0 \le j < \ell$, where $B_{i,j} = \sum_{\tau=0}^{k_0-1} A_{i,j,\tau} \cdot \mathbf{S}_\tau^{(0)} + \frac{q}{\beta^{j+1}}S_{k_0+i}^{(1)} + E_{\text{ksk},i,j}$, and $E_{\text{ksk},i,j} = \sum_{\tau=0}^{N-1} e_{\text{ksk},i,j,\tau} \cdot X^\tau$ and $e_{\text{ksk},i,j,\tau} \leftarrow \mathcal{N}_{\sigma_{\text{ksk}}^2}$.

The output of this algorithm is computed as:

$$ (A_{\text{in},0}, \dots, A_{\text{in},k_0-1}, B_{\text{in}}) - \sum_{i=0}^{k_1-k_0-1} \text{Dec}^{(\beta, \ell)}(A_{\text{in},k_0+i}) \cdot \text{KSK}_i \in \text{GLWE}_{\mathbf{S}^{(0)}}(\Delta M) \subseteq R_{q,N}^{k_0+1} $$

By definition, in the decomposition described in Supplementary Material C, we have that $\text{Dec}^{(\beta, \ell)}(A_{\text{in},i}) = (\tilde{A}_{\text{in},i,0}, \dots, \tilde{A}_{\text{in},i,\ell-1})$ such that $\tilde{A}_{\text{in},i} = \sum_{j=0}^{\ell-1} \frac{q}{\beta^{j+1}} \tilde{A}_{\text{in},i,j}$, for all $k_0 \le i < k_1$.

Let define $\tilde{A}_{\text{in},i} = A_{\text{in},i} - \tilde{A}_{\text{in},i}$, $|\tilde{a}_{i,\tau}| = |a_{i,\tau} - \tilde{a}_{i,\tau}| < \frac{q}{2\beta^\ell}$, $\tilde{a}_{i,\tau} \in [\frac{-q}{2\beta^\ell}, \frac{q}{2\beta^\ell}]$ for all $0 \le \tau < N$. So we have that their expectations and variances are respectively $\mathbb{E}(\tilde{a}_{i,\tau}) = -\frac{1}{2}$, $\text{Var}(\tilde{a}_{i,\tau}) = \frac{q^2}{12\beta^2\ell} - \frac{1}{12}$, $\mathbb{E}(\tilde{a}_{i,\tau}) = -\frac{1}{2}$ and $\text{Var}(\tilde{a}_{i,\tau}) = \frac{\beta^2-1}{12}$.
Now, we can decrypt:

$$
\begin{align*}
& \left\langle (A_{\text{in},0}, \dots, A_{\text{in},k_0-1}, B_{\text{in}}) - \sum_{i=0}^{k_1-k_0-1} \mathbf{Dec}^{(\beta, \ell)} (A_{\text{in},k_0+i}) \cdot \mathbf{KSK}_i, (-S^{(0)}, 1) \right\rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_0-1} A_{\text{in},i} \cdot S_i^{(0)} - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot \langle \mathbf{KSK}_{i,j}, (-S^{(0)}, 1) \rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_0-1} A_{\text{in},i} \cdot S_i^{(0)} - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot \left( \frac{q}{\beta^{j+1}} S_{k_0+i}^{(1)} + E_{\mathbf{ksk},i,j} \right) \\
&= B_{\text{in}} - \sum_{i=0}^{k_0-1} A_{\text{in},i} \cdot S_i^{(0)} - \sum_{i=0}^{k_1-k_0-1} \tilde{A}_{\text{in},k_0+i} \cdot S_{k_0+i}^{(1)} - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot E_{\mathbf{ksk},i,j} \\
&= B_{\text{in}} - \sum_{i=0}^{k_0-1} A_{\text{in},i} \cdot S_i^{(0)} - \sum_{i=0}^{k_1-k_0-1} (A_{\text{in},k_0+i} - \tilde{A}_{\text{in},k_0+i}) \cdot S_{k_0+i}^{(1)} \\
&\qquad - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot E_{\mathbf{ksk},i,j}
\end{align*}
$$

Since $S_i^{(0)} = S_i^{(1)}$ for all $0 \le i < k_0$, the equation becomes:

$$
\begin{align*}
&= B_{\text{in}} - \sum_{i=0}^{k_0-1} A_{\text{in},i} \cdot S_i^{(1)} - \sum_{i=0}^{k_1-k_0-1} (A_{\text{in},k_0+i} - \bar{A}_{\text{in},k_0+i}) \cdot S_{k_0+i}^{(1)} \\
&\quad - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot E_{\text{ksk},i,j} \\
&= \Delta M + E_{\text{in}} + \underbrace{\sum_{i=0}^{k_1-k_0-1} \bar{A}_{\text{in},k_0+i} \cdot S_{k_0+i}^{(1)}}_{(I)} - \underbrace{\sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_0+i,j} \cdot E_{\text{ksk},i,j}}_{(II)}
\end{align*}
$$

The $w^{th}$ coefficient of part (I) is equal to:

$$
\sum_{i=k_0}^{k_1-1} \left( \sum_{\tau=0}^{w} \bar{a}_{\text{in},i,w-\tau} \cdot s_{i,\tau}^{(1)} - \sum_{\tau=w+1}^{N-1} \bar{a}_{\text{in},i,N+w-\tau} \cdot s_{i,\tau}^{(1)} \right)
$$

The $w^{th}$ coefficient of part (II) is equal to:

$$
\sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{\text{in},k_0+i,j,w-\tau} \cdot e_{\text{ksk},i,j,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{\text{in},k_0+i,j,N+w-\tau} \cdot e_{\text{ksk},i,j,\tau} \right)
$$

We can now isolate the output error for the $w^{th}$ coefficient and remove the message
coefficient. We obtain that the output error is:

$$e'_{w} = e_{\text{in},w} + \sum_{i=k_0}^{k_1-1} \left( \sum_{\tau=0}^{w} \bar{a}_{\text{in},i,w-\tau} \cdot s_{i,\tau}^{(1)} - \sum_{\tau=w+1}^{N-1} \bar{a}_{\text{in},i,N+w-\tau} \cdot s_{i,\tau}^{(1)} \right) \\ - \sum_{i=0}^{k_1-k_0-1} \sum_{j=0}^{\ell-1} \left( \sum_{\tau=0}^{w} \tilde{a}_{\text{in},k_0+i,j,w-\tau} \cdot e_{\text{ksk},i,j,\tau} - \sum_{\tau=w+1}^{N-1} \tilde{a}_{\text{in},k_0+i,j,N+w-\tau} \cdot e_{\text{ksk},i,j,\tau} \right)$$

So the variance is:

$$\begin{aligned} \mathrm{Var}(e'_{w}) &= \mathrm{Var}(e_{\text{in},w}) + (k_1 - k_0)N\mathrm{Var}(\bar{a}_{\text{in},i,\cdot} s_{i,\cdot}^{(1)}) \\ &\quad + (k_1 - k_0)\ell N\mathrm{Var}(\tilde{a}_{\text{in},i,j,\cdot} \cdot e_{\text{ksk},i,j,\cdot}) \\ &= \sigma_{\text{in}}^2 + (k_1 - k_0)N \left( \frac{q^2 - \beta^2\ell}{12\beta^2\ell} \right) \left( \mathrm{Var}(S^{(1)}) + \mathbb{E}^2(S^{(1)}) \right) \\ &\quad + \frac{(k_1 - k_0)N}{4} \mathrm{Var}(S^{(1)}) + (k_1 - k_0)\ell N \frac{\beta^2 + 2}{12} \sigma_{\text{KSK}}^2. \end{aligned}$$

**Proof 13 (Theorem 11)** Let's consider two shared and partial secret keys such that $S_{\text{out}}^{[\phi_{\text{out}}]} \prec S_{\text{in}}^{[\phi_{\text{in}}]}$. We have $S_{\text{out}}^{[\phi_{\text{out}}]} = (S_{\text{out},0}, \dots, S_{\text{out},k_{\text{out}}-1})$, where $S_{\text{out},k_{\text{out}}-1} = \sum_{i=0}^{\phi_{\text{out}}-(k_{\text{out}}-1)N-1} s_{\text{out},k_{\text{out}}-1,i} X^i$ we call $S_{\text{out},k_{\text{out}}-1} : \underline{S}$.

We have $S_{\text{in}}^{[\phi_{\text{in}}]} = (S_{\text{in},0}, \dots, S_{\text{in},k_{\text{in}}-1})$ such that for all $j \in [0, k_{\text{out}} - 1]$, $S_{\text{out},j} = S_{\text{in},j}$ and $S_{\text{in},k_{\text{out}}-1} = \underline{S} + \bar{S}$ where $\bar{S} = \sum_{j=\phi_{\text{out}}-(k_{\text{out}}-1)N}^{N-1} s_{\text{in},k_{\text{out}}-1,j} X^j$.

The inputs of a GLWE key switching with partial & shared randomness keys (Algorithm 8) are:

* The input GLWE ciphertext: $\mathrm{CT}_{\text{in}} = (\mathbf{A}_{\text{in}}, B_{\text{in}}) \in \mathrm{GLWE}_{S_{\text{in}}^{[\phi_{\text{in}}]}}(\Delta \cdot M) \subseteq R_{q,N}^{k_{\text{in}}+1}$, where $B_{\text{in}} = \sum_{i=0}^{k_{\text{in}}-1} A_{\text{in},i} \cdot S_{\text{in},i} + \Delta \cdot M + E_{\text{in}}$, $A_{\text{in},i} = \sum_{j=0}^{k-1} a_{i,j} \cdot X^j \leftarrow \mathcal{U}(R_{q,N})$ for all $i \in [0, k]$, and $E_{\text{in}} = \sum_{j=0}^{k-1} e_j \cdot X^j$, and $e_j \leftarrow \mathcal{N}_{\sigma_{\text{in}}^2}$ for all $j \in [0, N-1]$.

* The key switch key: $\text{KSK} = (\text{KSK}_{k_{\text{out}}-1}, \text{KSK}_{k_{\text{out}}} \dots, \text{KSK}_{k_{\text{in}}-1})$, where $\text{KSK}_i \in \mathrm{GLEV}_{S_{\text{out}}^{[\phi_{\text{out}}]}}^{(\beta, \ell)}(S_{\text{in},i}) = (\mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta}S_{\text{in},i}), \dots, \mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^\ell}S_{\text{in},i}))$ for all $k_{\text{out}} \le i < k_{\text{in}}$, and $\text{KSK}_{k_{\text{out}}-1} \in \mathrm{GLEV}_{S_{\text{out}}^{[\phi_{\text{out}}]}}^{(\beta, \ell)}(\bar{S}) = (\mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta}\bar{S}), \dots, \mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^\ell}\bar{S}))$

We note by $\text{KSK}_{i,j} = (\mathbf{A}_{i,j}, B_{i,j}) \in \mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^{j+1}}S_{\text{in},i})$, for all $k_{\text{out}} \le i < k_{\text{in}}$ for all $0 \le j < \ell$, where $B_{i,j} = \sum_{\tau=0}^{k_{\text{out}}-1} A_{i,j,\tau} \cdot S_{\text{out},\tau} + \frac{q}{\beta^{j+1}}S_{\text{in},i} + E_{\text{ksk},i,j}$, and $E_{\text{ksk},i,j} = \sum_{\tau=0}^{N-1} e_{\text{ksk},i,j,\tau} \cdot X^\tau$ and $e_{\text{ksk},i,j,m} \leftarrow \mathcal{N}_{\sigma_{\text{ksk}}^2}$.

We note $\text{KSK}_{k_{\text{out}}-1,j} = (\mathbf{A}_{k_{\text{out}}-1,j}, B_{k_{\text{out}}-1,j}) \in \mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\frac{q}{\beta^{j+1}}\bar{S})$ for all $0 \le j < \ell$, where $B_{k_{\text{out}}-1,j} = \sum_{\tau=0}^{k_{\text{out}}-1} A_{k_{\text{out}}-1,j,\tau} \cdot S_{\text{out},\tau} + \frac{q}{\beta^{j+1}}\bar{S} + E_{\text{ksk},k_{\text{out}}-1,j}$, and $E_{\text{ksk},k_{\text{out}}-1,j} = \sum_{\tau=0}^{N-1} e_{\text{ksk},k_{\text{out}}-1,j,\tau} \cdot X^\tau$ and $e_{\text{ksk},k_{\text{out}}-1,j,m} \leftarrow \mathcal{N}_{\sigma_{\text{ksk}}^2}$.

The output of this algorithm is: $\mathrm{CT}_{\text{out}} = (\mathbf{A}_{\text{out}}, B_{\text{out}}) \in \mathrm{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(\Delta \cdot M) \subseteq R_{q,N}^{k_{\text{out}}+1}$.
By definition, for any polynomial $A_{in,i}$, we have the decomposition (described in Supplementary Material C), $\text{Dec}^{(\beta, \ell)}(A_{in,i}) = (\tilde{A}_{in,i,1}, \dots, \tilde{A}_{in,i,\ell})$ such that $\tilde{A}_{in,i} = \sum_{j=0}^{\ell-1} \frac{q}{\beta^{j+1}} \tilde{A}_{in,i,j}$. Now, we can decrypt:

$$
\begin{align*}
B_{\text{out}} - \langle \mathbf{A}_{\text{out}}, \mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]} \rangle &= \langle (\mathbf{A}_{\text{out}}, B_{\text{out}}), (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= \langle (A_{\text{in},0}, \dots, A_{\text{in},k_{\text{out}}-1}, 0, \dots, 0, B_{\text{in}}) - \text{Dec}^{(\beta, \ell)}(A_{\text{in},k_{\text{out}}-1}) \text{KSK}_{k_{\text{out}}-1} \\
&\quad - \sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \text{Dec}^{(\beta, \ell)}(A_{\text{in},i}) \text{KSK}_i, (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_{\text{out}}-1} A_{\text{in},i} S_{\text{out},i} - \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_{\text{out}}-1,j} \langle \text{KSK}_{k_{\text{out}}-1,j}, (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&\quad - \sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \langle \text{KSK}_{i,j}, (-\mathbf{S}_{\text{out}}^{[\phi_{\text{out}}]}, 1) \rangle \\
&= B_{\text{in}} - \sum_{i=0}^{k_{\text{out}}-2} A_{\text{in},i} S_{\text{in},i} - A_{\text{in},k_{\text{out}}-1} \underline{S} - \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_{\text{out}}-1,j} \left( \frac{q}{\beta^{j+1}} \tilde{S} + E_{\text{ksk},k_{\text{out}}-1,j} \right) \\
&\quad - \sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \left( \frac{q}{\beta^{j+1}} S_{\text{in},i} + E_{\text{ksk},i,j} \right) \\
&= B_{\text{in}} - \underbrace{\sum_{i=0}^{k_{\text{out}}-1} A_{\text{in},i} S_{\text{in},i} - A_{\text{in},k_{\text{out}}-1} \underline{S} - \tilde{A}_{\text{in},k_{\text{out}}-1} \tilde{S} - \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},k_{\text{out}}-1,j} \cdot E_{\text{ksk},k_{\text{out}}-1,j}_{\phantom{\tilde{A}_{\text{in},k_{\text{out}}-1,j}}}}_{(I)} \\
&\quad - \underbrace{\sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} S_{\text{in},i} - \sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{\text{ksk},i,j}}_{(II)} \\
&\quad - \underbrace{\sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \tilde{A}_{\text{in},i} S_{\text{in},i} - \sum_{i=k_{\text{out}}}^{k_{\text{in}}-1} \sum_{j=0}^{\ell-1} \tilde{A}_{\text{in},i,j} \cdot E_{\text{ksk},i,j}}_{(III)}
\end{align*}
$$

After decrypting, we can split the previous result in three distinct part and analyze the noise provide by each of them. The first part of the result (term (I)) is only composed of the noise present in the $B_{in}$.

The second part of the result (term (II)) can be seen as a key switching with partial key (Algorithm 9) from $\tilde{S}$ to $S_{out}$. The proof of noise add by this part follows the proof of Theorem 2.

As for the second part of the result, the third part of the result (term (III)) can be seen as a key switching with partial key (Algorithm 9) from ($S_{in,k_{out}}$, ..., $S_{in,k_{in}-1}$) to $S_{out}$. The proof of noise add by this part follows as well the proof of Theorem 2.

By adding this different noises, we will obtain $\text{Var}(e_{out}) = \text{Var}(I) + \text{Var}(II) + \text{Var}(III)$ where :
$$ \mathrm{Var}(I) = \sigma_{\mathrm{in}}^2 $$

$$ \mathrm{Var}(II) = (Nk_{\mathrm{out}} - \phi_{\mathrm{out}}) \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \mathbb{E}^2(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right) \\ + \frac{Nk_{\mathrm{out}} - \phi_{\mathrm{out}}}{4} \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \ell N \sigma_{\mathrm{ksk}}^2 \frac{\beta^2 + 2}{12} $$

$$ \mathrm{Var}(III) = (\phi_{\mathrm{in}} - Nk_{\mathrm{out}}) \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \mathbb{E}^2(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right) \\ + \frac{\phi_{\mathrm{in}} - Nk_{\mathrm{out}}}{4} \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \ell(k_{\mathrm{in}} - k_{\mathrm{out}} - 1) N \sigma_{\mathrm{ksk}}^2 \frac{\beta^2 + 2}{12} $$

To conclude we have :

$$ \mathrm{Var}(e_{\mathrm{out}}) = \sigma_{\mathrm{in}}^2 + (\phi_{\mathrm{in}} - \phi_{\mathrm{out}}) \left( \frac{q^2 - \beta^{2\ell}}{12\beta^{2\ell}} \right) \left( \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \mathbb{E}^2(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) \right) \\ + \frac{\phi_{\mathrm{in}} - \phi_{\mathrm{out}}}{4} \mathrm{Var}(S_{\mathrm{in}}^{[\phi_{\mathrm{in}}]}) + \ell(k_{\mathrm{in}} - k_{\mathrm{out}}) N \sigma_{\mathrm{ksk}}^2 \frac{\beta^2 + 2}{12} $$

□

## C Algorithms From Literature

In this section we recall a few useful algorithms from the literature such as the GLWE-to-GLWE key switch with and without a secret product, and the decomposition algorithm.

**Decomposition Algorithms.** Let $\beta \in \mathbb{N}^*$ be a decomposition base and $\ell \in \mathbb{N}^*$ be a decomposition level. The decomposition algorithm with respect to $\beta$ and $\ell$ is noted $\mathrm{Dec}^{(\beta, \ell)}$: it takes as input an integer $x \in \mathbb{Z}_q$ and outputs a decomposition vector of integers $(x_1, \dots, x_\ell) \in \mathbb{Z}_q^\ell$ such that:

$$ \langle \mathrm{Dec}^{(\beta, \ell)}(x), \left( \frac{q}{\beta} \cdots \frac{q}{\beta^\ell} \right) \rangle = \left\lfloor x \cdot \frac{\beta^\ell}{q} \right\rfloor \cdot \frac{q}{\beta^\ell} \in \mathbb{Z}_q. $$

Usually, the decomposition is done starting from the most significant bits. When applying the decomposition on a vector of integers, the result is a vector of decomposition vectors of integers.

Note that it is possible to decompose an integer polynomials $X \in \mathbb{R}_q$ with this algorithm i.e.,

$$ \langle \mathrm{Dec}^{(\beta, \ell)}(X), \left( \frac{q}{\beta} \cdots \frac{q}{\beta^\ell} \right) \rangle = \left\lfloor X \cdot \frac{\beta^\ell}{q} \right\rfloor \cdot \frac{q}{\beta^\ell} \in \mathbb{R}_q $$

After applying this kind of decomposition on a vector of polynomials, the output is a vector of vector of polynomials.
# D Algorithms in Details

In this section we give details about some algorithms introduced in this paper, such as the different sample extraction algorithms (and its inverse) when dealing with partial GLWE secret keys, the enlarging/shrinking key switch when dealing with shared randomness secret keys, and the GLWE-to-GLWE key switch when dealing with both partial and shared randomness secret keys.

# E Parameter Sets

In this section we provide the formulae to compute the size of the key switching keys and bootstrapping keys, and we also give the most important parameter sets we used for our experiments. They are displayed in Tables 4, 5 and 6. To compute the filling amount of the FFT-KS $\phi_{in}$ of the FFT-based shrinking key switch, one needs to compute $\phi_{PBS} - n$.

## E.1 Size of Public Material

The size (in MB) of the traditional LWE-to-LWE key switching key Size (KSK) is computed with the following formula:

$$Size(\text{KSK}) := (n + 1) \cdot l_{\text{KS}} \cdot k \cdot N \cdot 2^{-17}$$

The size (in MB) of the traditional bootstrapping key Size (BSK) is computed with the following formula:

$$Size(\text{BSK}) := n \cdot l_{\text{PBS}} \cdot (k + 1)^2 \cdot N \cdot 2^{-17}$$

The size (in MB) of the FFT-Shrinking keyswitching key Size (FFT-KS) is computed with the following formula:

$$Size(\text{FFT-KS}) := (k_{\text{out}} + 1) \cdot l_{\text{KS}} \cdot k_{\text{in}} \cdot N \cdot 2^{-17}$$

The size (in MB) of the Stair keyswitching key Size (Stair-KS) with 2 steps is computed with the following formula:

$$Size(\text{Stair-KS}) := ((n_{\text{KS}} + 1) \cdot l_{\text{KS}_1} \cdot (\phi - n_{\text{KS}}) + (n + 1) \cdot l_{\text{KS}_2} \cdot (n_{\text{KS}} - n)) \cdot 2^{-17}$$

For the shrinking key switch, it is enough to use one of the formulae above and changing some parameters. For instance, for an LWE-to-LWE shrinking (Algorithm 5) key switch one uses Size (KSK) with $n = n_{in} - n_{out}$.

## E.2 Parameter Sets

The following parameter sets are for a failure probability of $p_{fail} \le 2^{-13.9}$.
<figure><img src="image_4.png" /><figcaption>Figure 2: Size of public material</figcaption></figure>

Figure 3: Comparison between traditional CJP and two variants of CJP based on both partial secret keys and shared randomness secret keys. More details in Section 6.3 and exact plotted values in Tables 4, 5, 6 and 7 in Supplementary Material.
<caption>Algorithm 8: $CT_{out} \leftarrow \text{GlweKeySwitch}'(CT_{in}, KSK)$</caption>

```
Algorithm 8: $CT_{out} \leftarrow \text{GlweKeySwitch}'(CT_{in}, KSK)$
    \text{Input:} \quad \begin{cases}
        S_{in}^{[\phi_{in}]} \in R_{q,N}^{k_{in}} : \text{the input partial secret key (Definition 6)} \\
        S_{in}^{[\phi_{in}]} = (S_{in,0}, \dots, S_{in,k_{in}-1}) \\
        S_{out}^{[\phi_{out}]} \in R_{q,N}^{k_{out}} : \text{the output partial secret key (Definition 6)} \\
        S_{out}^{[\phi_{out}]} = (S_{out,0}, \dots, S_{out,k_{out}-1}) \\
        (k_{in}-1)N < \phi_{in} \le k_{in}N \text{ and } (k_{out}-1)N < \phi_{out} \le k_{out}N \\
        S_{out}^{[\phi_{out}]} \prec S_{in}^{[\phi_{in}]} : \text{shared randomness secret keys (Definition 9)} \\
        S_{in}^{[\phi_{in}]} \neq S_{out}^{[\phi_{out}]} \text{ and } k_{out} \le k_{in} \\
        k \in \{k_{out}-1, k_{out}\} \text{ such that } \forall 0 \le i < k, S_{in,i} = S_{out,i} \\
        P \in R_{q,N} \\
        \text{CT}_{in} = (A_0, \dots, A_{k_{in}-1}, B) \in R_{q,N}^{k_{in}+1} \\
        \text{CT}_{i,j} \in \text{GLWE}_{S_{out}^{[\phi_{out}]}} \left( \frac{g}{\beta^j} \cdot S_{in,i} \right), \text{ for } k_{out} \le i < k_{in} \text{ and } 0 \le j \le \ell-1 \\
        \text{if } k = k_{out}-1 : \\
        \quad \text{CT}_{k,j} \in \text{GLWE}_{S_{out}^{[\phi_{out}]}} \left( \frac{g}{\beta^j} \cdot (S_{in,k} - S_{out,k}) \right), \text{ for } 0 \le j \le \ell-1 \\
        \quad \ell \in \mathbb{N} : \text{ the number of levels in the decomposition} \\
        \quad \beta \in \mathbb{N} : \text{ the base in the decomposition}
    \end{cases}
    \text{Output:} \quad \begin{cases}
        \text{CT}_{in} \in \text{GLWE}_{S_{in}^{[\phi_{in}]}}(P) \\
        \text{KSK} = \{K_i = (\text{CT}_{i,0}, \dots, \text{CT}_{i,\ell-1})\}_{k \le i < k_{in}}
    \end{cases}
    \quad \text{*/}
    \text{Set } CT_{out} := (A_0, \dots, A_{k_{out}-1}, B) \in R_{q,N}^{k_{out}+1}
    \text{*/}
    \text{Different public material for this potential partial-shared secret key} \\
    \text{polynomial}
    \quad \text{*/}
    \text{if } k = k_{out}-1 \text{ then}
    \text{Update } CT_{out} = CT_{out} - \langle K_k, \text{Dec}^{(\beta, \ell)}(A_k) \rangle
    \quad \text{*/}
    \text{for } i \in [k_{out}; k_{in}-1] \text{ do}
    \quad \text{Decompose the mask}
    \quad \text{*/}
    \text{Update } CT_{out} = CT_{out} - \langle K_i, \text{Dec}^{(\beta, \ell)}(A_i) \rangle
    \quad \text{*/}
    \text{return } CT_{out}
```

<table><caption>Table 3: Comparison between secret key types in terms of public knowledge.</caption><thead><tr><th>Key Type</th><th>Size</th><th>Ring</th><th>Distribution</th><th>Hamming Weight</th></tr></thead><tbody><tr><td>Uniform Binary</td><td>k</td><td>R<sub>q,N</sub></td><td>U({0, 1})</td><td>unknown</td></tr><tr><td>Uniform Ternary</td><td>k</td><td>R<sub>q,N</sub></td><td>U({-1, 0, 1})</td><td>unknown</td></tr><tr><td>Gaussian</td><td>k</td><td>R<sub>q,N</sub></td><td>N<sub>μ</sub>σ<sup>2</sup></td><td>unknown</td></tr><tr><td>Small Uniform</td><td>k</td><td>R<sub>q,N</sub></td><td>U(Z<sub>α</sub>)</td><td>unknown</td></tr><tr><td>Uniform</td><td>k</td><td>R<sub>q,N</sub></td><td>U(Z<sub>q</sub>)</td><td>unknown</td></tr><tr><td>FHW Binary</td><td>k</td><td>R<sub>q,N</sub></td><td>FHW (h, {0, 1})</td><td>h</td></tr><tr><td>FHW Ternary</td><td>k</td><td>R<sub>q,N</sub></td><td>FHW (h, {-1, 0, 1})</td><td>h</td></tr></tbody></table>
<caption>Algorithm 9: $\text{CT}_{\text{out}} \leftarrow \text{GlweKeySwitch}(\text{CT}_{\text{in}}, \text{KSK})$</caption>

Context:
$$
\left\{
\begin{array}{l}
(k_{\text{in}} - 1)N < \phi_{\text{in}} \le k_{\text{in}}N \text{ and } (k_{\text{out}} - 1)N < \phi_{\text{out}} \le k_{\text{out}}N \\
S_{\text{in}}^{[\phi_{\text{in}}]} \in R_{q,N}^{k_{\text{in}}}: \text{the input partial secret key (Definition 6)} \\
S_{\text{in}}^{[\phi_{\text{in}}]} = (S_{\text{in},0}, \dots, S_{\text{in},k_{\text{in}}-1}) \\
S_{\text{out}}^{[\phi_{\text{out}}]} \in R_{q,N}^{k_{\text{out}}}: \text{the output partial secret key (Definition 6)} \\
\ell \in \mathbb{N}: \text{ the number of levels in the decomposition} \\
\beta \in \mathbb{N}: \text{ the base in the decomposition}
\end{array}
\right.
$$
Input:
$$
\left\{
\begin{array}{l}
\text{CT}_{\text{in}} = (A_0, \dots, A_{k_{\text{in}}-1}, B) \in \text{GLWE}_{S_{\text{in}}^{[\phi_{\text{in}}]}}(P) \subseteq R_{q,N}^{k_{\text{in}}+1}, \text{ with } P \in R_{q,N} \\
\text{KSK} = \{\text{KSK}_i = \{\text{KSK}_{i,j}\}_{0 \le j \le \ell-1}\}_{0 \le i \le k_{\text{in}}-1}, \text{ with} \\
\text{KSK}_{i,j} \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}\left(\frac{q}{\beta^j} \cdot S_{\text{in},i}\right), \text{ for } 0 \le i \le k_{\text{in}}-1 \text{ and } 0 \le j \le \ell-1
\end{array}
\right.
$$
Output:
$$
\text{CT}_{\text{out}} \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(P)
$$
/* Keep the B part */
1 Set $\text{CT}_{\text{out}} := (0, \dots, 0, B) \in R_{q,N}^{k_{\text{out}}+1}$
2 for $i \in [0; k_{\text{in}} - 1]$ do
3 Update $\text{CT}_{\text{out}} = \text{CT}_{\text{out}} - \langle \mathbf{K}_i, \text{Dec}^{(\beta, \ell)}(A_i) \rangle$ */
4 return $\text{CT}_{\text{out}}$

<caption>Algorithm 10: $\text{CT}_{\text{out}} \leftarrow \text{SecretProductGlweKeySwitch}(\text{CT}_{\text{in}}, \text{KSK})$</caption>

Context:
$$
\left\{
\begin{array}{l}
S_{\text{in}}^{[\phi_{\text{in}}]} \in R_{q,N}^{k_{\text{in}}}: \text{ the input partial secret key (Definition 6)} \\
S_{\text{in}}^{[\phi_{\text{in}}]} = (S_{\text{in},0}, \dots, S_{\text{in},k_{\text{in}}-1}) \\
S_{\text{out}}^{[\phi_{\text{out}}]} \in R_{q,N}^{k_{\text{out}}}: \text{ the output partial secret key (Definition 6)} \\
(k_{\text{in}} - 1)N < \phi_{\text{in}} \le k_{\text{in}}N \text{ and } (k_{\text{out}} - 1)N < \phi_{\text{out}} \le k_{\text{out}}N \\
Q \in R_{q,N} \\
\text{CT}_{\text{in}} = (A_0, \dots, A_{k_{\text{in}}-1}, B) \in R_{q,N}^{k_{\text{in}}+1} \\
\text{CT}_{i,j} \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}\left(\frac{q}{\beta^j} \cdot Q \cdot S_{\text{in},i}\right), \text{ for } 0 \le i \le k_{\text{in}} - 1 \text{ and } 0 \le j \le \ell - 1 \\
\text{CT}_{k_{\text{in}},j} \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}\left(\frac{q}{\beta^j} \cdot Q\right), \text{ for } 0 \le j \le \ell - 1 \\
\ell \in \mathbb{N}: \text{ the number of levels in the decomposition} \\
\beta \in \mathbb{N}: \text{ the base in the decomposition}
\end{array}
\right.
$$
Input:
$$
\left\{
\begin{array}{l}
\text{CT}_{\text{in}} \in \text{GLWE}_{S_{\text{in}}^{[\phi_{\text{in}}]}}(P), \text{ with } P \in R_{q,N} \\
\text{KSK} = \{\mathbf{K}_i = (\text{CT}_{i,0}, \dots, \text{CT}_{i,\ell-1})\}_{0 \le i \le k_{\text{in}}}
\end{array}
\right.
$$
Output:
$$
\text{CT}_{\text{out}} \in \text{GLWE}_{S_{\text{out}}^{[\phi_{\text{out}}]}}(Q \cdot P)
$$
/* Decompose the B part */
1 Set $\text{CT}_{\text{out}} = \langle \mathbf{K}_{k_{\text{in}}}, \text{Decomp}^{(\beta, \ell)}(B) \rangle$
2 for $i \in [0; k - 1]$ do
3 Update $\text{CT}_{\text{out}} = \text{CT}_{\text{out}} - \langle \mathbf{K}_i, \text{Decomp}^{(\beta, \ell)}(A_i) \rangle$ */
4 return $\text{CT}_{\text{out}}$
<table><caption>**Algorithm 11:** ct<sub>out</sub> ← SampleExtract (CT<sub>in</sub>, α)</caption><tr><td>Context:</td><td><pre>S<sup>[φ]</sup> ∈ R<sup>k</sup><sub>q,N</sub> : a partial secret key (Definition 6)<br/>(k − 1)N + 1 ≤ φ ≤ kN : filling amount of the partial secret key<br/>s̄ ∈ Z<sup>φ</sup> : the flattened version of S<sup>[φ]</sup> (Definition 7)<br/>P := &sum;<sup>N−1</sup><sub>i=0</sub> p<sub>i</sub>X<sup>i</sup> ∈ R<sub>q,N</sub></pre></td></tr><tr><td>Input:</td><td><pre>CT<sub>in</sub> ∈ GLWE<sub>S<sup>[φ]</sup></sub>(P) : a GLWE encryption of the plaintext P<br/>0 ≤ α ≤ N − 1 : the coefficient to extract</pre></td></tr><tr><td>Output:</td><td>ct<sub>out</sub> ∈ LWE<sub>s̄</sub>(p<sub>α</sub>) : an LWE encryption of the plaintext p<sub>α</sub></td></tr><tr><td colspan="2">/* Rotation of the GLWE ciphertext */</td></tr><tr><td>1</td><td>set CT := X<sup>−α</sup> · CT<sub>in</sub></td></tr><tr><td></td><td>/* Call to Algorithm 2 */</td></tr><tr><td>2</td><td>return ct<sub>out</sub> := ConstantSampleExtract (CT)</td></tr></table>
<table><caption>Table 4: Parameter sets, benchmarks for PBS+LWE-KS and sizes of public material for CJP and two variants based on both partial and shared randomness secret keys. Note that we use $log_2(\nu) = p$. Sizes are given in MB and times in milliseconds.</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">Partial Shared Keys</th><th rowspan="2">LWE-KS Algorithm</th><th colspan="2">GLWE Parameters</th><th colspan="2">PBS Parameters</th><th colspan="2">LWE-KS Parameters</th><th colspan="2">Metrics</th></tr><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td rowspan="3">1</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>588<br>-12.66</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>15</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>5.43</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>5<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>ℓ<sub>KS</sub></td><td>3</td><td>size</td><td>58.6</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-31.07</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">1</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>532<br>-11.17</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>15</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>782<br>-17.82</td><td>time</td><td>3.78</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>5<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(β<sub>KS1</sub>)<br>ℓ<sub>KS1</sub></td><td>9<br>1</td><td>size</td><td>44.45</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1280<br>-31.07</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">1</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>534<br>-11.22</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>15</td><td>k<sub>in</sub><br>k<sub>out</sub></td><td>3<br>3</td><td>time</td><td>3.27</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>5<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)</td><td>8<br>1</td><td>size</td><td>37.76</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1280<br>-31.07</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">2</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>668<br>-14.79</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>18</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>4</td><td>time</td><td>8.75</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>6<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>ℓ<sub>KS</sub></td><td>3</td><td>size</td><td>87.45</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-37.88</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">2</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>576<br>-12.34</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>18</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>896<br>-20.85</td><td>time</td><td>6.28</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>6<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(β<sub>KS1</sub>)<br>ℓ<sub>KS1</sub></td><td>10<br>1</td><td>size</td><td>66.55</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-37.88</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">2</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>590<br>-12.71</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>18</td><td>k<sub>in</sub><br>k<sub>out</sub></td><td>1<br>1</td><td>time</td><td>5.32</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>6<br>8</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)</td><td>10<br>1</td><td>size</td><td>56.64</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-37.88</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">3</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>720<br>-16.17</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>21</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>4</td><td>time</td><td>12.2</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>4<br>9</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>ℓ<sub>KS</sub></td><td>3</td><td>size</td><td>104.1</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-51.49</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">3</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>648<br>-14.25</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>18</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>944<br>-22.13</td><td>time</td><td>6.22</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>3<br>9</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(β<sub>KS1</sub>)<br>ℓ<sub>KS1</sub></td><td>7<br>2</td><td>size</td><td>57.83</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-37.88</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">3</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>686<br>-15.27</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>18</td><td>k<sub>in</sub><br>k<sub>out</sub></td><td>1<br>1</td><td>time</td><td>5.12</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>3<br>9</td><td>ℓ<sub>PBS</sub></td><td>1</td><td>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)</td><td>10<br>1</td><td>size</td><td>43.08</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-37.88</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table 5: Parameter sets, benchmarks for PBS+LWE-KS and sizes of public material for CJP and two variants based on both partial and shared randomness secret keys. Note that we use $log_2(\nu) = p$. Sizes are given in MB and times in milliseconds.</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">Partial Shared Keys</th><th rowspan="2">LWE-KS Algorithm</th><th colspan="2">GLWE Parameters</th><th colspan="2">PBS Parameters</th><th colspan="2">LWE-KS Parameters</th><th colspan="2">Metrics</th></tr><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td rowspan="3">4</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>788<br>-17.98</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>23</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>4</td><td>time</td><td>12.6</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>2<br>10<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td>l<sub>KS</sub></td><td>3</td><td>size</td><td>92.39</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>664<br>-14.68</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>22</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)<br>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>1126<br>-26.97<br>13</td><td>time</td><td>9.35</td></tr><tr><td rowspan="3">4</td><td rowspan="3">✓</td><td rowspan="3">2 steps (Alg. 6)</td><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2<br>10<br>2048<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td>l<sub>KS1</sub><br>log<sub>2</sub>(β<sub>KS2</sub>)<br>l<sub>KS2</sub></td><td>1<br>2<br>6</td><td>size</td><td>68.68</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>682<br>-15.16</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>23</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)<br>l<sub>KS</sub></td><td>3<br>3<br>9<br>1<br>14</td><td>time</td><td>7.38</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2<br>10<br>2048<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td></td><td></td><td>size</td><td>48.61</td></tr><tr><td rowspan="3">5</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>840<br>-19.36</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>23</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>20.0</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>1<br>11<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td>l<sub>KS</sub></td><td>6</td><td>size</td><td>131.3</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>732<br>-16.49</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>23</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)<br>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>1171<br>-28.17<br>9</td><td>time</td><td>13.8</td></tr><tr><td rowspan="3">5</td><td rowspan="3">✓</td><td rowspan="3">2 steps (Alg. 6)</td><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1<br>11<br>2048<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td>l<sub>KS1</sub><br>log<sub>2</sub>(β<sub>KS2</sub>)<br>l<sub>KS2</sub></td><td>2<br>2<br>7</td><td>size</td><td>78.62</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>766<br>-17.39</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>23</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)<br>l<sub>KS</sub></td><td>3<br>3<br>9<br>1<br>15</td><td>time</td><td>11.0</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1<br>11<br>2048<br>-51.49</td><td>l<sub>PBS</sub></td><td>1</td><td></td><td></td><td>size</td><td>48.58</td></tr><tr><td rowspan="3">6</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>840<br>-19.36</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>14</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>55.6</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>1<br>12<br>-62.00</td><td>l<sub>PBS</sub></td><td>2</td><td>l<sub>KS</sub></td><td>5</td><td>size</td><td>341.4</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>748<br>-16.91</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>14</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)<br>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>1313<br>-31.94<br>16</td><td>time</td><td>44.3</td></tr><tr><td rowspan="3">6</td><td rowspan="3">✓</td><td rowspan="3">2 steps (Alg. 6)</td><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1<br>12<br>2443<br>-62.00</td><td>l<sub>PBS</sub></td><td>2</td><td>l<sub>KS1</sub><br>log<sub>2</sub>(β<sub>KS2</sub>)<br>l<sub>KS2</sub></td><td>1<br>2<br>8</td><td>size</td><td>224.2</td></tr><tr><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>774<br>-17.61</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>14</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)<br>log<sub>2</sub>(β<sub>KS</sub>)<br>l<sub>KS</sub></td><td>1<br>1<br>11<br>1<br>15</td><td>time</td><td>41.1</td></tr><tr><td>k<br>log<sub>2</sub>(N)<br>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>1<br>12<br>2443<br>-62.00</td><td>l<sub>PBS</sub></td><td>2</td><td></td><td></td><td>size</td><td>194.0</td></tr></tbody></table>
<table><caption>Table 6: Parameter sets, benchmarks for PBS+LWE-KS and sizes of public material for CJP and two variants based on both partial and shared randomness secret keys. Note that we use $log_2(\nu) = p$. Sizes are given in MB and times in milliseconds.</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">Partial Shared Keys</th><th rowspan="2">LWE-KS Algorithm</th><th colspan="2">GLWE Parameters</th><th colspan="2">PBS Parameters</th><th colspan="2">LWE-KS Parameters</th><th colspan="2">Metrics</th></tr><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td rowspan="3">7</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>896<br>-20.85</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>15</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>129.0</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>13</td><td>l<sub>PBS</sub></td><td>2</td><td>l<sub>KS</sub></td><td>6</td><td>size</td><td>784.4</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">7</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>776<br>-17.66</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>15</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>1332<br>-32.45</td><td>time</td><td>101.0</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>13</td><td>l<sub>PBS</sub></td><td>2</td><td>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>10<br>2</td><td>size</td><td>463.3</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">7</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>818<br>-18.78</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>14</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)</td><td>1<br>1<br>11</td><td>time</td><td>90.3</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>13</td><td>l<sub>PBS</sub></td><td>2</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>1<br>1</td><td>size</td><td>409.5</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">8</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>968<br>-22.77</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>11</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>415</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>14</td><td>l<sub>PBS</sub></td><td>3</td><td>l<sub>KS</sub></td><td>6</td><td>size</td><td>2179</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">8</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>816<br>-18.72</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>11</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>1359<br>-33.17</td><td>time</td><td>323</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>14</td><td>l<sub>PBS</sub></td><td>3</td><td>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>9<br>2</td><td>size</td><td>1304</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">8</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>854<br>-19.73</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>11</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)</td><td>1<br>1<br>11</td><td>time</td><td>306</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>14</td><td>l<sub>PBS</sub></td><td>3</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>1<br>1</td><td>size</td><td>1282</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">9</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>1024<br>-24.26</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>9</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>3</td><td>time</td><td>1340</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>15</td><td>l<sub>PBS</sub></td><td>4</td><td>l<sub>KS</sub></td><td>7</td><td>size</td><td>5890</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">9</td><td rowspan="4">✓</td><td rowspan="4">2 steps (Alg. 6)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>860<br>-19.89</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>8</td><td>n<sub>KS</sub><br>log<sub>2</sub>(σ<sub>nKS</sub>)</td><td>1388<br>-33.94</td><td>time</td><td>1010</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>15</td><td>l<sub>PBS</sub></td><td>4</td><td>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>10<br>2</td><td>size</td><td>3525</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">9</td><td rowspan="4">✓</td><td rowspan="4">FFT-based (Alg. 7)</td><td>n<br>log<sub>2</sub>(σ<sub>n</sub>)</td><td>902<br>-21.01</td><td>log<sub>2</sub>(β<sub>PBS</sub>)</td><td>8</td><td>k<sub>in</sub><br>k<sub>out</sub><br>log<sub>2</sub>(N<sub>KS</sub>)</td><td>1<br>1<br>11</td><td>time</td><td>1003</td></tr><tr><td>k<br>log<sub>2</sub>(N)</td><td>1<br>15</td><td>l<sub>PBS</sub></td><td>4</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>1<br>1</td><td>size</td><td>3609</td></tr><tr><td>φ<br>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>2443<br>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table 7: Parameter sets, benchmarks for PBS+LWE-KS and sizes of public material for CJP and two variants based on both partial and shared randomness secret keys. Note that we use $log_2(\nu) = p$. Sizes are given in MB and times in milliseconds.</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">Partial Shared Keys</th><th rowspan="2">LWE-KS Algorithm</th><th colspan="2">GLWE Parameters</th><th colspan="2">PBS Parameters</th><th colspan="2">LWE-KS Parameters</th><th colspan="2">Metrics</th></tr><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td rowspan="3">10</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n</td><td>1096</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">6</td><td rowspan="3">log<sub>2</sub>(β<sub>KS</sub>)</td><td rowspan="3">2</td><td>time</td><td>4710</td></tr><tr><td>log<sub>2</sub>(σ<sub>n</sub>)</td><td>-26.17</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">6</td><td rowspan="3">ℓ<sub>KS</sub></td><td rowspan="3">12</td><td>size</td><td>19730</td></tr><tr><td>k</td><td>1</td></tr><tr><td rowspan="3">10</td><td rowspan="3">✓</td><td rowspan="3">2 steps (Alg. 6)</td><td>log<sub>2</sub>(N)</td><td>16</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">6</td><td rowspan="3">n<sub>KS</sub></td><td>1417</td><td>time</td><td>3620</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-62.00</td><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-34.71</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">6</td><td>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>11</td><td>size</td><td>10940</td></tr><tr><td>k</td><td>1</td><td>ℓ<sub>KS1</sub></td><td>2</td></tr><tr><td rowspan="3">10</td><td rowspan="3">✓</td><td rowspan="3">FFT-based (Alg. 7)</td><td>log<sub>2</sub>(N)</td><td>16</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">6</td><td>log<sub>2</sub>(β<sub>KS2</sub>)</td><td>1</td><td>time</td><td>3603</td></tr><tr><td>φ</td><td>2443</td><td>ℓ<sub>KS2</sub></td><td>19</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">6</td><td>k<sub>in</sub></td><td>3</td><td>size</td><td>11260</td></tr><tr><td>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-62.00</td><td>k<sub>out</sub></td><td>3</td></tr><tr><td rowspan="3">11</td><td rowspan="3">X</td><td rowspan="3">traditional LWE-to-LWE</td><td>n</td><td>938</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">6</td><td>log<sub>2</sub>(β<sub>KS</sub>)</td><td>2</td><td>time</td><td>43900</td></tr><tr><td>log<sub>2</sub>(σ<sub>n</sub>)</td><td>-21.97</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">20</td><td rowspan="3">ℓ<sub>KS</sub></td><td rowspan="3">13</td><td>size</td><td>105300</td></tr><tr><td>k</td><td>1</td></tr><tr><td rowspan="3">11</td><td rowspan="3">✓</td><td rowspan="3">2 steps (Alg. 6)</td><td>log<sub>2</sub>(N)</td><td>17</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">3</td><td rowspan="3">n<sub>KS</sub></td><td>1471</td><td>time</td><td>18000</td></tr><tr><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-62.00</td><td>log<sub>2</sub>(σ<sub>k·N</sub>)</td><td>-36.15</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">12</td><td>log<sub>2</sub>(β<sub>KS1</sub>)</td><td>11</td><td>size</td><td>47330</td></tr><tr><td>k</td><td>1</td><td>ℓ<sub>KS1</sub></td><td>2</td></tr><tr><td rowspan="3">11</td><td rowspan="3">✓</td><td rowspan="3">FFT-based (Alg. 7)</td><td>log<sub>2</sub>(N)</td><td>17</td><td rowspan="3">log<sub>2</sub>(β<sub>PBS</sub>)</td><td rowspan="3">3</td><td>log<sub>2</sub>(β<sub>KS2</sub>)</td><td>1</td><td>time</td><td>19450</td></tr><tr><td>φ</td><td>2443</td><td>ℓ<sub>KS2</sub></td><td>21</td><td rowspan="3">ℓ<sub>PBS</sub></td><td rowspan="3">13</td><td>k<sub>in</sub></td><td>3</td><td>size</td><td>52940</td></tr><tr><td>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-62.00</td><td>k<sub>out</sub></td><td>3</td></tr><tr><td></td><td></td><td></td><td>n</td><td>1018</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>log<sub>2</sub>(σ<sub>n</sub>)</td><td>-24.10</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>k</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>log<sub>2</sub>(N)</td><td>17</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>φ</td><td>2443</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td>log<sub>2</sub>(σ<sub>φ</sub>)</td><td>-62.00</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>