Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys

Fully homomorphic encryption (FHE) schemes allow to perform arbitrary computation on ciphertexts without resorting to decryption. After over a decade, FHE schemes have been well developed, and have been applied to various privacy-preserving tasks, such as private database query [1], private information retrieval [2, 3], private decision tree evaluation [4], etc.

In FHE schemes, ciphertexts must be bootstrapped periodically in order to run on them arbitrary circuits of arbitrary depth. Originally the term referred to refreshing a ciphertext that has a large error so that after the refreshment, the error decreases to a small bound [5]. Later on it was extended to “functional bootstrapping”, which refers to evaluating an arbitrary function that is represented by a look-up table. Bootstrapping is the most important part of FHE schemes.

All bootstrapping schemes are based on Gentry’s idea of running the decryption circuit homomorphically in a new FHE environment. [5]. Take as an example the most popular FHE scheme BFV, whose ciphertexts are of either LWE or its ring variant RLWE format. The decryption of an LWE ciphertext consists of two steps: the first step is to compute the phase of the ciphertext homomorphically, where the phase is $\Delta m+e\in{\mathbb{Z}}_{q}$, with $m\in{\mathbb{Z}}_{t}$ being the plaintext, $e$ being the error, and $|e|<\Delta/2$ where $\Delta=\lfloor q/t\rfloor$. The second step is to remove $e$ from the plaintext in the encrypted phase. The first step is generally easy, while the second step is difficult.

The trick lies in how to represent the additive group ${\mathbb{Z}}_{q}$ in the plaintext space, so that when the group acts on a vector or polynomial (called test vector or polynomial) that encodes the look-up table of the function to be evaluated, the group element corresponding to phase $\Delta m+e$ results in a vector or polynomial with $f(m)$ as its first entry, which can then be extracted homomorphically to get a ciphertext encrypting $f(m)$.

In 2014, Alperin-Sheriff and Peikert [6] proposed a bootstrapping scheme which we call “AP14”. They use permutation matrices to represent group ${\mathbb{Z}}_{q}$, where every $u\in[0,q)$ is represented by a $q\times q$ matrix

so that the addition of integers agrees with the multiplication of matrices. By encrypting $\boldsymbol{P}_{u}$ in a GSW-ciphertext [7], the homomorphic phase computation is realized by successive GSW ciphertext multiplications, and the error is small in the resulting ciphertext that encrypts the phase of the input ciphertext, due to the fact that in $\boldsymbol{P}_{u}$, every row and column respectively contain one and only one nonzero entry, and the entry is 1.

For any function $f$ defined on ${\mathbb{Z}}_{t}$, if extending $f$ to a function $f^{\prime}$ on ${\mathbb{Z}}_{q}$ such that $f^{\prime}(\Delta m+e)=f(m)$ for all $m\in{\mathbb{Z}}_{t}$ and $|e|<\Delta/2$, then for test vector ${\bf test}_{f}=[f^{\prime}(0)\ \ f^{\prime}(1)\ \ \ldots f^{\prime}(q-1)]$, it is easy to verify that

So $f(m)=f^{\prime}(\Delta m+e)$ is the first entry of the resulting plaintext vector. (I.2) is called the test-coefficient look-up property of the AP14 scheme.

In 2015, Ducas and Micciancio [8] proposed another bootstrapping scheme called “FHEW”. In this scheme, first $q$ is switched to $2N$ where $N$ is a power of 2, then every $u\in[0,2N)$ is represented by a monic monomial $x^{u}$, so that the addition of integers agrees with the multiplication of monic monomials. By encrypting every $x^{u}$ in an RGSW-ciphertext where the polynomial ring is ${\mathbb{Z}}[x]/(x^{N}+1)$, the homomorphic phase computation is realized by successive RGSW ciphertext multiplications, and the error is small in the resulting ciphertext that encrypts the phase of the input ciphertext.

For any function $f$ defined on ${\mathbb{Z}}_{t}$, if $f$ can be extended to a nega-cyclic function $f^{\prime}$ on ${\mathbb{Z}}_{2N}$, such that $f^{\prime}(x+N)=-f^{\prime}(x)$ for all $x\in{\mathbb{Z}}_{2N}$, and $f^{\prime}(\Delta m+e)=f(m)$ for all $m\in{\mathbb{Z}}_{t}$ and $|e|<\Delta/2$, where $\Delta=\lfloor 2N/t\rfloor$, then for test polynomial ${\rm test}_{f}=\sum_{i=0,\ldots,N-1}f^{\prime}(i)x^{-i}$, it is easy to verify that

So $f(m)=f^{\prime}(\Delta m+e)$ is the first entry, a.k.a. the constant term, of the resulting plaintext polynomial. (I.3) is called the test-coefficient look-up property of the FHEW scheme.

Since FHEW scheme adopts RGSW ciphertext format in homomorphic phase computation, FFT can be used to accelerate the computing. As a result, bootstrapping a ciphertext encrypting a single-bit plaintext by FHEW scheme costs less than 1 second. Later on, another scheme called TFHE was proposed by Chillotti et al. in 2016 [9] to optimize homomorphic phase computation in FHEW, which improves the run-time cost to less than 0.1 second. In 2021, both schemes were extended to make functional bootstrapping for arbitrary functions in 2021 [10, 11].

The last few years have witnessed fast developments of bootstrapping algorithms. To name a few, in [12], a scheme was proposed to evaluate several functions on the same ciphertext simultaneously by one bootstrapping. In [10, 13], to bootstrap ciphertexts encrypting long plaintext, a strategy of block-wise bootstrapping from the tail up was proposed; the strategy can be used for functional bootstrapping where the function is either the identity function $f(x)=x$, or the sign function. In [14, 15], FHEW/TFHE was extended to bootstrap a ciphertext encrypting several plaintexts in SIMD mode.

We notice that for large-plaintext bootstrapping, block-wise bootstrapping works only for some special functions. For a general function, the look-up table representation of the function demands big polynomial degree in RLWE/RGSW ciphertexts. The bigger the polynomial degree, the slower the computation, and the bigger the memory cost due to bootstrapping keys and key-switching keys.

A natural idea is to resort to a polynomial vector instead of only a polynomial to encode the look-up table of a general function $f$. For example, let $N$ be the maximal value of ring dimension for efficient computing of RLWE/RGSW ciphertext multiplication. For an ${\rm LWE}_{n,q}$ ciphertext whose plaintext modulus $t$ is big, the ciphertext modulus $q$ must be large, say $q>2N$. Let

After modulus switch from $q$ to $q^{\prime}$, and extending $f$ to a function defined on ${\mathbb{Z}}_{q^{\prime}}$ such that $f^{\prime}(\Delta m+e)=f(m)$ for all $m\in{\mathbb{Z}}_{t}$ and $|e|<\Delta/2$, where $\Delta=\lfloor q^{\prime}/t\rfloor$, then $f$ can be encoded to the following $r$-dimensional polynomial vector:

Now that ${\rm test}_{f}$ in (I.3) is replaced by test vector (I.5), the representation space of ${\mathbb{Z}}_{q^{\prime}}$ must be replaced by a group of matrices, where in each matrix, every row and column respectively contains one and only one nonzero entry, and the entry is a monic monomial. Such matrices are called monic monomial permutation matrices in this paper. A subgroup $G$ of the monic monomial permutation matrices is to be constructed, so that $G$ is isomorphic to ${\mathbb{Z}}_{q^{\prime}}$, and the action of $G$ on (I.5) by matrix-vector multiplication has the property that for any $\Delta m+e\in{\mathbb{Z}}_{q^{\prime}}$, its counterpart $g_{\Delta m+e}\in G$ when acting on (I.5), changes the vector into one whose first entry has its constant term as $f^{\prime}(\Delta m+e)=f(m)$. The last property is the test-coefficient look-up property, and is the counterpart of (I.2) and (I.3).

The above analysis outlines the main idea of our work. This paper proposes to use monic monomial permutation matrices to represent the additive group ${\mathbb{Z}}_{q^{\prime}}$, finds among all its cyclic subgroups those that has the test-coefficient look-up property, and designs a new scheme of FHEW/TFHE style, called BootMMPM, for general functional bootstrapping of LWE ciphertexts encrypting large plaintext.

The new scheme BootMMPM has the feature that the size of bootstrapping keys and the size of key-switching keys are both irrelevant to $r$. This is significant for saving memory cost. Indeed, in recent years there have been several papers dedicated to reducing the size of bootstrapping keys. Yongwoo Lee et al. [16] proposed a modification of FHEW scheme by making phase accumulation with ring automorphisms, which requires much fewer bootstrapping keys on the server. In [17, 18], bootstrapping keys are packed into small number of transfer keys by the client, and then reconstructed by the server upon receival. It reduced the key size on the client’s side. Such method can be applied to TFHE scheme and the new scheme BootMMPM to further reduce the key size both on the client’s side and on the server’s side.

Compared with the TFHE scheme, the new scheme BootMMPM also has slight improvement in run time. The following table shows that for $r={\rm poly}(n)$, the time improvement of BootMMPM is a constant factor, while the key-size improvement is a polynomial factor.

This paper reports the following work:

1. 1.

   Classification of all monic monomial permutation matrices under similar transformations. It turns out that any $r\times r$ monic monomial permutation matrix is similar to a block diagonal matrix, where each block in the diagonal is of the form

   $$\begin{bmatrix}&&&&x^{u_{0}}\\ x^{u_{1}}&&&&\\ &x^{u_{2}}&&&\\ &&\ddots&&\\ &&&x^{u_{k-1}}&\end{bmatrix},$$

   (I.6)

   where $k\geq 1$, and if $k=1$, then (I.6) is just $x^{u_{0}}$.

2. 2.

   Computation of the order of any monic monomial permutation matrix. Only cyclic subgroups of order $2Nr$ in the group ${\rm MMPM}_{r}$ of $r\times r$ monic monomial permutation matrices are useful in bootstrapping.

3. 3.

   Classification of cyclic subgroups of ${\rm MMPM}_{r}$ by their number of orbits when acting on the following set of monic monomial indicator vectors:

   $${\rm MMIV}_{r}:=\{x^{i}\mathbf{e}_{j}\,\big{|}\,i=0,\ldots,2N-1,\ j=1,\ldots,r\},$$

   (I.7)

   where $\mathbf{e}_{j}$ is the $r$-dimensional vector whose $j$-entry is $1$ while all other entries are $0$. Only cyclic subgroups of order $2Nr$ and 1 orbit have test-coefficient look-up property.

4. 4.

   construction of test polynomial vector for any cyclic subgroup of order $2Nr$ and 1 orbit.

5. 5.

   A new algorithm BootMMPM for functional bootstrapping based on the cyclic subgroup of order $2Nr$ and 1 orbit that is generated by $\begin{bmatrix}&x\\ \boldsymbol{I}_{(r-1)\times(r-1)}\end{bmatrix}$.

6. 6.

   Implementation of BootMMPM on PALISADE library[19], and experiments of bootstrapping with the identity function $f(x)=x$ on ciphertexts where the plaintext size ranges from 5 bits to 15 bits.

The content is arranged as follows. In Section 2, some terminology, notations, and basics of FHEW/TFHE functional bootstrapping are introduced. In Section 3, theoretical investigation of the monic monomial permutation matrix group is done. In Section 4, the new algorithm BootMMPM is proposed and analyzed. In Section 5, experimental results on BootMMPM are reported.

We first present some notations and terminology:

(1) For any integer $n>0$, denote by $[n]$ the set $\{0,1,\cdots,n-1\}$.

(2) Given a polynomial $a=a_{0}+a_{1}x+\cdots+a_{N-1}x^{N-1}$, denote by $\overrightarrow{a}=(a_{0},a_{1},\cdots,a_{N-1})$ its coefficient vector.

(3) Given a matrix $\boldsymbol{A}$, denote by $\boldsymbol{A}(i,j)$ its $(i,j)$-th entry.

(4) If $g$ is an element of group $G$, denote by $\left\langle g\right\rangle$ the cyclic subgroup generated by $g$.

(5) That a random variable $x\in\mathbb{Z}$ has zero-centered subgaussian distribution with variance proxy ${\rm Var}(x)=\sigma\ll Q$, refers to the property that there exists a constant $C>0$, such that for all $u>0$, ${\rm Prob}(|x|>u)\leq Ce^{-\sigma u^{2}}$. In particular, if $x$ is Gaussian with variance $\sigma$, then it is subgaussian with variance proxy $\sigma$.

The heuristic bound of subgaussian random variable $x$ is $H\sqrt{{\rm Var}(x)}$, where constant $H=O(1)$ is determined by the failure probability of the bound.

(6) Let $n,N$ be both powers of 2, where $n<N$. Let $q\leq q^{\prime}<Q$ be three positive integers, where $q^{\prime}$ is even. For any $M\in\{n,N\}$ and $p\in\{q,q^{\prime},Q\}$, set

(7) Let $t$ be an even positive integer. A function $f:{\mathbb{Z}}_{t}\longrightarrow\mathbb{Z}_{t^{\prime}}$ is said to be nega-cyclic, if for any $k\in[t/2]$, $f(k+t/2\ {\rm mod}\ t)=-f(k)\mod t^{\prime}$.

Let $2N>t$, and let $f^{\prime}:{\mathbb{Z}}_{2N}\longrightarrow\mathbb{Z}_{t^{\prime}}$ be a nega-cyclic function such that for all $m\in{\mathbb{Z}}_{t}$, all $e\in{\mathbb{Z}}_{2N}$ satisfying $2|e|<\lfloor 2N/t\rfloor$,

Then $f^{\prime}$ is called a nega-cyclic extension of $f$ from ${\mathbb{Z}}_{t}$ to ${\mathbb{Z}}_{2N}$.

(8) An ${\rm LWE}_{n,q}$ ciphertext of BFV format, with modulus $q$, dimension $n$, and secret $\boldsymbol{s}\in{\mathbb{Z}}_{q}^{n}$, is of the form $(\boldsymbol{a},b)$, where $\boldsymbol{a}\in{\mathbb{Z}}_{q}^{n}$, $b\in{\mathbb{Z}}_{q}$, and the phase

such that $m\in{\mathbb{Z}}_{t}$ is the plaintext, and $e\in{\mathbb{Z}}_{q}$ is the error. The ciphertext is decryptable if and only if $2|e|<\lfloor q/t\rfloor$.

Given a message $m\in{\mathbb{Z}}_{t}$, the trivial encryption of $m$ in ${\rm LWE}_{n,q}$ is the ciphertext $(0^{n},m\lfloor q/t\rfloor){\rm mod}\ q$. It is independent of secret $\boldsymbol{s}$.

(9) Given an ${\rm LWE}_{n,q}$ ciphertext $(\boldsymbol{a},b)$, the modulus switch from $q$ to $q^{\prime}$ outputs an ${\rm LWE}_{n,q^{\prime}}$ ciphertext $(\boldsymbol{a}^{\prime},b^{\prime})$ that encrypts the same plaintext as the input ciphertext:

(10) Let $B>1$ be an integer. The $B$-digit decomposition (or gadget decomposition) of an integer $x\in[0,q)$ generates an integer sequence of length $l_{B}:=\lceil\log_{B}q\rceil$: $x_{0},x_{1},\ldots,x_{l_{B}}$, where each $x_{i}\in[B]$, and $x=\sum_{i\in[l_{B}]}x_{i}B^{i}$.

The $B$-digit decomposition operation on ${\mathbb{Z}}_{q}$ is denoted by $\boldsymbol{g}_{B}^{-1}$. Integer $B$ is called the digit decomposition base.

(11) Given an ${\rm LWE}_{n,q}$ ciphertext $(\boldsymbol{a},b)$ with secret $\boldsymbol{s}\in{\mathbb{Z}}_{q}^{n}$, the key switch from $\boldsymbol{s}$ to $\boldsymbol{z}\in{\mathbb{Z}}_{q}^{N}$ outputs an ${\rm LWE}_{N,q}$ ciphertext $(\boldsymbol{a}_{z},b_{z})$ encrypting the same plaintext as the input ciphertext but under secret $\boldsymbol{z}$.

Key switch requires not only all the components of $\boldsymbol{s}=(s_{1},\ldots,s_{n})$ to be encrypted with $\boldsymbol{z}$ beforehand, but also the multiples of the components of the form $s_{i}B_{KS}^{j}k$, where (i) $i\in\{1,\ldots,n\}$, (ii) $B_{\rm KS}$ is the digit decomposition base, (iii) $j\in[l_{\rm KS}]$ where $l_{\rm KS}=\lceil\log_{B_{\rm KS}}q\rceil$, (iv) $k\in[B_{\rm KS}]$. Let $\texttt{ct}(i,j,k)$ be an ${\rm LWE}_{N,q}$ ciphertext encrypting $s_{i}B_{KS}^{j}k\ {\rm mod}\ q$ with secret $\boldsymbol{z}$. These ciphertexts are called the key-switching keys; they cannot be decrypted correctly with $\boldsymbol{z}$.

Let $\boldsymbol{a}=(a_{1},\ldots,a_{n})$, and for each $a_{i}$ taken as an integer in $[0,q)$, let $\boldsymbol{g}^{-1}_{B_{KS}}(a_{i})=(a_{i,j})_{j\in[l_{\rm KS}]}$ be its $B_{KS}$-digit decomposition. Then

(12) An ${\rm RLWE}_{n,q}$ ciphertext of BFV format, with modulus $q$, ring dimension $n$ that is a power of 2, and secret key $s\in{\cal R}_{n,q}$, is of the form $(a,b)$, where $a,b\in{\cal R}_{n,q}$, and the phase

such that $m\in{\cal R}_{n,t}$ is the plaintext, and $e\in{\cal R}_{n,q}$ is the error.

The ciphertext is decryptable if and only if $2\|e\|_{\infty}<\lfloor q/t\rfloor.$ Given a message $m\in{\cal R}_{n,t}$, the trivial encryption of $m$ in ${\rm RLWE}_{n,q}$ is the ciphertext $(0,m\lfloor q/t\rfloor)$. It is independent of secret $s$.

(13) Given an ${\rm RLWE}_{n,q}$ ciphertext $(a,b)$ (where $a=\sum_{i\in[n]}a_{i}x^{i}$, $b=\sum_{j\in[n]}b_{j}x^{j}$) encrypting a message $m=\sum_{k\in[n]}m_{k}x^{k}$ with secret key $s=\sum_{l\in[n]}s_{l}x^{l}$, the constant-term extraction outputs an ${\rm LWE}_{n,q}$ ciphertext $(a^{\prime\prime},b^{\prime\prime})$ encrypting the constant term $m_{0}\in{\mathbb{Z}}_{t}$ with secret key $\overrightarrow{s}=(s_{0},s_{1},\ldots,s_{n-1},1)\in{\mathbb{Z}}_{q}^{n}$:

(14) An ${\rm RGSW}_{n,q}$ ciphertext with modulus $q$, ring dimension $n$ that is a power of 2, secret key $s\in{\cal R}_{n,q}$, and digit decomposition base $B$, is an $2l_{B}\times 2$ matrix $C$ with entries in ${\cal R}_{n,q}$, where $l_{B}=\lceil\log_{B}q\rceil$, such that the phase

with $\boldsymbol{g}_{B}=[B^{0}\ B^{1}\ \cdots\ B^{l_{B}-1}]^{T}\in{\mathbb{Z}}^{2l_{B}}$, $m\in{\cal R}_{n,t}$ being the plaintext, and $\boldsymbol{e}\in{\cal R}_{n,q}^{2l_{B}}$ being the error.

The ciphertext is decryptable if and only if $2\|\boldsymbol{e}\|_{\infty}<\lfloor q/t\rfloor.$ Given a message $m\in{\cal R}_{n,t}$, the trivial encryption of $m$ in ${\rm RGSW}_{n,q}$ is the ciphertext $m\left(\begin{array}[]{cc}\boldsymbol{g}_{B}\\ &\boldsymbol{g}_{B}\end{array}\right)$. It is independent of secret $s$.

The multiplication of an ${\rm RLWE}_{n,q}$ ciphertext $(a,b)$ with an ${\rm RGSW}_{n,q}$ ciphertext $C$ under the same secret, is

where the $B$-digit decomposition operator $\boldsymbol{g}_{B}^{-1}$ acts on $a,b$ separately, so that $\boldsymbol{g}_{B}^{-1}(a,b)\in{\cal R}_{n,B}^{2l_{B}}$. (II.9) is an ${\rm RLWE}_{n,q}$ ciphertext encrypting the product of the plaintexts in the two ciphertexts respectively. Similarly, the multiplication between two ${\rm RGSW}_{n,q}$ ciphertexts $C_{1},C_{2}$, is $\left(\boldsymbol{g}_{B}^{-1}(C_{1})\right)C_{2}$.

(15) The CMux (controlled multiple executions) operator controlled by ternary variable $d\in\{1,0,-1\}$ and three operations $E_{1},E_{0},E_{-1}$, outputs operation $E_{d}$. Set

Then the CMux operator can be denoted by ${\rm CMux}(d+,d-;E_{1},E_{0},E_{-1})$, whose expression is

Gentry’s bootstrapping idea is to execute the decryption circuit homomorphically. As the decryption needs to use the secret key $\boldsymbol{s}$, it must be provided beforehand and in a ciphertext form. The first step of decryption is to compute the phase of the input LWE ciphertext $\texttt{ct}_{0}=(\boldsymbol{a},b)$, which is essentially the inner product between vectors $\boldsymbol{a},\boldsymbol{s}$. Now that $\boldsymbol{s}$ is encrypted, the inner product is between a plaintext vector and a ciphertext vector. This can be done similar to the key switch procedure.

For example, for $\boldsymbol{a}=(a_{1},\ldots,a_{n})$, let $\boldsymbol{g}^{-1}_{B}(a_{i})=(a_{i,j})_{j\in[l_{B}]}$ be the $B$-digit decomposition of $a_{i}$, where $l_{B}=\lceil\log_{B}q\rceil$; if $z\in{\cal R}_{N,Q}$ is the new secret key, then as in (II.5), for $\boldsymbol{s}=(s_{i})_{i=1,\ldots,n}$, let each $a_{i,j}B^{j}s_{i}\,{\rm mod}\ Q$ be encrypted to an ${\rm RGSW}_{N,Q}$ ciphertext $\texttt{ct}(i,j,a_{i,j})$ with secret key $\boldsymbol{z}$, then

is an ${\rm RGSW}_{N,Q}$ ciphertext encrypting ${\rm phase}(\boldsymbol{a},b)\ {\rm mod}\ q$. The procedure of computing the additions in (II.12) homomorphically is called phase accumulation. The ciphertexts $\texttt{ct}(i,j,a_{i,j})$ are called FHEW bootstrapping keys.

The second step of decryption is to remove the error in the phase by rounding, and execute the “modulo-$q$” operation. In bootstrapping, both need to be done homomorphically. To get rid of the error part of ${\rm phase}(\boldsymbol{a},b)\,{\rm mod}\ q$, the FHEW scheme uses the monomial representation of ${\mathbb{Z}}_{q}$: for a power-of-2 integer $N>q$, first the input ciphertext is changed into an ${\rm LWE}_{n,2N}$ ciphertext $\texttt{ct}_{1}$ by modulus switch, then each $a_{i,j}B^{j}s_{i}\,{\rm mod}\ 2N$ is represented as a monic monomial $x^{a_{i,j}B^{j}s_{i}}$ before being encrypted in an ${\rm RGSW}_{N,Q}$ ciphertext.

In the plaintext, the additions in phase accumulation (II.12) are done in the exponent space of a monomial; in the ciphertext, the additions are done by RGSW ciphertext multiplications. Since RGSW ciphertexts have the unique property that the error in the product of two RGSW ciphertexts is additive in the error of the second ciphertext, ciphertext $\texttt{ct}_{2}$ has small error growth. After phase accumulation, the plaintext becomes

where the error $e^{\prime}$ satisfies $2|e^{\prime}|<\lfloor 2N/t\rfloor$.

For a nega-cyclic function $f:{\mathbb{Z}}_{t}\longrightarrow{\mathbb{Z}}_{t^{\prime}}$, let $f^{\prime}:{\mathbb{Z}}_{2N}\longrightarrow{\mathbb{Z}}_{t^{\prime}}$ be a nega-cyclic extension of $f$, so that for all $u=i\lfloor 2N/t\rfloor+e\ {\rm mod}\ 2N$, where $i\in{\mathbb{Z}}_{t}$, and $e\in{\mathbb{Z}}_{2N}$ satisfies $2|e|<\lfloor 2N/t\rfloor$,

The right side of (II.14) is a polynomial in ${\cal R}_{N,t^{\prime}}$, called the test polynomial of $f$.

In FHEW scheme, the trivial ${\rm RLWE}_{N,Q}$-encryption of test polynomial (II.14) is multiplied with ${\rm RLWE}_{N,Q}$ ciphertext $\texttt{ct}_{2}$, the result is an ${\rm RLWE}_{N,Q}$ ciphertext $\texttt{ct}_{3}$ encrypting plaintext $f^{\prime}(u)x^{m\lfloor 2N/t\rfloor}x^{e^{\prime}}\in{\cal R}_{N,t^{\prime}}$.

The constant term of the plaintext in $\texttt{ct}_{3}$ is exactly $f(m)$. Then constant-term extraction is used to obtain from $\texttt{ct}_{3}$ an ${\rm LWE}_{N,Q}$ ciphertext $\texttt{ct}_{4}$ encrypting $f(m)$ with secret key $\overrightarrow{z}$, according to (II.7).

After this, the key switch procedure is used to change the secret key to $\boldsymbol{s}\in{\mathbb{Z}}_{q}^{n}$, resulting in an ${\rm LWE}_{n,Q}$ ciphertext $\texttt{ct}_{5}$. Finally, the modulus switch from $Q$ to $q$ changes $\texttt{ct}_{5}$ to an ${\rm LWE}_{n,q}$ ciphertext $\texttt{ct}_{6}$, which is the output. This is the whole procedure of the FHEW scheme.

The TFHE scheme improves upon the FHEW scheme by merging the generation of $\texttt{ct}_{2}$ and $\texttt{ct}_{3}$ it starts from the trivial ${\rm RLWE}_{N,Q}$-encryption of test polynomial (II.14), and consecutively multiplies it from the right side with an ${\rm RGSW}_{N,Q}$ ciphertext each encrypting a term of (II.12). Then $\texttt{ct}_{3}$ is generated without generating $\texttt{ct}_{2}$. This trick replaces the product of two matrices to the product between a matrix and a vector.

A typical setting is where $\boldsymbol{s}$ is ternary, namely, $\boldsymbol{s}=(s_{i})_{i=1,\ldots,n}$ where each $s_{i}\in\{1,0,-1\}$. In this setting, the plaintext $x^{-a_{i}s_{i}}$ that corresponds to the term $-a_{i}s_{i}$ in ${\rm phase}(\boldsymbol{a},b)=b-\sum_{i=1,\ldots,n}a_{i}s_{i}$, has three possibilities: $x^{-a_{i}},1,x^{a_{i}}$, if $s_{i}=1,0,-1$, respectively. In terms of the CMux operator and its expression (II.11), for $s_{i+}=\max(s_{i},0)$ and $s_{i-}=\max(-s_{i},0)$,

In (II.15), if both $s_{i+},s_{i-}$ are encrypted as ${\rm RGSW}_{N,Q}$ ciphertexts, and 1 is trivially encrypted, then the right side becomes the sum of three ${\rm RGSW}_{N,Q}$ ciphertexts; it replaces the product $\prod_{j\in[l_{\rm KS}]}\texttt{ct}(i,j,a_{i,j})$ in FHEW phase accumulation (II.12). The ${\rm RGSW}_{N,Q}$ ciphertexts encrypting the $s_{i+},s_{i-}$ are called TFHE bootstrapping keys when the secret is ternary.

In summary, the procedure of TFHE functional bootstrapping for LWE ciphertext with ternary secret is as follows:

Input:

1. 1.

   ${\rm LWE}_{n,q}$ ciphertext $\texttt{ct}_{0}$ to be bootstrapped, whose plaintext modulus is $t$, whose plaintext is $m\in{\mathbb{Z}}_{t}$ and whose secret is $\boldsymbol{s}=(s_{i})_{i=1,\ldots,n}$;

2. 2.

   TFHE bootstrapping keys encrypting $s_{i+},s_{i-}$ for $i\in\{1,\ldots,n\}$, which are ${\rm RGSW}_{N,Q}$ ciphertexts whose secret is $z=\sum_{i\in[N]}z_{i}x^{i}\in{\cal R}_{N,Q}$;

3. 3.

   test polynomial of the form (II.14) in ${\cal R}_{N,t^{\prime}}$ , which encodes the nega-cyclic function $f:{\mathbb{Z}}_{t}\longrightarrow{\mathbb{Z}}_{t^{\prime}}$;

4. 4.

   key-switching keys, which are ${\rm RLWE}_{n,Q}$ ciphertexts encrypting $z_{i}B_{\rm KS}^{j}k\ {\rm mod}\ Q$ with secret $\boldsymbol{s}$ for all $i\in[N]$, $j\in[\lceil\log_{B_{\rm KS}}Q\rceil]$, $k\in[B_{\rm KS}]$, where $B_{\rm KS}$ is the digit decomposition base for key switch.

Output: ${\rm LWE}_{n,q}$ ciphertext $\texttt{ct}_{5}$ encrypting $f(m)\in{\mathbb{Z}}_{t^{\prime}}$.

Step 1. Modulus switch from $q$ to $q^{\prime}=2N$. The result is an ${\rm LWE}_{n,q^{\prime}}$ ciphertext $\texttt{ct}_{1}:=(a_{1},\ldots,a_{n},b)$ with secret $\boldsymbol{s}$.

Step 2. Phase accumulation (or blind rotation). It starts from the product $\texttt{ct}_{2}$ of the trivial ${\rm RLWE}_{N,Q}$ encryption of the test polynomial and the trivial ${\rm RGSW}_{N,Q}$ encryption of $b\in{\mathbb{Z}}_{q}$, for every $i=1,\ldots,n$, updates $\texttt{ct}_{2}$ by multiplying it from the right side with an ${\rm RGSW}_{N,Q}$ ciphertext encrypting ${\rm CMux}(s_{i+},s_{i-};x^{-a_{i}},1,x^{a_{i}})$. The result, still denoted by $\texttt{ct}_{2}$, is an ${\rm RLWE}_{N,Q}$ ciphertext with secret $z$.

Step 3. Constant-term extraction (also called sample extract) of $\texttt{ct}_{2}$. The result is an ${\rm LWE}_{N,Q}$ ciphertext $\texttt{ct}_{3}$ encrypting $f(m)$ with secret $\overrightarrow{z}$.

Step 4. Key switch from $\overrightarrow{z}$ to $\boldsymbol{s}$. The result is an ${\rm LWE}_{n,Q}$ ciphertext $\texttt{ct}_{4}$.

Step 5. Modulus switch from $Q$ to $q$. The result is an ${\rm LWE}_{n,q}$ ciphertext $\texttt{ct}_{5}$.

The order of an element $g$ in a group, denoted by ${\rm order}(g)$, is the smallest positive integer $m$ such that $g^{m}=1$, where 1 is the identity element.

When a group $G$ acts on a set $S$, the action is said to be transitive, if for all $x,y\in S$, there exists a $g\in G$ such that $gx=y$. The action is said to be regular or faithful, if for any $g\in G$, $gx=x$ for all $x\in S$ if and only if $g=1$.

An $\mathbb{F}$-representation of a group $G$ is a homomorphism from $G$ to some $GL_{\mathbb{F}}({\mathcal{V}})$, where ${\mathcal{V}}$ is a finite-dimensional $\mathbb{F}$-vector space. Two representations $\boldsymbol{\Phi}_{i}:G\longrightarrow GL_{\mathbb{F}}({\mathcal{V}}_{i})$ for $i=1,2$, are said to be equivalent, if there is an $\mathbb{F}$-linear isomorphism $\boldsymbol{T}:{\mathcal{V}}_{1}\rightarrow{\mathcal{V}}_{2}$, such that for all $g\in G$, $\boldsymbol{\Phi}_{2}(g)=\boldsymbol{T}\boldsymbol{\Phi}_{1}(g)\boldsymbol{T}^{-1}$.

Now fix the field $\mathbb{F}$ as the following one, where $N$ is a power of 2:

For any $r>0$, an element of $GL({\mathbb{F}}^{r})$ is called a monic monomial permutation matrix if in the matrix, every row and every column respectively contains one and only one nonzero entry, and the entry is a monic monomial. All $r\times r$ monic monomial permutation matrices form a finite subgroup ${\rm MMPM}_{r}$ of $GL({\mathbb{F}}^{r})$. It is easy to see that any $r\times r$ monic monomial permutation matrix $\boldsymbol{A}$ is of the form

where $u_{i}\in[2N]$, $\delta$ is the Kronecker symbol, and $\phi\in S_{r}$ is a permutation acting on $[r]$.

Consider the additive cyclic group ${\mathbb{Z}}_{q^{\prime}}$, where $q^{\prime}=2Nr$. The identity element is 0, and the generator is 1. Let $\boldsymbol{\Phi}:\mathbb{Z}_{q^{\prime}}\longrightarrow{\rm MMPM}_{r}$ be a representation of group $\mathbb{Z}_{q^{\prime}}$. Then $\boldsymbol{\Phi}(\mathbb{Z}_{q^{\prime}})$ is a subgroup generated by matrix $\boldsymbol{\Phi}(1)$.