# Exploring General Cyclotomic Rings in Torus-Based Fully Homomorphic Encryption

Philippe Chartier, Michel Koskas, Mohammed Lemou

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

## To cite this version:

Philippe Chartier, Michel Koskas, Mohammed Lemou. Exploring General Cyclotomic Rings in Torus-Based Fully Homomorphic Encryption. 2025. hal-05369141

HAL Id: hal-05369141

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

Preprint submitted on 17 Nov 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Exploring General Cyclotomic Rings in Torus-Based Fully Homomorphic Encryption

P. Chartier\*, M. Koskas†, M. Lemou‡

November 17, 2025

## Abstract

In this article, we develop algebraic tools for fully homomorphic encryption over the torus in the setting of general composite cyclotomic indices. Working in cyclotomic rings and fields beyond the power-of-two case, we reframe and optimize key primitives—reduction modulo $\Phi_M$, homomorphic evaluation of trace operators, blind extraction and the blind rotation used in bootstrapping—using systematic duality and trace techniques. Our approach yields a simpler, more modular description of bootstrapping, including a new systematic treatment of so-called “nega-cyclicity” conditions and featuring an optimal reduction of the input noise, and provides sharp error bounds showing that bootstrap noise growth remains mild compared with the classical power-of-two instantiation. In addition, we introduce a new fast packing strategy. These results broaden the algebraic toolkit for torus-based FHE and pave the way for new cryptographic constructions and applications.

**Keywords:** fully homomorphic encryption, residue number system, trace operator, extraction, bootstrapping.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Related works</td><td>5</td></tr><tr><td>3</td><td>Algebraic setting</td><td>6</td></tr><tr><td>3.1</td><td>General cyclotomic polynomials</td><td>6</td></tr><tr><td>3.2</td><td>The cyclotomic field $\mathcal{K}$ and the ring of algebraic integers $\mathcal{R}$</td><td>7</td></tr><tr><td>3.2.1</td><td>Canonical and powerful bases</td><td>8</td></tr><tr><td>3.2.2</td><td>Computing the polynomial modulo</td><td>10</td></tr><tr><td>3.3</td><td>Trace operator and dual sets</td><td>11</td></tr><tr><td>3.4</td><td>From the powerful basis to its dual and back</td><td>15</td></tr><tr><td>4</td><td>Plaintext messages in the TFHE framework</td><td>19</td></tr><tr><td>4.1</td><td>The set of torus plaintexts</td><td>19</td></tr><tr><td>4.2</td><td>The set of polynomial plaintexts</td><td>20</td></tr></table>

<footnote>\*INRIA-IRMAR-University of Rennes, Campus de Beaulieu, 35042 Rennes Cedex</footnote>

<footnote>†Ravel Technologies, 75 rue de Richelieu, 75002 Paris</footnote>

<footnote>‡CNRS-IRMAR-University of Rennes, Campus de Beaulieu, 35042 Rennes Cedex</footnote>
<table>
  <tbody>
    <tr>
      <td>5</td>
      <td>LWE and RLWE encryptions cryptographic schemes</td>
      <td>20</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Encryption/decryption schemes in T</td>
      <td>20</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Encryption/decryption schemes in T and T<sup>√</sup></td>
      <td>21</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Encryption/decryption schemes in R and R<sup>√</sup></td>
      <td>24</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Homomorphic addition</td>
      <td>26</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Homomorphic modular product</td>
      <td>27</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Key switching</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Extraction of a LWE from a RLWE</td>
      <td>28</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>An extraction procedure using dual bases</td>
      <td>29</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Blind extraction using encrypted indices</td>
      <td>31</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>Simple blind extraction</td>
      <td>32</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>Blind extraction of a linear form of a vector in T<sup>N</sup></td>
      <td>32</td>
    </tr>
    <tr>
      <td>7</td>
      <td>Bootstrapping in the general cyclotomic setting</td>
      <td>33</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>General formulation of the compatibility conditions</td>
      <td>34</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>Algorithm to determine the optimal v* for r = 1</td>
      <td>36</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>Algorithm to determine the optimal v* for r > 1</td>
      <td>37</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>Homomorphic implementation</td>
      <td>39</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>Error estimate of the bootstrap output</td>
      <td>42</td>
    </tr>
    <tr>
      <td>7.6</td>
      <td>General cyclotomic bootstrapping versus standard one</td>
      <td>43</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Trace operators and their homomorphic evaluations</td>
      <td>45</td>
    </tr>
    <tr>
      <td>8.1</td>
      <td>The complete trace and its encryption</td>
      <td>45</td>
    </tr>
    <tr>
      <td>8.2</td>
      <td>Partial traces and fast evaluation of the complete trace for r = 1</td>
      <td>47</td>
    </tr>
    <tr>
      <td>8.2.1</td>
      <td>Fast evaluation of the trace: a first approach</td>
      <td>47</td>
    </tr>
    <tr>
      <td>8.2.2</td>
      <td>Fast evaluation of the Trace: the algebraic approach</td>
      <td>48</td>
    </tr>
    <tr>
      <td>8.2.3</td>
      <td>General expression of the trace for t ≥ 3.</td>
      <td>50</td>
    </tr>
    <tr>
      <td>8.3</td>
      <td>Partial traces and fast evaluation of the complete trace for r > 1</td>
      <td>51</td>
    </tr>
    <tr>
      <td>9</td>
      <td>Fast packing operations</td>
      <td>52</td>
    </tr>
    <tr>
      <td>9.1</td>
      <td>From a single LWE-ciphertext to an RLWE-ciphertext</td>
      <td>52</td>
    </tr>
    <tr>
      <td>9.2</td>
      <td>Packing a set of LWE-ciphertexts into one RLWE-ciphertext</td>
      <td>54</td>
    </tr>
    <tr>
      <td>9.2.1</td>
      <td>A first strategy</td>
      <td>54</td>
    </tr>
    <tr>
      <td>9.2.2</td>
      <td>A second strategy</td>
      <td>55</td>
    </tr>
    <tr>
      <td>9.2.3</td>
      <td>The optimal strategy</td>
      <td>56</td>
    </tr>
  </tbody>
</table>

# 1 Introduction

Non-power of two cyclotomic polynomials, which pertain to cyclotomic rings indexed by integers $M$ that are not restricted to the form $M = 2^k$, carry significant implications for fully homomorphic encryption (FHE) systems. Non-power of two cyclotomic polynomials $\Phi_M$ are associated with a wider variety of primitive roots of unity. Generally speaking, this diversity allows for richer algebraic structures and facilitates computations on more complex data types, thereby enhancing the versatility of Fully Homomorphic Encryption (FHE) schemes. Specifically, we highlight five key advantages that we believe justify the significance of our current work. Several of these points have already been emphasized by Lyubashevsky, Peikert, and Regev in [29], as well as by Joye and Walter in [25].
* **Increased Input Space:** Utilizing cyclotomic rings beyond powers of two can significantly expand the plaintext space available for bootstrapping operations. This makes it feasible to encrypt and perform homomorphic computations on a greater range of data, improving the overall utility of the encryption scheme. In the power-of-two case, algebraic constraints effectively halves the size of messages that can be accurately bootstrapped. In general, the proportion of the usable plaintext space is limited by the ratio $N/M$, where $N$ is the degree of the cyclotomic polynomial. For $M = t^\alpha$ we have $N = (t-1)t^{\alpha-1}$, and hence

$$ \frac{N}{M} = 1 - \frac{1}{t}. $$

This quotient grows with $t$, reflecting an increasing fraction of usable plaintext space. For $M = \prod_{k=1}^{r} t_k^{\alpha_k}$ with distinct primes $t_k$, this ratio becomes

$$ \frac{N}{M} = \prod_{k=1}^{r} \left(1 - \frac{1}{t_k}\right), $$

which likewise increases as the prime factors $t_k$ become larger. In this paper, we will further show that the usual "nega-cyclicity" requirement in bootstrapping can be removed at no extra cost, and we will present an optimal algorithm for constructing the bootstrap polynomial.

* **Flexibility in Parameter Choices:** Non-power of two cyclotomic polynomials enable the customization of FHE parameters to better align with specific applications or security requirements. For example, attaining a given security level may require a ring dimension much smaller than the next larger power of two; restricting to powers of two can therefore double key sizes and runtimes unnecessarily, reducing practicality. This flexibility is essential for implementations that must meet specific performance targets or operational constraints. Powers of two are sparsely distributed: for example, among all values $M = t^\alpha$ in the range 500 to 10000, those with $t=2$ (i.e. powers of two) are comparatively rare — the corresponding entries are highlighted in bold in the table below.

<table><thead><tr><th>t</th><th>α</th><th>t<sup>α</sup></th><th>t</th><th>α</th><th>t<sup>α</sup></th><th>t</th><th>α</th><th>t<sup>α</sup></th><th>t</th><th>α</th><th>t<sup>α</sup></th></tr></thead><tbody><tr><td>2</td><td>9</td><td><b>512</b></td><td>37</td><td>2</td><td>1369</td><td>53</td><td>2</td><td>2809</td><td>73</td><td>2</td><td>5329</td></tr><tr><td>23</td><td>2</td><td>529</td><td>41</td><td>2</td><td>1681</td><td>5</td><td>5</td><td>3125</td><td>79</td><td>2</td><td>6241</td></tr><tr><td>5</td><td>4</td><td>625</td><td>43</td><td>2</td><td>1849</td><td>59</td><td>2</td><td>3481</td><td>3</td><td>8</td><td>6561</td></tr><tr><td>3</td><td>6</td><td>729</td><td>2</td><td>11</td><td><b>2048</b></td><td>61</td><td>2</td><td>3721</td><td>19</td><td>3</td><td>6859</td></tr><tr><td>29</td><td>2</td><td>841</td><td>3</td><td>7</td><td>2187</td><td>2</td><td>12</td><td><b>4096</b></td><td>83</td><td>2</td><td>6889</td></tr><tr><td>31</td><td>2</td><td>961</td><td>13</td><td>3</td><td>2197</td><td>67</td><td>2</td><td>4489</td><td>89</td><td>2</td><td>7921</td></tr><tr><td>2</td><td>10</td><td><b>1024</b></td><td>47</td><td>2</td><td>2209</td><td>17</td><td>3</td><td>4913</td><td>2</td><td>13</td><td><b>8192</b></td></tr><tr><td>11</td><td>3</td><td>1331</td><td>7</td><td>4</td><td>2401</td><td>71</td><td>2</td><td>5041</td><td>97</td><td>2</td><td>9409</td></tr></tbody></table>

In Section 7.6, a plot demonstrates that using non-power-of-two values for $N$ provides greater flexibility in supporting a fixed number of additions within the cryptosystem. Of course, allowing for general indices $M$ further broadens the range of options available.

* **Flexibility in Using NTT-like Algorithms:** The most computationally intensive step during bootstrapping is performing a series of multiplications within the cyclotomic ring $\mathbb{Z}_q[X]/\Phi_M(X)$. In most current implementations, both $q$ and $N$ are chosen as powers of two—commonly $q = 2^{32}$ or $q = 2^{64}$, with $2^{10} \le N \le 2^{16}$. Due to the large polynomial degrees, Fast Fourier Transform (FFT) techniques are employed to perform these multiplications efficiently. However, FFT methods introduce approximation errors, which can
impact the accuracy of the computations. The approach proposed here offers greater flexibility in utilizing NTT-like algorithms such as Schönhage-Strassen or Nussbaumer, providing an alternative to FFT-based methods, especially when FFT is ill-conditioned. Indeed, more options exist for selecting NTT-friendly parameters, such as choosing $q$ mod $M = 1$ or just $\gcd(q, M) = 1$. This enhanced adaptability can lead to more robust and efficient implementations of FHE.

* **SIMD and diversified security assumptions:** Beyond expanding the space of permissible parameters, fully general cyclotomic polynomials yield both theoretical and practical benefits. Certain applications demand non-power-of-two rings because the power-of-two case can lack the algebraic structure required for efficient SIMD packing or for supporting plaintext spaces isomorphic to finite fields other than $\mathbb{Z}_2$. Equally important is the diversification of security assumptions: although ring-LWE hardness is conjectured for all high-order cyclotomic rings, some rings may exhibit weaker instantiations, as observed in [29].

* **Potential for Optimized Bootstrapping:** With access to a wider variety of polynomial structures, it becomes possible to develop strategies that improve both the efficiency and effectiveness of noise mitigation techniques.

The standard TFHE [16] and FHEW [21] schemes, primarily operating under the assumption that $M = 2^{\alpha}$, have rarely been practically extended to more general cyclotomic rings. In fact, such extensions have typically been limited to cyclotomic polynomials of the forms $M = 2^{\alpha_1}3^{\alpha_2}$ [24, 25] or $M = t^{\alpha}$ as shown in [4], particularly for homomorphically testing the equality of an encrypted message with a specified plaintext message. Here, we propose an extension of both the FHEW and TFHE comprehensive frameworks to include the class of M-th cyclotomic polynomials with $M = t_1^{\alpha_1}t_2^{\alpha_2}\cdots t_r^{\alpha_r}$, where the $t_i$'s are distinct primes and the $\alpha_i$'s are positive integers. More concretely, whereas traditional TFHE systems often operate within the polynomial ciphertext space defined as:

$$ \mathbb{Z}[X]/(X^{2^k} + 1) \quad \text{and} \quad \mathbb{T}[X]/(X^{2^k} + 1), \quad \mathbb{T} = \mathbb{Q}/\mathbb{Z}, $$

we are addressing a broader scenario characterized by:

$$ \mathcal{R} := \mathbb{Z}[X]/(\Phi_M(X)) \quad \text{and} \quad \mathcal{T} := \mathbb{T}[X]/(\Phi_M(X)), $$

where $M$ adopts the aforementioned form $M = t_1^{\alpha_1}t_2^{\alpha_2}\cdots t_r^{\alpha_r}$.

In the upcoming sections, we will explore the processes of extraction, bootstrapping, and efficient homomorphic evaluation of the trace operator. We will investigate tasks such as *blind extraction* and *fast packing*, and the algorithms we develop are expected to contribute innovative solutions in this context. Our aim is to clarify the objectives of each procedure and demonstrate how existing methods can be adapted, enhanced, or streamlined for applications. Before we delve into these topics, Section 3 will present the essential algebraic tools necessary for constructing the various algorithms discussed. Furthermore, we will offer a brief overview of standard procedures for LWE and RLWE, including encryption, decryption, addition, and external product, as described in Section 5. It is essential to highlight that throughout this text, the scalar messages considered are contained within $\frac{1}{p}\mathbb{Z}_p$ for moderate values of $p$, with applications to large integers via the Residual Number System in mind, as discussed for instance in [8, 9, 10, 11].

We now summarize the main content of the paper. Section 6 shows how to extract an encryption of a coefficient $\mu_i$ (with respect to a polynomial basis) from an encryption of the polynomial $\mu(X)$. While this process is standard practice, we introduce a systematic framework
for defining it within the context of any cyclotomic field. This section also emphasizes the
significance of the dual basis related to the scalar product, which we express in terms of the
trace operator (refer to Section 3). Notably, the application of duality techniques facilitates a
natural approach to scenarios where the multi-index **i** is also encrypted.

In Section 7 we present a novel formulation of the standard functional bootstrapping procedure in terms of the trace operator and the dual basis. This viewpoint makes transparent the “negacyclic” constraints that target functions must satisfy: first in the setting of prime-power cyclotomic rings $M = t^\alpha$ with $p = t$, and then for arbitrary composite $M$ and any choice of $p$.

We introduce two algorithms to determine the bootstrap test polynomial and prove that they are quasi-optimal with respect to the admissible incoming error they tolerate. Moreover, we show that adopting non-power-of-two cyclotomic rings does not worsen error performance. Concretely, we provide a noise analysis of the bootstrap output for general $M$ and show, for example, that the variance increase when passing from $M = 2^\alpha$ to $M = t_1^{\alpha_1} \dots t_r^{\alpha_r}$ is bounded by a factor of $2^r$—precisely the variance growth associated with $2^r - 1$ homomorphic additions. Our analysis also recovers in certain results from [20].

Fully homomorphic encryption schemes are governed by two principal security notions; the stronger, IND-CPA$^D$ (introduced in [28]), explicitly accounts for possible decryption failures. When the failure probability is merely small, achieving IND-CPA$^D$ typically demands substantially larger parameters than those sufficient for IND-CPA. A primary source of such failures is the modulus-switch operation, which induces a drift in noise levels<fnref n="1" /> [3]. Although a detailed analysis of this phenomenon within our general cyclotomic framework lies outside the scope of this paper, it is noticeable that an appropriate choice of parameters $M$ and $p$ can substantially lower the probability of decryption failure by allowing bootstrapping of ciphertexts with larger admissible error. We conclude Section 7 by presenting several practical choices of $M$ and $p$ together with the corresponding security parameters.

Section 8 begins by a comprehensive overview of the various trace operations discussed throughout this paper. Building on the strategy of [13] for power-of-two cyclotomic fields, we show how classical Galois theory can be applied within our algebraic framework to construct fast homomorphic computations of field traces. This constitutes a nontrivial extension to the general case of cyclotomic indices, and we believe that the trace operator offers significant advantages for a range of applications.

Finally, Section 9 presents fast strategies for packing, i.e., combining multiple LWE encryp-
tions into a single polynomial encryption. The structure of the fields considered in this paper
introduces additional complexities to standard algorithms. Once again, we will revisit accelera-
tion techniques, as demonstrated in [13], and show how they can be effectively adapted to the
context of general cyclotomic polynomials while maintaining computational efficiency.

## 2 Related works

The selection of underlying algebraic structures, particularly cyclotomic polynomials, is a crucial
element of Fully Homomorphic Encryption (FHE) schemes, as these choices significantly influ-
ence efficiency and functionality. Notably, several studies have investigated the adaptation of the
Number Theoretic Transform (NTT) for these polynomials, which can greatly enhance the speed
of polynomial multiplication, with efficiency gains being especially pronounced for specific pa-
rameter selections, as demonstrated by Bajard et al. [2] in their RNS variant of FV-like schemes.
In addition to efficiency, noise growth behavior presents another critical concern, particularly
as it differs from what is observed in power-of-two cyclotomic rings; this issue was examined in

<footnote n="1">¹The use of more general indices $M$ integrates well with the procedure of [3].</footnote>
the recent paper by De Micheli et al. [20], underscoring the importance of understanding noise dynamics for establishing the parameters and overall effectiveness of FHE schemes. For instance, Kim et al. [26] explore how these polynomials specifically impact noise growth within the context of private query processing. When employing general cyclotomic polynomials, selecting optimal parameters becomes increasingly complex due to the interplay between polynomial structure, noise growth, and security considerations. Costache and Smart [18] provide a comprehensive comparison of various ring choices, offering detailed evaluations of schemes that utilize different prime-power cyclotomic structures. Given the critical nature of security in FHE schemes based on general cyclotomic polynomials, Eric Crockett and Chris Peikert [19] explore significant obstacles associated with the Ring Learning With Errors (Ring-LWE) problem. They discuss various factors that complicate the implementation and security of RLWE-based schemes, including issues related to parameter selection, the implications of error distributions, and the impact of specific polynomial structures on both security and efficiency. Finally, extension to multivariate RLWE with several cyclotomic polynomials is for instance considered in [5] while Chen et al. [14] investigate potential vulnerabilities and attack strategies that could be exploited due to the unique characteristics of Galois non-dual RLWE families.

# 3 Algebraic setting

In this section, we present several basic definitions essential for the foundation of the encryption protocol. While some of this material could have been introduced later in the paper, doing so would have compromised clarity, as many concepts here also possess more compact though more abstract definitions we could have relied upon. The identification of the dual sets with their expressions is provided below.

## 3.1 General cyclotomic polynomials

We begin by briefly revisiting the definition of cyclotomic polynomials, along with some of their properties and representations when $M$ is a power of a prime or more generally the product of prime powers. Let $M \ge 1$ and $\zeta_M = e^{2\pi i/M}$.

**Definition 3.1** The $M$-th cyclotomic polynomial is the minimal polynomial of a primitive $M$-th root of unity:

$$ \Phi_M(X) = \prod_{1 \le k \le M, \gcd(k,M)=1} (X - \zeta_M^k). $$

Equivalently,

$$ X^M - 1 = \prod_{d|M} \Phi_d(X), $$

and $\Phi_M(X) \in \mathbb{Z}[X]$ is monic, irreducible over $\mathbb{Q}$, with $\deg \Phi_M = \varphi(M)$, where $\varphi$ is the Totient function.

If $t$ is prime and $\alpha \ge 1$, then

$$ \Phi_{t^\alpha}(X) = \frac{X^{t^\alpha} - 1}{X^{t^\alpha - 1} - 1} = \sum_{j=0}^{t^\alpha - 1} X^{jt^{\alpha-1}}. $$

In particular $\Phi_t(X) = 1 + X + \cdots + X^{t-1}$ and $\Phi_{2^\alpha}(X) = X^{2^\alpha - 1} + 1$, which is the common special case.
**Reduction rules for composite indices.** Writing $M = t^\alpha u$ with $t$ prime and $\gcd(t, u) = 1$, the following identities in $\mathbb{Z}[X]$ hold:

1. Coprime lift: $\Phi_{ut}^\alpha(X) = \Phi_{ut}(X^{t^{\alpha-1}})$.

2. Adjoining a new prime factor: if $t \nmid u$ then $\Phi_u(X)|\Phi_u(X^t)$ in $\mathbb{Z}[X]$ and

$$ \Phi_{ut}(X) = \frac{\Phi_u(X^t)}{\Phi_u(X)}. $$

**Example 3.2** Using previous rules, one obtains-for example-

$$ \Phi_{15}(X) = \frac{(X^{15} - 1)(X - 1)}{(X^5 - 1)(X^3 - 1)}, $$

which simplifies to a monic degree $\varphi(15) = 8$ polynomial with integer coefficients.

In this text, we consider a general index $M$, factored as

$$ M = \prod_{\ell=1}^{r} m_{\ell} \in \mathbb{N}_{>0}, \qquad (1) $$

where each $m_\ell = t_\ell^{\alpha_\ell}$ for $\ell = 1, \dots, r$, with $t_\ell$ prime integers and $\alpha_\ell \in \mathbb{N}_{>0}$. It is common in practice to consider $r = 1, 2$, or $3$; we will mention these cases briefly throughout the paper. For each $\ell = 1, \dots, r$, define:

$$ \hat{m}_{\ell} = \frac{M}{m_{\ell}}, \quad m'_{\ell} = \frac{m_{\ell}}{t_{\ell}} \quad \text{and} \quad N_{\ell} = \varphi(m_{\ell}) = (t_{\ell} - 1)m'_{\ell}. $$

Note that the total degree factorizes as $N = N_1 \cdots N_r$. We end up this subsection by stating a useful (and well-known) relation on cyclotomic polynomials:

**Proposition 3.3** Let $M$ be composite of the form (1) and $d$ a coprime with $M$. Then

$$ \forall 1 \le \ell \le r, \quad \Phi_M(X) | \Phi_{m_\ell}(X^{\hat{m}_\ell}) \quad \text{and} \quad \Phi_M(X) | \Phi_M(X^d). $$

## 3.2 The cyclotomic field $\mathcal{K}$ and the ring of algebraic integers $\mathcal{R}$

All polynomial sets considered in the following sections are embedded within the ring of polynomials with rational coefficients modulo $\Phi_M$, which we denote by $\mathcal{K}$. This ring forms a Galois extension of $\mathbb{Q}$ and admits both the structure of a field and that of a $\mathbb{Q}$-vector space, with dimension $N = \varphi(M)$. Consequently, it is natural to examine the action of the trace operator on $\mathcal{K}$, the associated scalar product on $\mathcal{K}^2$, and to construct the dual basis of the powerful basis—see below—which allows both $\mathcal{R}^\vee$ and $\mathcal{T}^\vee$ to be expressed explicitly. In this work, the notations $P \bmod \Phi_M$ or $[P]_{\Phi_M}$ will be used interchangeably to refer either to the equivalence class

$$ P(X) + \Phi_M(X)Q(X), $$

where $Q \in \mathbb{Q}[X]$, or to a specific representative polynomial $P$ of this class.

**Definition 3.4 (Field of rational polynomials modulo $\Phi_M$)** The field of polynomials with coefficients in $\mathbb{Q}$ modulo $\Phi_M(X)$ is defined as the quotient ring

$$ \mathcal{K} = \frac{\mathbb{Q}[X]}{(\Phi(X))} = \{P \bmod \Phi_M, P \in \mathbb{Q}_{N-1}[X]\}. $$

We denote the ring of algebraic integers of $\mathcal{K}$ as $\mathcal{R}$: it is made of the equivalence classes of $\mathcal{K}$ which have representatives in $\mathbb{Z}_{N-1}[X]$, that is to say

$$ \mathcal{R} = \{P \bmod \Phi_M, P \in \mathbb{Z}_{N-1}[X]\}. $$
The trace operator in the context of Galois extensions is a linear map from a field extension (here $\mathcal{K}$) back to its base field (here $\mathbb{Q}$). Denoting the associated Galois group $\text{Gal}(\mathcal{K}/\mathbb{Q})$, the trace of an element $P \in \mathcal{K}$ is given by

$$ \text{Tr}_{\mathcal{K}/\mathbb{Q}}(P) = \sum_{\tau \in \text{Gal}(\mathcal{K}/\mathbb{Q})} \tau(P) \in \mathbb{Q}, $$

where the sum accounts for the action of each automorphism $\tau$ in the Galois group (that is to say here the group of substitutions $X \mapsto X^d$ for all $1 \le d \le M$ coprime with $M$) on $P$. As the trace plays a crucial role in studying the structure and properties of $\mathcal{K}$, we give below its definition instantiated in the context of cyclotomic rings:

**Definition 3.5 (Trace operator)** The trace operator $\text{Tr}$ is defined as the linear map

$$ \text{Tr}: \quad \mathcal{K} \to \mathbb{Q} \\ P(X) \mapsto \sum_{\text{gcd}(d,M)=1} P(X^d) \quad \text{mod} \quad \Phi_M \qquad (2) $$

The trace is a well-defined operator on $\mathcal{K}$, as its value does not depend on the particular representative of a class in $\mathcal{K}$: for any $d$ such that $\text{gcd}(d, M) = 1$, the cyclotomic polynomial $\Phi_M(X)$ indeed divides $\Phi_M(X^d)$ (Proposition 3.3), so that

$$ \sum_{\text{gcd}(d,M)=1} (P + k\Phi_M)(X^d) = \sum_{\text{gcd}(d,M)=1} P(X^d) \quad \text{mod} \quad \Phi_M. $$

We are now in position to introduce the following scalar product:

**Definition 3.6 (Scalar product)** The scalar product $\langle \cdot, \cdot \rangle$ is defined on $\mathcal{K}^2$ as follows

$$ \forall (P, Q) \in \mathcal{K}^2, \quad \langle P, Q \rangle = \text{Tr}(P(X)\bar{Q}(X)) \in \mathbb{Q} \qquad (3) $$

$$ \text{with } \bar{Q}(X) = Q(X^{-1}) \quad \text{mod} \quad \Phi_M = Q(X^{M-1}) \quad \text{mod} \quad \Phi_M. $$

It is straightforward to verify that this scalar product adheres to the typical requirements found in vector spaces, such as bilinearity, symmetry, and positive definiteness. This ensures that $\langle P, Q \rangle$ is both a well-defined and fundamentally sound operation within the context of this algebraic framework.

### 3.2.1 Canonical and powerful bases

The family of monomials $(X^i)_{0 \le i \le N-1}$ forms the canonical basis of $\mathcal{K}$, but its computational efficiency is limited—reducing a polynomial modulo $\Phi_M$ with degree exceeding $N-1$ is inherently complex. In contrast, the powerful basis, introduced in [29], offers a sparse dual basis and greatly simplifies arithmetic operations. Monomials in the set

$$ \mathcal{P}_M = \{ X^{i_1 \hat{m}_1 + i_2 \hat{m}_2 + \dots + i_r \hat{m}_r} \mod \Phi_M : 0 \le i_\ell < N_\ell, \ 1 \le \ell \le r \} $$

constitute a basis of $\mathcal{K} = \mathbb{Q}[X]/\Phi_M(X)$, herein referred to as the powerful basis$^2$. This basis can be described by the one-to-one mapping $\rho$ from $\mathbf{I} = \{ \mathbf{i} = (i_1, \dots, i_r) \mid 0 \le i_\ell < m_\ell, \ \ell = 1, \dots, r \}$, to $\{0, \dots, M-1\}$ such that

$$ \mathbf{i} \mapsto \rho(\mathbf{i}) = [i_1 \hat{m}_1 + i_2 \hat{m}_2 + \dots + i_r \hat{m}_r]_M \qquad (4) $$

<footnote>$^2$The fact that it is a basis can be established through numerous methods, such as employing Euclidean division sequentially with respect to each variable $X_\ell = X^{\hat{m}_\ell}$, or via a direct argument based on duality principles and scalar products.</footnote>
where the indices satisfy

$$0 \le i_{\ell} < (t_{\ell} - 1)m'_{\ell}, \quad \text{for } \ell = 1, \dots, r,$$

and where $[i]_m$ denotes the integer between 0 and $m-1$, coinciding with $i$ modulo $m$, i.e., equivalent to $i$ up to a multiple of $m$. This construction distinctly diverges from the traditional canonical basis $(X^k)_{0 \le k \le N-1}$, as exemplified in the following illustrative case.

**Example 3.7** Designate $t_1 = 3$ and $t_2 = 5$ and consider $M = t_1t_2 = 15$. The cyclotomic polynomial explicitly is:

$$\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3 - X + 1.$$

The standard basis is the set $\{1, X, X^2, X^3, X^4, X^5, X^6, X^7\}$, whereas the powerful basis corresponds to exponents $i = i_1t_2 + i_2t_1$, with $i_1 \in \{0, 1\}$ and $i_2 \in \{0, 1, 2, 3\}$, and assumes the form:

$$\mathcal{P}_M = \{1, X^3, X^5, X^6, X^8, X^9, X^{11}, X^{14}\}.$$

As a matter of fact, we have, for example, $X^8 = X^7 - X^5 + X^4 - X^3 + X - 1 \pmod{\Phi_M}$. In this framework however, if we define the elements $X_1 = X^{t_2} = X^5$ and $X_2 = X^{t_1} = X^3$, then the powerful basis can be interpreted as the tensor product of the bases associated to the subfields:

$$\{1, X_1\} \quad \text{for} \quad \mathbb{Q}[X_1]/\Phi_{t_1}(X_1) \quad \text{and} \quad \{1, X_2, X_2^2, X_2^3\} \quad \text{for} \quad \mathbb{Q}[X_2]/\Phi_{t_2}(X_2).$$

Thus, the powerful basis $\mathcal{P}_M$ can be alternatively written as

$$\{1, X_2, X_2^2, X_2^3, X_1, X_1X_2, X_1X_2^2, X_1X_2^3\}.$$

This expresses the powerful basis as the basis of the space $\mathbb{Q}[X_1, X_2]/\Phi_{t_1}(X_1)/\Phi_{t_2}(X_2)$.

**Remark 3.8** It is noteworthy that the family $(X^i)_{0 \le i \le M-1}$, where each $i$ is coprime to $M$, does not always constitute a basis of $K$, particularly when $M = 2^\alpha$. In such scenarios, the relations:

$$X^{N+j} = -X^j, \quad \text{for } 0 \le j \le N-1,$$

hold, and, crucially, if $j$ is odd, then $N+j$ is also odd, implying linear dependencies among the set of monomials.

For practical applications, we define the set of multi-indices:

$$\mathbf{J} = \{\mathbf{j} = (j_1, \dots, j_r) \mid 0 \le j_\ell < \varphi(m_\ell), \ \ell = 1, \dots, r\}. \qquad (5)$$

From a computational perspective, any polynomial $A(X)$ in $\mathbb{Q}[X]/\Phi_M(X)$ can be expressed in the basis $\mathcal{P}_M$ as:

$$A(X) = \sum_{\mathbf{j} \in \mathbf{J}} a_{\mathbf{j}} X^{[j_1 \hat{m}_1 + j_2 \hat{m}_2 + \dots + j_r \hat{m}_r]_M},$$

where $\mathbf{j} = (j_1, \dots, j_r)$. Furthermore, this polynomial may be interpreted as a multivariate polynomial by setting:

$$X_{\ell} = X^{\hat{m}_{\ell}}, \quad 1 \le \ell \le r,$$

which yields:

$$A(X) = A(X_1, X_2, \dots, X_r) = \sum_{\mathbf{j} \in \mathbf{J}} a_{\mathbf{j}} X_1^{j_1} X_2^{j_2} \cdots X_r^{j_r}.$$
### 3.2.2 Computing the polynomial modulo

Our objective in this section is to demonstrate that reducing any polynomial modulo $\Phi_M \in \mathbb{Q}[X]$ becomes straightforward when the polynomial is expressed as a multivariate polynomial in variables $X_1, X_2, \dots, X_r$, whereas this reduction process is considerably more cumbersome when utilizing the standard canonical basis $(X^i)_{0\le i<N}$. To elaborate, consider the following:

**Proposition 3.9** Let $t_1, \dots, t_r$ be $r$ distinct prime integers and let $M = m_1 \cdots m_r$ where $m_\ell = t_\ell^{\alpha_\ell}$ and $\alpha_\ell \in \mathbb{N}_>$ for all $1 \le \ell \le r$. Let $P \in \mathbb{Q}[X]$ and assume that $A = P \bmod (X^M - 1)$ is expressed as:

$$A(X) = \sum_{\mathbf{i} \in \mathbf{I}} a_{\mathbf{i}} X^{\rho(\mathbf{i})} = \sum_{(i_1, i_2, \dots, i_r) \in \mathbf{I}} a_{i_1, \dots, i_r} X_1^{i_1} \cdots X_r^{i_r}.$$

The reduction of $A$ modulo $\Phi_M$ is given by evaluating the multivariate polynomial representation and reducing each term according to $\Phi_{m_\ell}(X_\ell)$. Specifically, the expression is:

$$(A \bmod \Phi_M)(X) = \sum_{\mathbf{i} \in \mathbf{J}} \left( \sum_{\mathbf{u} \in \{0,1\}^r} (-1)^{|\mathbf{u}|_1} a_{\mathbf{u}(\mathbf{N}+[\mathbf{i}]_{\mathbf{m}'})+(\mathbf{1}-\mathbf{u})\mathbf{i}} \right) X^{\rho(\mathbf{i})} \quad (6)$$

where $\mathbf{N} = (N_1, \dots, N_r)$, $\mathbf{1} = (1, \dots, 1) \in \mathbb{N}^r$, $[\mathbf{i}]_{\mathbf{m}'} = ([i_1]_{m'_1}, \dots, [i_r]_{m'_r})$ and the product of vectors is meant to be component-wise.

*Proof.* Expressing $A$ as a polynomial of $(\mathbb{Q}[X_2, \dots, X_\ell]/(\Phi_{m_2}(X_2) \cdots \Phi_{m_\ell}(X_\ell))[X_1]/\Phi_{m_1}(X_1)$, we write:

$$A(X) = \sum_{0 \le i_1 < m_1} \left( \sum_{\mathbf{j} \in \mathbf{I} / j_1 = i_1} a_{i_1, j_2, \dots, j_r} X_2^{j_2} \cdots X_r^{j_r} \right) X_1^{i_1}$$

The reduction modulo $\Phi_{m_1}(X_1)$ then becomes

$$(A \bmod \Phi_{m_1})(X_1, \dots, X_r) = \sum_{i_1=0}^{N_1-1} \left( \sum_{\mathbf{j} \in \mathbf{I}/j_1=i_1} (a_{j_1, j_2, \dots, j_r} - a_{N_1+[j_1]_{m'_1}, j_2, \dots, j_r}) X_2^{j_2} \cdots X_r^{j_r} \right) X_1^{i_1}.$$

Introducing the notation

$$\forall \mathbf{i} \in \mathbf{I} \text{ such that } i_1 < N_1, \quad a_{\mathbf{i}}^{[1]} = a_{i_1, i_2, \dots, i_r} - a_{N_1 + [i_1]_{m'_1}, i_2, \dots, i_r}$$

we can write

$$(A \bmod \Phi_{m_1})(X_1, \dots, X_r) = \sum_{\mathbf{i} \in \mathbf{I} / i_1 < N_1} a_{\mathbf{i}}^{[1]} X_1^{i_1} \cdots X_r^{i_r}.$$

Repeating the same reduction modulo $\Phi_{m_2}(X_2)$ now with respect to $X_2$ we obtain

$$(A \bmod \Phi_{m_1} \bmod \Phi_{m_2})(X_1, \dots, X_r) = \sum_{\mathbf{i} \in \mathbf{I} / i_1 < N_1, i_2 < N_1} a_{\mathbf{i}}^{[2]} X_1^{i_1} \cdots X_r^{i_r}$$

with

$$\forall \mathbf{i} \in \mathbf{I} \text{ such that } i_1 < N_1, i_2 < N_2, \quad a_{\mathbf{i}}^{[2]} = a_{i_1, i_2, \dots, i_r}^{[1]} - a_{i_1, N_2 + [i_2]_{m'_2}, \dots, i_r}^{[1]}.$$

Continuing this recurrence over the remaining indices $i_3, \dots, i_r$, we arrive at

$$(A \bmod \Phi_M)(X_1, \dots, X_r) = \sum_{\mathbf{i} \in \mathbf{J}} a_{\mathbf{i}}^{[r]} X_1^{i_1} \cdots X_r^{i_r}$$
where, for each multi-index $i \in \mathbf{I}$, the initial coefficients satisfy $a_i^{[0]} = a_i$ and where moreover, for each step $\ell = 1, \dots, r$

$$ \forall i \in \mathbf{I} \text{ such that } i_1 < N_1, \dots, i_\ell < N_\ell, \quad a_i^{[\ell]} = a_{i_1, \dots, i_\ell, \dots, i_r}^{[\ell-1]} - a_{i_1, \dots, N_\ell + [i_\ell]_{m'_\ell}, \dots, i_r}^{[\ell-1]} $$

By unfolding this iterative scheme, we recover the explicit formula expressed in Equation (6).

**Example 3.10 (Case $r=1$)** Let $t$ be a prime, $\alpha \in \mathbb{N}_>$, $N = (t-1)t^{\alpha-1}$ and $m' = t^{\alpha-1}$. We have

$$ A \bmod \Phi_M = \sum_{i=0}^{N-1} (a_i - a_{N+[i]_{m'}}) X^i. \qquad (7) $$

**Example 3.11 (Case $r=2$)** Let $t_1, t_2$ be prime numbers, $(\alpha_1, \alpha_2) \in \mathbb{N}_>^2$, $N_1 = (t_1-1)t_1^{\alpha_1-1}$, $N_2 = (t_2-1)t_2^{\alpha_2-1}$, $m'_1 = t_1^{\alpha_1-1}$ and $m'_2 = t_2^{\alpha_2-1}$. We have

$$ A \bmod \Phi_M = \sum_{i \in \mathbf{J}} \left( a_{i_1, i_2} - a_{i_1, N_2 + [i_2]_{m'_2}} - a_{N_1 + [i_1]_{m'_1}, i_2} + a_{N_1 + [i_1]_{m'_1}, N_2 + [i_2]_{m'_2}} \right) X_1^{i_1} X_2^{i_2} $$

**Example 3.12 (Case $r=3$)** Mutatis mutandis, the expression of $A \bmod \Phi_M$ becomes

$$ \sum_{i \in \mathbf{I}} \left( -a_{N_1+[i_1]_{m'_1}, i_2, i_3} - a_{i_1, N_2+[i_2]_{m'_2}, i_3} - a_{i_1, i_2, N_3+[i_3]_{m'_3}} + a_{N_1+[i_1]_{m'_1}, N_2+[i_2]_{m'_2}, i_3} + a_{i_1, i_2, i_3} + a_{N_1+[i_1]_{m'_1}, i_2, N_3+[i_3]_{m'_3}} + a_{i_1, N_2+[i_2]_{m'_2}, N_3+[i_3]_{m'_3}} - a_{N_1+[i_1]_{m'_1}, N_2+[i_2]_{m'_2}, N_3+[i_3]_{m'_3}} \right) X_1^{i_1} X_2^{i_2} X_3^{i_3} $$

In practice, this proposition indicates that to compute the reduction of a polynomial modulo $\Phi_M$, it suffices to perform successive reductions with respect to each variable $X_\ell$ independently. The following algorithm illustrates this process:

**Algorithm 1 Iterative Modulo Reduction**

**Input:** Initial coefficients $a_i$ for all $i \in \mathbf{I}$.

**Parameters:** $N_\ell, m'_\ell$ for $\ell = 1, \dots, r$.

**Output:** Coefficients $a_i^{[r]}$.

1: Initialization:

2: **for all** $i \in \mathbf{I}$ **do**

3: $a_i^{[0]} := a_i$

4: **end for**

5: **for** $\ell = 1$ to $r$ **do**

6: **for all** $i = (i_1, \dots, i_r) \in \mathbf{I}$ such that $i_1 < N_1, \dots, i_\ell < N_\ell$ **do**

7: $a_i^{[\ell]} := a_{i_1, \dots, i_\ell, \dots, i_r}^{[\ell-1]} - a_{i_1, \dots, N_\ell + [i_\ell]_{m'_\ell}, \dots, i_r}^{[\ell-1]}$

8: **end for**

9: **end for**

### 3.3 Trace operator and dual sets

We recall the expression of the trace operator introduced earlier (omitting the indexation and with the notation $\tau_d : P(X) \mapsto P(X^d)$):

$$ \forall P \in \mathcal{K}, \quad \mathrm{Tr}(P) = \sum_{\substack{1 \le d < M \\ \mathrm{gcd}(d, M)=1}} \tau_d(P). $$
and refer to the associated scalar product defined on $\mathcal{K} \times \mathcal{K}$ (see Definition 3.6). Now, given a basis $(B_i)_{i \in \mathcal{J}}$ of $\mathcal{R}$, we denote by $(B_i^*)_{i \in \mathcal{J}} \subset \mathcal{K}$ its dual basis with respect to the bilinear form (3):

$$ \forall (\mathbf{i}, \mathbf{j}) \in \mathbf{J}^2, \quad \langle B_i^*, B_j \rangle = \delta_{\mathbf{i}, \mathbf{j}}. $$

The dual basis corresponding to the powerful basis admits an explicit, computationally effective form, which we now describe:

* Case $M = t^\alpha$, where $t$ is prime and $\alpha \in \mathbb{N}_>$ and $N = \varphi(M)$. The powerful basis is

$$ \Omega_i(X) = X^i, \quad 0 \le i < N. $$

Its dual basis is explicitly given by (with $m' = \frac{M}{t}$)

$$ \Omega_i^*(X) = \frac{1}{M} \left( X^i - X^{N+[i]_{m'}} \right), \quad 0 \le i < N. $$

* Case $M = m_1 m_2 \cdots m_r$ defined as in Formula (1). The basis elements are

$$ \Omega_i(X) = X^{i_1 \hat{m}_1 + \cdots + i_r \hat{m}_r} = \Omega_{i_1}(X_1) \cdots \Omega_{i_r}(X_r), $$

where $\mathbf{i} = (i_1, \dots, i_r) \in \mathbf{J}$ and the dual basis takes the form

$$ \forall \mathbf{i} \in \mathbf{J}, \quad \Omega_i^*(X) = \frac{1}{M} \prod_{\ell=1}^{r} \left( X_{\ell}^{i_{\ell}} - X_{\ell}^{N_{\ell} + [i_{\ell}]_{m'_{\ell}}} \right) = \Omega_{i_1}^*(X_1) \cdots \Omega_{i_r}^*(X_r). $$

**Lemma 3.13** Under the previous assumptions and notations, the following identities hold:

* For all $\mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbf{I}$

$$ \mathrm{Tr}(\Omega_i(X)) = \prod_{\ell=1}^{r} (m_\ell \delta_{i_\ell, 0} - m'_\ell) \delta_{[i_\ell]_{m'_\ell}, 0}. $$

where $\delta$ denotes the Kronecker delta.

* If the formula for $\Omega_i^*$ is extended to encompass indices $\mathbf{i} \in \mathbf{I} \setminus \mathbf{J}$, it evaluates to zero:

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad \Omega_i^* = 0. $$

* For all $\mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbf{I}$ and for all $1 \le \ell \le r$, the expansion of $\Omega_{i_\ell}(X_\ell)$ in terms of the canonical/powerful basis of $\mathbb{Q}[X_\ell]/\Phi_{m_\ell}(X_\ell)$ is given by:

$$ [\Omega_{i_\ell}(X_\ell)]_{\Phi_{m_\ell}} = \mathbb{1}_{0 \le i_\ell < N_\ell} \Omega_{i_\ell}(X_\ell) - \sum_{\substack{0 \le k < N_\ell \\ N_\ell + [k]_{m'_\ell} = i_\ell}} \Omega_k(X_\ell), $$

and the multivariate expansion:

$$ [\Omega_i(X)]_{\Phi_M} = \prod_{\ell=1}^{r} [\Omega_{i_\ell}(X_\ell)]_{\Phi_{m_\ell}}. $$
• For all $\mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbf{I}$ and $\mathbf{j} = (j_1, j_2, \dots, j_r) \in \mathbf{J}$, the scalar product satisfies:

$$ \langle \Omega_{\mathbf{i}}, \Omega_{\mathbf{j}}^* \rangle = \prod_{\ell=1}^{r} (\delta_{i_{\ell}, j_{\ell}} - \delta_{i_{\ell}, N_{\ell} + [j_{\ell}]_{m'_{\ell}}}) = \sum_{\substack{\mathbf{u} \in \{0,1\}^r, \\ \mathbf{i} = (\mathbf{1}-\mathbf{u})\mathbf{j} + \mathbf{u}(\mathbf{N}+[\mathbf{j}]_{\mathbf{m}'})}} (-1)^{|\mathbf{u}|} $$

where $\mathbf{N} = (N_1, \dots, N_r)$, $\mathbf{1} = (1, \dots, 1) \in \mathbb{N}^r$, $[\mathbf{j}]_{\mathbf{m}'} = ([j_1]_{m'_1}, \dots, [j_r]_{m'_r})$ and the product of vectors is meant to be component-wise. Here and in the sequel, $|\mathbf{u}| = \#\{1 \le \ell \le r, u_\ell \ne 0\}$.

*Proof.* Assume $M = t^\alpha$ with $t$ prime and $\alpha \ge 1$. In $\mathcal{K}$ one has, for all $n, k \in \mathbb{Z}$,

$$ \mathrm{Tr}(X^n) = 0 \text{ if } [n]_{m'} \neq 0 \text{ and } \mathrm{Tr}(X^{km'}) = M \delta_{[k]_t, 0} - m', $$

where $^3 m' = \frac{M}{t}$. These identities are checked by elementary computation. Now, using the following fundamental property of the trace in tensor rings

$$ \mathrm{Tr} \left( \prod_{\ell=1}^{r} P_{\ell}(X_{\ell}) \right) = \prod_{\ell=1}^{r} \mathrm{Tr} (P_{\ell}(X_{\ell})) $$

where the $P_\ell(X_\ell)$'s are polynomials in the respective rings $\mathbb{Q}[X_\ell]/\Phi_{m_\ell}(X_\ell)$, we obtain, for any $\mathbf{i} = (i_1, \dots, i_r) \in \mathbf{I}$:

$$ \mathrm{Tr} \left( \prod_{\ell=1}^{r} \Omega_{i_{\ell}} \right) = \prod_{\ell=1}^{r} \mathrm{Tr} (\Omega_{i_{\ell}}) = \prod_{\ell=1}^{r} (m_{\ell} \delta_{i_{\ell}, 0} - m'_{\ell}) \delta_{[i_{\ell}]_{m'_{\ell}}, 0} $$

where we have used the formula for the trace in $\mathbb{Q}[X_\ell]/\Phi_{m_\ell}(X_\ell)$. The second point follows from observing that $i_\ell = N_\ell + [i_\ell]_{m'_\ell}$ if $N_\ell \le i_\ell < m_\ell$. The third point directly derives from the formula (7) for the modulo of $\Omega_{i_\ell}$ for $1 \le \ell \le r$ (see Proposition 3.9) and the fourth point once again follows from the tensorization of the trace:

$$ \langle \Omega_{\mathbf{i}}, \Omega_{\mathbf{j}}^* \rangle = \prod_{\ell=1}^{r} \langle \Omega_{i_{\ell}}, \Omega_{j_{\ell}}^* \rangle = \prod_{\ell=1}^{r} (\delta_{i_{\ell}, j_{\ell}} - \delta_{i_{\ell}, N_{\ell} + [j_{\ell}]_{m'_{\ell}}}) = \sum_{\substack{\mathbf{u} \in \{0,1\}^r, \\ \mathbf{i} = (\mathbf{1}-\mathbf{u})\mathbf{j} + \mathbf{u}(\mathbf{N}+[\mathbf{j}]_{\mathbf{m}'})}} (-1)^{|\mathbf{u}|} $$

where we have first used the formula (7) and then expanded the product. In our discussion, we will utilize the ring $\mathcal{R}$ along with its dual $\mathcal{R}^\vee$. They are defined as follows:

$$ \mathcal{R} = \left\{ \sum_{\mathbf{i} \in \mathbf{J}} n_{\mathbf{i}} \Omega_{\mathbf{i}}, \ n_{\mathbf{i}} \in \mathbb{Z} \text{ for all } \mathbf{i} \in \mathbf{J} \right\} \quad \text{and} \quad \mathcal{R}^{\vee} = \left\{ \sum_{\mathbf{i} \in \mathbf{J}} \omega_{\mathbf{i}}^{*} \Omega_{\mathbf{i}}^{*}, \ \omega_{\mathbf{i}}^{*} \in \mathbb{Z} \text{ for all } \mathbf{i} \in \mathbf{J} \right\}. $$

Accordingly, we define the related modules:

$$ \mathcal{T} = \left\{ \sum_{\mathbf{i} \in \mathbf{J}} \mu_{\mathbf{i}} \Omega_{\mathbf{i}}, \ \mu_{\mathbf{i}} \in \mathbb{T}, \forall \mathbf{i} \in \mathbf{J} \right\} = \mathcal{K}/\mathcal{R} \quad \text{and} \quad \mathcal{T}^{\vee} = \left\{ \sum_{\mathbf{i} \in \mathbf{J}} \mu_{\mathbf{i}} \Omega_{\mathbf{i}}^{*}, \ \mu_{\mathbf{i}} \in \mathbb{T}, \forall \mathbf{i} \in \mathbf{J} \right\} = \mathcal{K}/\mathcal{R}^{\vee}. $$

The following proposition links the ring $\mathcal{R}$ and module $\mathcal{T}$ to their respective duals.

<footnote n="3">³More generally, for any $\mu(X) = \sum_{n=0}^{N-1} \mu_n X^n \in \mathcal{K}$, we have $\mathrm{Tr}(\mu(X)) = N\mu_0 - \frac{M}{t} \sum_{k=1}^{t-2} \mu_{kM/t}$.</footnote>
**Proposition 3.14** • The inverse of $\Omega_0^*(X)$ modulo $\Phi_M$ is given by

$$ \Omega_0^*(X)^{-1} = \prod_{\ell=1}^{r} m'_{\ell} \left( 1 + \sum_{k=1}^{t_{\ell}-2} (k-t_{\ell}+1) X^{km'_{\ell}} \right) \mod \Phi_M, $$

and its image through the automorphism (denoted by a bar) $X \mapsto X^{-1}$ is

$$ \overline{\Omega_0^*(X)}^{-1} = \prod_{\ell=1}^{r} m'_{\ell} \left( \sum_{k=0}^{t_{\ell}-2} (t_{\ell}-k-1) X^{km'_{\ell}} \right) \mod \Phi_M. \quad (8) $$

• For every $\mathbf{j} \in \mathbf{J}$, the relation

$$ (\Omega_0^*)^{-1} \Omega_j^* = \tilde{\Omega}_j $$

holds, where

$$ \tilde{\Omega}_j(X) = \prod_{\ell=1}^{r} \left( \sum_{k=0}^{(j\ell - [j\ell]_{m'_{\ell}})/m'_{\ell}} X^{j\ell - km'_{\ell}} \right) \in \mathbb{Z}[X]. $$

• The modules $\mathcal{R}^{\vee}$ and $\mathcal{T}^{\vee}$ are related to $\mathcal{R}$ and $\mathcal{T}$ via

$$ \mathcal{R}^{\vee} = \Omega_0^* \mathcal{R}, \quad \mathcal{T}^{\vee} = \Omega_0^* \mathcal{T}. $$

• The families $((\Omega_0^*)^{-1}\Omega_j^*)_{j \in \mathbf{J}}$ and $(\Omega_0^*\Omega_j)_{j \in \mathbf{J}}$ form bases of respectively the $\mathbb{Z}$-module $\mathcal{R}$ and the $\mathbb{Z}$-module $\mathcal{R}^{\vee}$.

*Proof.* In the special case where $M = t^\alpha$, the expression for $(\Omega_0^*)^{-1}$ can be derived by noting that

$$ \Omega_0^*(X) = \frac{1 - X^N}{M} $$

and recognizing that, since $\Phi_M(X)$ and $\Omega_0^*(X)$ are coprime in the Euclidean ring $\mathbb{Q}[X]$, Bézout's theorem guarantees the existence of polynomials $U, V \in \mathbb{Q}[X]$ such that

$$ \Omega_0^* U + \Phi_M V = 1. $$

This makes $U = (\Omega_0^*)^{-1} \mod \Phi_M$, i.e., the inverse of $\Omega_0^*$ modulo $\Phi_M$. It can be explicitly checked that whereas $V(X) = 1 + \frac{1}{t}(X^N - \Phi_M(X)) \in \mathcal{T}$,

$$ (\Omega_0^*)^{-1}(X) = t^{\alpha-1} \left( 1 + \sum_{k=1}^{t-2} (k+1-t) X^{k \frac{M}{t}} \right) \mod \Phi_M \quad \underbrace{\qquad \in \mathbb{Z}_{N-1}[X]} $$

is the representative of an element of $\mathcal{R}$, with integer coefficients. This can also be derived directly from the identity

$$ \Phi_M(X) \cdot (1 - X^{m'}) = 1 - X^M, $$

by differentiating with respect to $X$ (notably, in this case, $\overline{\Omega_0^*}(X) = \frac{1}{M}(1 - X^{m'})$). For composite $M$, observe that for each $\ell = 1, \dots, r$,

$$ (\overline{\Omega_0^*})^{-1}(X_\ell) = -X_\ell \Phi'_{m_\ell}(X_\ell) \mod \Phi_{m_\ell}, $$
which implies, due to the divisibility relation $\Phi_M(X) | \Phi_{m_\ell}(X^{\hat{m}_\ell})$,

$$ (\bar{\Omega}_0^*)^{-1}(X^{\hat{m}_\ell}) = -X^{\hat{m}_\ell} \Phi'_{m_\ell}(X^{\hat{m}_\ell}) \mod \Phi_M. $$

From this, the formula (8) follows by multiplication. Next, through tensorization, it suffices to establish the form of $\tilde{\Omega}_j$ for the case $r = 1$. We begin by expressing $j = u \frac{M}{t} + v$ with $0 \le u < t-1$ and $0 \le v < m'$:

$$ \bar{\Omega}_j^*(X) = X^{m'-v} \left( \frac{X^{(t-u-1)m'} - 1}{M} \right) = X^{m'-v} \cdot (-\bar{\Omega}_0^*)(X) \cdot \sum_{k=0}^{t-u-2} X^{km'}. $$

Thus,

$$ \bar{\Omega}_j^*(X) = -X^{-v} \sum_{k=0}^{t-u-2} X^{(k+1)m'}, $$

and

$$ \tilde{\Omega}_j^*(X) = -X^v \sum_{k=u+1}^{t-1} X^{km'} = X^v \sum_{k=0}^{u} X^{km'} \mod \Phi_M. $$

Since $(\Omega_i^*)_i \in \mathbf{J}$ and $(\Omega_0^*)^{-1} \Omega_i^* \in \mathbb{Z}[X]$ for all $i \in \mathbf{J}$, we have $\mathcal{R}^\vee \subset \Omega_0^* \mathcal{R}$. Moreover, $\Omega_0^* \Omega_i \in \mathcal{R}$ for all $i \in \mathbf{J}$, since $\langle \Omega_0^* \Omega_i, \Omega_k \rangle = \langle \Omega_0^*, \Omega_{k-i} \rangle \in \mathbb{Z}$. This proves the third claim, and the last one follows immediately. We conclude this subsection with the following definitions addressing the case of random coefficients:

**Definition 3.15** Let $a = \sum_{i \in \mathbf{J}} a_i \Omega_i \in \mathcal{T}$ and $a^* = \sum_{i \in \mathbf{J}} a_i^* \Omega_i^* \in \mathcal{T}^\vee$, where the coefficients $a_i$ and $a_i^*$ are random variables with standard deviations $\sigma(a_i)$ and $\sigma(a_i^*)$. We define

$$ \sigma(a) = \max_{i \in \mathbf{J}} \sigma(a_i) \quad \text{and} \quad \sigma(a^*) = \max_{i \in \mathbf{J}} \sigma(a_i^*). $$

**Remark 3.16** The standard deviation of a polynomial is thus defined via its representation in the basis $(\Omega_i)_{i \in \mathbf{J}}$ (or its dual $(\Omega_i^*)_{i \in \mathbf{J}}$).

## 3.4 From the powerful basis to its dual and back

Certain operations are more naturally carried out in a particular polynomial basis. For instance, fast multiplication via the FFT is most conveniently performed when polynomials are expressed in the powerful basis $(\Omega_i)_{i \in \mathbf{J}}$. In this section, we present an explicit, invertible, and sparse map between the coefficient vectors in this basis and in the dual basis $(\Omega_i^*)_i \in \mathbf{J}$. We first consider the prime-power case $M = t^\alpha$ and then extend the approach tensorially to the general case.

**Lemma 3.17** Let $M = t^\alpha$ for a given prime $t$ and $\alpha \in \mathbb{N}_>$. Denote by $\mu$ the expansions of a polynomial of $\mathcal{K}$ in both bases $(\Omega_i)_{0 \le i \le N-1}$ and $(\Omega_i^*)_{0 \le i \le N-1}$:

$$ \mu = \sum_{i=0}^{N-1} \mu_i \Omega_i = \sum_{i=0}^{N-1} \mu_i^* \Omega_i^*. $$

Then, the coefficients are related via

$$ \mu_i^* = M \mu_i - \frac{M}{t} S_{[i]_{m'}} \quad \mu_i = \frac{1}{M} \left( \mu_i^* + S_{[i]_{m'}} \right) $$
where $m' = \frac{M}{t}$ and for each $0 \le \lambda \le m' - 1$,

$$S_{\lambda} := \sum_{\substack{0 \le j \le N-1 \\ [j]_{m'} = \lambda}} \mu_j, \quad S_{\lambda}^* := \sum_{\substack{0 \le j \le N-1 \\ [j]_{m'} = \lambda}} \mu_j^* = m'S_{\lambda}.$$

In terms of the basis elements $\Omega$ and $\Omega^*$, the relations can be expressed as

$$\Omega_i^* = \frac{1}{M} (\Omega_i - \Omega_{N+[i]_{m'}}) = \frac{1}{M} (\Omega_i + \Sigma_{[i]_{m'}}) \\ \Omega_i = M\Omega_i^* - m'\Sigma_{[i]_{m'}}^*,$$

where

$$\Sigma_j := \sum_{k=0}^{t-2} \Omega_{km'+j} = m' \sum_{k=0}^{t-2} \Omega_{km'+j}^* =: m' \Sigma_j^*$$

for all $0 \le j \le m' - 1$.

*Proof.* The last two formulas of the lemma derive easily from the definition of $\Omega_i$ and $\Omega_i^*$ for $i = 0, \dots, N-1$. We then have

$$\mu(X) = \sum_{i=0}^{N-1} \mu_i (M\Omega_i^* - m'\Sigma_{[i]_{m'}}^*) = \sum_{i=0}^{N-1} M\mu_i\Omega_i^* - m' \sum_{\substack{0 \le k, K<t-1 \\ 0 \le j < m'}} \mu_{Km'+j}\Omega_{km'+j}^*.$$

This leads to the expression $\mu_i^* = M\mu_i - m'S_{[i]_{m'}}$. The formula for $\mu_i$ in terms of the $\mu_j^*$ is derived in a similar manner. These formulas can be easily and efficiently implemented (see the following algorithms). We next extend these computations to the composite case (1).

**Algorithm 2** Compute $\mu_i^*$ from $\mu_i$

**Require:** $(\mu_j)_{j=0}^{N-1}$: the coefficients in the canonical/powerful basis

**Require:** Parameters $M$ and $t$

1: Initialize an array $S$ of length $m' = M/t$ with zeros: $\forall \lambda, S_{\lambda} \leftarrow 0$

2: **for** $\lambda = 0$ to $m' - 1$ **do**

3: **for** $k = 0$ to $t - 2$ **do**

4: $S_{\lambda} \leftarrow S_{\lambda} + \mu_{km'+\lambda}$

5: **end for**

6: **end for**

7: **for** $i = 0$ to $N - 1$ **do**

8: $\lambda \leftarrow [i]_{m'}$

9: $\mu_i^* \leftarrow M \cdot \mu_i - m' \cdot S_{\lambda}$

10: **end for**

11: **Output:** the array $(\mu_i^*)_{i=0}^{N-1}$
**Algorithm 3** Compute $\mu_i$ from $\mu_i^*$

**Require:** $(\mu_j^*)_{j=0}^{N-1}$: the coefficients in the dual basis

**Require:** Parameters $M$ and $t$

1: Initialize an array $S^*$ of length $m' = M/t$ with zeros: $\forall \lambda, S_\lambda^* \leftarrow 0$

2: **for** $\lambda = 0$ to $m' - 1$ **do**

3: **for** $k = 0$ to $t - 2$ **do**

4: $S_\lambda^* \leftarrow S_\lambda^* + \mu_{km'+\lambda}^*$

5: **end for**

6: **end for**

7: **for** $i = 0$ to $N - 1$ **do**

8: $\lambda \leftarrow [i]_{m'}$

9: $\mu_i \leftarrow \frac{1}{M} \cdot \mu_i^* - \frac{1}{M} \cdot S_\lambda^*$

10: **end for**

11: **Output:** the array $(\mu_i)_{i=0}^{N-1}$

**Proposition 3.18** Assume $M$ is of the form (1). With the notation of the previous lemma, we have, for all $\mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbf{J}$,

$$ \Omega_{\mathbf{i}}^* = \frac{1}{M} \prod_{\ell=1}^{r} \left( \Omega_{i_{\ell}}(X_{\ell}) + \sum_{[i_{\ell}]_{m'_{\ell}}} (X_{\ell}) \right) = \frac{1}{M} \sum_{\mathbf{u} \in \{0,1\}^r} (-1)^{\|\mathbf{u}\|} \Omega_{(1-\mathbf{u})\mathbf{i}+\mathbf{u}(\mathbf{N}+[\mathbf{i}]_{m'})}, $$

where

$$ \Sigma_j(X_\ell) = \sum_{k=0}^{t_\ell-2} \Omega_{km'_\ell+j}(X_\ell) $$

and where $\mathbf{N} = (N_1, \dots, N_r)$, $[\mathbf{i}]_{m'} = ([i_1]_{m'_1}, \dots, [i_r]_{m'_r})$ and the product of vectors is meant to be component-wise. Conversely, we have

$$ \Omega_{\mathbf{i}} = M \prod_{\ell=1}^{r} \left( \Omega_{i_{\ell}}^*(X_{\ell}) - \frac{1}{t_{\ell}} \sum_{[i_{\ell}]_{m'_{\ell}}} \Omega_{[i_{\ell}]_{m'_{\ell}}}^*(X_{\ell}) \right), $$

where

$$ \Sigma_j^*(X_\ell) = \sum_{k=0}^{t_\ell-2} \Omega_{km'_\ell+j}^*(X_\ell) = \frac{1}{m'_\ell} \Sigma_j(X_\ell) $$

for all $1 \le \ell \le r$ and $0 \le j \le m'_\ell - 1$.

**Remark 3.19** By Lemma 3.13 the coordinates in the dual basis are obtained from those in the powerful basis by the explicit formula

$$ \forall i \in \mathbf{J}, \quad \mu_i^* = M \sum_{\substack{j \in \mathbf{J} \text{ s.t.} \\ [j_\ell - i_\ell]_{m'_\ell} = 0}} \left( \prod_{\ell=1}^{r} \left( \delta_{j_\ell, i_\ell} - \frac{1}{t_\ell} \right) \right) \mu_j. $$

where the sum runs over all multi-indices $j \in \mathbf{J}$ such that each component $j_\ell$ satisfies the congruence $[j_\ell - i_\ell]_{m'_\ell} = 0$, for $\ell = 1, \dots, r$.

**Proposition 3.20** Assume $M$ is of the form (1) with $\alpha_1 = \dots = \alpha_r$. Denote by $\mu$ the expansions of a polynomial of $K$ in both bases $(\Omega_{\mathbf{i}})_{\mathbf{i} \in \mathbf{J}}$ and $(\Omega_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}}$:

$$ \mu = \sum_{\mathbf{i} \in \mathbf{J}} \mu_{\mathbf{i}} \Omega_{\mathbf{i}} = \sum_{\mathbf{i} \in \mathbf{J}} \mu_{\mathbf{i}}^* \Omega_{\mathbf{i}}^*. $$
Then, for every $\mathbf{i} \in \mathbf{J}$, the coordinates $\mu_{\mathbf{i}}$ and $\mu_{\mathbf{i}}^*$ satisfy

$$ \mu_{\mathbf{i}} = \frac{1}{M} \sum_{L \subseteq \{1, \dots, r\}} \sum_{\mathbf{j} \in \mathbf{J}_{\mathbf{i}}} \mu_{\mathbf{j}}^*, $$

and

$$ \mu_{\mathbf{i}}^* = \sum_{L \subseteq \{1, \dots, r\}} (-1)^{r-\#L} \left( \prod_{k \in L} t_k \right) \sum_{\mathbf{j} \in \mathbf{J}_{\mathbf{i}}} \mu_{\mathbf{j}}. $$

**Example 3.21 (Case r = 2)** Let $t_1, t_2$ be two distinct prime integers and $M = t_1t_2$. We have:

$$ \mu_{i_1, i_2} = \frac{1}{t_1 t_2} \left( \mu_{i_1, i_2}^* + \sum_{j_1=0}^{t_1-2} \mu_{j_1, i_2}^* + \sum_{j_2=0}^{t_2-2} \mu_{i_1, j_2}^* + \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \mu_{j_1, j_2}^* \right), $$

$$ \mu_{i_1, i_2}^* = t_1 t_2 \mu_{i_1, i_2} - t_2 \sum_{j_1=0}^{t_1-2} \mu_{j_1, i_2} - t_1 \sum_{j_2=0}^{t_2-2} \mu_{i_1, j_2} + \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \mu_{j_1, j_2}. $$

**Algorithm 4** From the powerful basis to its dual for r = 2 and M = $t_1t_2$

**Require:** Input $\mu$ — array of coefficients $(\mu_i)_{i \in \mathbf{I}}$ in the powerful basis.

**Require:** Vector $m = (m_1, m_2)$.

1: **for** $i_1 \leftarrow 0$ **to** $m_1 - 2$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;S$_2[i_1]$ $\leftarrow \sum_{i_2=0}^{m_2-2} \mu[i_1, i_2]$

3: **end for**

4: **for** $i_2 \leftarrow 0$ **to** $m_2 - 2$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;S$_1[i_2]$ $\leftarrow \sum_{i_1=0}^{m_1-2} \mu[i_1, i_2]$

6: **end for**

7: &nbsp;&nbsp;&nbsp;&nbsp;S$_{12}$ $\leftarrow \frac{1}{2} (\sum_{i_2=0}^{m_2-2} S_1[i_2] + \sum_{i_1=0}^{m_1-2} S_2[i_1])$

8: &nbsp;&nbsp;&nbsp;&nbsp;S$_1$ $\leftarrow t_2 \cdot S_1$ and $S_2$ $\leftarrow t_1 \cdot S_2$

9: **for** $i_1 \leftarrow 0$ **to** $m_1 - 2$ **do**

10: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i_2 \leftarrow 0$ **to** $m_2 - 2$ **do**

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mu^*[i_1, i_2] \leftarrow M \cdot \mu[i_1, i_2] - S_1[i_2] - S_2[i_1] + S_{12} $$

12: **end for**

13: **end for**

14: **return** $\mu^*$
**Algorithm 5** From the dual of the powerful basis to the powerful basis for $r = 2$ and $M = t_1t_2$

**Require:** Input $\mu^*$ — array of coefficients $(\mu_i^*)_{i \in I}$ in the dual of the powerful basis.

**Require:** Vector $m = (m_1, m_2)$.

1: **for** $i_1 \leftarrow 0$ **to** $m_1 - 2$ **do**

2: $S_2^*[i_1] \leftarrow \sum_{i_2=0}^{m_2-2} \mu^*[i_1, i_2]$

3: **end for**

4: **for** $i_2 \leftarrow 0$ **to** $m_2 - 2$ **do**

5: $S_1^*[i_2] \leftarrow \sum_{i_1=0}^{m_1-2} \mu^*[i_1, i_2]$

6: **end for**

7: $S_{12}^* \leftarrow \frac{1}{2}(\sum_{i_2=0}^{m_2-2} S_1^*[i_2] + \sum_{i_1=0}^{m_1-2} S_2^*[i_1])$

8: **for** $i_1 \leftarrow 0$ **to** $m_1 - 2$ **do**

9: **for** $i_2 \leftarrow 0$ **to** $m_2 - 2$ **do**

10: $\mu[i_1, i_2] \leftarrow \frac{1}{M} \cdot (\mu^*[i_1, i_2] + S_1^*[i_2] + S_2^*[i_1] + S_{12}^*)$

11: **end for**

12: **end for**

13: **return** $\mu$

**Example 3.22 (Case r = 3)** Let $t_1, t_2, t_3$ be three distinct prime integers and $M = t_1t_2t_3$. We have:

$$ \mu_{i_1,i_2,i_3} = \frac{1}{t_1 t_2 t_3} \left( \mu_{i_1,i_2,i_3}^* + \sum_{j_1=0}^{t_1-2} \mu_{j_1,i_2,i_3}^* + \sum_{j_2=0}^{t_2-2} \mu_{i_1,j_2,i_3}^* + \sum_{j_3=0}^{t_3-2} \mu_{i_1,i_2,j_3}^* \right. \\ \left. + \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \mu_{j_1,j_2,i_3}^* + \sum_{j_1=0}^{t_1-2} \sum_{j_3=0}^{t_3-2} \mu_{j_1,i_2,j_3}^* + \sum_{j_2=0}^{t_2-2} \sum_{j_3=0}^{t_3-2} \mu_{i_1,j_2,j_3}^* + \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \sum_{j_3=0}^{t_3-2} \mu_{j_1,j_2,j_3}^* \right) $$

$$ \mu_{i_1,i_2,i_3}^* = t_1 t_2 t_3 \mu_{i_1,i_2,i_3} - t_2 t_3 \sum_{j_1=0}^{t_1-2} \mu_{j_1,i_2,i_3} - t_1 t_3 \sum_{j_2=0}^{t_2-2} \mu_{i_1,j_2,i_3} - t_1 t_2 \sum_{j_3=0}^{t_3-2} \mu_{i_1,i_2,j_3} \\ + t_3 \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \mu_{j_1,j_2,i_3} + t_2 \sum_{j_1=0}^{t_1-2} \sum_{j_3=0}^{t_3-2} \mu_{j_1,i_2,j_3} + t_1 \sum_{j_2=0}^{t_2-2} \sum_{j_3=0}^{t_3-2} \mu_{i_1,j_2,j_3} - \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} \sum_{j_3=0}^{t_3-2} \mu_{j_1,j_2,j_3} $$

We omit explicit algorithms for $r = 3$ since they are analogous to the cases already treated.

# 4 Plaintext messages in the TFHE framework

In the context of TFHE, all messages, also referred to as *plaintext messages* or simply *plaintexts*, can be classified into two types: either as elements of the torus $\mathbb{T}$, or as polynomials within a cyclotomic ring, with coefficients that belong either to $\mathbb{T}$ or $\mathbb{Z}$.

## 4.1 The set of torus plaintexts

Despite the fact that all elements of the torus can be encrypted, only a discretized subset can be safely decrypted. This observation leads to the following definition:
**Definition 4.1 (Discretized torus for messages)** Let $p \ge 3$ be an odd integer. The structure of the discrete torus $\mathbb{T}_p$ is inherited from $(\mathbb{Z}_p, +, \times)$, with privileged representative$^4$ $i$ mods $p$. The discrete torus $\mathbb{T}_p \subset \mathbb{T} = [-\frac{1}{2}, \frac{1}{2}) + \mathbb{Z}$ is defined by $\mathbb{T}_p = \frac{1}{p}\mathbb{Z}_p$:

$$ \mathbb{T}_p = \{ - (p-1)/(2p), \dots, (p-1)/(2p) \} + \mathbb{Z} $$

This discretized plaintext subset is central to schemes like TFHE: it constrains decryption correctness, and its choice directly impacts efficiency, security and the trade-off between functionality and noise growth. Note that $\mathbb{T}_p$, the $p$-adic torus, is a ring that is isomorphic to $(\mathbb{Z}_p, +, \times)$. Its structure can be outlined as follows:

1. Addition: The addition operation in $\mathbb{T}_p$ is inherited from the torus $\mathbb{T}$. Specifically, for any $(x, y) \in \mathbb{T}_p \times \mathbb{T}_p$:

$$ x + y \equiv x + y \quad \text{mod } 1. $$

2. Multiplication: The multiplication in $\mathbb{T}_p$ is inherited from the integers modulo $p$. For any $(x, y) \in \mathbb{T}_p \times \mathbb{T}_p$:

$$ x \times y = (px) \times y \quad \text{mod } 1. $$

## 4.2 The set of polynomial plaintexts

The extension to prime power cyclotomic rings manifests itself when considering polynomial messages and all subsequent attached procedures (packing, extraction, bootstrapping...).

**Definition 4.2 (Polynomial plaintext)** Let $M$ be a non-zero integer and let $\Phi_M$ be the $M^{th}$ cyclotomic polynomial. Polynomial plaintexts are polynomial representatives of equivalence classes, either in $\mathcal{R}$ or in

$$ \mathcal{T}_p = \{ P(X) \mod \mathbb{Z}[X] \mod \Phi_M, P \in \frac{1}{p}\mathbb{Z}[X] \} \subset \mathcal{T}. $$

The polynomials in $\mathcal{T}_p$ can not only be encrypted and manipulated but also decrypted exactly with a high probability under standard parameter conditions (see next Section).

# 5 LWE and RLWE encryptions cryptographic schemes

## 5.1 Encryption/decryption schemes in $\mathbb{T}$

Learning With Errors (LWE) is a cryptographic problem widely used in post-quantum cryptography due to its hardness against quantum attacks [35]. The LWE problem consists in solving systems of noisy linear equations. More specifically, given a secret vector $\mathbf{s} \in \mathbb{S}^n$, where $\mathbb{S}$ is a finite subset of $\mathbb{Z}$, if we are given a set of linear equations of the form

$$ \mathbf{c} = \mathbf{A} \cdot \mathbf{s} + \mathbf{e}, $$

where $\mathbf{A}$ is randomly chosen matrix over a finite field (e.g., modulo $\mathbb{Z}_q$) and $\mathbf{e}$ is a random noise vector with small entries, recovering $\mathbf{s}$ from the equations is computationally hard. Of course, if $\mathbf{A} \in \mathcal{M}_n(\mathbb{Z}_q)$ and $\mathbf{e} \in (\mathbb{Z}_q)^n$, the actual hardness depends on how large $q$ and $n$ are. When it is hard enough, the LWE-problem is said to be secure.

Now, assume the LWE-problem on $\mathbb{Z}_q$ is secure and assimilate $\mathbb{T} \equiv \frac{1}{q}\mathbb{Z}_q$ for the purpose of the following definition [15, 16].

<footnote>$^4$The symmetric modulo operation returns the remainder of a division such that the result is centered around zero. For a number $i$ and odd modulus $p$, it maps $i$ to the interval $\{-(p-1)/2, \dots, (p-1)/2\}$, ensuring the result is balanced symmetrically around zero.</footnote>
**Definition 5.1 (EncryptLWE<sub>s</sub>(μ))** The LWE-encryption of a message μ ∈ T with the secret key s ∈ S<sup>n</sup> is defined as

$$c = \text{LWE}_{\text{s}}(\mu) = (\mathbf{a}, b) \in \mathbb{T}^{n+1}$$

with

$$\mathbf{a} = (a_1, \dots, a_n) \stackrel{\$}{\leftarrow} \mathbb{T}^n, \quad e \leftarrow \mathcal{N}(0, \sigma^2)$$

and

$$b = \mathbf{s} \cdot \mathbf{a} + \mu + e.$$

**Algorithm 6 LWE Encryption of Message μ**

**Input:** Message μ ∈ T, secret key s ∈ S<sup>n</sup>.

1: **Generate random vector:** a = (a<sub>1</sub>, ..., a<sub>n</sub>) $\stackrel{\$}{\leftarrow}$ T<sup>n</sup>

2: **Sample error term:** e $\leftarrow$ N(0, σ<sup>2</sup>)

3: b $\leftarrow$ s · a + μ + e

4: **Return** c = (a, b).

**Definition 5.2 (DecryptLWE<sub>s</sub>(c, p))** The LWE-decryption of a ciphertext (a, b) ∈ T<sup>n+1</sup> with secret key s ∈ S<sup>n</sup> is defined as

$$\pi_p(b - \mathbf{s} \cdot \mathbf{a}) \in \mathbb{T}_p$$

where π<sub>p</sub> is a projection on the discrete torus T<sub>p</sub>.

**Algorithm 7 LWE Decryption**

**Input:** Ciphertext (a, b) ∈ T<sup>n+1</sup>, secret key s ∈ S<sup>n</sup>, modulus p.

1: $\varphi \leftarrow b - \mathbf{s} \cdot \mathbf{a}$

2: **Return** $\frac{|p\varphi|}{p} \in \mathbb{T}_p$.

It is clear that if c = (a, b) is the LWE-encryption of a message μ in T<sub>p</sub>, then

$$\pi_p(b - \mathbf{a} \cdot \mathbf{s}) = \mu$$

if |e| < 1/2p. Here, the projection π<sub>p</sub> is defined as π<sub>p</sub>(μ) = |pμ|/p for all μ ∈ T.

## 5.2 Encryption/decryption schemes in T and T<sup>√</sup>

The security of Ring Learning With Errors (Ring-LWE) is rooted in the same principles as the standard LWE problem [36]. The dual modules T and T<sup>√</sup>, while abstractly well-defined, admit concrete representations in the powerful basis and its dual, which are convenient for computations. The Ring-LWE problem (adapted to the torus in this context) as articulated by Regev in [36] is defined as follows:

**Ring-LWE problem.** For M > 1, consider the cyclotomic ring R and the cyclotomic Z[X]-module T<sup>√</sup>. Given samples of the form

$$(a^*, b^*) \in T^{\sqrt{\nu}} \times T^{\sqrt{\nu}},$$

with b* = s · a* + e* and where
* $a^*$ is chosen uniformly at random from $\mathcal{T}^\vee$;

* $s$ is a secret element in $\mathcal{R}$ with coefficients in $\mathbb{S}$;

* $e^*$ is a small error term sampled from a normal distribution over $\mathcal{T}^\vee$;

it is a computationally hard problem to distinguish such samples from uniformly random pairs in $\mathcal{T}^\vee \times \mathcal{T}^\vee$.

The security of Ring-LWE is built upon its reduction to hard problems on ideal lattices [36], such as the *Ideal Shortest Vector Problem (Ideal-SVP)* and the *Ideal Closest Vector Problem (Ideal-CVP)*. Once again, the effective level of security depends in particular on how large parameters $M$ and $q$ in $\mathbb{T} \equiv \frac{1}{q}\mathbb{Z}_q$ are. Now, assume the RLWE-problem is secure. We may encrypt and decrypt polynomial messages as follows:

**Definition 5.3 (EncryptRLWE\*$_s(\mu^*)$** The RLWE\*-encryption of a message $\mu^*(X) \in \mathcal{T}^\vee$ with the secret key

$$s(X) = \sum_{\mathbf{i} \in \mathbf{J}} s_{\mathbf{i}} \Omega_{\mathbf{i}}(X) \in \mathcal{R}, \quad (s_{\mathbf{i}})_{\mathbf{i} \in \mathbf{J}} \in \mathbb{S}^N,$$

is defined as

$$c^*(X) = \mathrm{RLWE}_s^*(\mu^*(X)) = (a^*(X), b^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$$

with

$$(a_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}} \stackrel{\$}{\leftarrow} \mathbb{T}^N, \quad a^*(X) = \sum_{\mathbf{i} \in \mathbf{J}} a_{\mathbf{i}}^* \Omega_{\mathbf{i}}^*(X),$$

$$(e_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}} \stackrel{\mathcal{N}(0, \sigma^2)}{\leftarrow} \mathbb{T}^N, \quad e^*(X) = \sum_{\mathbf{i} \in \mathbf{J}} e_{\mathbf{i}}^* \Omega_{\mathbf{i}}^*(X),$$

and

$$b^* = s \cdot a^* + \mu^* + e^* \mod \mathcal{R}^\vee.$$

The equality holds modulo $\Omega_0^*\mathbb{Z}[X]$ and $\Phi_M$, and $b^* \in \mathcal{T}^\vee$. For later use, we denote $\mathrm{Err}(c^*) = e^*$.

**Remark 5.4** Drawing the noise $e^*$ in $\mathcal{T}^\vee$ follows the security analysis of [36]. We question whether it's preferable to draw the coefficients of $e^*$ in the basis $(\Omega_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}}$ or another. Consider the dual basis $(B_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}}$ of a basis $(B_{\mathbf{i}})_{\mathbf{i} \in \mathbf{J}}$ to encrypt polynomial messages $\mu^*(X) = b^*(X) - s(X)a^*(X) - e^*(X)$, where $a^*$, $b^*$, and $e^*$ are expressed in $(B_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}}$. Specifically, $e^* = \sum_{\mathbf{i} \in \mathbf{J}} e_{\mathbf{i}}^* B_{\mathbf{i}}^*$. The canonical embedding $\mathcal{E}$ is:

$$\mathcal{E}: \quad e^* \mapsto (e^*(\xi^j))_{j \in \mathbb{Z}_M^\times}$$

where $\xi$ is a primitive $M$-th root of unity. Its inverse is represented by the $N \times N$ matrix $\mathcal{B} = (\bar{B}_{\mathbf{i}}(\xi^j))_{\mathbf{i} \in \mathbf{J}, j \in \mathbb{Z}_M^\times}$. As a matter of fact, for all $\mathbf{i} \in \mathbf{J}$:

$$\begin{aligned} e_{\mathbf{i}}^* &= \langle B_{\mathbf{i}}, e^* \rangle = \mathrm{Tr}(\bar{B}_{\mathbf{i}} e^*) = \sum_{j \in \mathbb{Z}_M^\times} \bar{B}_{\mathbf{i}}(\xi^j) e^*(\xi^j) \\ &= \sum_{k \in K} \left( \Re(\bar{B}_{\mathbf{i}}(\xi^k))\Re(e^*(\xi^k)) - \Im(\bar{B}_{\mathbf{i}}(\xi^k))\Im(e^*(\xi^k)) \right) \end{aligned}$$

where $K \cup \bar{K}$ partitions $\mathbb{Z}_M^\times$ such that $k \in K$ iff $M - k \in \bar{K}$. If the real and imaginary parts of $e^*(\xi^k)$, $k \in K$, have identical normal distributions with standard deviation $\sigma$, then

$$\sigma^2(e_{\mathbf{i}}^*) = \sigma^2 \sum_{k \in K} |B_{\mathbf{i}}(\xi^k)|^2$$
This variance is independent of i if $B_i = \Omega_i$ for all $i \in \mathbf{J}$, resulting in $\sigma(e_i^*) = \sigma\sqrt{N/2}$ for all $i \in \mathbf{J}$. Finally, we observe that for $M = t^\alpha$ with $t \neq 2$ or when $M$ is composite, the canonical embedding does not guarantee the independence of the random variable $e_i^*$. Strictly speaking, it is advisable in this setting to draw the errors in the ideal lattice and subsequently compute the corresponding $e_i^*$ via the canonical embedding. When the dual basis $\Omega_i^*$ is employed, isotropy is then ensured, with a growth factor of the variance approaching $N/2$.

**Algorithm 8 RLWE* Encryption of a polynomial message $\mu^*(X) \in \mathcal{T}^\vee$**

**Input:** Message $\mu^*(X) \in \mathcal{T}^\vee$ and secret key $s(X) \in \mathcal{R}$.

1: **Generate:** $(a_i^*)_{i \in \mathbf{J}} \stackrel{\$}{\leftarrow} \mathbb{T}^N$ and $(e_i^*)_{i \in \mathbf{J}} \stackrel{\mathcal{N}(0, \sigma^2)}{\leftarrow} \mathbb{T}^N$

2: $a^*(X) \leftarrow \sum_{i \in \mathbf{J}} a_i^* \Omega_i^*(X)$ and $e^*(X) \leftarrow \sum_{i \in \mathbf{J}} e_i^* \Omega_i^*(X)$

3: $b^*(X) \leftarrow s(X) \cdot a^*(X) + \mu^*(X) + e^*(X) \mod \mathcal{R}^\vee$.

4: **Return** $c^*(X) = (a^*(X), b^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$.

**Remark 5.5** It is also possible to choose $s \in \mathcal{R}^\vee$ and sample $a \in \mathcal{T}$, so that $b \in \mathcal{T}^\vee$ as in [37, 36].

**Definition 5.6 (EncryptRLWE$_s(\mu)$)** The RLWE-encryption of a message $\mu(X) \in \mathcal{T}$ with the secret key

$$s(X) = \sum_{i \in \mathbf{J}} s_i \Omega_i(X) \in \mathcal{R}, \quad (s_i)_{i \in \mathbf{J}} \in \mathbb{S}^N,$$

is defined as

$$c(X) = \mathrm{RLWE}_s(\mu(X)) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$$

with $a = (\Omega_0^*)^{-1}a^* \mod \Phi_M$, $b = (\Omega_0^*)^{-1}b^* \mod \Phi_M$ and where

$$(a^*(X), b^*(X)) = \mathrm{RLWE}_s^*(\Omega_0^*(X)\mu(X)).$$

Note that

$$b = s \cdot a + \mu + e \mod \mathcal{R} \quad \text{with} \quad e = (\Omega_0^*)^{-1}e^*.$$

The equality holds modulo $\mathbb{Z}[X]$ and $\Phi_M$, and $b \in \mathcal{T}$. For later use, we define $\mathrm{Err}(c) = e$.

**Algorithm 9 RLWE Encryption of Message $\mu$**

**Input:** Message $\mu(X) \in \mathcal{T}$, secret key $s(X)$.

1: **Compute the RLWE*-encryption:** $(a^*(X), b^*(X)) = \mathrm{RLWE}_s^*(\Omega_0^*(X)\mu(X))$.

2: $a \leftarrow ((\Omega_0^*)^{-1}a^* \mod \Phi_M) \mod \mathcal{R}$

3: $b \leftarrow ((\Omega_0^*)^{-1}b^* \mod \Phi_M) \mod \mathcal{R}$

4: **Return** $c(X) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$.

**Definition 5.7 (DecryptRLWE$_s^*(c^*(X), p)$)** The RLWE*-decryption of the ciphertext $c^*(X) = (a^*(X), b^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$ with the secret key $s \in \mathcal{R}$ is defined as

$$\pi_p(b^*(X) - s(X)a^*(X)) \in \mathcal{T}_p$$

where $\pi_p$ is a projection coefficient by coefficient in the basis $(\Omega_i^*(X))_{i \in \mathbf{J}}$ on the discrete torus $\mathbb{T}_p$.
**Algorithm 10 RLWE* Decryption**

**Input:** Ciphertext $c^*(X) = (a^*(X), b^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$, secret key $s \in \mathcal{R}$, modulus $p$.

1: $\varphi^*(X) \leftarrow b^*(X) - s(X)a^*(X) \bmod \mathcal{R}^\vee$.

2: **Return**

$$ \tilde{\varphi}^*(X) = \sum_{i \in \mathcal{J}} \frac{|p\varphi_i^*|}{p} \Omega_i^*(X) \in \mathcal{T}_p^\vee. $$

**Definition 5.8 (DecryptRLWE<sub>s</sub> (c(X), p))** The RLWE-decryption of the ciphertext $c(X) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$ with the secret key $s \in \mathcal{R}$ is defined as

$$ (\Omega_0^*)^{-1}(X) \cdot \pi_p((\Omega_0^*(X)(b(X) - s(X)a(X))) \in \mathcal{T}_p $$

where $\pi_p$ is a projection coefficient by coefficient in the basis $(\Omega_i^*)_{i \in \mathcal{J}}$ on the discrete torus $\mathbb{T}_p$.

**Algorithm 11 RLWE Decryption**

**Input:** Ciphertext $c(X) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$, secret key $s \in \mathcal{R}$, modulus $p$.

1: Compute the RLWE*-decryption $\tilde{\varphi}^*(X)$ of $(a^*(X), b^*(X)) = (\Omega_0^*(X)a(X), \Omega_0^*(X)b(X))$.

2: **Return**

$$ \tilde{\varphi}(X) = (\Omega_0^*)^{-1}(X) \tilde{\varphi}^*(X) \in \mathcal{T}_p. $$

It is clear that if $c^*(X) = (a^*(X), b^*(X))$ is the RLWE*-encryption of a message $\mu^*(X)$ in $\mathcal{T}_p^\vee$, then

$$ \pi_p(b^*(X) - s(X)a^*(X)) = \mu^*(X) $$

if $\|e^*\|_\infty < \frac{1}{2p}$. The norm $\|\cdot\|_\infty$ of a polynomial denotes here, as is customary, the maximum of the absolute values of its coefficients in the basis $(\Omega_i^*)_{i \in \mathcal{J}}$.

## 5.3 Encryption/decryption schemes in $\mathcal{R}$ and $\mathcal{R}^\vee$

In this subsection, we describe the encryption of elements in the dual sets $\mathcal{R}$ and $\mathcal{R}^\vee$:

$$ \mathcal{R} = \{ P \bmod \Phi_M, P \in \mathbb{Z}_{N-1}[X] \} \subset \mathcal{K} \text{ and } \mathcal{R}^\vee = \{ \Omega_0^* P \bmod \Phi_M, P \in \mathbb{Z}_{N-1}[X] \} \subset \mathcal{K}. $$

**Definition 5.9 (EncryptGRLWE<sub>s</sub>(μ<sup>*</sup>))** Given two integers $D \ge 2$ and $\ell \ge 1$, the GRLWE*-encryption of a message

$$ \mu^*(X) = \sum_{i \in \mathcal{J}} \mu_i^* \Omega_i^*(X) \in \mathcal{R}^\vee $$

with the secret key

$$ s(X) = \sum_{i \in \mathcal{J}} s_i \Omega_i(X) \in \mathcal{R}, \quad (s_i)_{i \in \mathcal{J}} \in \mathbb{S}^N, $$

is defined as

$$ C^*(X) = \text{GRLWE}_s^*(\mu^*(X)) = \begin{pmatrix} \text{RLWE}_s^*\left(\frac{\mu^*(X)}{D}\right) \\ \vdots \\ \text{RLWE}_s^*\left(\frac{\mu^*(X)}{D^\ell}\right) \end{pmatrix}. $$

For later use, we define $\text{Err}(C^*) = (\text{Err}(C_1^*), \dots, \text{Err}(C_\ell^*))^T$.
**Algorithm 12** GRLWE* Encryption of Message $\mu^* \in \mathcal{R}^\nabla$

**Input:** Message $\mu^*(X) \in \mathcal{R}^\nabla$, secret key $s(X)$, integers $D \ge 2$ and $\ell \ge 1$.

1: **Initialize an empty vector:** $C^*(X) \leftarrow \emptyset$ of dimension $\ell$.

2: **for** each $k$ from 1 to $\ell$ **do**

3: $c_k^*(X) \leftarrow \text{RLWE}_s^*\left(\frac{\mu^*(X)}{D^k}\right)$.

4: **Append** $c_k^*(X)$ to $C^*(X)$.

5: **end for**

6: **Return** $C^*(X) = (c_1^*(X), \dots, c_\ell^*(X))^T$.

**Definition 5.10 (EncryptGRLWE$_s(\mu)$)** Given two integers $D \ge 2$ and $\ell \ge 1$, the GRLWE-encryption of a message

$$ \mu(X) = \sum_{i \in \mathcal{J}} \mu_i \Omega_i(X) \in \mathcal{R} $$

with the secret key

$$ s(X) = \sum_{i \in \mathcal{J}} s_i \Omega_i(X) \in \mathcal{R}, \quad (s_i)_{i \in \mathcal{J}} \in \mathbb{S}^N, $$

is defined as

$$ C(X) = \text{GRLWE}_s(\mu(X)) = \begin{pmatrix} \text{RLWE}_s\left(\frac{\mu(X)}{D}\right) \\ \vdots \\ \text{RLWE}_s\left(\frac{\mu(X)}{D^\ell}\right) \end{pmatrix}. $$

For later use, we define $\text{Err}(C) = (\text{Err}(C_1), \dots, \text{Err}(C_\ell))^T$.

**Algorithm 13** GRLWE Encryption of Message $\mu \in \mathcal{R}$

**Input:** Message $\mu(X) \in \mathcal{R}$, secret key $s(X)$, integers $D \ge 2$ and $\ell \ge 1$.

1: **Initialize an empty vector:** $C(X) \leftarrow \emptyset$ of dimension $\ell$.

2: **for** each $k$ from 1 to $\ell$ **do**

3: $c_k(X) \leftarrow \text{RLWE}_s\left(\frac{\mu(X)}{D^k}\right)$.

4: **Append** $c_k(X)$ to $C(X)$.

5: **end for**

6: **Return** $C(X) = (c_1(X), \dots, c_\ell(X))^T$.

**Definition 5.11 (EncryptRGSW$_s^*(\mu^*)$)** Given two integers $D \ge 2$ and $\ell \ge 1$, the RGSW*-encryption of a message $\mu^*(X) \in \mathcal{T}^\nabla$ with the secret key

$$ s(X) = \sum_{i \in \mathcal{J}} s_i \Omega_i(X) \in \mathcal{R}, \quad (s_i)_{i \in \mathcal{J}} \in \mathbb{S}^N, $$

is defined as

$$ C^*(X) = \text{RGSW}_s^*(\mu^*(X)) = \begin{pmatrix} \text{GRLWE}_s^*(-s(X)\mu^*(X)) \\ \text{GRLWE}_s^*(\mu^*(X)) \end{pmatrix}. $$

For later use, we define $\text{Err}(C^*) = (\text{Err}(C_1^*), \dots, \text{Err}(C_{2\ell}^*))^T$.
**Algorithm 14 RGSW* Encryption of Message $\mu^*$**

**Input:** Message $\mu^*(X) \in \mathcal{T}^\vee$, secret key $s(X)$, integers $D \ge 2$ and $\ell \ge 1$.

1: $\hat{C}^*(X) \leftarrow \text{GRLWE}_s^*(-s(X)\mu(X))$ and $\check{C}^*(X) \leftarrow \text{GRLWE}_s^*(\mu(X))$

2: **Return**

$$C^*(X) = \begin{pmatrix} \hat{C}^*(X) \\ \check{C}^*(X) \end{pmatrix}.$$

**Definition 5.12 (EncryptRGSW$_s(\mu)$)** Given two integers $D \ge 2$ and $\ell \ge 1$, the RGSW-encryption of a message $\mu(X) \in \mathcal{T}$ with the secret key

$$s(X) = \sum_{i \in \mathcal{J}} s_i \Omega_i(X) \in \mathcal{R}, \quad (s_i)_{i \in \mathcal{J}} \in \mathbb{S}^N,$$

is defined as

$$C(X) = \text{RGSW}_s(\mu(X)) = \begin{pmatrix} \text{GRLWE}_s(-s(X)\mu(X)) \\ \text{GRLWE}_s(\mu(X)) \end{pmatrix}.$$

For later use, we define $\text{Err}(C) = (\text{Err}(C_1), \dots, \text{Err}(C_{2\ell}))^T$.

**Algorithm 15 RGSW Encryption of Message $\mu$**

**Input:** Message $\mu(X) \in \mathcal{T}$, secret key $s(X)$, integers $D \ge 2$ and $\ell \ge 1$.

1: $\hat{C}(X) \leftarrow \text{GRLWE}_s(-s(X)\mu(X))$ and $\check{C}(X) \leftarrow \text{GRLWE}_s(\mu(X))$

2: **Return**

$$C(X) = \begin{pmatrix} \hat{C}(X) \\ \check{C}(X) \end{pmatrix}.$$

## 5.4 Homomorphic addition

We denote unambiguously by $\oplus$ the addition of (R)LWE-ciphertexts and RGSW-ciphertexts, as well as (R)LWE*-ciphertexts and RGSW*-ciphertexts. We recall that, if $c_1$ and $c_2$ are two (R)LWE-ciphertexts, i.e.

$$c_1 = (\text{R})\text{LWE}_s(\mu_1) \text{ and } c_2 = (\text{R})\text{LWE}_s(\mu_2),$$

then

$$c_1 \oplus c_2 = (\text{R})\text{LWE}_s(\mu_1 + \mu_2)$$

where the equality means that

$$\text{Decrypt}(\text{R})\text{LWE}_s(c_1 \oplus c_2, p) = \mu_1 + \mu_2.$$

Similarly, if $C_1$ and $C_2$ are two RGSW-ciphertexts, i.e.

$$C_1 = \text{RGSW}_s(m_1) \text{ and } C_2 = \text{RGSW}_s(m_2)$$

then

$$C_1 \oplus C_2 = \text{RGSW}_s(m_1 + m_2)$$

where the equality means that both sides are (possibly different) encryptions of $m_1 + m_2$. All previous equalities hold with RLWE or RGSW replaced by RLWE* or RGSW*. In all cases, the effective addition is component-wise on the ciphertext arrays.
## 5.5 Homomorphic modular product

We recall that the $\mathbb{Z}_N[X]$-module $\mathbb{T}_N[X]$ is by definition endowed with a *modular product* $\cdot$ whose counterpart on RGSW-ciphertexts is the co-called *external product* $\Box$. Besides, if

$$C^* = \mathrm{RGSW}_s^*(m^*) \in \mathcal{R}^{\vee} \text{ and } c = \mathrm{RLWE}_s(\mu) \in \mathcal{T},$$

then

$$C^* \Box c = \mathrm{RLWE}_s^*(m^* \cdot \mu) \in \mathcal{T}^{\vee}$$

in the sense that

$$C^* \Box c \text{ is an RLWE}_s\text{-encryption of } m^* \cdot \mu. \qquad (9)$$

The effective external product of $C^*$ and $c$ is obtained through the vector-matrix multiplication (with polynomial coefficients)

$$C^* \Box c = \mathrm{dec}_{D,\ell}(c) C^*$$

where $\mathrm{dec}_{D,\ell}(c(X)) = (\mathrm{dec}_{D,\ell}(a(X)), \mathrm{dec}_{D,\ell}(b(X)))$ and

$$\mathrm{dec}_{D,\ell}(a(X)) = \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i)_1 \Omega_i(X), \dots, \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i)_\ell \Omega_i(X) \right),$$

$$\mathrm{dec}_{D,\ell}(b(X)) = \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(b_i)_1 \Omega_i(X), \dots, \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(b_i)_\ell \Omega_i(X) \right),$$

for some integers $D \ge 2$ and $\ell \ge 1$. To complete the definition of $\mathrm{dec}_{D,\ell}(c)$ we decompose any $x \in \mathbb{T} \equiv [-\frac{1}{2}, \frac{1}{2})$ as:

$$x = \sum_{g=1}^{\ell} \mathrm{dec}_{D,\ell}(x)_g D^{-g} + \delta(x), \quad \mathrm{dec}_{D,\ell}(x)_t \in \{-D/2, \dots, D/2\}, \quad |\delta(x)| \le \frac{D^{-\ell}}{2}.$$

The other external products $C \Box c$ and $C \Box c^*$ are defined similarly with the only difference that $\mathrm{dec}_{D,\ell}(c^*(X)) = (\mathrm{dec}_{D,\ell}(a^*(X)), \mathrm{dec}_{D,\ell}(b^*(X)))$ where

$$\mathrm{dec}_{D,\ell}(a^*(X)) = \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i^*)_1 \Omega_i^*(X), \dots, \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i^)_\ell \Omega_i^*(X) \right),$$

$$\mathrm{dec}_{D,\ell}(b^*(X)) = \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(b_i^*)_1 \Omega_i^*(X), \dots, \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(b_i^)_\ell \Omega_i^*(X) \right).$$

Note that, for instance

$$\mathrm{dec}_{D,\ell}(a(X)) = \sum_{g=1}^{\ell} D^{-g} \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i)_g \Omega_i(X) \right) + \delta(a(X)), \quad \delta(a(X)) = \sum_{i \in \mathbf{J}} \delta(a_i) \Omega_i(X)$$

and

$$\mathrm{dec}_{D,\ell}(a^*(X)) = \sum_{g=1}^{\ell} D^{-g} \left( \sum_{i \in \mathbf{J}} \mathrm{dec}_{D,\ell}(a_i^*)_g \Omega_i^*(X) \right) + \delta(a^*(X)), \quad \delta(a^*(X)) = \sum_{i \in \mathbf{J}} \delta(a_i^*) \Omega_i^*(X).$$

We then have the following standard formulas:
**Proposition 5.13** Let C and c = (a, b) be respectively RGSWs and RLWEs encryptions of m and µ. Then the following equality holds for all integers D ≥ 2 and ℓ ≥ 1:

$$ \mathrm{Err}(C \boxdot c) = \mathrm{dec}_{D,\ell}(c) \cdot \mathrm{Err}(C) + m(\delta(b) - s \delta(a)) + m \mathrm{Err}(c). $$

Mutatis mutandis, we have

$$ \mathrm{Err}(C^* \boxdot c) = \mathrm{dec}_{D,\ell}(c) \cdot \mathrm{Err}(C^*) + m^*(\delta(b) - s \delta(a)) + m^* \mathrm{Err}(c) $$

$$ \mathrm{Err}(C \boxdot c^*) = \mathrm{dec}_{D,\ell}(c^*) \cdot \mathrm{Err}(C) + m(\delta(b^*) - s \delta(a^*)) + m \mathrm{Err}(c^*) $$

## 5.6 Key switching

Key switching is a technique that changes a RLWE-ciphertext (or RLWE*-ciphertext) encrypted under one key to another RLWE-ciphertext (or RLWE*-ciphertext) of the same message encrypted under another key, without decrypting the message. This process uses a key switching key: the key switching key, written as

$$ \mathrm{KS}_{s \to \hat{s}} = \begin{pmatrix} \mathrm{RLWE}_{\hat{s}}\left(\frac{s}{D}\right) \\ \vdots \\ \mathrm{RLWE}_{\hat{s}}\left(\frac{s}{D^{\ell}}\right) \end{pmatrix} = \begin{pmatrix} (a^{(1)}, \frac{s}{D} + \hat{s} \cdot a^{(1)} + e^{(1)}) \\ \vdots \\ (a^{(\ell)}, \frac{s}{D^{\ell}} + \hat{s} \cdot a^{(\ell)} + e^{(\ell)}) \end{pmatrix}, $$

is created by encrypting the first key s using the second key $\hat{s}$ (we denote $\sigma^2(\mathrm{Err}(\mathrm{KS}_{s \to \hat{s}})) = \max_{1 \le k \le \ell} \sigma^2(e^{(k)})$). This is a standard method described in many research papers (see, for example, [15, 16, 21]), and for our purposes, we will just assume we have a function called

$$ \mathrm{KeySwitch}_{s \to \hat{s}} $$

that performs this operation$^5$. In order to estimate the error after a keyswitch $\hat{c} = \mathrm{RLWE}_{\hat{s}}(\mu) = \mathrm{KeySwitch}_{s \to \hat{s}}((a, b))$ we just write $\mu = b - s \cdot a - e$ and decompose $a$ using $\mathrm{KS}_{s \to \hat{s}}$

$$ \left(b - \sum_{k=1}^{\ell} \mathrm{dec}_{D,\ell}(a)_k b^{(k)}\right) + \hat{s} \cdot \left(-\sum_{k=1}^{\ell} \mathrm{dec}_{D,\ell}(a)_k a^{(k)}\right) + \left(-s \cdot \delta(a) - e + \sum_{k=1}^{\ell} \mathrm{dec}_{D,\ell}(a)_k e^{(k)}\right) $$

If we denote c = (a, b) the RLWEs-input, then we have the following estimate (using Lemma 9.2):

$$ \sigma^2(\mathrm{Err}(\hat{c})) \le \Gamma_M \ell N \frac{D^2 + \xi_D}{12} \sigma^2(\mathrm{Err}(\mathrm{KS}_{s \to \hat{s}})) + \Gamma_M \frac{D^{-2\ell}}{12} \|s\|_2^2 + \sigma^2(\mathrm{Err}(c)) \quad (10) $$

where $\Gamma_M = \prod_{i=1}^r \frac{2t_i-3}{t_i-1} < 2^r$, $\xi_D = 2$ if D is even and $\xi_D = -1$ if D is odd and where $\| \cdot \|_2$ is the usual L2-norm in the basis $(\Omega_i)_{i \in \mathbf{J}}$.

## 6 Extraction of a LWE from a RLWE

This section describes a procedure aimed at extracting an LWE-encryption LWEs($\mu_i$) of the $i^{th}$ coefficient $\mu_i \in \mathbb{T}$ from a RLWE-ciphertext RLWEs($\mu$). The message polynomial is written in the powerful basis as

$$ \mu(X) = \sum_{i \in \mathbf{J}} \mu_i \Omega_i(X), $$

though any basis of $\mathcal{R}$ could be used. The connection between s and s will be elucidated in the subsequent discussion.

<footnote>$^5$We don't need to go into the details of how it works internally, as the process is the same regardless of the specific cyclotomic polynomial used in the encryption scheme.</footnote>
## 6.1 An extraction procedure using dual bases

The extraction operation can be articulated using the scalar product: from the polynomial message $\mu(X)$, the coefficient $\mu_i$ can be obtained as $\mu_i = \langle \Omega_i^*, \mu \rangle$. Now, considering that

$$ \mu(X) = b(X) - s(X) \cdot a(X) - e(X) \mod \mathcal{R}, $$

that is to say that $\mu$ is given in RLWE-encrypted form $c = (a, b) \in \mathcal{T} \times \mathcal{T}$, we have the following relations:

$$ \mu_i = \langle \Omega_i^*, \mu \rangle = \langle \Omega_i^*, b \rangle - \langle \Omega_i^*, s \cdot a \rangle - \langle \Omega_i^*, e \rangle = \langle \Omega_i^*, b \rangle - \sum_{j \in \mathcal{J}} s_j \langle \Omega_i^*, B_j \cdot a \rangle - \langle \Omega_i^*, e \rangle $$

where we have assumed that $s(X)$ is written in a basis $(B_j)_{j \in \mathcal{J}}$ as

$$ s(X) = \sum_{j \in \mathcal{J}} s_j B_j(X) \quad \text{and} \quad s_j = s_j \quad \text{for} \quad j \in \mathcal{J}. \qquad (11) $$

The values $b^{(i)}$, $a^{(i)}$ and $e^{(i)}$ are thus defined as

$$ b^{(i)} = \langle \Omega_i^*, b \rangle, \quad a_j^{(i)} = \langle \Omega_i^*, B_j \cdot a \rangle \quad \text{for} \quad j \in \mathcal{J}, $$

and $e^{(i)} = \langle \Omega_i^*, e \rangle$. Thus, we obtain an LWE-encryption of $\mu_i$ as $\text{LWE}_s(\mu_i) = (a^{(i)}, b^{(i)})$ satisfying $\mu_i = b^{(i)} - s \cdot a^{(i)} - e^{(i)}$, where the scalar product $s \cdot a^{(i)}$ is meant to be $\sum_{i \in \mathcal{J}} s_i a_j^{(i)}$.

**Proposition 6.1** Let $(B_i)_{i \in \mathcal{J}}$ be a basis of $\mathcal{R}$. Suppose $(a, b)$ is a RLWE-encryption of

$$ \mu = \sum_{j \in \mathcal{J}} \mu_j \Omega_j \in \mathcal{T}, $$

with secret key

$$ s = \sum_{j \in \mathcal{J}} s_j B_j \in \mathcal{R}. $$

A LWE-encryption of $\mu_i$ for $i \in \mathcal{J}$ is given by

$$ c^{(i)} = \text{LWE}_s(\mu_i) = \left( (a_j^{(i)})_{j \in \mathcal{J}}, b^{(i)} \right) \in \mathbb{T}^{N+1}, $$

where

$$ b^{(i)} = b_i, \quad a_j^{(i)} = \langle \Omega_i^*, B_j \cdot a \rangle \quad \text{and} \quad s = (s_j)_{j \in \mathcal{J}} \quad \text{for} \quad j \in \mathcal{J}. $$

The associated error is $\text{Err}(c^{(i)}) = \langle \Omega_i^*, e \rangle$ with variance $\sigma^2(e_i)$.

**Remark 6.2** The dual version of this procedure can be derived in a similar fashion: given an RLWE*-encryption $(a^*, b^*)$ of the polynomial message $\mu^* = \sum_{j \in \mathcal{J}} \mu_j^* \Omega_j^*$, the coefficient $\mu_i^*$ can be obtained as

$$ \mu_i^* = \langle \Omega_i, \mu^* \rangle = \langle \Omega_i, b^* \rangle - \sum_{j \in \mathcal{J}} s_j \langle \Omega_i, B_j \cdot a^* \rangle - \langle \Omega_i, e^* \rangle $$

where we have assumed (11). Thus, we obtain an LWE-encryption of $\mu_i$ as

$$ \text{LWE}_s(\mu_i) = (a^{(i)}, b^{(i)}). $$

with $b^{(i)} = \langle \Omega_i, b^* \rangle$, $a_j^{(i)} = \langle \Omega_i, B_j \cdot a^* \rangle$ for all $i \in \mathcal{J}$ and $e^{(i)} = \langle \Omega_i, e^* \rangle$.
If a and b are expanded in the powerful basis as $a = \sum_{\mathbf{k} \in \mathbf{J}} a_{\mathbf{k}} \Omega_{\mathbf{k}}$ and $b = \sum_{\mathbf{k} \in \mathbf{J}} b_{\mathbf{k}} \Omega_{\mathbf{k}}$, then

$$a_{\mathbf{j}}^{(i)} = \langle \Omega_{\mathbf{i}}^{*}, \Omega_{\mathbf{k}} B_{\mathbf{j}} \rangle.$$

Furthermore, if we choose $B_{\mathbf{i}} = \Omega_{\mathbf{i}}$ for all $\mathbf{i} \in \mathbf{J}$, then

$$a_{\mathbf{j}}^{(i)} = \sum_{\mathbf{k} \in \mathbf{J}} a_{\mathbf{k}} \langle \Omega_{\mathbf{i}}^{*}, \Omega_{[\mathbf{j}+\mathbf{k}]_{M}} \rangle = \sum_{\substack{\mathbf{k} \in \mathbf{J}, \mathbf{u} \in \{0,1\}^{r} \text{ s.t.} \\ [\mathbf{j}+\mathbf{k}]_{M} = (\mathbf{1}-\mathbf{u})\mathbf{i}+\mathbf{u}(\mathbf{N}+[\mathbf{i}]_{\mathbf{m}'})}} (-1)^{\|\mathbf{u}\|_1} a_{\mathbf{k}},$$

where $\mathbf{N} = (N_1, \dots, N_r)$, $\mathbf{1} = (1, \dots, 1) \in \mathbb{N}^r$, $[\mathbf{i}]_{\mathbf{m}'} = ([i_1]_{m'_1}, \dots, [i_r]_{m'_r})$, $[\mathbf{j} + \mathbf{k}]_M = ([j_1 + k_1]_{m_1}, \dots, [j_r + k_r]_{m_r})$ and the product of vectors is meant to be component-wise.

**Example 6.3** ($r = 1$) For all $0 \le i, j \le N - 1$, the coefficient $a_j^{(i)}$ is given by:

$$a_{j}^{(i)} = a_{i-j} - a_{N-j+[i]_{m'}}, \quad m' = \frac{M}{t}.$$

**Algorithm 16** LWE extraction of $\mu_i$ from $\mu(X) = \sum_{j=0}^{N-1} \mu_j \Omega_j(X) \in \mathcal{T}$ (case $r = 1$)

**Input:** $(a(X), b(X)) = \text{RLWE}_s(\mu(X)) \in \mathcal{T} \times \mathcal{T}$, index $i \in \{0, \dots, N-1\}$.

1: **for** each $j$ from 1 to $N$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;**a**$_j \leftarrow a_{i-j} - a_{N-j+[i]_{m'}}$

3: **end for**

4: &nbsp;&nbsp;&nbsp;&nbsp;**b** $\leftarrow$ $(b(X))_i$

5: **Return:** $\text{LWE}_s(\mu_i) = (\mathbf{a}, \mathbf{b})$

**Note:** $a(X), b(X), s(X)$ are expressed in $(\Omega_j)_{0 \le j < N}$

**Example 6.4** ($r = 2$) Let $t_1, t_2$ be two distinct primes. For all $\mathbf{i}, \mathbf{j} \in \mathbf{J}$

$$a_{\mathbf{j}}^{(i)} = a_{y_1,y_2} - a_{y_1,z_2} - a_{z_1,y_2} + a_{z_1,z_2},$$

where

$$y_{\ell} = i_{\ell} - j_{\ell}, \quad z_{\ell} = N_{\ell} - j_{\ell} + [i_{\ell}]_{m'_{\ell}}, \quad \ell = 1, 2.$$

**Example 6.5** ($r = 3$) Let $t_1, t_2, t_3$ be three distinct primes. For all $\mathbf{i}, \mathbf{j} \in \mathbf{J}$

$$a_{\mathbf{j}}^{(i)} = a_{y_1,y_2,y_3} - a_{y_1,y_2,z_3} - a_{y_1,z_2,y_3} + a_{y_1,z_2,z_3} - a_{z_1,y_2,y_3} + a_{z_1,y_2,z_3} + a_{z_1,z_2,z_3} - a_{z_1,z_2,z_3},$$

where

$$y_{\ell} = i_{\ell} - j_{\ell}, \quad z_{\ell} = N_{\ell} - j_{\ell} + [i_{\ell}]_{m'_{\ell}}, \quad \ell = 1, 2, 3.$$

**Algorithm 17** LWE extraction of $\mu_i^*$ from $\mu^*(X) = \sum_{j=0}^{N-1} \mu_j^* \Omega_j^*(X) \in \mathcal{T}^\vee$ (case $r = 1$)

**Input:** $(a^*(X), b^*(X)) = \text{RLWE}_s^*(\mu^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$, index $i \in \{0, \dots, N-1\}$.

1: **for** each $j$ from 1 to $N$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp;**a**$_j \leftarrow \langle X^{i+M-j+1}, a^*(X) \rangle$

3: **end for**

4: &nbsp;&nbsp;&nbsp;&nbsp;**b** $\leftarrow$ $(b^*(X))_i$

5: **Return:** $\text{LWE}_s(\mu_i) = (\mathbf{a}, \mathbf{b})$

**Note:** $a^*(X), b^*(X)$ expressed in $(\Omega_j^*)_{0 \le j < N}$ and $s(X)$ in $(\Omega_j)_{0 \le j < N}$

Obtaining an LWE encryption of the trace proceeds analogously:
**Proposition 6.6 (LWE of the trace from a RLWE or RLWE<sup>*</sup>)** Let $(B_i)_{i \in \mathcal{J}}$ be a basis of $\mathcal{R}$. Then:

* RLWE<sup>*</sup> case: If $(a^*(X), b^*(X))$ is a RLWE<sup>*</sup>-encryption of $\mu^* \in \mathcal{T}^\vee$ with secret key $s(X) = \sum_{j \in \mathcal{J}} s_j B_j(X) \in \mathcal{R}$, and error $e^* \in \mathcal{T}^\vee$, then a LWE-encryption of $\mathrm{Tr}(\mu^*)$ is given by

$$ \mathrm{LWE}_s(\mathrm{Tr}(\mu^*)) = ((\mathrm{Tr}(B_i a^*))_{i \in \mathcal{J}}, \mathrm{Tr}(b^*)) $$

with secret key $\mathbf{s} = (s_j)_{j \in \mathcal{J}}$. The error is $\mathrm{Tr}(e^*) = \langle \Omega_0^*, e^* \rangle =: e_0^*$ with variance $\sigma^2(e_0^*)$.

* RLWE case: If $(a(X), b(X))$ is a RLWE-encryption of $\mu \in \mathcal{T}$ with secret key $s(X) = \sum_{j \in \mathcal{J}} s_j B_j(X) \in \mathcal{R}$, and error $e \in \mathcal{T}$, then a LWE encryption of $\mathrm{Tr}(\mu)$ is given by

$$ \mathrm{LWE}_s(\mathrm{Tr}(\mu)) = ((\mathrm{Tr}(B_i a))_{i \in \mathcal{J}}, \mathrm{Tr}(b)) $$

with secret key $\mathbf{s} = (s_j)_{j \in \mathcal{J}}$ and error $\mathrm{Tr}(e)$.

## 6.2 Blind extraction using encrypted indices

If the index $i$ of the coefficient we want to extract from

$$ (i) : \mu(X) \in \mathcal{T} \quad \text{or} \quad (ii) : \mu^*(X) \in \mathcal{T}^\vee $$

is not provided as a specific value but instead as an encrypted index, then the previous procedure becomes ineffective. In this subsection, we consider the scenario where $i$ is represented as an RGSW<sup>*</sup>-encryption of $\Omega_i^*$ (in case (i)) or as an RGSW-encryption of $\Omega_i$ (in case (ii)). These RGSW-encryptions are referred to as registers in [33]. In the first scenario, we write

$$ \mu_i = \langle \Omega_i^*, \mu \rangle = \mathrm{Tr}(\bar{\Omega}_i^* \mu) $$

where now both $\mu \in \mathcal{T}$ and $\bar{\Omega}_i^* \in \mathcal{R}^\vee$ are encrypted as

$$ c = (a, b) = \mathrm{RLWE}_s(\mu) \in \mathcal{T} \times \mathcal{T} $$

and

$$ C^* = (a_k^*, b_k^*)_{1 \le k \le 2\ell} = \mathrm{RGSW}_s^*(\bar{\Omega}_i^*) \in (\mathcal{T}^\vee \times \mathcal{T}^\vee)^{2\ell}. $$

A homomorphic external product results in:

$$ c^* = (a^*, b^*) = C^* \Box c = \mathrm{RLWE}_s^*(\bar{\Omega}_i^* \mu). $$

It then remains to obtain a LWE-encryption of the trace of $c^*$ and this can be done as in Proposition 6.6. In the dual version, we express $\mu_i^* = \langle \Omega_i, \mu^* \rangle = \mathrm{Tr}(\bar{\Omega}_i \mu^*)$ where now both $\mu^* \in \mathcal{T}^\vee$ and $\bar{\Omega}_i \in \mathcal{R}$ are encrypted as

$$ c^* = \mathrm{RLWE}_s^*(\mu^*) \in \mathcal{T}^\vee \times \mathcal{T}^\vee \quad \text{and} \quad C = \mathrm{RGSW}_s(\bar{\Omega}_i) \in (\mathcal{T} \times \mathcal{T})^{2\ell}. $$

An homomorphic external product then gives

$$ c^* = (a^*, b^*) = C \Box c^* = \mathrm{RGSW}_s(\bar{\Omega}_i \mu) $$

and it remains to get a LWE-encryption of the trace of $c^*$ as in Proposition 6.6.
### 6.2.1 Simple blind extraction

In some scenarios, it is convenient to consider a secret key $s = \sum_{j \in \mathbf{J}} s_j \bar{\Omega}_j(X)$ with bases $(B_i)_{i \in \mathbf{J}}$ of $\mathcal{R}$ and $(B_i^*)_{i \in \mathbf{J}}$ of its dual $\mathcal{R}^\vee$.

**Objective:** From an encryption $C^* = \text{RGSW}_s^*(\bar{B}_i^*)$ of an index $\mathbf{i} \in \mathbf{J}$ and an encryption $c = (a, b) = \text{RLWE}_s(\mu)$ of the polynomial $\mu = \sum_{i \in \mathbf{J}} \mu_i B_i$, recover an LWE encryption of $\mu_i$.

**Procedure:** Proceed in two steps:

1. Compute $c^* = (a^*, b^*) = C^* \boxdot c = \text{RLWE}_s^*(\bar{B}_i^* \mu)$;

2. Express the corresponding LWE encryption. Recall that that $\bar{B}_i^* \mu = b^* - s \cdot a^* - e^*$, and note that $\mu_i = \langle B_i^*, \mu \rangle = \text{Tr}(b^*) - \sum_{j \in \mathbf{J}} s_j \langle \Omega_j, a^* \rangle - \text{Tr}(e^*)$. Therefore, define

$$ \text{LWE}_s(\mu_i) = (\tilde{a}, \tilde{b}) \quad \text{with} \quad \tilde{a}_j = \langle \Omega_j, a^* \rangle \quad \text{and} \quad s_j = s_j \quad \text{for all} \quad j \in \mathbf{J} \quad \text{and} \quad \tilde{b} = \text{Tr}(b^*) $$

If $a^*$ and $b^*$ are, for instance, both expressed in the basis $(\Omega_i^*)_{i \in \mathbf{J}}$ as $a^* = \sum_{\mathbf{k} \in \mathbf{J}} a_k^* \Omega_k^*$ and $b^* = \sum_{\mathbf{k} \in \mathbf{J}} b_k^* \Omega_k^*$, then we have $\tilde{b} = b_0^*$ and for all $\mathbf{j} \in \mathbf{J}$, $\mathbf{a}_j = a_j^*$. When $s = \sum_{j \in \mathbf{J}} s_j \Omega_j$, the extraction is carried out via Algorithm 18. Note that the error of $\text{LWE}_s(\mu_i)$ is given by

$$ \text{Tr}(e^*) = \text{Tr}(\text{Err}(C^* \boxdot c)) = \text{Tr}(\text{dec}_{D,\ell}(c) \cdot \text{Err}(C^*) + \bar{B}_i^*(\delta(b) - s \delta(a)) + \bar{B}_i^* \text{Err}(c)) $$

which simplifies to

$$ \text{Tr}(e^*) = \text{Tr}(\text{Err}(C^* \boxdot c)) = \text{Tr}(\text{dec}_{D,\ell}(c) \cdot \text{Err}(C^*)) + (\delta(b) - s \delta(a))_i + (\text{Err}(c))_i $$

when $(B_j)_{j \in \mathbf{J}} = (\Omega_j)_{j \in \mathbf{J}}$. Its variance can be bounded using Corollary 9.5 with $\nu = 0$ and $\nu = \rho(\mathbf{i})$ as

$$ \sigma^2(\text{Tr}(e^*)) \le 2\ell N \Gamma_M \frac{D^2 + \xi_D}{12} \max_{1 \le k \le 2\ell} \sigma^2(\text{Err}(C_k^*)) + \frac{D^{-2\ell}}{12} (1 + \Gamma_M \|s\|_2^2) + \sigma^2((\text{Err}(c))_i) \quad (12) $$

**Algorithm 18 Blind Extraction of Coefficient $\mu_i$ of $\mu(X) \in \mathcal{T}$**

**Input:** Encryptions $c \in \mathcal{T} \times \mathcal{T}$ of $\mu = \sum_{j \in \mathbf{J}} \mu_j B_j$ and $C^* = \text{RGSW}_s^*(\bar{B}_i^*)$ of an index $\mathbf{i} \in \mathbf{J}$.

1: $c^* = (a^*, b^*) \leftarrow C^* \boxdot c$

2: $\tilde{b} \leftarrow b_0^*$

3: **for** $\mathbf{j} \in \mathbf{J}$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $\tilde{a}_j \leftarrow \langle \bar{\Omega}_j, a^* \rangle$,

5: **end for**

6: **Return** $\text{LWE}_s(\mu_i) = (\tilde{a}, \tilde{b})$ with $s = (s_j)_{j \in \mathbf{J}}$.

### 6.2.2 Blind extraction of a linear form of a vector in $\mathbb{T}^N$.

Assume $s = \sum_{j \in \mathbf{J}} s_j \Omega_j$ and let $(B_i)_{i \in \mathbf{J}}$ be a basis of $\mathcal{R}$ and $(B_i^*)_{i \in \mathbf{J}}$ its dual w.r.t. $\langle \cdot, \cdot \rangle$. Let $\ell \in \mathbb{Z}^\mathbf{J}$ be a linear form from $\mathbb{T}^{N-1}$ to $\mathbb{T}$:

$$ \mu \in \mathbb{T}^N \mapsto \sum_{\mathbf{i} \in \mathbf{J}} \ell_{\mathbf{i}} \mu_{\mathbf{i}} \in \mathbb{T}. $$

**Objective:** from an encryption $C^* = \text{RGSW}_s^*(L^*)$ of a well-chosen polynomial $L^*$ and an encryption $c = \text{RLWE}_s(\mu)$ of the polynomial $\mu = \sum_{i \in \mathbf{J}} \mu_i B_i$, get a LWE-encryption of $\ell^T \mu$.

**Procedure:** Proceed in two steps:
1. Compute $c^* = (a^*, b^*) = C^* \boxdot c = \text{RLWE}_s^*(\bar{L}^*\mu)$;

2. Write the corresponding LWE-encryption. If $C^*$ is built to encrypt $L^* = \sum_{i \in \mathcal{J}} \ell_i B_i^*$, then we get

$$ \langle L^*, \mu \rangle = \sum_{i \in \mathcal{J}} \ell_i \langle B_i^*, \mu \rangle = \sum_{i \in \mathcal{J}} \ell_i \mu_i. $$

The corresponding Algorithm is given below:

**Algorithm 19** Blind Extraction of $\sum_{i \in \mathcal{J}} \ell_i \mu_i$ from $\mu \in \mathcal{T}$

**Input:** Encryptions $c \in \mathcal{T} \times \mathcal{T}$ of $\mu = \sum_{j \in \mathcal{J}} \mu_j B_j$ and $C^* = \text{RGSW}_s^*(\bar{L}^*)$ with $L^* = \sum_{i \in \mathcal{J}} \ell_i B_i^*$.

1: $c^* = (a^*, b^*) \leftarrow C^* \boxdot c$

2: $\tilde{b} \leftarrow b_0^*$

3: **for** $j \in \mathcal{J}$ **do**

4: $\tilde{a}_j \leftarrow \langle \bar{\Omega}_j, a^* \rangle$,

5: **end for**

6: **Return** LWE$_s$($\sum_{i \in \mathcal{J}} \ell_i \mu_i$) = $(\tilde{a}, \tilde{b})$.

# 7 Bootstrapping in the general cyclotomic setting

The primary objective of bootstrapping in fully homomorphic encryption (FHE) is to reduce the noise that builds up in ciphertext during operations, as excessive noise can impede decryption. The key objectives of bootstrapping can be summarized as follows:

(i) **Noise Reduction:** Enables an unlimited number of homomorphic operations by refreshing the ciphertext and lowering the noise level;

(ii) **Function Mapping:** Facilitates the application of a function during the bootstrapping process;

(iii) **Security Maintenance:** Ensures that the original data remains secure throughout the operation.

In the context of TFHE, this goal can be articulated as follows:

**Goal of bootstrapping:** Given a LWE-encryption $c$ of $\mu \in \mathbb{T}_p$ with error $e$ and a function $f$ that maps $\mathbb{T}_p$ to $\mathbb{T}$, produce a LWE-encryption of $f(\mu)$ with a fresh error of smaller size than $e$.

Bootstrapping is, by definition, the mechanism that makes an encryption scheme fully homomorphic—hence it is crucial for practical homomorphic computation. The TFHE authors achieved a highly efficient refinement of FHEW-style bootstrapping; to retain comparable performance in the setting of general cyclotomics, one must reframe its algebraic structure. The bootstrapping scheme we employ is built upon the following fundamental function:

**Definition 7.1** Given a polynomial $v^*(X) \in \mathcal{T}^\vee$, the bootstrap function $\Theta_{v^*}$ is defined as

$$ \Theta_{v^*}: \begin{array}{rcl} \mathbb{T} & \rightarrow & \mathbb{T} \\ \mu & \mapsto & \text{Tr} \left( X^{-[M\mu]} v^*(X) \right) = \langle X^{[M\mu]}, v^*(X) \rangle \end{array} $$
It is important to highlight that this definition and its implementation retain the concepts of the bootstrapping procedure proposed by Ducas and Micciancio [21], with the distinction lying solely in its formulation. It is evident that $\Theta_{v^*}$ is fully characterized by the values

$$ \Theta_{v^*} \left( \frac{i}{M} \right), \quad 0 \le i \le M-1, $$

along with the observation that

$$ \forall \mu \in \mathbb{T}, \quad \Theta_{v^*}(\mu) = \Theta_{v^*} \left( \frac{\lfloor M\mu \rfloor}{M} \right). $$

A homomorphic and efficient implementation of this function, essential for the correctness of the bootstrapping procedure, must satisfy the following:

**Requirement:** For all $\mu \in \mathbb{T}_p$ and all errors $e \in \mathbb{T}$ such that $\mu + e \in \mathcal{U}(\mu)$ we require

$$ \Theta_{v^*} (\mu + e) = f(\mu), \qquad (13) $$

where $\mathcal{U}(\mu)$ is some interval around $\mu$ specifying the allowed error tolerance. In particular, when $\mathcal{U}(\mu) = (\mu - \frac{1}{2p}, \mu + \frac{1}{2p})$ we have

$$ \forall \mu \in \mathbb{T}, \quad \Theta_{v^*} (\mu) = f \left( \frac{\lfloor p\mu \rfloor}{p} \right), $$

i.e. the ideal (optimal) behaviour: the function returns the correct value as soon as the input error permits the correct projection on the torus. Since this ideal is not always attainable, taking a smaller $\mathcal{U}(\mu)$ relaxes the requirement.

In this section, we aim to establish clear and concise compatibility conditions on $f$ that guarantee the existence of $v^*$ and explicitly determine its form.

## 7.1 General formulation of the compatibility conditions

Consider the function $F$ be defined on the set $\mathbf{I}$ by

$$ \forall \mathbf{i} \in \mathbf{I}, \quad F(\mathbf{i}) := \Theta_{v^*} \left( \frac{\rho(\mathbf{i})}{M} \right) = \langle X^{\rho(\mathbf{i})}, v^*(X) \rangle. $$

As $X^{\rho(\mathbf{i})} = \Omega_{\mathbf{i}}(X)$, all the coefficients of the polynomial $v^*$ are uniquely determined by the relations $v_{\mathbf{i}}^* = F(\mathbf{i})$ for all $\mathbf{i} \in \mathbf{J}$. However, the values of $F(\mathbf{i})$ for $\mathbf{i} \in \mathbf{I} \setminus \mathbf{J}$ are then constrained by

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad F(\mathbf{i}) = \langle \Omega_{\mathbf{i}}, v^* \rangle. $$

For these values of $\mathbf{i}$, the elements $\Omega_{\mathbf{i}}$ can be expressed using Lemma 3.13.

$$ \Omega_{\mathbf{i}} = \sum_{\mathbf{j} \in \mathbf{J}} \langle \Omega_{\mathbf{i}}, \Omega_{\mathbf{j}}^* \rangle \Omega_{\mathbf{j}} = \sum_{\mathbf{j} \in \mathbf{J}} \beta_{\mathbf{i}, \mathbf{j}} \Omega_{\mathbf{j}} \quad \text{with} \quad \beta_{\mathbf{i}, \mathbf{j}} = \langle \Omega_{\mathbf{i}}, \Omega_{\mathbf{j}}^* \rangle = \sum_{\substack{\mathbf{u} \in \{0,1\}^r, \\ \mathbf{i}=(\mathbf{1}-\mathbf{u})\mathbf{j}+\mathbf{u}(\mathbf{N}+[\mathbf{j}]_{\mathbf{m}'})}} (-1)^{|\mathbf{u}|}. $$

It is convenient to consider the $\beta_{\mathbf{i}, \mathbf{j}}$'s for all $(\mathbf{i}, \mathbf{j}) \in \mathbf{I} \times \mathbf{J}$, so that $\beta_{\mathbf{i}, \mathbf{j}} = \delta_{\mathbf{i}, \mathbf{j}}$ for all $(\mathbf{i}, \mathbf{j}) \in \mathbf{J} \times \mathbf{J}$ and $\beta_{\mathbf{i}, \mathbf{j}} \in \{-1, 0, 1\}$ for all $(\mathbf{i}, \mathbf{j}) \in \mathbf{i} \in \mathbf{I} \setminus \mathbf{J} \times \mathbf{J}$. We thus end up with the compatibility relations

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad F(\mathbf{i}) = \sum_{\mathbf{j} \in \mathbf{J}} \beta_{\mathbf{i}, \mathbf{j}} F(\mathbf{j}) \mod 1. \qquad (14) $$
These compatibility relations must be solved together with the constraints imposed by (13):

$$ \forall \mu \in \mathbb{T}_p, \forall \mathbf{i} \in \mathcal{U}(\mu), \quad F(\mathbf{i}) = f(\mu). \qquad (15) $$

We summarize the result in the following proposition

**Proposition 7.2** Let $M = t_1^{\alpha_1} t_2^{\alpha_2} \cdots t_r^{\alpha_r}$ and $v^* \in \mathcal{T}^\vee$. Then the function $F$ satisfies the $M-N$ compatibility conditions

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad F(\mathbf{i}) = \sum_{(\mathbf{u}, \mathbf{j}) \in \{0,1\}^r \times \mathbf{J} \atop (\mathbf{1}-\mathbf{u})\mathbf{j} + \mathbf{u}(\mathbf{N}+[\mathbf{j}]_{\mathbf{m}'}) = \mathbf{i}} (-1)^{|\mathbf{u}|} F(\mathbf{j}) \bmod 1. \qquad (16) $$

For convenience and later use, we introduce the sets

$$ A_i = \{\mathbf{i}\} \cup \{\mathbf{j} \in \mathbf{J} \mid \forall 1 \le \ell \le r, \ j_\ell = i_\ell \text{ or } [j_\ell]_{m'_\ell} = i_\ell - N_\ell\} \qquad (17) $$

and rewrite the $M-N$ compatibility conditions (16) as

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad \sum_{\mathbf{j} \in A_i} (-1)^{n_{\mathbf{i},\mathbf{j}}} F(\mathbf{j}) = 0 \bmod 1, \qquad (18) $$

where for all $\mathbf{i} \in (\mathbf{I} \setminus \mathbf{J})$ and all $\mathbf{j} \in A_i$

$$ n_{\mathbf{i},\mathbf{j}} = \begin{cases} \# \left\{ 1 \le \ell \le r \mid i_\ell = [j_\ell]_{m'_\ell} + N_\ell \right\} & \text{if } \mathbf{i} \ne \mathbf{j} \\ 1 & \text{if } \mathbf{i} = \mathbf{j} \end{cases} $$

**Example 7.3 (Case $r=1$)** Let $t$ be a prime, $\alpha \in \mathbb{N}_>$ and $M = t^\alpha$. For all $i \in \mathbf{I} \setminus \mathbf{J} = \{i \in \mathbb{N}, N \le i \le M-1\}$, we have

$$ \sum_{j=0}^{t-1} F(jm' + [i]_{m'}) = 0 \bmod 1. $$

Note that for $\alpha = 1$, we have $N = M-1 = t-1$ and the only remaining relation is $\sum_{j=0}^{t-1} F(j) = 0$.

**Example 7.4 (Case $r=2$)** Let $t_1, t_2$ be distinct prime numbers and $(\alpha_1, \alpha_2) \in (\mathbb{N}_>)^2$. Denoting $I_1 = \{0, \dots, m_1-1\}$, $J_1 = \{0, \dots, N_1-1\}$, $I_2 = \{0, \dots, m_2-1\}$, $J_2 = \{0, \dots, N_2-1\}$, we have

$$ \mathbf{I} \setminus \mathbf{J} = (I_1 \setminus J_1 \times J_2) \cup (J_1 \times I_2 \setminus J_2) \cup (I_1 \setminus J_1 \times I_2 \setminus J_2), $$

and (16) split into three groups of conditions: for all $\mathbf{i} \in I_1 \setminus J_1 \times J_2$:

$$ F(i_1, i_2) + \sum_{j_1=0}^{t_1-2} F(j_1 m'_1 + [i_1]_{m'_1}, i_2) = 0 \bmod 1. $$

For all $\mathbf{i} \in J_1 \times J_2 \setminus J_2$:

$$ F(i_1, i_2) + \sum_{j_2=0}^{t_2-2} F(i_1, j_2 m'_2 + [i_2]_{m'_2}) = 0 \bmod 1. $$
For all $\mathbf{i} \in I_1 \setminus J_1 \times I_2 \setminus J_2$:

$$ 
\begin{aligned}
F(i_1, i_2) + \sum_{j_1=0}^{t_1-2} F(j_1 m'_1 + [i_1]_{m'_1}, i_2) + \sum_{j_2=0}^{t_2-2} F(i_1, j_2 m'_2 + [i_2]_{m'_2}) &= \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} F(j_1 m'_1 + [i_1]_{m'_1}, j_2 m'_2 + [i_2]_{m'_2}) \mod 1.
\end{aligned}
$$

Note that for $\alpha_1 = \alpha_2 = 1$, we have $N_1 = t_1 - 1$, $N_2 = t_2 - 1$ and the only remaining relations are

$$ (i) : \forall 0 \le i_2 \le t_2 - 2, \sum_{j_1=0}^{t_1-1} F(j_1, i_2) = 0, \quad (ii) : \forall 0 \le i_1 \le t_1 - 2, \sum_{j_2=0}^{t_2-1} F(i_1, j_2) = 0 \mod 1, $$

and

$$ (iii) : F(t_1 - 1, t_2 - 1) + \sum_{j_1=0}^{t_1-2} F(j_1, t_2 - 1) + \sum_{j_2=0}^{t_2-2} F(t_1 - 1, j_2) = \sum_{j_1=0}^{t_1-2} \sum_{j_2=0}^{t_2-2} F(j_1, j_2) \mod 1. $$

We can now observe that the $M-N$ compatibility conditions (16) constrained by (15) have no general solution that is valid for all functions $f$ if we insist on having $U(\mu) = (\mu - \frac{1}{2p}, \mu + \frac{1}{2p})$ for all $\mu \in \mathbb{T}_p$. Indeed, this would imply that all functions $f$ satisfy

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad f\left(\frac{\lceil p^{\rho(\mathbf{i})} \rceil}{p}\right) = \sum_{\mathbf{j} \in \mathbf{J}} \beta_{\mathbf{i}, \mathbf{j}} \quad f\left(\frac{\lceil p^{\rho(\mathbf{j})} \rceil}{p}\right) \mod 1, $$

which imposes a rather strict constraint. In practice, beyond particular choices of $p$ and $M$, one must relax this requirement by allowing the tolerance neighborhood $U$ to be smaller. The natural question then becomes whether an optimal size for these neighborhoods exists and, if so, whether the corresponding test polynomial $v^*$ can be computed explicitly in the general case.

## 7.2 Algorithm to determine the optimal $v^*$ for $r = 1$

Note that for $r = 1$, the sets $A_i = \{[i]_{m'} + km', 0 \le k \le t-1\}$ for $i \in \mathbf{J} = \{N, \dots, M-N-1\}$ are pairwise disjoint and cover $\mathbf{I} = \{0, \dots, M-1\}$; this need not hold for $^6 r \ge 2$. While we do not give a formal proof of correctness for the algorithm of this section in the case $r > 1$, we present it in full generality because a straightforward adaptation performs satisfactorily in practice. We nevertheless evaluate its performance only in the $M = t^\alpha$ setting.

Our goal is to realize a target function $f$ on plaintexts via bootstrapping, which is fully specified by the discrete function $F$ on indices. Concretely, for any message $\mu = \frac{k}{p} \in \mathbb{T}_p$ we require

$$ \forall \mathbf{i} \in \mathbf{I}, \quad \rho(\mathbf{i}) \in \mathcal{U}(\mu) \Rightarrow F(\mathbf{i}) = f(\mu) \quad (19) $$

where $\text{dist}$ is the torus distance. The task is thus to remove the compatibility constraints (18) while maximizing the tolerated error interval around each $\mu \in \mathbb{T}_p$ on which the implication holds. We proceed as follows:

<footnote>$^6$For $M = t_1 t_2$, for example, we have $(0,0) \in A_{(0,N_2)} \cap A_{(N_1,0)}$.</footnote>
**Step 1:** For each compatibility relation (18) choose the index in $A_i$ farthest from its nearest message. More precisely, for each $\mathbf{i} \in \mathbf{I} \setminus \mathbf{J}$ set

$$ \mathbf{e}_i := \operatorname{Argmax}_{\mathbf{j} \in A_i} \left| \frac{|p^{\rho(\mathbf{j})}|}{p} - \frac{\rho(\mathbf{j})}{M} \right| \quad (20) $$

**Step 2:** For every $\mathbf{j} \in A_i$ assign

$$ \forall \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad \forall \mathbf{j} \in A_i, \quad F(\mathbf{j}) = \begin{cases} f\left(\frac{|p^{\rho(\mathbf{j})}|}{p}\right) & \text{if } \mathbf{j} \neq e_i \\ -\sum_{\mathbf{j} \in A_i \setminus \{e_i\}} (-1)^{n_{\mathbf{i},\mathbf{j}}-n_{\mathbf{i},e_i}} f\left(\frac{|p^{\rho(\mathbf{j})}|}{p}\right) & \text{if } \mathbf{j} = e_i \end{cases} \quad (21) $$

so that the compatibility relation for $\mathbf{i}$ is satisfied.

**Step 3:** Finally set the coefficients of $v^*$ by $v_j^* = F(\mathbf{j})$ for all $\mathbf{j} \in \mathbf{J}$.

In order to evaluate the efficiency of the procedure, we define, for a fixed $t$, the function $G$ on values of $p$ that are not multiples of $t$ as follows:

$$ G_M(p) = \inf_{\mathbf{i} \in \mathbf{I} \setminus \mathbf{J}} \max_{\mathbf{j} \in A_i} \left| \frac{|p^{\rho(\mathbf{j})}|}{p} - \frac{\rho(\mathbf{j})}{M} \right| $$

The closer to $\frac{1}{2p}$ the value $G_M(p)$, the larger the tolerance on incoming errors.

**Remark 7.5** For $M = t^\alpha$, as illustrated in Figure 1a, when $t > 10$, we have $G_M(p) \sim \frac{1}{2p}$. When $t = 2$ and $p$ is odd, $G_M(p) \sim \frac{1}{4p}$, and for $t \ge 2$, $G_M(p)$ ranges between $\frac{1}{4p}$ and $\frac{1}{2p}$. In the regime where $G_M(p) \sim \frac{1}{2p}$, an effective choice is

$$ v^*(X) = \sum_{i=0}^{N-1} f\left(\frac{|p^{\frac{i}{M}}|}{p}\right) \Omega_i^*(X). $$

<figure><img src="image_3.png" /><figcaption>Figure 1: Functions $p \mapsto pG_M(p)$ and $F(i)$ with $p = 5$ for various $(t, \alpha)$.</figcaption></figure>

## 7.3 Algorithm to determine the optimal $v^*$ for $r > 1$

We reformulate the goal for $r > 1$ as solving for $(F(\mathbf{j}))_{\mathbf{j} \in \mathbf{I}}$, the linear system

$$ \sum_{\mathbf{j} \in A_i} (-1)^{n_{\mathbf{i},\mathbf{j}}} F(\mathbf{j}) \mod 1 = 0, \quad \text{for } \mathbf{i} \in \mathbf{I} \setminus \mathbf{J}, \quad (22) $$
<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>Figure 2: Function $F(i) = \Theta_{v^*}(\frac{i}{M})$ for various $(p, t, \alpha)$.</figcaption></figure>

subject to the constraints

$$ \forall i \in \{0, \dots, M-1\} \text{ such that } -\eta_k' < \text{mods} \left( \frac{k}{p} - \frac{i}{M} \right) < \eta_k, \quad F(\rho^{-1}(i)) = f\left(\frac{k}{p}\right), \quad (23) $$

where $k = \lfloor \frac{pi}{M} \rfloor$ and $\eta_k, \eta_k' \in (0, \frac{1}{2p})$ (typically chosen near $N/(2pM)$). For fixed $0 \le k \le p-1$, the number of indices $0 \le i \le M-1$ satisfying

$$ -\eta_k' < \text{mods} \left( \frac{k}{p} - \frac{i}{M} \right) < \eta_k, $$

is

$$ \left\lfloor \frac{kM}{p} + M\eta_k' \right\rfloor - \left\lfloor \frac{kM}{p} - M\eta_k \right\rfloor - 1. $$

The system (22) with constraints (23) reduces to at most $M-N$ equations in $M-N$ unknowns iff

$$ \sum_{k=0}^{p-1} \left[ \left\lfloor \frac{kM}{p} + M\eta_k' \right\rfloor - \left\lfloor \frac{kM}{p} - M\eta_k \right\rfloor - 1 \right] \le N. $$

To maximize these intervals we choose $\eta_k, \eta_k'$ as large as feasible; heuristically they satisfy

$$ \eta \approx \frac{N}{2pM} $$

since maintaining $M-N$ unknowns requires $M-N \approx M-p \cdot 2\eta M$. A convenient discrete choice is, for $0 \le k \le p-1$,

$$ M\eta_k = \left\lfloor \frac{N}{2p} \right\rfloor + \varepsilon_k, \quad M\eta_k' = \left\lfloor \frac{N}{2p} \right\rfloor + \varepsilon_k', $$

with $\varepsilon_k, \varepsilon_k' \in [-1, 1]$. In this case, the above inequality becomes

$$ \sum_{k=0}^{p-1} \left[ \left\lfloor \frac{kM}{p} + \varepsilon_k' \right\rfloor - \left\lfloor \frac{kM}{p} - \varepsilon_k \right\rfloor - 1 \right] \le N - 2p \left\lfloor \frac{N}{2p} \right\rfloor $$

with

$$ r_{k,p} = kM/p - \lfloor kM/p \rfloor \in [-1/2, 1/2), $$
and we obtain

$$ \sum_{k=0}^{p-1} (\lceil r_{k,p} + \varepsilon'_{k} \rceil - \lfloor r_{k,p} - \varepsilon_{k} \rfloor - 1) \le N - 2p \lfloor \frac{N}{2p} \rfloor. $$

Assuming $\varepsilon_k, \varepsilon'_k \in -1, 0, 1$, it follows that

$$ \sum_{k=0}^{p-1} (\varepsilon_k + \varepsilon'_k) \le N - 2p \lfloor \frac{N}{2p} \rfloor + L_p, $$

where

$$ L_p := \sum_{k=0}^{p-1} (\lfloor r_{k,p} \rfloor - \lfloor r_{k,p} \rfloor + 1). $$

The optimal choice is

$$ \varepsilon_k = \operatorname{sign} \left( N - 2p \lfloor \frac{N}{2p} \rfloor \right) \quad \text{for } 0 \le k < \lfloor N - 2p \lfloor \frac{N}{2p} \rfloor \rfloor, $$

and

$$ \varepsilon_k = 0 \quad \text{for} \quad \lfloor N - 2p \lfloor \frac{N}{2p} \rfloor \rfloor \le k \le p - 1, $$

with

$$ \varepsilon'_{k} = \lfloor r_{k,p} \rfloor - \lfloor r_{k,p} \rfloor + 1 \quad \text{for } 0 \le k < p $$

which saturates the inequality.

Finally, after determining the parameters $\eta_k$ and $\eta'_k$, we solve the linear system from (22-23), comprising $M-N$ equations with $M-N$ unknowns. Figure (2) shows the bootstrap function $\Theta_{v*}$ for varied $p$, $(t_1, t_2)$, and $(\alpha_1, \alpha_2)$. These plots reveal that except at interval edges around messages, $\Theta_{v*}$ aligns with $f$. The question of the linear system's invertibility and its conditions remains. Experiments varying $p$, $t_1$, and $t_2$ confirmed the system's invertibility, indicating a unique solution for various parameters; however, theoretical analysis would be needed for general invertibility conditions.

## 7.4 Homomorphic implementation

We now convert Definition 7.1 into a practical algorithm that operates on the ciphertext $(\mathbf{a}, b)$, which encrypts $\mu \in \mathbb{T}_p$ with a secret key $\mathbf{s}$:

$$ \mu = b - \mathbf{s} \cdot \mathbf{a} - e. $$

The first step, while not critical to the definition of bootstrapping, is essential for enhancing its efficiency. This step involves re-encrypting the ciphertext with a smaller key $\hat{\mathbf{s}} \in \mathbb{S}^{\hat{n}}$, such that

$$ \mu = \hat{b} - \hat{\mathbf{s}} \cdot \hat{\mathbf{a}} - \hat{e}. $$

Bootstrapping fundamentally entails the homomorphic computation of an LWE-encryption of $\Theta_{v*}(\mu)$ from an LWE-encryption of $\mu$. Since rounding to an integer is not inherently a homomorphic operation, it is necessary to first approximate

$$ \lfloor M\mu \rfloor = \lfloor M(\hat{b} - \hat{\mathbf{s}} \cdot \hat{\mathbf{a}} - \hat{e}) \rfloor $$
To achieve this, we employ the collapsing strategy from [9]. For the sake of simplicity, we suppose here that $m$ divides $\hat{n}$. We denote, on the one hand,

$$ \tilde{s}_k = (\hat{s}_{m(k-1)+1}, \hat{s}_{m(k-1)+2}, \dots, \hat{s}_{mk}) \in \mathbb{S}^m, \quad k = 1, \dots, \hat{n}/m, \qquad (24) $$

and on the other hand

$$ \tilde{\mathbf{a}}_k = (\hat{a}_{m(k-1)+1}, \hat{a}_{m(k-1)+2}, \dots, \hat{a}_{mk}) \in \mathbb{T}_q^m, \quad k = 1, \dots, \hat{n}/m, \qquad (25) $$

so that

$$ \mu + e = \hat{b} - \hat{s} \cdot \hat{a} = \hat{b} - \sum_{k=1}^{\hat{n}/m} \tilde{s}_k \cdot \tilde{a}_k. $$

As explained in [9], we then round partial sums $\tilde{s}_k \cdot \tilde{a}_k$ and not individual products $s_k a_k$ as it is customary [15, 16, 21]. This leads to the approximation

$$ [M(\mu + e)] \approx - \sum_{k=1}^{\hat{n}/m} \sum_{\mathbf{j} \in \mathbb{S}^m} \delta_{\mathbf{j}, \tilde{s}_k} \bar{a}_{k, \mathbf{j}} = - \sum_{k=1}^{\hat{n}/m} \bar{a}_{k, \tilde{s}_k} =: \iota, \qquad (26) $$

where we denote $\delta_{\tilde{i}, \tilde{j}}$, for $(\tilde{i}, \tilde{j}) \in \mathbb{S}^m \times \mathbb{S}^m$, the symbol with value 1 if $\tilde{i} = \tilde{j}$ and 0 otherwise, and where

$$ \bar{a}_{1, \tilde{j}} = [M \tilde{a}_1 \cdot \tilde{j} - Mb], \quad \bar{a}_{k, \tilde{j}} = [M \tilde{a}_k \cdot \tilde{j}] \quad \text{for } k = 2, \dots, \hat{n}/m \text{ and } \tilde{j} \in \mathbb{S}^m. \qquad (27) $$

Note that the sum in (26) is valid for all $m$ dividing $\hat{n}$, in particular for $m = 1$, where we recover the usual expression, as seen in [15], for example. We finally observe that

$$ X^{-\iota} = \prod_{k=1}^{\hat{n}/m} X^{\bar{a}_{k, \tilde{s}_k}} = \prod_{k=1}^{\hat{n}/m} \sum_{\tilde{j} \in \mathbb{S}^m} \delta_{\tilde{j}, \tilde{s}_k} X^{\bar{a}_{k, \tilde{j}}} = \prod_{k=1}^{\hat{n}/m} H_k(X) \qquad (28) $$

with

$$ H_k(X) = \sum_{\tilde{j} \in \mathbb{S}^m} \delta_{\tilde{j}, \tilde{s}_k} X^{\bar{a}_{k, \tilde{j}}} \in \mathcal{R}, \quad k = 1, \dots, \hat{n}/m, \qquad (29) $$

so that $X^{-\iota} \cdot v^*(X)$ can be computed as the result of $\hat{n}/m$ successive modular products $\mathcal{R} \times \mathcal{T}^{\vee}$ applied from the right to the left

$$ X^{-\iota} \cdot v^*(X) = H_{\hat{n}/m}(X) \dots (H_2(X) \cdot (H_1(X) \cdot v^*(X))) \dots \qquad (30) $$

The full bootstrapping procedure involves three steps:

1. **Keyswitch Operation:** Given $\mathbf{c} = (\mathbf{a}, \mathbf{b})$ a LWE$_s$-encryption of a message $\mu \in \mathbb{T}_p$, compute $\hat{\mathbf{c}} = (\hat{\mathbf{a}}, \hat{\mathbf{b}})$ a LWE$_{\tilde{s}}$-encryption for a reduced size key $\hat{s}$;

2. **Blind Rotate Operation:** Given RGSW$_s$-encryptions of the $\delta_{\tilde{j}, \tilde{s}_k}$, computes a RLWE$_{\tilde{s}}$-encryption of $X^{-\iota} \cdot v^*(X)$;

3. **Extract Operation:** Compute an LWE$_s$-encryption of the trace of $X^{-\iota} \cdot v^*(X)$, which is the final output of the bootstrap$^7$.

The first step is entirely standard and resembles for instance what is done in the context of powers-of-two cyclotomic polynomials; therefore, we will omit its description. Below, we will outline the two other essential steps in detail.

<footnote>$^7$The final LWE-key is fully specified by the polynomial key $s(X) = \sum_{j=0}^{N-1} s_j X^j \in \mathcal{R}$, and the extraction procedure we adopt guarantees that $\mathbf{s} = (s_0, s_1, \dots, s_{N-1})$.</footnote>
Blind rotation

Given RGSW$_s$-encryptions of the $\delta_{\tilde{j},\tilde{s}_k}$, it is straightforward to compute the homomorphic RGSW$_s$-encryptions of $H_k(X)$ for $k = 1, \dots, \hat{n}/m$, as outlined in Formula (29). Specifically, we have:

$$ \mathrm{RGSW}_s(H_k) = \bigoplus_{\tilde{j} \in \mathbb{S}^m} \left( X^{\bar{a}_{k, \tilde{j}}} \cdot \mathrm{RGSW}_s(\delta_{\tilde{j}, \bar{s}_k}) \right), \quad (31) $$

where the $\cdot$ denotes the product of the polynomial $X^{\bar{a}_{k, \tilde{j}}} \in \mathcal{R}$ by each of the polynomial components of RGSW$_s(\delta_{\tilde{j},\bar{s}_k})$, all of which reside in $\mathcal{T}^\vee$. The RLWE$_s^*$-encrypted value $X^{-\iota} \cdot v^*(X)$ can now be computed homomorphically according to Formula (30) as follows:

$$ \mathrm{RGSW}_s(H_{n/m}) \boxtimes (\dots (\mathrm{RGSW}_s(H_1) \boxtimes \mathrm{RLWE}_s^*(v^*))\dots). \quad (32) $$

Note that RLWE$_s^*(v^*)$ is defined here as the trivial noise-free zero-mask $(0, v^*(X))$. Additionally, we assume that $v^*$ aligns with its definition in Section 7.3 for the specified target function $f$.

<caption>**Algorithm 20 Blind Rotation Algorithm**</caption>

1: **Input:** $c = (\mathbf{a}, b) \in \mathbb{T}^{\hat{n}+1}$ and RGSW$_s(\delta_{\tilde{j},\bar{s}_k})$ for $\tilde{j} \in \mathbb{S}^m$, $k = 1, \dots, \hat{n}/m$.
2: **for** $\tilde{j} \in \mathbb{S}^m$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $\bar{a}_{1,\tilde{j}} = [M\tilde{a}_1 \cdot \tilde{j} - Mb]$ 
4: &nbsp;&nbsp;&nbsp;&nbsp;**for** $k = 2$ to $\hat{n}/m$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $\bar{a}_{k,\tilde{j}} = [M\tilde{a}_k \cdot \tilde{j}]$.
6: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
7: **end for**
8: **for** $k = 1$ to $\hat{n}/m$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;**Initialize:** RGSW$_s(H_k) = \mathrm{RGSW}_s(0)$
10: &nbsp;&nbsp;&nbsp;&nbsp;**for** $\tilde{j} \in \mathbb{S}^m$ **do**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $\mathrm{RGSW}_s(H_k) = \mathrm{RGSW}_s(H_k) \oplus (X^{\bar{a}_{k,\tilde{j}}} \cdot \mathrm{RGSW}_s(\delta_{\tilde{j},\bar{s}_k}))$
12: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
13: **end for**
14: **Initialize:** $\mathrm{ACC}^* = (0, v^*(X))$.
15: **for** $k = 1$ to $\hat{n}/m$ **do**
16: &nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $\mathrm{ACC}^* = \mathrm{RGSW}_s(H_k) \boxtimes \mathrm{ACC}^*$
17: **end for**
18: **Output:** $\mathrm{ACC}^* = \mathrm{RLWE}_s^*(X^{-\iota}v^*(X))$ with $\iota = -\sum_{k=1}^{\hat{n}/m} \bar{a}_{k,\bar{s}_k}$.

Extraction

Assume $n \le N = \varphi(M)$ and let $\pi: \mathbf{J} \to \{0, \dots, N-1\}$ be a bijection. Suppose the polynomial key $s \in \mathcal{R}$ is assembled from $\mathbf{s} = (s_0, \dots, s_{n-1})$ by

$$ s(X) = \sum_{\mathbf{j} \in \mathbf{J}} s_{\pi(\mathbf{j})} X^{\rho(\mathbf{j})}, $$

where the vector $(s_i)_{0 \le i < n}$ is extended to $0 \le i < N$ by setting $s_i = 0$ for $i \ge n$. The extraction of the trace $\mathrm{Tr}(X^{-\iota} \cdot v^*(X))$ is straightforward using Proposition 6.6 with $\mu^* = X^{-\iota} \cdot v^*(X)$: as a matter of fact, given the encryption $\mathrm{ACC}^* = (a^*(X), b^*(X)) = \mathrm{RLWE}_s^*(X^{-\iota} \cdot v^*(X)) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$
of the output of the blind rotate, a LWE-encryption with key $\mathbf{s}$ of $\mathrm{Tr}(X^{-i} \cdot v^*(X)))$ is obtained as

$$ \mathrm{LWE}_{\mathbf{s}}(\mathrm{Tr}(\mu^*)) = ((\mathrm{Tr}(\Omega_{\pi^{-1}(i)}a^*))_{0 \le i < n}, b_{\mathbf{0}}^*) = (a_{\pi^{-1}(0)}^*, \dots, a_{\pi^{-1}(n-1)}^*, b_{\mathbf{0}}^*) := (\mathbf{a}, \mathbf{b}) $$

with $\mathbf{s} = (s_0, \dots, s_{n-1})$, $\mathbf{a} = (a_{\pi^{-1}(0)}^*, \dots, a_{\pi^{-1}(n-1)}^*)$ and $b = b_{\mathbf{0}}^*$.

## 7.5 Error estimate of the bootstrap output

An interesting question now arises as to whether the validity of the output error estimate, established in the standard case $M = 2^{\alpha}$, extends to other composite indices within the current framework. The next proposition will demonstrate that the increase in variance when moving from $M = 2^{\alpha}$ to $M = t^{\alpha}$ for $t \ge 3$ (respectively to any composite $M$) is bounded by a factor of two (respectively $2^r$)—a growth exactly corresponding to the variance increase resulting from $2^r - 1$ LWE-additions.

**Proposition 7.6** Assume $\hat{\mathbf{s}} \in \mathbb{S}^{\hat{n}}$, with an integer $1 \le m \le \hat{n}$ dividing $\hat{n}$, and $s(X) = \sum_{\mathbf{j} \in \mathbf{J}} s_{\mathbf{j}} X^{\rho(\mathbf{j})}$. Consider bootstrapping keys

$$ \mathrm{RGSW}_{s}(\delta_{\tilde{\mathbf{j}}, \tilde{\mathbf{s}}_{i}}), \quad 1 \le i \le \frac{\hat{n}}{m}, \quad \tilde{\mathbf{j}} \in \mathbb{S}^{m}, $$

where $\tilde{\mathbf{s}}_i$ are as per (24) and $\delta_{\tilde{\mathbf{j}}, \tilde{\mathbf{s}}_i}$ as per (26) and define $c_{*}^{(0)}$ the trivial noise-free RLWE$_s^*$ encryption of $v^*$ and, for $k = 1, \dots, \hat{n}/m$

$$ c_{*}^{(k)} = (a_{*}^{(k)}, b_{*}^{(k)}) = C^{(k)} \boxtimes c_{*}^{(k-1)} \quad \text{where} \quad C^{(k)} = \bigoplus_{\tilde{\mathbf{j}} \in \mathbb{S}^{m}} \left( X^{\tilde{\mathbf{a}}_{k, \tilde{\mathbf{j}}}} \cdot \mathrm{RGSW}_{s}(\delta_{\tilde{\mathbf{j}}, \tilde{\mathbf{s}}_{k}}) \right). $$

Then the variance $\mathrm{Var}(\mathcal{E})$ of the LWE-encryption error $\mathcal{E} = \langle 1, c_{*}^{(n/m)} \rangle$ of the bootstrap output is given by

$$ \frac{\hat{n}}{m} \gamma_M (1 + \|\bar{s}\|_2^2) \frac{D^{-2\ell}}{12} + \frac{\hat{n}}{m} N \gamma_M \ell \frac{D^2 + \xi_D}{6} |\mathbb{S}|^m \sigma_{BK}^2 \quad (33) $$

with $\xi_D = 2$ if $D$ is even and $\xi_D = -1$ if $D$ is odd and with $\bar{s}(X) = \sum_{\mathbf{i} \in \mathbf{J}} \bar{s}_{\mathbf{i}} X^{\rho(\mathbf{i})}$ and $\|\bar{s}\|_2^2 = \sum_{\mathbf{i} \in \mathbf{J}} \bar{s}_{\mathbf{i}}^2$. The cardinal of $\mathbb{S}$ is here denoted $|\mathbb{S}|$ and $\gamma_M$ is defined in Appendix (corollaries. 9.6,9.5).

**Remark 7.7** Note that for $r = 1$ and $t = 2$ we have $\gamma \le 2^1 (1 - \frac{1}{2}) = 1$, recovering the usual variance estimate for the bootstrap error. For general $M$ the bound increases by at most a factor $2^r$.

*Proof.* The following induction, valid for $1 \le k \le \hat{n}/m$, can be easily derived from Proposition 5.13:

$$ \begin{aligned} \mathrm{Err}(c_{*}^{(k)}) &= X^{\nu_k} \mathrm{Err}(c_{*}^{(k-1)}) + X^{\nu_k} \delta_{*}^{(k-1)} + \Lambda_{*}^{(k)} \\ &= \sum_{j=0}^{k-1} \left( \prod_{r=j+2}^{k} X^{\nu_r} \right) \left( X^{\nu_{j+1}} \delta_{*}^{(j)} + \Lambda_{*}^{(j+1)} \right), \end{aligned} $$

where

$$ \nu_k = \bar{a}_{k, \tilde{\mathbf{s}}_k}, \quad \delta_{*}^{(j)} = \delta(b_{*}^{(j)}) - s\delta(a_{*}^{(j)}) \quad \text{and} \quad \Lambda_{*}^{(j+1)} = \mathrm{dec}_{B, \ell}(c_{*}^{(j)}) \mathrm{Err}(C^{(j+1)}). $$
The error embedded in the bootstrap output is obtained by extracting an LWE-encryption of the trace of $c_*^{(n/m)}$, i.e., $\mathcal{E} = \langle 1, c_*^{(n/m)} \rangle$. Assuming all variables are independent and centered, its variance is given by

$$ \mathrm{Var}(\mathcal{E}) = \sum_{j=0}^{k-1} \mathrm{Var} \left( \left\langle 1, \left( \prod_{r=j+1}^{k} X^{\nu_r} \right) \delta_{*}^{(j)} \right\rangle \right) + \sum_{j=0}^{k-1} \mathrm{Var} \left( \left\langle 1, \left( \prod_{r=j+2}^{k} X^{\nu_r} \right) \Lambda_{*}^{(j+1)} \right\rangle \right). $$

The first sum can be split into two terms, computed using Corollary 9.6 of the Appendix:

$$ \mathrm{Var} \left( \left\langle 1, \left( \prod_{r=j+1}^{k} X^{\nu_r} \right) \delta(b_{*}^{(j)}) \right\rangle + \left\langle 1, \left( \prod_{r=j+1}^{k} X^{\nu_r} \right) s\delta(a_{*}^{(j)}) \right\rangle \right) = \gamma_M (1 + \|\bar{s}\|_2^2) \frac{D^{-2\ell}}{12}. $$

Similarly, the second sum is computed as follows (using Corollary 9.5 of the Appendix):

$$ \mathrm{Var} \left( \sum_{g=1}^{\ell-1} \sum_{\tilde{j} \in \mathbb{S}^m} \left\langle 1, \left( X^{\bar{a}_{j+1}, \tilde{j}} \prod_{r=j+2}^{k} X^{\nu_r} \right) \mathrm{dec}_{B, \ell}(c_{*}^{(j)}) \mathrm{Err}(C^{(j+1)}) \right\rangle \right) = 2\ell |\mathbb{S}|^m \gamma_M N \frac{D^2 + \xi_D}{12}. $$

This completes the proof.

## 7.6 General cyclotomic bootstrapping versus standard one

This subsection showcases the enhanced flexibility of the general cyclotomic bootstrapping compared to its standard counterpart. To illustrate this, we fix several parameters as follows:

* **Security parameters:** Consistent with common practice, we select binary keys $|\mathbb{S}| = 2$ and $\mathbb{S} = \{0, 1\}$, aiming for 128-bit security. Using the LWE-estimator from [1]—maintained by Martin Albrecht—for $q$ around $2^{64}$, an interpolation allows to translate $N$ into a noise standard deviation:

$$ \sigma_{BK} = 2^{-0.0265N+1.8709}, $$

where $N = \varphi(M)$ is the degree of the cyclotomic polynomial as well as the dimension of the ambient LWE-mask. Note that for each value of $M = t^\alpha$ we consider, there exists a prime $q$ close to $2^{64}$ such that its order in $\mathbb{Z}_M^\times$ is $N = \varphi(M)$. For such a choice, $q$ is a primitive root modulo $M$, ensuring that $\Phi_M(X)$ is irreducible over $\mathbb{Z}_q$ and the RLWE problem in $\mathcal{R}_q$ is strongly secure, provided that the noise and other parameters are chosen appropriately (see Section 4.3 of [34] or Section 4.1 of [30]). For example, when $M = 31^2 = 961$, the prime $q = 18446744073709551653 = 2^{64} + 37$ is the smallest prime greater than $2^{64}$ for which $q$ has order $N = 930$.

* **Design parameters:** We choose here $M = t^\alpha$ (i.e. $r = 1$) for $\gamma_M$ remains bounded by 2 and the collapse parameter $m = 4$, balancing computational efficiency and accuracy. For the decomposition steps (see Section 5.5), we set $\ell_{KS} = 16$, $D_{KS} = 2$, $\ell_{BR} = 6$, and $D_{BR} = 2^{16}$. These parameters influence the error similarly for $t = 2$ and larger primes $t \ge 3$.

* **Messages and external products:** To examine how variations in $N$ affect performance, we fix $\hat{n} = 464$ and $p = 31$.

The expected computational cost—neglecting the very fast extraction phase—is approximated by summing the costs of the bootstrap and key-switch operations:

$$ C_{BR} + C_{KS}, $$
where

$$C_{BR} = \hat{n}/m \left( 8N(K^m - 1)\ell_{BR} + 4N \left( 1 + \frac{3}{2} \log_2 N \right) + 4N\ell_{BR} \right),$$

and

$$C_{KS} = (\ell_{KS} + 3) \times \frac{3}{2} N \log_2 N + N(3\ell_{KS} - 1).$$

Note that for $t \ge 3$, substitute $N$ with $M$ in the $C_{BR}$ formula; $C_{KS}$ remains unchanged. Next, consider a ciphertext with error $e$, modeled as a centered Gaussian with standard deviation $\sigma$, with density function:

$$f(x) = \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{x^2}{2\sigma^2}}.$$

The probability of decryption failure—i.e., $|e| > \frac{1}{2p}$—is:

$$\mathbb{P}(\text{fail}) = \mathbb{P}\left(|e| > \frac{1}{2p}\right) = 2 \int_{1/(2p)}^{\infty} f(x)dx = \text{erfc}\left(\frac{1}{2p\sigma\sqrt{2}}\right).$$

Thus, for a prescribed failure probability $\mathbb{P}_{\text{fail}}$, the noise threshold is:

$$\sigma_{\text{threshold}} = \frac{1}{2p\sqrt{2}\text{erfc}^{-1}(\mathbb{P}_{\text{fail}})}.$$

When multiple bootstrap outputs are combined via addition, the resulting ciphertext remains correct with high probability as long as:

$$n_{\text{add}} \sigma_{\varepsilon}^2 \le \sigma_{\text{threshold}}^2,$$

where $\sigma_{\varepsilon}$ is the error standard deviation after one bootstrap. Building on this setting, we analyze the maximum number of additions $n_{\text{add}}$ permitted before the failure probability exceeds $\mathbb{P}_{\text{fail}} = 10^{-12}$. Specifically, we plot:

$$\left\lfloor \frac{\sigma_{\text{threshold}}^2}{\sigma_{\varepsilon}^2} \right\rfloor$$

against $C_{BR} + C_{KS}$ for several $N$ values, using the variance $\text{Var}(\mathcal{E}) = \sigma_{\varepsilon}^2$ derived from formula (33). Here, in the sums involving $\gamma$ it is replaced by 2 for $t \ge 3$, and by 1 for $t = 2$. We have highlighted in red the points corresponding to values of $N$ that are powers of two, specifically $N = 2048$ and $N = 4096$. It is evident from this distinction that if we require our cryptosystem to support a specific number of additions, choosing non-power-of-two values for $N$ provides significantly more options and flexibility.
<figure><img src="image_6.png" /><figcaption>Figure 3: Number of correct additions of bootstrap outputs versus the cost of a single bootstrap.</figcaption></figure>

# 8 Trace operators and their homomorphic evaluations

The trace operator is a crucial concept in the study of algebraic fields and structures. It fundamentally allows for the mapping of elements from a field extension back to the base field. Moreover, the trace operator is utilized to analyze and manipulate algebraic structures effectively. In this section, we will demonstrate how it can be computed efficiently.

## 8.1 The complete trace and its encryption

We recall that if $\mathcal{K}$ is a Galois extension of a number field $\mathcal{K}_0$, then the associated Galois group $\text{Gal}(\mathcal{K}/\mathcal{K}_0)$ is defined as the collection of all automorphisms of $\mathcal{K}$ that leave the subfield $\mathcal{K}_0$ unchanged. In our context, the field $\mathcal{K} = \mathbb{Q}[X]/\Phi_M(X)$ serves as a Galois extension of the field $\mathcal{K}_0 = \mathbb{Q}$. It is well-known that the Galois group in this scenario comprises the automorphisms $\tau_d$ defined by

$$ \tau_d(P)(X) = P(X^d) \quad \text{for all} \quad P \in \mathcal{K}, $$

where $d$ is any integer that is co-prime to $M$. Notably, this group is isomorphic to $\mathbb{Z}_M^\times$ and its cardinality is precisely $N = \phi(M)$, which also represents the degree of the extension. In what follows, we will explicitly denote the extension and base fields in the notation of the trace (refer to Definition 3.5) as follows:

$$ \forall P \in \mathcal{K}, \quad \text{Tr}_{\mathcal{K}/\mathcal{K}_0}(P) = \sum_{\substack{1 \le d \le M \\ \gcd(d, M)=1}} \tau_d(P). $$

Now, to derive an RLWE-encryption of the quantity $\text{Tr}_{\mathcal{K}/\mathcal{K}_0}(\mu)$ from a RLWE-encryption of $\mu \in \mathcal{T}$, a well-established and intuitive strategy can be employed. Start with an encryption $c = (a, b) \in \mathcal{T} \times \mathcal{T}$ of $\mu$ using the key $s \in \mathcal{R}$:

$$ b(X) = s(X) \cdot a(X) + \mu(X) + e(X) \mod \mathcal{R}. $$

For any integer $d$ that is co-prime to $M$, we can write the action of $\tau_d$ as follows:

$$ b(X^d) = s(X^d) \cdot a(X^d) + \mu(X^d) + e(X^d) \mod \mathcal{R}. $$
Since $\Phi_M(X^d)$ is a multiple of $\Phi_M(X)$ for all integers $d$ co-prime to $M$ (see Proposition 3.3), it follows that $(a(X^d), b(X^d))$ constitutes an encryption of $\mu(X^d)$ with the secret key $s(X^d)$. Next, a simple key switching from $s(X^d)$ to $s(X)$ transforms this encryption into one of $\mu(X^d)$ under the key $s(X)$, which is now independent of $d$. Finally, by summing these encryptions over all integers $d$ that are less than $M$ and co-prime to $M$, we obtain an encryption of $\text{Tr}_{\mathcal{K}/\mathcal{K}_0}(\mu)$ with the key $s$.

<caption>**Algorithm 21 RLWE Encryption of the Trace of $\mu(X) \in \mathcal{T}$**</caption>

1. **Input:** RLWE encryption $c(X) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$ of $\mu(X)$ with key $s(X) \in \mathcal{R}$

2. **Initialize:** $(a_\Sigma(X), b_\Sigma(X)) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$

3. **for** $d = 2$ **to** $M-1$ **such that** $\text{gcd}(d, M) = 1$ **do**

4. **Compute:** $(a(X^d), b(X^d)) \bmod \mathcal{R}$

5. **Perform key switching:**

$$ (a_d(X), b_d(X)) = \text{KeySwitch}_{s(X^d) \to s(X)}((a(X^d), b(X^d))) $$

$$ 6. \quad (a_\Sigma(X), b_\Sigma(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X)) + (a_d(X), b_d(X)) $$

7. **end for**

$$ 8. \quad \text{Output: } (a_\Sigma, b_\Sigma) = \text{RLWE}_s(\text{Tr}_{\mathcal{K}/\mathcal{K}_0}(\mu)) \text{ with key } s(X) $$

Using error estimates in Appendix, it is then easy to see that the following estimate holds (with $s_d(X) = s(X^d) \bmod \Phi_M(X)$)

$$ \sigma^2(\text{Err}(c_\Sigma)) \le \sigma^2(\text{Err}(c)) + \frac{\Gamma_M}{12} \left( \sum_{\text{gcd}(d,M)=1} \ell N(D^2 + \xi_D) \sigma^2(\text{Err}(\text{KS}_{s_d \to s})) + \frac{\|s_d\|_2^2}{D^{2\ell}} \right) $$

where $\Gamma_M = \prod_{\ell=1}^r \frac{2t_\ell - 3}{t_\ell - 1}$. Despite its straightforward nature, we note that the algorithm necessitates $N = \varphi(M)$ key-switches to obtain homomorphic encryptions of all quantities $P(X^d)$ from the encryption of $P(X)$. To mitigate this cost, we will utilize a Galois tower of field extensions

$$ \mathbb{Q} = \mathcal{K}_0 \subset \mathcal{K}_1 \subset \dots \subset \mathcal{K}_\alpha = \mathcal{K} $$

along with the associated partial traces.

**Remark 8.1** A polynomial $\mu^* \in \mathcal{T}^\vee$ is described by the set:

$$ \{[\mu^*]_{\mathcal{R}^\vee} + \Omega_0^* Z_1 + \Phi_M Q_1 \mid (Z_1, Q_1) \in \mathbb{Z}[X] \times \mathbb{Q}[X]\} \subset \mathcal{K}, $$

where $[\mu^*]_{\mathcal{R}^\vee}$ is the representative polynomial with degree $< N$ and coefficients in the interval $[-\frac{1}{2}, \frac{1}{2})$ in the basis $(\Omega_i^*)_{i \in \mathbf{J}}$. In $\mathcal{K}$, this extends to:

$$ \{[\mu^*]_{\mathcal{R}^\vee} + Z_2 + \Phi_M Q_2 \mid (Z_2, Q_2) \in \mathbb{Z}[X] \times \mathbb{Q}[X]\} \in \mathcal{T}. $$

This allows us to associate each $\mu^* \in \mathcal{T}^\vee$ with an element $\mu \in \mathcal{T}$. This construction is naturally aligned because:

$$ \begin{aligned} \text{Tr}(\mu^*) &= \text{Tr}([\mu^*]_{\mathcal{R}^\vee} + \Omega_0^* Z_1 + Z_2) = \text{Tr}(\mu) + \text{Tr}(\Omega_0^* Z_1) + \text{Tr}(Z_2) \\ &= \text{Tr}(\mu) + \langle \Omega_0^*, \bar{Z}_1 \rangle \bmod 1 = \text{Tr}(\mu) \bmod 1, \end{aligned} $$

which is consistent with the fact that the operator $\text{Tr}$ maps $\mathcal{R}^\vee$ to $\mathcal{R}$. Specifically, if $(a^*, b^*) = \text{RLWE}^*(\mu^*) \in \mathcal{T}^\vee \times \mathcal{T}^\vee$, then $([a^*]_{\mathcal{R}^\vee}, [b^*]_{\mathcal{R}^\vee}) = \text{RLWE}([\mu^*]_{\mathcal{R}^\vee}) \in \mathcal{T} \times \mathcal{T}$, allowing Algorithm 21 to output an RLWE-encryption of $\text{Tr}(\mu^*)$. A similar argument applies to the composition of partial traces of RLWE($[\mu^*]_{\mathcal{R}^\vee}$), enabling the fast computation of its full trace.
## 8.2 Partial traces and fast evaluation of the complete trace for $r = 1$

When dealing with a tower of field extensions $\mathbb{Q} \subseteq \mathcal{L} \subseteq \mathcal{K}$, the complete trace from $\mathcal{K}$ to $\mathbb{Q}$ can be efficiently expressed in terms of partial traces. The procedure involves first calculating the partial trace from $\mathcal{K}$ down to $\mathcal{L}$, and then from $\mathcal{L}$ to $\mathbb{Q}$. We explore these optimizations in this section.

### 8.2.1 Fast evaluation of the trace: a first approach

A tower of fields can be constructed by introducing, for $1 \le j \le \alpha$, the extensions over $K_0 = \mathbb{Q}$, which have degree $(t-1)t^{j-1}$, defined as follows:

$$K_j = \{P(X^{M/t^j}) \mod \Phi_M(X), P \in \mathbb{Q}[X]\}$$

It is noteworthy that $K_1$ is isomorphic to the field $\mathbb{Q}[X]/\Phi_t(X)$, while $K_2$ corresponds to the field $\mathbb{Q}[X]/\Phi_{t^2}(X)$. This pattern continues until $K_\alpha$ which coincides with $K = \mathbb{Q}[X]/\Phi_M(X)$. We thus have the tower structure defined by the following inclusions:

$$\mathbb{Q} = K_0 \subset K_1 \subset K_2 \subset \dots \subset K_{\alpha-1} \subset K_\alpha = \mathcal{K},$$

which enables the decomposition of the trace using the tower structure of the Galois groups:

$$\mathrm{Tr}_{\mathcal{K}/\mathbb{Q}} = \mathrm{Tr}_{K_1/\mathbb{Q}} \circ \mathrm{Tr}_{K_2/K_1} \circ \dots \circ \mathrm{Tr}_{K/\mathcal{K}_{\alpha-1}}. \quad (34)$$

**Lemma 8.2** The Galois groups associated to the successive field extensions may be described as follows: for all $1 \le j \le \alpha$

$$\mathrm{Gal}(K_{j+1}/K_j) = \{\tau_d | d = kt^j + 1, 0 \le k < t\}, \quad \mathrm{Gal}(K_j/K_0) = \{\tau_d | 1 \le d < t^j, \mathrm{gcd}(d,t) = 1\} \quad (35)$$

and for all $0 \le j \le \alpha - 1$:

$$\mathrm{Gal}(K/K_j) = \{\tau_d | d = kt^j + 1, 0 \le k \le t^{\alpha-j} - 1\}.$$

*Proof.* To prove (35), observe that we must have

$$\forall \tau_d \in \mathrm{Gal}(K_{j+1}/K_j), \quad \tau_d(X^{M/t^j}) = X^{M/t^j}.$$

Hence, $X^{(d-1)M/t^j} = 1$, so that $(d-1)M/t^j = 0 \mod M$. In other words, $d = kt^j + 1$ for some $k \in \mathbb{Z}$. In order to prove that we only need to consider values of $k$ in $\{0, \dots, t-1\}$, we decompose $k = qt + r$ with $0 \le r \le t-1$, and notice that

$$\frac{dM}{t^{j+1}} = \frac{(kt^j + 1)M}{t^{j+1}} = \frac{((qt + r)t^j + 1)M}{t^{j+1}} = \frac{((rt^j + 1)M}{t^{j+1}} \mod M.$$

This completes the proof of (35). We now elucidate why the decomposition formula (34) facilitates a more efficient homomorphic evaluation of an encryption of $\mathrm{Tr}_{K/\mathcal{K}_0}(\mu(X))$. The costs can be assessed in terms of the number of necessary automorphisms (or key-switchings). Recall that directly computing the complete trace requires $N-1 = (t-1)t^{\alpha-1} - 1$ non-trivial automorphisms. By utilizing the decomposition (34), only $t-1$ non-trivial automorphisms are needed for each partial trace $\mathrm{Tr}_{K_{j+1}/K_j}$, for $1 \le j \le \alpha-1$, and $t-2$ automorphisms for evaluating $\mathrm{Tr}_{K_1/\mathcal{K}_0}$. Indeed, the order of the Galois group $\mathrm{Gal}_{K_{j+1}/K_j}$ is $t$ for $1 \le j \le \alpha-1$, and $t-1$ for $j = 0$.
Consequently, the total number of required automorphisms is $(\alpha-1)(t-1)+t-2 = \alpha(t-1)-1$, which is significantly less than $N-1$.

The structure of the Galois groups allows us to express the successive traces, for $1 \le j \le \alpha-1$, as

$$ \forall P \in \mathcal{K}, \mathrm{Tr}_j(P) = \sum_{0 \le k \le t-1} \tau_{kt^{j+1}}(P) \quad \text{and} \quad \mathrm{Tr}_0(P) = \sum_{0 \le k \le t-1} \tau_k(P). \qquad (36) $$

Note that $\mathrm{Tr}_j|_{\mathcal{K}_{j+1}} = \mathrm{Tr}_{\mathcal{K}_{j+1}/\mathcal{K}_j}$. Introducing the notation (note that $\mathcal{T}_\alpha = \mathcal{T}$ and $\mathcal{T}_0 = \mathbb{T}$)

$$ \forall 0 \le j \le \alpha, \quad \mathcal{T}_j = \{ P(X^{M/t^j}) \mod \mathbb{Z}[X] \mod \Phi_M(X), P \in \mathbb{Q}[X] \}, $$

their homomorphic computation can be carried out as described in the following algorithm:

**Algorithm 22 Partial Trace Tr_j(μ) of μ ∈ K for 1 ≤ j ≤ α − 1**

1: **Input:** RLWE encryption $c = (a, b) \in \mathcal{T} \times \mathcal{T}$ of $\mu$ with key $s \in \mathcal{R}$

2: **Initialize:** $(a_\Sigma(X), b_\Sigma(X)) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$

3: **for** $k = 1$ **to** $t-1$ **do**

4: **Compute:** $d = kt^j + 1$

5: **Compute:** $(a(X^d), b(X^d)) \mod \mathcal{R}$

6: **Perform key switching:** $(a_d(X), b_d(X)) = \mathrm{KeySwitch}_{s(X^d) \to s(X)}((a(X^d), b(X^d)))$

7: $(a_\Sigma(X), b_\Sigma(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X)) + (a_d(X), b_d(X))$

8: **end for**

9: **Output:** $(a_\Sigma, b_\Sigma) = \mathrm{RLWE}_s(\mathrm{Tr}_{\mathcal{K}_{j+1}/\mathcal{K}_j}(\mu))$ with key $s$

### 8.2.2 Fast evaluation of the Trace: the algebraic approach

We recall the fundamental Galois correspondence: subgroups $G \subseteq \mathrm{Gal}(\mathcal{K}/\mathbb{Q})$ correspond bijec- tively to intermediate fields $\mathcal{G}$ with $\mathbb{Q} \subseteq \mathcal{G} \subseteq \mathcal{K}$, where $\mathcal{G}$ is the fixed field of $G$ (the elements of $\mathcal{K}$ fixed by every $\tau \in G$). In our situation this is particularly simple since

$$ \mathrm{Gal}(\mathcal{K}/\mathbb{Q}) \simeq (\mathbb{Z}_M)^\times, $$

so subgroups of the Galois group identify with subgroups of $(\mathbb{Z}_M)^\times$. To list elements of these subgroups one typically uses generators of $(\mathbb{Z}_M)^\times$. For a prime $t \ge 3$ the group $(\mathbb{Z}_{t^\alpha})^\times$ is cyclic (hence has a generator); for $t = 2$ it is cyclic only when $\alpha = 2$ or $\alpha = 4$. Furthermore, this generator can be readily derived in one of the following ways:

* If $\tilde{g}$ is of order $t-1$ in $(\mathbb{Z}_{t^\alpha})^\times$ then $g = (t+1)\tilde{g}$ serves as a generator of $(\mathbb{Z}_{t^\alpha})^\times$;

* Alternatively, if $\tilde{g}$ is a generator of $\mathbb{Z}_t^\times$, it is known that either $g = \tilde{g}$ or $g = \tilde{g} + t$ will act as a generator of $(\mathbb{Z}_{t^\beta})^\times$ for any power $\beta \ge 2$.

Thus, assuming that $g$ is a generator of $(\mathbb{Z}_{t^\alpha})^\times$ coinciding with $\tilde{g}$ or $\tilde{g}+t$ (where $\tilde{g}$ is a generator of $\mathbb{Z}_t^\times$), we have

$$ \mathrm{Gal}(\mathcal{K}/\mathbb{Q}) = \{\tau_{g^k}, k = 0, \dots, N-1\} \cong \mathbb{Z}_M^\times \cong (\mathbb{Z}_N, +) $$

and we have the following sequence of inclusions of additive sub-groups:

$$ (t-1)t^{\alpha-1}\mathbb{Z}_1 \subset (t-1)t^{\alpha-2}\mathbb{Z}_t \subset (t-1)t^{\alpha-3}\mathbb{Z}_{t2} \subset \dots \subset (t-1)t^{\alpha-\alpha+1}\mathbb{Z}_{t\alpha-1} \subset \mathbb{Z}_N, $$
to which we can associate a tower of Galois groups $G_j = \{\tau_{gk}, k \in (t-1)t^{\alpha-1-j}\mathbb{Z}_{t^j}\}, j = 0, \dots, \alpha-1$, and by the Galois correspondence, a tower of Galois fields

$$ \mathcal{K} \supset \mathcal{K}_{\alpha-1} \supset \dots \supset \mathcal{K}_1 \supset \mathbb{Q}. \qquad (37) $$

Note that the fixed field $\mathcal{G}_j$ associated with $G_j$ for $1 \le j \le \alpha - 1$ is unique and must coincide with $\mathcal{K}_j$ due to the following relationships:

$$ [\mathcal{K} : \mathcal{K}_j] = |\mathrm{Gal}(\mathcal{K}/\mathcal{K}_j)| = t^{\alpha-j} = |G_j| = [\mathcal{K} : \mathcal{G}_j]. $$

In summary, we can state the following:

**Lemma 8.3** The successive Galois groups associated with the field tower described in (37) can be characterized as follows:

$$ \mathrm{Gal}(\mathcal{K}_{j+1}/\mathcal{K}_j) = \{\tau_d, d = g^{k(t-1)t^{j-1}}, 0 \le k \le t-1\}, \quad \text{for all } 1 \le j \le \alpha-1, $$

$$ \mathrm{Gal}(\mathcal{K}_j/\mathcal{K}_0) = \{\tau_d, d = g^k, 0 \le k \le (t-1)t^{j-1}-1\}, \quad \text{for all } 1 \le j \le \alpha. $$

Now, a last observation is in order: If $\ell$ divides $t-1$, it is in fact always possible to introduce a subgroup $G_{\alpha-1,\ell}$ in the sequence of inclusions

$$ G_{\alpha-1} \subset G_{\alpha-1,\ell} \subset G_{\alpha} = \mathbb{Z}_M^{\times} $$

into strict subgroups of cardinals $\ell$ and $(t-1)/\ell$ as soon as $t \ge 3$. The Galois subgroup $G_{\alpha-1,\ell}$ is again characterized by the corresponding subgroup $\ell\mathbb{Z}_{\ell/N}$ of $\mathbb{Z}_N$

$$ G_{\alpha-1,\ell} = \{\tau_{g^k}, k \in \ell\mathbb{Z}_{\ell/N}\} $$

to which we can associated the field extension $\mathcal{K}_{1,\ell} := \mathbb{Q}(\tau(X), \tau \in G_{\alpha-1,\ell})$ in such a way that

$$ \mathcal{K}_1 \supset \mathcal{K}_{1,\ell} \supset \mathbb{Q}. $$

More generally, if $t-1 = \ell_1\ell_2\cdots\ell_r$ with $r \ge 2$, we can establish the following tower of subgroups:

$$ G_{\alpha-1} \subset G_{\alpha-1,\ell_1\ell_2\cdots\ell_r} \subset G_{\alpha-1,\ell_1\ell_2\cdots\ell_{r-1}} \subset \dots \subset G_{\alpha-1,\ell_1} \subset G_{\alpha} = \mathbb{Z}_M^{\times} $$

Let $\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_j}$ denote the associated fixed field such that:

$$ \mathcal{K}_1 \supset \mathcal{K}_{1,\ell_1\ell_2\cdots\ell_r} \supset \mathcal{K}_{1,\ell_1\ell_2\cdots\ell_{r-1}} \supset \dots \supset \mathcal{K}_{1,\ell_1} \supset \mathbb{Q}. $$

For $2 \le j \le r$, we have:

$$ \mathrm{Gal}(\mathcal{K}/\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_{j-1}}) = \{\tau_{g^k}, k \in (\ell_1 \cdots \ell_{j-1})\mathbb{Z}_{\ell_j\cdots\ell_r}\}. $$

Additionally,

$$ \mathrm{Gal}(\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_j}/\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_{j-1}}) = \{\tau_{g^k\ell_1\cdots\ell_{j-1}}, k \in \mathbb{Z}_{\ell_j}\}. $$

As an immediate consequence, the first term of the decomposition in (34) can be factored as follows:

$$ \mathrm{Tr}_{\mathcal{K}_1/\mathbb{Q}} = \mathrm{Tr}_{\mathcal{K}_{1,\ell_1}/\mathbb{Q}} \circ \mathrm{Tr}_{\mathcal{K}_{1,\ell_1\ell_2}/\mathcal{K}_{1,\ell_1}} \circ \dots \circ \mathrm{Tr}_{\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_r}/\mathcal{K}_{1,\ell_1\ell_2\cdots\ell_{r-1}}}. \qquad (38) $$
The evaluation of this trace requires $\sum_{j=1}^{r} (\ell_j - 1)$ non-trivial automorphisms instead of $t - 2$. This reduction is particularly significant when $t - 1 = 2^\gamma$, since $\sum_{j=1}^{r} (\ell_j - 1) = \gamma$. It has become quite straightforward to obtain the following algorithm for the optimized partial trace $\text{Tr}_{K_1/Q}$:

<caption>**Algorithm 23 Partial Trace Tr₀(μ) of μ ∈ K**</caption>

1: **Input:** $c = (a, b) = \text{RLWE}_s(\mu)$ of $\mu$ with key $s \in \mathcal{R}$, $g$ a generator of $\mathbb{Z}_M^\times$ and $t-1$.
2: **Initialize:** $\Pi = t-1$, $\ell = 2$ and $(\tilde{a}(X), \tilde{b}(X)) = (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$
3: **while** $\Pi > 1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;**while** $\ell \nmid \Pi$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\ell \leftarrow \text{NextPrime}(\ell)$
6: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
7: &nbsp;&nbsp;&nbsp;&nbsp;$\Pi \leftarrow \Pi/\ell$
8: &nbsp;&nbsp;&nbsp;&nbsp;$(a_\Sigma(X), b_\Sigma(X)) \leftarrow (\tilde{a}(X), \tilde{b}(X))$
9: &nbsp;&nbsp;&nbsp;&nbsp;**for** $k = 1$ **to** $\ell - 1$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $d = g^{k\Pi}$
11: &nbsp;&nbsp;&nbsp;&nbsp;**Compute:** $(\tilde{a}(X^d), \tilde{b}(X^d)) \bmod \mathcal{R}$
12: &nbsp;&nbsp;&nbsp;&nbsp;**Perform key switching:** $(\tilde{a}_d(X), \tilde{b}_d(X)) = \text{KeySwitch}_{s(X^d) \to s(X)}((\tilde{a}(X^d), \tilde{b}(X^d)))$
13: &nbsp;&nbsp;&nbsp;&nbsp;$(a_\Sigma(X), b_\Sigma(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X)) + (\tilde{a}_d(X), \tilde{b}_d(X))$
14: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
15: &nbsp;&nbsp;&nbsp;&nbsp;$(\tilde{a}(X), \tilde{b}(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X))$
16: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
17: **Output:** $(\tilde{a}, \tilde{b}) = \text{RLWE}_s(\text{Tr}_0(\mu))$ with key $s$

### 8.2.3 General expression of the trace for $t \ge 3$.

Assume $g$ that is a generator of $\mathbb{Z}_M^\times$ and that $N = \ell_1\ell_2\cdots\ell_r$, where $(\ell_k)_{1\le k \le r}$ represents a sequence of prime divisors, some of which may occur more than once. We define

$$F_{\ell} = \{\tau_{g^k}, k \in \ell \mathbb{Z}_{\frac{N}{\ell}}\} \subset \mathbb{Z}_M^{\times}$$

resulting in the following sequence of subgroup inclusions:

$$\{1\} = F_{\ell_1 \cdots \ell_r} \subset F_{\ell_1 \cdots \ell_{r-1}} \subset \cdots \subset F_{\ell_1} \subset F_1 = \mathbb{Z}_M^\times$$

Let $\mathcal{F}_\ell$ denote the fixed field associated with $F_\ell$, such that:

$$\mathcal{K} = \mathcal{F}_N = \mathcal{F}_{\ell_1 \cdots \ell_r} \supset \mathcal{F}_{\ell_1 \cdots \ell_{r-1}} \supset \cdots \supset \mathcal{F}_{\ell_1} \supset \mathcal{F}_1 = \mathbb{Q}$$

Consequently, the trace can be expressed as:

$$\text{Tr}_{K/Q} = \text{Tr}_{\mathcal{F}_{\ell_1}/Q} \circ \text{Tr}_{\mathcal{F}_{\ell_1\ell_2}/\mathcal{F}_{\ell_1}} \circ \cdots \circ \text{Tr}_{K/\mathcal{F}_{\ell_1\ell_2\cdots\ell_{r-1}}}.$$

The corresponding Galois groups are given for $0 \le j \le r$ by

$$\text{Gal}(\mathcal{F}_{\ell_1 \cdots \ell_j} / \mathcal{F}_{\ell_1 \cdots \ell_{j-1}}) = \{\tau_{g^k}, k \in (\ell_1 \cdots \ell_{j-1})\mathbb{Z}_{\ell_j}\}$$

where we adopt the convention that $\ell_0 = 1$. We now present the corresponding algorithm:
**Algorithm 24** CompleteTrace: computes an encryption of $\text{Tr}_{\mathcal{K}/\mathbb{Q}}(\mu)$ for $\mu \in \mathcal{T}$

1: **Input:** $c = (a, b) = \text{RLWE}_s(\mu)$ of $\mu$ with key $s \in \mathcal{R}$, $g$ a generator of $\mathbb{Z}_M^\times$ and $N = \varphi(M)$.

2: **Initialize:** $\Pi \leftarrow N$, $\ell \leftarrow 2$ and $(\tilde{a}(X), \tilde{b}(X)) \leftarrow (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$

3: **while** $\Pi > 1$ **do**

4: **while** $\ell \nmid \Pi$ **do**

5: $\ell \leftarrow \text{NextPrime}(\ell)$

6: **end while**

7: $\Pi \leftarrow \Pi/\ell$

8: $(a_\Sigma(X), b_\Sigma(X)) \leftarrow (\tilde{a}(X), \tilde{b}(X))$

9: **for** $k = 1$ **to** $\ell - 1$ **do**

10: **Compute:** $d = g^{k\Pi}$

11: **Compute:** $(\tilde{a}(X^d), \tilde{b}(X^d)) \bmod \mathcal{R}$

12: **Perform key switching:** $(\tilde{a}_d(X), \tilde{b}_d(X)) = \text{KeySwitch}_{s(X^d) \to s(X)}((\tilde{a}(X^d), \tilde{b}(X^d)))$

13: $(a_\Sigma(X), b_\Sigma(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X)) + (\tilde{a}_d(X), \tilde{b}_d(X))$

14: **end for**

15: $(\tilde{a}(X), \tilde{b}(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X))$

16: **end while**

17: **Output:** $(\tilde{a}, \tilde{b}) = \text{RLWE}_s(\text{Tr}_{\mathcal{K}/\mathbb{Q}}(\mu))$ with key $s$

We conclude this section by presenting Algorithm 25 for the partial trace $\text{Tr}_{i,j}$, which maps a $\mathbb{Q}$-extension of degree $i$ to a $\mathbb{Q}$-extension of degree $j|i$ within the field $\mathcal{K}$:

$$ \text{Tr}_{i,j} = \text{Tr}_j \circ \dots \circ \text{Tr}_i. $$

Note that if $i/j$ has a non-trivial divisor, say $d$ for instance, then it is more efficient to compute

**Algorithm 25** PartialTrace$_{i \to j}$: computes an encryption of $\text{Tr}_{i,j}(\mu)$ for $\mu \in \mathcal{T}$

1: **Input:** $c = (a, b) = \text{RLWE}_s(\mu)$ of $\mu$ with key $s \in \mathcal{R}$, $g$ a generator of $\mathbb{Z}_M^\times$, $j|i$, $i|N = \varphi(M)$.

2: **Initialize:** $\ell \leftarrow i/j$ and $(a_\Sigma(X), b_\Sigma(X)) \leftarrow (a(X), b(X)) \in \mathcal{T} \times \mathcal{T}$

3: **for** $k = 1$ **to** $\ell - 1$ **do**

4: **Compute:** $d = g^{kj}$ and $(a(X^d), b(X^d)) \bmod \mathcal{R}$

5: **Perform key switching:** $(a_d(X), b_d(X)) = \text{KeySwitch}_{s(X^d) \to s(X)}((a(X^d), b(X^d)))$

6: $(a_\Sigma(X), b_\Sigma(X)) \leftarrow (a_\Sigma(X), b_\Sigma(X)) + (a_d(X), b_d(X))$

7: **end for**

8: **Output:** $(a_\Sigma, b_\Sigma) = \text{RLWE}_s(\text{Tr}_{i,j}(\mu))$ with key $s$

$\text{Tr}_{i,j}$ by applying Algorithm 25 twice, specifically as $\text{Tr}_{i,d_j} \circ \text{Tr}_{d_j,j}$.

## 8.3 Partial traces and fast evaluation of the complete trace for $r > 1$

The extension to general $r$ follows from the tensor product structure of $\mathcal{K}$. Writing

$$ \mathcal{K} = (\mathbb{Q}[X_2, \dots, X_\ell]/(\Phi_{m_2}(X_2) \cdots \Phi_{m_\ell}(X_\ell))[X_1]/\Phi_{m_1}(X_1)) $$

any element $P \in \mathcal{K}$ may be viewed as a polynomial in $X_1$ with coefficients in the subring generated by the remaining variables:

$$ P(X) = \sum_{0 \le i_1 < m_1} \left( \sum_{j \in \mathcal{I}/j_1 = i_1} p_{i_1, j_2, \dots, j_r} X_2^{j_2} \cdots X_r^{j_r} \right) X_1^{i_1} $$
Hence the trace is computed by taking the trace in $X_1$ (treating the inner sums as coefficients) and then repeating the procedure for $X_2, \dots, X_r$. Hence the trace is obtained by taking the trace in $X_1$ (treating the inner sums as coefficients) and iterating for $X_2, \dots, X_r$; the partial traces commute and may be applied in any order. Now let $d_1, \dots, d_\theta$ be divisors of $N = \varphi(M)$ with $d_1 \cdots d_\theta = N$. By Galois theory there is a corresponding tower of fields

$$ \mathbb{Q} = \mathcal{K}_0 \subset \tilde{\mathcal{K}}_1 \subset \cdots \subset \tilde{\mathcal{K}}_{\theta-1} \subset \tilde{\mathcal{K}}_{\theta} = \mathcal{K}, $$

with $[\tilde{\mathcal{K}}_j : \mathbb{Q}] = d_1 d_2 \cdots d_j$ and $[\tilde{\mathcal{K}}_j : \tilde{\mathcal{K}}_{j-1}] = d_j$ for $1 \le j \le \theta$. The trace factors along this tower as

$$ \mathrm{Tr} = \widetilde{\mathrm{Tr}}_1 \circ \widetilde{\mathrm{Tr}}_2 \circ \cdots \circ \widetilde{\mathrm{Tr}}_\theta, $$

where, for each $j$:

$$ \forall P \in \mathcal{K}, \quad \widetilde{\mathrm{Tr}}_j(P) = \sum_{\tau \in \mathrm{Gal}(\tilde{\mathcal{K}}_j / \tilde{\mathcal{K}}_{j-1})} \tau(P). $$

Thus one needs only $d_1 + d_2 + \cdots + d_\theta$ automorphisms instead of $N$. optimal factorizations of $N$ (with $t_i - 1 = \prod_{j=1}^{n_i} p_j^{\beta_{i,j}}$ and distinct primes $p_j$), the minimal number of automorphisms equals

$$ \sum_{i=1}^{r} \left( (\alpha_i - 1)t_i + \sum_{j=1}^{n_i} \beta_{i,j}p_j \right) $$

automorphisms. Algorithm 24 remains valid in this scenario.

# 9 Fast packing operations

A complete packing operation typically combines multiple LWE ciphertexts with messages $\mu_i \in \mathbb{T}_p$ into a single RLWE ciphertext encrypting a polynomial whose coefficients are the $\mu_i$'s (or linear combinations thereof). While this process, which is often computationally intensive, has been accelerated for power-of-two cyclotomic polynomials, it remains unaddressed for general cyclotomic fields. The aim of this section is to extend and adapt these acceleration techniques to composite cyclotomic indices.

## 9.1 From a single LWE-ciphertext to an RLWE-ciphertext

Consider a LWE-ciphertext $\mathbf{c} = (\mathbf{a}, b) = (a_0, \dots, a_{n-1}, b) \in \mathbb{T}^n \times \mathbb{T}$ representing a message $\mu_0 \in \mathbb{T}$ with the key $\mathbf{s} = (s_0, s_1, \dots, s_{n-1})$:

$$ b = \mathbf{s} \cdot \mathbf{a} + \mu_0 + e \quad \mathrm{mod} \ 1. $$

Our aim is to transform $\mathbf{c}$ into an RLWE encryption of $\mu_0 \in \mathcal{T}$, treating it as a constant polynomial. In the conventional scenario where $t = 2$, it is well-established, as detailed for instance in [12], that this can be achieved through the following procedure. First, we define (assuming that $N \ge n$)

$$ a(X) = \sum_{i=0}^{n-1} a_i X^{-i} \mod (X^N + 1) \mod 1, \quad b(X) = b, $$

and

$$ s(X) = \sum_{i=0}^{n-1} s_i X^i, $$
and then compute

$$ \mu(X) = b - s(X) \cdot a(X). $$

The pair $(a(X), b(X))$ does not directly serve as an RLWE encryption of $\mu_0$; rather, it is an RLWE encryption of $\mu(X)$, which encapsulates $\mu_0$ (with some associated noise) in its constant term. To “purify" this ciphertext and eliminate unwanted coefficients, the trace is then applied homomorphically, yielding the desired RLWE encryption of $\mu_0$.

In the broader context where $M = t_1^{\alpha_1} t_2^{\alpha_2} \cdots t_r^{\alpha_r}$, this methodology necessitates some modifications. Assume that $n \le N = \varphi(M)$ and impose the ordering $\mathbf{i}_0 < \cdots < \mathbf{i}_{M-1}$ of $\mathbf{I}$ by increasing weight, i.e. $\mathbf{i}_k = \rho^{-1}(k)$ for $k \in \{0, \dots, M-1\}$. Define vectors $\mathbf{a}$ and $\mathbf{s}$ on $\mathbf{J}$ (with the understood slight abuse of notation) as follows

$$ \forall k \in \{0, \dots, n-1\}, \quad a_{\mathbf{j}_k} = a_k, \quad s_{\mathbf{j}_k} = s_k \quad \text{and} \quad \forall k \in \{n, \dots, N-1\}, \quad a_{\mathbf{j}_k} = 0, \quad s_{\mathbf{j}_k} = 0, $$

and consider

$$ \mu^*(X) = \bar{\Omega}_0^*(X) \mu(X) = b^*(X) - s(X) a^*(X) \mod \mathcal{R}^\vee $$

where

$$ a^* = \sum_{\mathbf{i} \in \mathbf{J}} a_{\mathbf{i}} \bar{\Omega}_{\mathbf{i}}^* \in \mathcal{T}^{\vee}, \quad s = \sum_{\mathbf{i} \in \mathbf{J}} s_{\mathbf{i}} \Omega_{\mathbf{i}} \in \mathcal{R}, \quad b^* = \bar{\Omega}_0^* b \in \mathcal{T}^{\vee}. $$

This formulation encompasses the case $M = 2^\alpha$, since in that scenario, $(\bar{\Omega}_0^*)^{-1} \bar{\Omega}_i^* = \bar{\Omega}_i$. Then

$$ (a^*, b^*) = \mathrm{RLWE}_s^*(\mu^*) \text{ and } \mathrm{Tr}(\mu^*) = \mathrm{Tr}(b^* - s a^*) = b - \mathrm{Tr}(s a^*) = b - \sum_{\mathbf{i} \in \mathbf{J}} s_{\mathbf{i}} a_{\mathbf{i}} = \mu_0 + e \mod 1. $$

At this juncture, a point merits attention: the product $\mu^* = \bar{\Omega}_0^* \cdot \mu$, which maps $\mathcal{R}^\vee \times \mathcal{T}$ to $\mathcal{T}^\vee$ must be calculated modulo $\mathcal{R}^\vee$. However, as indicated in Remark 8.1, we treat $(a^*, b^*)$ as a RLWE$_s$([$(\mu^*)_{\mathcal{R}^\vee}$]) and compute a homomorphic RLWE encryption of its trace $\mathrm{Tr}(\mu^*)$ in $\mathcal{T}$, using

**Algorithm 26** LWE-to-RLWE: re-encryption of a single LWE-ciphertext

Input: $\mathbf{c} = (\mathbf{a}, b) = (a_0, \dots, a_{n-1}, b) = \mathrm{LWE}_s(\mu_0)$ with $b - \mathbf{s} \cdot \mathbf{a} = \mu_0 + e$

1: $a^* \leftarrow \sum_{i=0}^{n-1} a_i \bar{\Omega}_{\rho^{-1}(i)}^*$ mod $\mathcal{R}$, $b^*(X) \leftarrow \bar{\Omega}_0^* b$.

2: **Return** $\hat{c} = (\hat{a}, \hat{b}) = \widetilde{\mathrm{Tr}}_1 \circ \widetilde{\mathrm{Tr}}_2 \circ \dots \circ \widetilde{\mathrm{Tr}}_\theta(a^*, b^*) \in \mathcal{T} \times \mathcal{T}$.

an appropriate decomposition along a tower of extensions (and the corresponding Galois groups of automorphisms), as described in Section 8:

$$ \mathrm{Tr}_{\mathcal{K}/\mathcal{K}_0} = \widetilde{\mathrm{Tr}}_1 \circ \widetilde{\mathrm{Tr}}_2 \circ \dots \circ \widetilde{\mathrm{Tr}}_\theta. \qquad (39) $$

where $d_1, d_2, \dots, d_\theta$ are divisors of $N = \varphi(M)$ such that $d_1 d_2 \cdots d_\theta = N$,

$$ \mathbb{Q} = \mathcal{K}_0 \subset \mathcal{K}_1 \subset \cdots \subset \mathcal{K}_{\theta-1} \subset \mathcal{K}_\theta = \mathcal{K}, $$

with $\dim_{\mathbb{Q}} \mathcal{K}_j = d_1 d_2 \cdots d_j$ and $\dim_{\mathcal{K}_{j-1}} \mathcal{K}_j = d_j$ for all $1 \le j \le \theta$ is the tower extension, and where

$$ \forall \mu \in \mathcal{K}, \quad \widetilde{\mathrm{Tr}}_j(\mu) = \sum_{\tau \in \mathrm{Gal}(\mathcal{K}_j / \mathcal{K}_{j-1})} \tau(\mu). $$

Indeed with this factorization only $d_1 + d_2 + \cdots d_\theta$ automorphisms have to be computed, while $d_1 d_2 \cdots d_\theta = N$ automorphisms are needed in the original expression of the trace. If $M =$
$t_1^{\alpha_1} t_2^{\alpha_2} \cdots t_r^{\alpha_r}$ and $t_i - 1 = \prod_{j=1}^{n_i} p_j^{\beta_{i,j}}$ for distinct primes $t_i$ and distinct primes $p_j$, then the optimal factorization should use only

$$ \sum_{i=1}^{r} \left( (\alpha_i - 1)t_i + \sum_{j=1}^{n_i} \beta_{i,j}p_j \right) \text{ automorphisms.} $$

This can be accomplished very efficiently, as demonstrated in Lemma 8.3, or even more effectively using Algorithm 24. A comprehensive description of the re-encryption procedure is provided in Algorithm 26.

## 9.2 Packing a set of LWE-ciphertexts into one RLWE-ciphertext

Our goal in this section is to present efficient strategies to pack many LWE encryptions into a single RLWE ciphertext. Fix $\beta = (\beta_1, \beta_2, \dots, \beta_r) \in \mathbb{N}^r$ with $1 \le \beta_k \le \alpha_k - 1$ for all $1 \le k \le r$, and set

$$ \mathbf{J}_{\beta} := \{ \mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbb{I} \mid 0 \le i_k \le t_k^{\beta_k} \frac{N_k}{m_k} - 1 \}. $$

Suppose we have $(\#\mathbf{J}_{\beta}) = t_1^{\beta_1} t_2^{\beta_2} \cdots t_r^{\beta_r} \frac{N}{M}$ LWE ciphertexts encrypting messages $(\mu_i)_{i \in \mathbf{J}_{\beta}}$. We aim to pack them into one RLWE encryption of

$$ \sum_{i \in \mathbf{J}_{\beta}} \mu_i X_1^{i_1 \frac{m_1}{t_1^{\beta_1}}} X_2^{i_2 \frac{m_2}{t_2^{\beta_2}}} \cdots X_r^{i_r \frac{m_r}{t_r^{\beta_r}}}. $$

By the construction of the previous section, each $\mu_i$ corresponds to a RLWE ciphertext $c^{(i)} = (a^{(i)}, b^{(i)})$, whose plaintext component $\mu^{(i)}$ has $\mu_i$ in its constant term (up to noise). We now describe three methods to combine the

$$ \sum_{i \in \mathbf{J}_{\beta}} \mu_i X_1^{i_1 \frac{m_1}{t_1^{\beta_1}}} X_2^{i_2 \frac{m_2}{t_2^{\beta_2}}} \cdots X_r^{i_r \frac{m_r}{t_r^{\beta_r}}}, $$

into a single RLWE encryption of the target polynomial above. To facilitate our discussion in the sequel, we introduce the following spaces and traces for $1 \le k \le r$:

$$ \mathcal{K}_j^{(k)} := \mathbb{Q}[X]/\Phi_{t_k^j}(X_k^{m_k/t_k^j}), \quad \mathcal{R}_j^{(k)} := \mathbb{Z}[X]/\Phi_{t_k^j}(X_k^{m_k/t_k^j}), \quad 0 \le j \le \alpha_k - 1, $$

$$ \mathrm{Tr}_j^{(k)} := \mathrm{Tr}_{\mathcal{K}_j^{(k)} / \mathcal{K}_{j-1}^{(k)}}, \quad 1 \le j \le \alpha_k - 1, $$

$$ \mathrm{Tr}^{(k)} := \mathrm{Tr}_{\mathcal{K}_{\alpha_k}^{(k)} / \mathcal{K}_0^{(k)}} = \mathrm{Tr}_{\mathcal{K}_1^{(k)} / \mathcal{K}_0^{(k)}} \circ \mathrm{Tr}_{\mathcal{K}_2^{(k)} / \mathcal{K}_1^{(k)}} \circ \cdots \circ \mathrm{Tr}_{\mathcal{K}_{\alpha_k}^{(k)} / \mathcal{K}_{\alpha_k-1}^{(k)}}, $$

so that

$$ \mathrm{Tr}_{\mathcal{K}/\mathcal{K}_0} = \mathrm{Tr}^{(1)} \circ \mathrm{Tr}^{(2)} \circ \cdots \circ \mathrm{Tr}^{(r)}. $$

### 9.2.1 A first strategy

This first approach is somewhat naive; it involves cleaning each $c^{(i)}(X)$ by applying the complete trace operator $\mathrm{Tr}_{\mathcal{K}/\mathcal{K}_0}(\Omega_0^* \cdot)$ homomorphically to each $c^{(i)}$ in order to obtain a new ciphertext

$$ \hat{c}^{(i)} = \mathrm{RLWE}_s \left( \mathrm{Tr} \left( \bar{\Omega}_0^* \cdot \mu^{(i)} \right) \right) $$
as described in the previous section, that now serves as an RLWE-encryption of $\mu_i$. Subsequently, the expression

$$ \sum_{i \in \mathbf{J}_{\beta}} \hat{c}^{(i)}(X) X_1^{i_1 \frac{m_1}{t^{\beta_1}}} X_2^{i_2 \frac{m_2}{t^{\beta_2}}} \cdots X_r^{i_r \frac{m_r}{t^{\beta_r}}} $$

naturally provides a RLWE-encryption of

$$ \sum_{i \in \mathbf{J}_{\beta}} \mu_i X_1^{i_1 \frac{m_1}{t^{\beta_1}}} X_2^{i_2 \frac{m_2}{t^{\beta_2}}} \cdots X_r^{i_r \frac{m_r}{t^{\beta_r}}}. $$

To expedite this process, we can employ a swift evaluation of the trace $\text{Tr}_{\mathcal{K}/\mathcal{K}_0}(\Omega_0^*(X) \cdot)$ using the following method. We decompose the trace as:

$$ \text{Tr}_{\mathcal{K}/\mathcal{K}_0}(\Omega_0^*(X) \cdot) = \text{Tr}^{(1)}(\Omega_0^*(X_1) \cdot) \circ \text{Tr}^{(2)}(\Omega_0^*(X_2) \cdot) \circ \cdots \circ \text{Tr}^{(r)}(\Omega_0^*(X_r) \cdot). $$

Here, each trace $\text{Tr}^{(k)}(\Omega_0^*(X_k) \cdot)$ is responsible for acting solely on the variable $X_k$ and reducing it to its constant term. Additionally, each trace $\text{Tr}^{(k)}(\Omega_0^*(X_k) \cdot)$ can be further decomposed using a Galois tower of fields, as discussed in the preceding section, to accelerate its evaluation.

Despite the potential for rapid evaluation of the trace $\text{Tr} = \text{Tr}_{\mathcal{K}/\mathcal{K}_0}$, this method can still be computationally intensive due to the requirement of calculating

$$ t_1^{\beta_1} t_2^{\beta_2} \cdots t_r^{\beta_r} \frac{N}{M} \sum_{k=1}^{r} \alpha_k (t_k - 1) $$

automorphisms homomorphically. To address this challenge, we will now suggest more efficient techniques for performing this packing operation.

**Algorithm 27** LWEs-to-RLWE : packs several LWEs in an encrypted polynomial

Input: $(\mathbf{a}_i, b_i) = \text{LWE}_s(\mu_i)$ for $i \in \mathbf{J}_{\beta}$

1: **for** $i \in \mathbf{J}_{\beta}$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $\hat{c}^{(i)}(X) \leftarrow \text{LWE-to-RLWE}(\mathbf{a}_i, b_i)$

3: **end for**

4: **Return** $\hat{c}(X) = \sum_{i \in \mathbf{J}_{\beta}} X_1^{i_1 \frac{m_1}{t^{\beta_1}}} X_2^{i_2 \frac{m_2}{t^{\beta_2}}} \cdots X_r^{i_r \frac{m_r}{t^{\beta_r}}} \cdot \hat{c}^{(i)}(X)$

### 9.2.2 A second strategy

We proceed here in two stages. In the first stage, we construct homomorphically a polynomial $c_{\beta}$ whose phase coincides up to an error with coefficient $\mu_i$ at the position $(i_1 \frac{m_1}{t^{\beta_1}}, i_2 \frac{m_2}{t^{\beta_2}}, \dots, i_r \frac{m_r}{t^{\beta_r}})$. Subsequently, in the second stage, we apply the trace

$$ \text{Tr}_{\mathcal{K}_{\alpha_1}^{(1)} / \mathcal{K}_{\beta_1}^{(1)}} \circ \text{Tr}_{\mathcal{K}_{\alpha_2}^{(2)} / \mathcal{K}_{\beta_2}^{(2)}} \circ \cdots \circ \text{Tr}_{\mathcal{K}_{\alpha_r}^{(r)} / \mathcal{K}_{\beta_r}^{(r)}} $$

homomorphically to this polynomial to eliminate all the extraneous coefficients. To perform the first step, we apply the following sequence of trace operators for each $1 \le k \le r$:

$$ \text{Tr}_{\beta_k-1}^{(k)} \circ \text{Tr}_{\beta_k-2}^{(k)} \circ \cdots \circ \text{Tr}_{1}^{(k)} \circ \text{Tr}_{0}^{(k)} (\Omega_0^*(X_k) \cdot), $$

to each $\mu^{(i)}(X)$, thereby removing all monomials in $X_k$ whose exponents are non-zero multiples of $\frac{m_k}{t_k^{\beta_k}} = t_k^{\alpha_k - \beta_k}$. Indeed, the trace operators act as follows:
* $\mathrm{Tr}_0^{(k)}$ systematically removes all monomials in $X_k$ whose exponents are divisible by $t_k^{\alpha_k-1}$, save for the constant term;

* $\mathrm{Tr}_1^{(k)}$ eliminates monomials with exponents divisible by $t_k^{\alpha_k-2}$, but not by $t_k^{\alpha_k-1}$;

* Proceeding similarly, up to...

* $\mathrm{Tr}_{\beta_k-1}^{(k)}$, which filters out all monomials in $X_k$ with exponents divisible by $t_k^{\alpha_k-\beta_k}$, but not by $t_k^{\alpha_k-\beta_k+1}$.

The total number of automorphisms required for this strategy sums to

$$ \sum_{k=1}^{r} \left( \beta_k t_k^{\beta_k} \frac{N_k}{m_k} (t_k - 1) + (\alpha_k - \beta_k)(t_k - 1) \right), $$

which is less than the cost associated with the initial, more naive approach (noting that $\beta_k \le \alpha_k - 1$).

### 9.2.3 The optimal strategy

We now present an additional refinement aimed at reducing the computational cost of the packing procedure. Recall that we start with the unprocessed ciphertext $c_\beta$, which encrypts $\mu$ (as previously described), composed of $(\#J_\beta)$ entries $c^{(i)}$ for $i \in J_\beta$. To illustrate our approach, we begin by describing the simplified scenario $r = 1$, where $M = t^\alpha$.

**Case $M = t^\alpha$:** Our goal is to evaluate the following expression more efficiently:

$$ \begin{aligned} \mu(X) &= \sum_{i=0}^{t^\beta \frac{N}{M}-1} \left( \mathrm{Tr} \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) \right) X^{i \frac{M}{t^\beta}} \\ &= \sum_{i=0}^{t^\beta \frac{N}{M}-1} \mathrm{Tr}_{\mathcal{K}/\mathcal{K}_\beta} \circ \mathrm{Tr}_{\mathcal{K}_\beta/\mathbb{Q}} \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) X^{i \frac{M}{t^\beta}}. \end{aligned} $$

We first utilize the fact that $\mathrm{Tr}_{\mathcal{K}/\mathcal{K}_\beta}$ preserves the monomials with exponents that are multiples of $\frac{M}{t^\beta}$, which allows us to express:

$$ \mu(X) = \mathrm{Tr}_{\mathcal{K}/\mathcal{K}_\beta}(\mu_\beta(X)), \quad \mu_\beta(X) = \sum_{i=0}^{t^\beta \frac{N}{M}-1} \mathrm{Tr}_{\mathcal{K}_\beta/\mathbb{Q}} \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) X^{i \frac{M}{t^\beta}}. $$

For $0 \le i \le t^\beta \frac{N}{M} - 1$, we decompose (uniquely) the index $i$ as follows:

$$ i = i_0 + i_1 t + \dots + i_{\beta-1} t^{\beta-1} = \sum_{k=0}^{\beta-1} i_k t^{\beta k} $$

where $0 \le i_k \le t-1$ for $k = 0, \dots, \beta-2$ and $0 \le i_{\beta-1} \le t-2$. We can then rewrite the previous sum as:

$$ \begin{aligned} \mu_\beta(X) &= \sum_{i_0, \dots, i_{\beta-2}} \sum_{i_{\beta-1}} \left( \mathrm{Tr}_{\beta-1} \circ \dots \circ \mathrm{Tr}_0 \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) \right) X^{i_0 \frac{M}{t^\beta} + i_1 \frac{M}{t^{\beta-1}} + \dots + i_{\beta-1} \frac{M}{t}} \\ &= \sum_{i_0, \dots, i_{\beta-2}} \mathrm{Tr}_{\beta-1} \circ \dots \circ \mathrm{Tr}_1 \left( \sum_{i_{\beta-1}} \mathrm{Tr}_0 \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) X^{i_{\beta-1} \frac{M}{t}} \right) X^{i_0 \dots + i_{\beta-2} \frac{M}{t^2}} \end{aligned} $$
Here, we have utilized the fact that $\mathrm{Tr}_{\beta-1} \circ \cdots \circ \mathrm{Tr}_1$ keeps intact those monomials with exponents that are multiples of $\frac{M}{t}$. Applying the same reasoning repetitively leads us to the final sum:

$$ \sum_{i_0} \mathrm{Tr}_{\beta-1} \left( \cdots \left( \sum_{i_{\beta-2}} \mathrm{Tr}_1 \left( \sum_{i_{\beta-1}} \mathrm{Tr}_0 \left( \bar{\Omega}_0^*(X) \cdot \mu^{(i)}(X) \right) X^{i_{\beta-1} \frac{M}{t}} \right) X^{i_{\beta-2} \frac{M}{t^2}} \right) \cdots \right) X^{i_0 \frac{M}{t^\beta}} $$

Let us denote

$$ \mu_0^{(i)} = \bar{\Omega}_0^*(X)\mu^{(i)}(X), \quad i = 0, \dots, t^\beta \frac{N}{M} - 1. $$

The various steps involved in the computation are as follows:

1. **Step 1:** Compute

$$ \mu_1^{(i)}(X) = \sum_{i_{\beta-1}=0}^{t-2} \mathrm{Tr}_0 \left( \mu_0^{(i+i_{\beta-1}t^{\beta-1})}(X) \right) X^{i_{\beta-1} \frac{M}{t}}, \quad i = 0, \dots, t^{\beta-1} - 1. $$

2. **Step j, for $j = 2, \dots, \beta$: Compute**

$$ \mu_j^{(i)}(X) = \sum_{i_{\beta-j}=0}^{t-1} \mathrm{Tr}_{j-1} \left( \mu_{j-1}^{(i+i_{\beta-j}t^{\beta-j})}(X) \right) X^{i_{\beta-j} \frac{M}{t^j}}, \quad i = 0, \dots, t^{\beta-j} - 1. $$

3. **Final step:** Compute the final result $\mu(X) = \mathrm{Tr}_{\alpha-1} \circ \dots \circ \mathrm{Tr}_{\beta}(\mu_{\beta}(X))$.

We summarize the individual steps in the algorithms below, first for cleartexts and then for ciphertexts. The associated computational cost can be readily assessed in terms of the occurrences of automorphisms (recall that $t-1 = \prod_{i=1}^r \ell_r$ in this context) by reviewing the various steps outlined above:

$$ \frac{N}{M} \left( (t-1)t^{\beta-1} \left( \sum_{i=1}^{r} (\ell_j - 1) \right) + \sum_{j=2}^{\beta-1} t(t-1)t^{\beta-j} \right) + t(t-1). $$

Algorithm 29 requires approximately $\beta \cdot t$-times fewer keyswitching operations than Algorithm 27 and is always strictly cheaper.

**Case $M = t_1^{\alpha_1} t_2^{\alpha_2} \cdots t_r^{\alpha_r}$:** A natural approach is to extend the previous algorithm, designed for the prime-power case, to the composite case by leveraging the tensor product structure of the polynomials in this setting. Specifically, we sequentially apply the method with respect to the variables $X_1$, then $X_2$, $X_3$, ..., up to $X_r$. For each step $k$, we utilize the partial traces $\mathrm{Tr}_j^{(k)}$, with $1 \le k \le r$ and $0 \le j \le \beta_k - 1$, as introduced earlier. This process systematically refines the polynomial, progressively removing unwanted coefficients in each variable.

# Appendix

## Elementary operations in general cyclotomic rings

In this section, we explore the operations necessary for manipulating the polynomials in $\mathcal{K}$.
**Algorithm 28** Packs $t^\beta \frac{N}{M}$ LWE-cleartexts in an polynomial for $r = 1$

1: **Input:** $(\mu^{(i)}(X))$ with $(\mu^{(i)}(X))_0 = \mu_i, i = 0, \dots, t^\beta \frac{N}{M} - 1$

2: Define $\mu_0^{(i)} = \bar{\Omega}_0^*(X)\mu^{(i)}(X)$, $i = 0, \dots, t^\beta \frac{N}{M} - 1$

3: **for** $i = 0$ **to** $t^{\beta-1} - 1$ **do**

4: Initialize: $\mu_1^{(i)}(X) \leftarrow 0$

5: **for** $i_{\beta-1} = 0$ **to** $t - 2$ **do**

6: $\mu_1^{(i)}(X) \leftarrow \mu_1^{(i)}(X) + \text{Tr}_0 (\mu_0^{(i+i_{\beta-1}t^{\beta-1})}(X)) X^{i_{\beta-1} \frac{M}{t}}$

7: **end for**

8: **end for**

9: **for** $j = 2$ **to** $\beta$ **do**

10: **for** $i = 0$ **to** $t^{\beta-j} - 1$ **do**

11: Initialize: $\mu_j^{(i)}(X) \leftarrow 0$

12: **for** $i_{\beta-j} = 0$ **to** $t - 1$ **do**

13: $\mu_j^{(i)}(X) \leftarrow \mu_j^{(i)}(X) + \text{Tr}_{j-1} (\mu_{j-1}^{(i+i_{\beta-j}t^{\beta-j})}(X)) X^{i_{\beta-j} \frac{M}{tj}}$

14: **end for**

15: **end for**

16: **end for**

17: **Output:** $\mu(X) \leftarrow \text{Tr}_{K/\mathcal{K}_\beta}(\mu_\beta^{(0)}(X))$

**Algorithm 29** Packs $t^\beta \frac{N}{M}$ LWE-ciphertexts in an encrypted polynomial for $r = 1$

1: **Input:** $\mathbf{c}^{(i)} = (\mathbf{a}^{(i)}, \mathbf{b}^{(i)}) = \text{LWE}_s(\mu_i)$ for $0 \le i < t^\beta \frac{N}{M}$

2: **for** $i = 0$ **to** $t^{\beta-1} \frac{N}{M} - 1$ **do**

3: $a^{(0,i)} \leftarrow \sum_{j=0}^{N-1} a_j^{(i)} \bar{\Omega}_j^* \mod \mathcal{R}, \quad b^{(0,i)} \leftarrow \bar{\Omega}_0^* b^{(i)} \mod \mathcal{R}$.

4: **end for**

5: **for** $i = 0$ **to** $t^{\beta-1} - 1$ **do**

6: Initialize: $(a^{(1,i)}, b^{(1,i)}) \leftarrow (0, 0)$

7: **for** $i_{\beta-1} = 0$ **to** $t - 2$ **do**

8: $(a^{(1,i)}, b^{(1,i)}) \leftarrow (a^{(1,i)}, b^{(1,i)}) + \text{TR}_0 (a^{(0,i+i_{\beta-1}t^{\beta-1})}, b^{(0,i+i_{\beta-1}t^{\beta-1})}) \Omega_{i_{\beta-1} \frac{M}{t}}$

9: **end for**

10: **end for**

11: **for** $j = 2$ **to** $\beta - 1$ **do**

12: **for** $i = 0$ **to** $t^{\beta-j} - 1$ **do**

13: Initialize: $(a^{(j,i)}, b^{(j,i)}) \leftarrow (0, 0)$

14: **for** $i_{\beta-j} = 0$ **to** $t - 1$ **do**

15: $(a^{(j,i)}, b^{(j,i)}) \leftarrow (a^{(j,i)}, b^{(j,i)}) + \text{TR}_{j-1} (a^{(j-1,i+i_{\beta-j}t^{\beta-j})}, b^{(j-1,i+i_{\beta-j}t^{\beta-j})}) \Omega_{i_{\beta-j} \frac{M}{tj}}$

16: **end for**

17: **end for**

18: **end for**

19: **Output:** $(a, b) \leftarrow \text{TR}_{\alpha-1} \circ \dots \circ \text{TR}_{\beta}(a^{(\beta,0)}, b^{(\beta,0)})$
## Multiplication of polynomials

We now give the expression of the product modulo $\Phi_M$ of two polynomials in the case $r = 1$.

**Lemma 9.1** Consider two polynomials of degrees less than $M - 1 = t^\alpha - 1$ for a prime integer $t$ and a positive integer $\alpha$

$$D(X) = \sum_{k=0}^{M-1} d_k X^k \in \mathbb{K} \quad \text{and} \quad P(X) = \sum_{k=0}^{M-1} a_k X^k \in \mathbb{K}.$$

The product $D \cdot P$ results in a polynomial in $\mathbb{K}$, and its unique representative modulo $\Phi_M$ of degree less than or equal to $N - 1$ can be expressed as follows:

$$(D \cdot P)(X) = \sum_{i=0}^{N-1} \left( \sum_{j=0}^{M-1} d_j (a_{i-j} - a_{N-j+[i]_{m'}}) \right) X^i \quad \mod \Phi_M,$$

where we adopt the convention that $a_{k+M} = a_k$ for all $k \in \mathbb{Z}$ and where $m' = \frac{M}{t}$.

*Proof.* The product $D \cdot P$ modulo $X^M - 1$ can easily be written as

$$D(X)P(X) = \sum_{i=0}^{M-1} \left( \sum_{j=0}^{M-1} d_j a_{i-j} \right) X^i \quad \mod X^M - 1,$$

with the convention that $a_{M+j} = a_j$ for all $j \in \mathbb{Z}$. Now, by applying Proposition 3.9 to $D \cdot P$, we obtain the result stated in this lemma.

## Estimates of the error growth resulting from a polynomial product

We now estimate the number of nonzero coefficients in the product (mod $\Phi_M$) of two polynomials of degree $< N$. An accurate bound on this number controls noise amplification in operations such as bootstrapping, key-switching and packing. In particular, for $t = 2$ the number equals $N$ (not $2N$), explaining the ubiquitous multiplicative factor $N$ in the noise growth of these operations. More precisely, we have the following lemma:

**Lemma 9.2** Let $M = t_1^{\alpha_1} \cdot t_r^{\alpha_r}$ where $t_1, \dots, t_r$ are prime integers and $\alpha_1, \dots, \alpha_r$ positive integers and let $N = \varphi(M)$. Consider the polynomials

$$D(X) = \sum_{i \in \mathbf{J}} d_i X^{\rho(i)}, \quad E(X) = \sum_{i \in \mathbf{J}} e_i X^{\rho(i)}$$

where the coefficients $(d_i)_{i \in \mathbf{J}}$ and $(e_i)_{i \in \mathbf{J}}$ are independent random variables with common standard deviations $\sigma(D)$ and $\sigma(E)$ and denote

$$P(X) = D(X) \cdot E(X) \mod \Phi_M(X) = \sum_{i \in \mathbf{J}} p_i X^{\rho(i)}$$

their product modulo $\Phi_M$ (i.e. in $\mathbb{K}$). For $r = 1$, the variance of the random variable $(p_i)_{0 \le i < N}$ can be expressed as follows:

$$\sigma(p_i)^2 = \left( N + i - [i]_{m'} + \max \left( N - 1 - \frac{M}{t} - i, 0 \right) \right) \sigma(D)^2 \sigma(E)^2, \quad 0 \le i \le N - 1$$

where $m' = \frac{M}{t}$, while for $r > 1$ we have the following bound

$$\max_{i \in \mathbf{J}} \sigma(p_i)^2 = N \Gamma_M \sigma(D)^2 \sigma(E)^2 \quad \text{where} \quad \Gamma_M = \prod_{\ell=1}^{r} \frac{2t_\ell - 3}{t_\ell - 1} \le 2^r.$$
Proof. We start by proving the result in the case $r = 1$: for $0 \le i \le N - 1$, let

$$A_i = \{0 \le j \le N-1, \text{ s. t. } (i-j) \bmod M \le N-1 \text{ and } (N-j + [i]_{\frac{M}{t}}) \le N-1\},$$

$$B_i = \{0 \le j \le N-1, \text{ s. t. } (i-j) \bmod M \ge N \text{ and } (N-j + [i]_{\frac{M}{t}}) \le N-1\},$$

$$C_i = \{0 \le j \le N-1, \text{ s. t. } (i-j) \bmod M \le N-1 \text{ and } (N-j + [i]_{\frac{M}{t}}) \ge N\}.$$

We have from Lemma 9.1 the following expression for the coefficient $p_i$:

$$p_i = \sum_{j \in A_i} d_j (e_{i-j} - e_{N-j+[i]_{m'}}) - \sum_{j \in B_i} d_j e_{N-j+[i]_{m'}} + \sum_{j \in C_i} d_j e_{i-j}.$$

This formulation relies on the facts

$$0 \le N - j + [i]_{m'} \le M - 1$$

and on the conventions $d_i = e_i = 0$ for $N \le i \le M - 1$ and $d_{i+M} = d_i$, $e_{i+M} = e_i$ for all $i \in \mathbb{Z}$.
We also note that

$$[i-j]_M \ge N \implies N - j + [i]_{\frac{M}{t}} \le N - 1.$$

Given the mutual independence of the random variables $d_i$ and $e_i$ for $0 \le i \le N - 1$, we can
derive the expression for the variance of $p_i$:

$$\sigma(p_i)^2 = \sum_{j \in A_i} \sigma(d_j)^2 \left( \sigma(e_{i-j})^2 + \sigma(e_{N-j+[i]_{\frac{M}{t}}})^2 \right) + \sum_{j \in B_i} \sigma(d_j)^2 \sigma(e_{N-j+[i]_{\frac{M}{t}}})^2 + \sum_{j \in C_i} \sigma(d_j)^2 \sigma(e_{i-j})^2.$$

Note that $i - j \bmod M \neq N - j + i \bmod \frac{M}{t}$ for $0 \le j \le N - 1$. We can easily determine the
sets:

$$A_i = \{j \text{ such that } 1 + [i]_{\frac{M}{t}} \le j \le i \text{ or } M - N + i + 1 \le j \le N - 1\},$$

$$B_i = \{j \text{ such that } i + 1 \le j \le \min(N - 1, M - N + i)\},$$

$$C_i = \{j \text{ such that } 0 \le j \le [i]_{\frac{M}{t}}\}.$$

From this, we derive the sizes:

$$|A_i| = i - ([i]_{\frac{M}{t}}) + \max(2N - M - i - 1, 0), |B_i| = \min(N - 1, M - N + i) - i, |C_i| = 1 + ([i]_{\frac{M}{t}}).$$

Now, taking into account $\sigma(d_i) = \sigma(D)$ and $\sigma(e_i) = \sigma(E)$, we obtain:

$$\sigma(p_i)^2 = (2|A_i| + |B_i| + |C_i|) \sigma(D)^2 \sigma(E)^2.$$

Finally noting that $|A_i| + |B_i| + |C_i| = N$, we conclude for $r = 1$. For later use, we notice<fnref n="8" /> that

$$\sigma(p_i)^2 = \sigma(D)^2 \sigma(E)^2 \times \begin{cases} \frac{2t-3}{t-1}N - [i]_{m'} - 1, & \text{if } i \le (t-2)m' - 1, \\ \frac{2t-3}{t-1}N, & \text{if } i \ge (t-2)m' \end{cases},$$

<footnote n="8">⁸These estimates align precisely with Theorem 1 in [20].</footnote>
so that

$$ \max_{0 \le i < N} \sigma(p_i)^2 = N \frac{2t - 3}{t - 1}. $$

The general case $r > 1$ is obtained by iterating over the variables $X_1, \dots, X_r$. At each step $1 \le l \le r$ the estimate of $\sigma^2$ is multiplied by the factor

$$ N_l \cdot \frac{2t_l - 3}{t_l - 1} $$

and we conclude from $N = \prod_{l=1}^{r} N_l$.

**Lemma 9.3** Let $\mathbf{i} \in \mathbf{J}$, $0 \le \nu \le M-1$ and set $\mathbf{j} = \rho^{-1}([-\nu]_M)$. Then

$$ \langle X^{-\nu}, \Omega_{\mathbf{i}}^{*}(X) \rangle = \sum_{\mathbf{u} \in \{0,1\}^r} (-1)^{|\mathbf{u}|} \in \{-1, 0, 1\} \quad (40) $$

where the sum runs over all $\mathbf{u} \in \{0,1\}^r$ satisfying $\mathbf{j} = (\mathbf{1} - \mathbf{u})\mathbf{i} + \mathbf{u}(\mathbf{N} + [\mathbf{i}]_{\mathbf{m}'}).$

*Proof.* For all $\mathbf{i} = (i_1, i_2, \dots, i_r) \in \mathbf{J}$ and $\mathbf{j} = \rho^{-1}([-\nu]_M) \in \mathbf{I}$, the scalar product satisfies:

$$ \langle \Omega_{\mathbf{j}}, \Omega_{\mathbf{i}}^{*} \rangle = \sum_{\substack{\mathbf{u} \in \{0,1\}^r, \\ \mathbf{j} = (\mathbf{1} - \mathbf{u})\mathbf{i} + \mathbf{u}(\mathbf{N} + [\mathbf{i}]_{\mathbf{m}'})}} (-1)^{|\mathbf{u}|} $$

where $\mathbf{N} = (N_1, \dots, N_r)$, $\mathbf{1} = (1, \dots, 1) \in \mathbb{N}^r$, $[\mathbf{i}]_{\mathbf{m}'} = ([i_1]_{m'_1}, \dots, [i_r]_{m'_r})$ and the product of vectors is meant to be component-wise. The constraint $\mathbf{j} = (\mathbf{1} - \mathbf{u})\mathbf{i} + \mathbf{u}(\mathbf{N} + [\mathbf{i}]_{\mathbf{m}'})$ holding for at most one $\mathbf{u} \in \{0,1\}^r$, the sum is over either a single sign $(-1)^{|\mathbf{u}|}$ or is empty.

**Lemma 9.4** Consider polynomials $P \in \mathcal{T}^\vee$ and $Q \in \mathcal{R}$, expressed in the bases $(\Omega_{\mathbf{i}}^*)_{\mathbf{i} \in \mathbf{J}}$ and $(\Omega_{\mathbf{i}})_{\mathbf{i} \in \mathbf{J}}$ respectively, with random coefficients. Then, we have

$$ \forall \mathbf{k} \in \mathbf{J}, \quad \sigma^2((P^*Q)_{\mathbf{k}}) \le \left( \prod_{\ell=1}^r (N_{\mathbf{k},\ell} + (N_\ell - N_{\mathbf{k},\ell})(t_\ell - 1)) \right) \sigma^2(P^*)\sigma^2(Q). $$

where $N_{\mathbf{k},\ell} = \max(k_\ell + 1, (t_\ell - 2)m'_\ell)$, with equality if all the coefficients of $P^*$ (respectively $Q$) have a common variance. In this case, we have in particular

$$ \sigma^2(P^*Q) = \Gamma_M N \sigma^2(P^*)\sigma^2(Q). \quad (41) $$

A similar result is valid for the product $P \in \mathcal{T}$ and $Q^* \in \mathcal{R}^\vee$.

*Proof.* Based on duality relations, for any $\mathbf{k} \in \mathbf{J}$, we obtain

$$ (P^*Q)_{\mathbf{k}} = \langle \Omega_{\mathbf{k}}, P^*Q \rangle = \sum_{\mathbf{i} \in \mathbf{J}} \sum_{\mathbf{j} \in \mathbf{J}} p_{\mathbf{i}}^* q_{\mathbf{j}} \langle \Omega_{\mathbf{k}-\mathbf{j}}, \Omega_{\mathbf{i}}^* \rangle \quad (42) $$

where, according to previous lemma, $\langle \Omega_{\mathbf{k}-\mathbf{j}}, \Omega_{\mathbf{i}}^* \rangle \in \{-1, 0, 1\}$. Since the random variables $p_{\mathbf{i}}^*$ and $q_{\mathbf{i}}$ are pairwise independent and centered, we have

$$ \sigma^2((P^*Q)_{\mathbf{k}}) \le \sigma^2(P^*)\sigma^2(Q) \sum_{\mathbf{i} \in \mathbf{J}} \sum_{\mathbf{j} \in \mathbf{J}} \langle \Omega_{\mathbf{k}-\mathbf{j}}, \Omega_{\mathbf{i}}^* \rangle^2 = \lambda_{\mathbf{k}} \sigma^2(P^*)\sigma^2(Q) \quad (43) $$

where

$$ \begin{aligned} \lambda_{\mathbf{k}} &= \sum_{\mathbf{i} \in \mathbf{J}} \sum_{\mathbf{j} \in \mathbf{J}} \prod_{\ell=1}^{r} \langle \Omega_{k_{\ell}-j_{\ell}}, \Omega_{i_{\ell}}^{*} \rangle^2 = \prod_{\ell=1}^{r} \sum_{i_{\ell}, j_{\ell}} \langle \Omega_{k_{\ell}-j_{\ell}}, \Omega_{i_{\ell}}^{*} \rangle^2 \\ &= \prod_{\ell=1}^{r} \left( \sum_{j_{\ell}, [k_{\ell}-j_{\ell}]_{m_{\ell}} < N_{\ell}} 1 + \sum_{j_{\ell}, [k_{\ell}-j_{\ell}]_{m_{\ell}} \ge N_{\ell}} (t_{\ell}-1) \right) = \prod_{\ell=1}^{r} \left( N_{\mathbf{k},\ell} + (N_{\ell} - N_{\mathbf{k},\ell})(t_{\ell}-1) \right) \end{aligned} $$

with $N_{\mathbf{k},\ell} = \#\{0 \le j_{\ell} \le N_{\ell}-1 \text{ s.t. } [k_{\ell}-j_{\ell}]_{m_{\ell}}\}$.
**Corollary 9.5** Let $P^* = \sum_{i \in \mathcal{J}} p_i^* \Omega_i^* \in \mathcal{K}^\vee$ and $Q = \sum_{i \in \tilde{\mathcal{J}}} q_i \Omega_i \in \mathcal{K}$ where $\tilde{\mathcal{J}} \subset \mathcal{J}$. Assume the coefficients of $P^*$ and $Q$ are all independent centered random variables with variances $\text{Var}(P^*)$ and $\text{Var}(Q)$ respectively. Then the following formula holds:

$$ \mathrm{Var} \left( \langle X^{-\nu}, P^*(X)Q(X) \rangle \right) = \gamma_M (\#\tilde{\mathcal{J}}) \mathrm{Var}(P^*) \mathrm{Var}(Q). \quad (44) $$

*Proof.* Let $Y = \langle X^{-\nu}, P^*(X)Q(X) \rangle$. Writing

$$ Y = \sum_{(i,j) \in \mathcal{J} \times \tilde{\mathcal{J}}} p_i^* q_j \underbrace{\mathrm{Tr}(X^{\nu+\rho(j)} \Omega_i^*)}_{\chi_{i,j+\rho^{-1}(\nu)}} $$

Conditioning on $\rho^{-1}(\nu) = \mathbf{k}$ and using independence between the coefficients $p_i^*$ of $P^*$ and the sums $\sum_{j \in \mathcal{J}} q_j \chi_{i,j,\mathbf{k}}$, we obtain

$$ \mathrm{Var}(Y|\rho^{-1}(\nu) = \mathbf{k}) = \mathrm{Var} \left( \sum_{i \in \mathcal{J}} p_i^* \sum_{j \in \tilde{\mathcal{J}}} q_j \chi_{i,j+\mathbf{k}} \right) = \left( \sum_{(i,j) \in \mathcal{J} \times \tilde{\mathcal{J}}} \chi_{i,j+\mathbf{k}}^2 \right) \sigma^2(P^*) \sigma^2(Q) $$

Finally, averaging over $\mathbf{k}$ via $\mathrm{Var}(Y) = \sum_{\mathbf{k} \in \mathcal{I}} \mathbb{P}(\rho^{-1}(\nu) = \mathbf{k}) \mathrm{Var}(Y|\rho^{-1}(\nu) = \mathbf{k})$ and noting $\mathbb{P}(\rho^{-1}(\nu) = \mathbf{k}) = 1/M$

$$ \mathrm{Var}(Y) = \frac{1}{M} \left( \sum_{\mathbf{k} \in \mathcal{I}} \sum_{(i,j) \in \mathcal{J} \times \tilde{\mathcal{J}}} \chi_{i,j+\mathbf{k}}^2 \right) \sigma^2(P^*) \sigma^2(Q) = \frac{(\#\tilde{\mathcal{J}})}{M} \left( \sum_{\mathbf{k} \in \mathcal{I}} \sum_{i \in \mathcal{J}} \chi_{i,\mathbf{k}}^2 \right) \sigma^2(P^*) \sigma^2(Q) $$

The conclusion then follows by applying the same tensorization argument as in Lemma 9.4. As an immediate consequence, we have the following:

**Corollary 9.6** Let $e^* = \sum_{i \in \mathcal{J}} e_i^* \Omega_i^* \in \mathcal{K}^\vee$ and set $\mathbf{j} = \rho^{-1}([-\nu]_M)$. Then

$$ \langle X^{-\nu}, e^*(X) \rangle = \sum_{\mathbf{u},\mathbf{i}} (-1)^{|\mathbf{u}|} e_i^* \quad (45) $$

where the sum runs over all $\mathbf{u} \in \{0,1\}^r$ and all $\mathbf{i} \in \mathcal{J}$ satisfying $\mathbf{j} = (\mathbf{1} - \mathbf{u})\mathbf{i} + \mathbf{u}(\mathbf{N} + [\mathbf{i}]_{\mathbf{m}'}).$ Furthermore, if the coefficients of $e^*$ are all centered random variables with the same standard deviation $\sigma(e^*)$ and $\nu$ is uniformly distributed in $\{0, \dots, M-1\}$, then one has

$$ \mathrm{Var} \left( \langle X^{-\nu}, e^*(X) \rangle \right) = \gamma_M \sigma^2(e^*) \quad \text{with} \quad \gamma_M = 2^r \prod_{\ell=1}^r \left(1 - \frac{1}{t_\ell}\right). \quad (46) $$

## References

[1] M. R. Albrecht, R. Player, and S. Scott, *On the concrete hardness of Learning with Errors*, Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169–203, October 2015. ISSN (Online): 1862-2984, ISSN (Print): 1862-2976.

[2] J.-C. Bajard, T. Gouget, B. Laigle, and M. Naya-Plasencia, *RNS Variant of FV-like Schemes*, in Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), 2017, pp. 1596–1600. IEEE.

[3] O. Bernard, M. Joye, N.P. Smart, M. Walter, *Drifting Towards Better Error Probabilities in Fully Homomorphic Encryption Schemes*. In: Fehr, S., Fouque, PA. (eds) Advances in Cryptology - EUROCRYPT 2025. EUROCRYPT 2025. Lecture Notes in Computer Science, vol 15608. Springer, Cham.
[4] J-F. Biasse and L. Ruiz, *FHEW with efficient multibit bootstrapping*. In Progress in Cryptology - LATINCRYPT 2015 (Lecture Notes in Computer Science, Vol. 9230), K. Lauter and F. Rodríguez-Henríquez (Eds.). Springer, 119-135. https://doi.org/10.1007/978-3-319-22174-8_7

[5] C. Bootland, W. Castryck, and F. Vercauteren, *On the Security of the Multivariate Ring Learning with Errors Problem*, in Proceedings of the 2020 ACM Conference on Computer and Communications Security (CCS), 2020, pp. 1237-1253. ACM.

[6] J.-P. Bossuat, A. Costache, C. Mouchet, L. Nürnberger, and J.R. Troncoso-Pastoriza, *Practical q-IND-CPA-D-Secure Approximate Homomorphic Encryption*, Cryptology ePrint Archive, Paper 2024/853, 2024.

[7] J. H. Cheon, A. Kim, and Y. Song, *A Simple, Efficient Bootstrapping Method for Fully Homomorphic Encryption over the Integers*, Cryptology ePrint Archive, 2021. https://eprint.iacr.org/2021/180

[8] P. Chartier, M. Koskas, M. Lemou, and F. Méhats, *Homomorphic Sign Evaluation with a RNS Representation of Integers*, Advances in Cryptology-ASIACRYPT 2024, Chung, K.M., Sasaki, Y. (eds.), Lecture Notes in Computer Science, vol. 15484, Springer, Singapore, 2025. https://doi.org/10.1007/978-981-96-0875-1_9.

[9] P. Chartier, M. Koskas, M. Lemou, and F. Méhats, *Fully Homomorphic Encryption on Large Integers*, Cryptology ePrint Archive, 2024.

[10] P. Chartier, M. Koskas, M. Lemou, and F. Méhats, *Method for Homomorphically Determining the Sign of a Message by Dilation, Associated Methods and Devices*, Patent no. WO2023242429 - 12/21/2023. Number and date of priority: FR2205957 - 06/17/2022.

[11] P. Chartier, M. Koskas, M. Lemou, and F. Méhats, *Homomorphic Encryption Method and Associated Devices and System*, Patent no. WO2022129979 - 06/23/2022. Number and date of priority: PCT/IB2020001147 - 12/18/2020.

[12] H. Chen, R. Gilad-Bachrach, K. Han, Z. Huang, A. Jalali, K. Laine, and K. Lauter, *Logistic Regression over Encrypted Data from Fully Homomorphic Encryption*, Cryptology ePrint Archive, Report 2018/462, 2018.

[13] H. Chen, W. Dai, M. Kim, and Y. Song, *Efficient Homomorphic Conversion Between (Ring) LWE Ciphertexts*, In: K. Sako and N. O. Tippenhauer (eds), Applied Cryptography and Network Security, ACNS 2021, Lecture Notes in Computer Science, vol. 12726, Springer, Cham.

[14] H. Chen, K. Lauter, and K. E. Stange, *Security Considerations for Galois Non-Dual RLWE Families*, Cryptology ePrint Archive, 2021. https://eprint.iacr.org/2021/1620

[15] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, *Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds*, Advances in Cryptology – ASIACRYPT 2016, pp. 3–33. Berlin, Heidelberg, Springer, 2016.

[16] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, *TFHE: Fast Fully Homomorphic Encryption over the Torus*, Journal of Cryptology, 33(1), pp. 34–91, 2020.

[17] A. Costache, B. R. Curtis, E. Hales, S. Murphy, T. Ogilvie, and R. Player, *On the Precision Loss in Approximate Homomorphic Encryption*, Cryptology ePrint Archive, Report 2022/162, 2022.
[18] A. Costache and N. P. Smart, *Ring-LWE and its Applications to Lattice-Based Cryptography*, in Proceedings of the 2016 IEEE International Conference on Advanced Information Networking and Applications (AINA), 2016, pp. 163–170.

[19] E. Crockett and C. Peikert, *Challenges for Ring-LWE*, in Proceedings of the 2017 IEEE International Conference on the Theory and Application of Cryptography Technology (ACT), 2017, pp. 125–130. IEEE.

[20] De Micheli, G., Kim, D., Micciancio, D., Suhl, A. (2024). Faster Amortized FHEW Bootstrapping Using Ring Automorphisms. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14604. Springer, Cham. https://doi.org/10.1007/978-3-031-57728-4_11

[21] L. Ducas and D. Micciancio, *FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second*, Advances in Cryptology – EUROCRYPT 2015, pp. 617–640. Berlin, Heidelberg, Springer, 2015.

[22] C. Gentry, *Fully Homomorphic Encryption Using Ideal Lattices*, 41st Annual ACM Symposium on Theory of Computing, pp. 169–178. ACM Press, 2009.

[23] R. Geelen and F. Vercauteren, *Fully Homomorphic Encryption for Cyclotomic Prime Moduli*, Cryptology ePrint Archive, Paper 2024/1587, 2024. https://eprint.iacr.org/2024/1587

[24] M. Joye, *SoK: Fully homomorphic encryption over the [discretized] torus PDF*, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(4):661-692, 2022

[25] M. Joye, M. Walter, *Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials*, WAHC'22: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography Pages 1 - 11 https://doi.org/10.1145/3560827.3563376

[26] A. Kim, J. H. Cheon, and Y. Song, *A Simple, Efficient Bootstrapping Method for Fully Homomorphic Encryption over the Integers*, in Proceedings of the 2020 ACM Conference on Computer and Communications Security (CCS), 2020, pp. 123–145. ACM.

[27] E. Lee, J.-W. Lee, J.-S. No, and Y.-S. Kim, *Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison*, IEEE Transactions on Dependable and Secure Computing, 2021.

[28] B. Li, D. Micciancio, *On the security of homomorphic encryption on approximate numbers*. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 648-677. Springer, Cham (Oct 2021).

[29] V. Lyubashevsky, C. Peikert, and O. Regev, *A Toolkit for Ring-LWE Cryptography*, Cryptology ePrint Archive, Paper 2013/293, 2013. https://eprint.iacr.org/2013/293

[30] V. Lyubashevsky, C. Peikert, and O. Regev, *On Ideal Lattices and Learning with Errors over Rings*, In: Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science, vol 6110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13190-5_1

[31] Y. Lee, D. Micciancio, A. Kim, R. Choi, M. Deryabin, J. Eom, and D. Yoo, *Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption*, Advances in Cryptology – EUROCRYPT 2023.
[32] D. Micciancio and Y. Polyakov, *Bootstrapping in FHEW-like Cryptosystems*, Association for Computing Machinery, New York, NY, USA, pp. 17–28, 2021.

[33] D. Micciancio and J. Sorrell, *Ring Packing and Amortized FHEW Bootstrapping*, Cryptology ePrint Archive, Paper 2018/532, 2018.

[34] C. Peikert, *A Decade of Lattice Cryptography*, Foundations and Trends in Theoretical Computer Science: Vol. 10: No. 4, pp 283-424. http://dx.doi.org/10.1561/0400000074

[35] O. Regev, “Learning with Errors,” in *Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)*, pp. 84–93, 2005, ACM. DOI: 10.1145/1060590.1060608.

[36] O. Regev, “On LWE and RLWE,” in *Proceedings of the 2010 5th Theory of Cryptography Conference (TCC)*, vol. 5978, pp. 1–20, 2009.

[37] O. Regev, *On Lattices, Learning with Errors, Random Linear Codes, and Cryptography*, Journal of the ACM (JACM), 56(6), pp. 1–40, 2009.

[38] M. Wang and F. Zhang, *On the Construction of Lattice-Based Fully Homomorphic Encryption Scheme with Prime Power Cyclotomic Polynomials*, International Journal of Information Security, 17(5), pp. 547–560, 2018. https://doi.org/10.1007/s10207-018-0437-1