D-1.8 Noise Bootstrapping

- Reference: TFHE Deep Dive - Part IV - Programmable Bootstrapping [10]

Continuing homomorphic additions of TFHE ciphertexts does not necessarily increase the noise $e$, because $e$ is randomly generated over the Gaussian distribution, thus adding up many noises would give the mean value of 0. On the other hand, continuing homomorphic multiplications increases the noise, because the noise terms get multiplied, growing its magnitude. Thus, we need to somehow reset the noise before it trespasses on the higher bits where plaintext $m$ resides (i.e., preventing the red noise bits from overflowing to the blue plaintext bits as shown in Figure 8). The process of re-initializing the noise to a smaller value is called noise bootstrapping.

As explained in the beginning of this section, TFHE uses LWE (which is GLWE with $n=1$) to encrypt & decrypt a plaintext. That is, each plaintext is $m$ (a single number), encoded as a zero-degree polynomial. Further, the secret key S that encrypts each $m$ is a vector $\{s_0,s_1,\cdots ,s_{k-1}\}$ instead of a polynomial. On the other hand, TFHE’s noise bootstrapping uses homomorphic addition between GLWE ciphertexts and homomorphic multiplication between GLWE and GGSW ciphertexts.

Suppose we have a TFHE ciphertext as follows:

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)=(a_0,a_1,\cdots a_{k-1},b)$

$b=\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{s}_i+\mathrm{\Delta }m+e_b$

$\overrightarrow{s}=(s_0,s_1,\cdots s_{k-1})$

, where $e_b$ is a big noise accumulated over a series of many ciphertext (or plaintext) multiplications. The goal of noise bootstrapping is to convert $(a_0,a_1,\cdots a_{k-1},b)$ into $(a_0^{\prime },a_1^{\prime },\cdots a_{k-1}^{\prime },b^{\prime })$ such that:

$b^{\prime }=\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i^{\prime }{s}_i+\mathrm{\Delta }m+e_s$

, where $e_s$ is a re-initialized noise.

D-1.8.1 Overview

To implement noise bootstrapping, we create a specially designed $(n-1)$-degree polynomial $V(X)$ called a Lookup Table (LUT). Before explaining $V(X)$, we will first motivate the idea based on a preliminary LUT polynomial $V_q(X)$. Imagine that the polynomial $V_q(X)$’s each degree term $X^j$ has its exponent $j=\mathrm{\Delta }{m}_i+e_{\ast }$, a plaintext $m_i$ with some noise $e_{\ast }\in {\mathbb{Z}}_{\mathrm{\Delta }}$, and its corresponding coefficient $v_j=m_i$, which is a noise-free plaintext. Therefore, the $(q-1)$-degree polynomial $V_q(X)$ is defined as follows:

$V_q(X)=v_0+v_1{X}^1+v_2{X}^2+\cdots +v_{q-1}{X}^{q-1}$

$=m_0{X}^{\mathrm{\Delta }{m}_0+e_0}+m_0{X}^{\mathrm{\Delta }{m}_0+e_1}+m_0{X}^{\mathrm{\Delta }{m}_0+e_2}+\cdots +m_0{X}^{\mathrm{\Delta }{m}_0+e_{\mathrm{\Delta }-1}}$ # total $\mathrm{\Delta }$ terms

$+m_1{X}^{\mathrm{\Delta }{m}_1+e_0}+m_1{X}^{\mathrm{\Delta }{m}_1+e_1}+m_1{X}^{\mathrm{\Delta }{m}_1+e_2}+\cdots +m_1{X}^{\mathrm{\Delta }{m}_1+e_{\mathrm{\Delta }-1}}$ # total $\mathrm{\Delta }$ terms

$+\cdots$

$+m_{t-1}{X}^{\mathrm{\Delta }{m}_{t-1}+e_0}+m_{t-1}{X}^{\mathrm{\Delta }{m}_{t-1}+e_1}+m_{t-1}{X}^{\mathrm{\Delta }{m}_{t-1}+e_2}+\cdots +m_{t-1}{X}^{\mathrm{\Delta }{m}_{t-1}+e_{\mathrm{\Delta }-1}}$ # total $\mathrm{\Delta }$ terms

In the above formula, each $m_i$ and $e_k$ represent every possible plaintext message and error values (where $m_i\in {\mathbb{Z}}_t$ and $e_k\in {\mathbb{Z}}_{\mathrm{\Delta }}$).

We design $V_q(X)$ to have the special property that each $v_j{X}^j$ term represents the special mapping (exponent, coefficient) $=(\mathrm{\Delta }{m}_i+e_{\ast },m_i)$, where $e_{\ast }$ can be any value in ${\mathbb{Z}}_{\mathrm{\Delta }}$. During the TFHE setup stage, we GLWE-encrypt $V_q(X)$ by using our newly defined GLWE key ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$, a bootstrapping key, which is different from the LWE secret key $\overrightarrow{s}$. ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$ is a list of $(n-1)$-degree polynomials with binary coefficients. Later, during the noise bootstrapping stage, we will rotate the coefficients of $V$ by $\mathrm{\Delta }m+e$ positions to the left by computing $V\cdot X^{-(\mathrm{\Delta }m+e)}=V^{\prime }$, by using the polynomial coefficient rotation method 1 technique (Summary A-5.2.1 in §A-5.2). Then, we will extract the polynomial’s constant term’s coefficient (i.e., the left-most 0-degree term’s coefficient in the rotated polynomial $V^{\prime }$) by using the coefficient extraction technique (§D-1.7). Further, we will encrypt $V_q(X)$ as a GLWE ciphertext at the TFHE setup stage, and thus the rotated $V_q^{\prime }(X)$’s extracted constant term’s coefficient is an LWE encryption of $m$ (i.e., ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$) with a re-initialized (i.e., completely reduced) noise.

To summarize, the noise bootstrapping procedure can be conceptually understood (at least for now) as follows:

1.

Input: ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m+e)$ as a noisy ciphertext encrypting $m$

2.

Convert the input into the form of $X^{-(\mathrm{\Delta }m+e)}$ as a rotator of $V_q(X)$ (Lookup Table).

3.

Rotate $V_q$ to the left by $\mathrm{\Delta }m+e$ positions by computing $V_q\cdot X^{-(\mathrm{\Delta }m+e)}=V_q^{\prime }$.

4.

Extract the rotated $V_q^{\prime }(X)$’s constant term’s coefficient $m$ as an LWE encryption, which is ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$.

5.

Output: ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$ as an LWE encryption of the plaintext $m$ with a re-initialized noise

The output ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$ encrypts the same plaintext message as the input ciphertext, but with completely reduced noise. Therefore, the output ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$ can be used for subsequent TFHE homomorphic operations (e.g., addition or multiplication). During this noise bootstrapping process, the polynomial $V_q$ is used as a dictionary that contains the mappings from the noisy plaintext $\mathrm{\Delta }m+e$ (i.e., as $\mathrm{\Delta }m+e=j$ where $v_j{X}^j$) to the noise-free plaintext $m$ (i.e., as $m=v_j$ where $v_j{X}^j$). Therefore, $V_q$ is called the Lookup Table (LUT).

Then, what should be the degree of $V_q(X)$? In order for $V_q(X)$ to encode all possible mappings from $\mathrm{\Delta }m+e\in {\mathbb{Z}}_q$ to $m\in {\mathbb{Z}}_t$, $V_q(X)$ should be a $(q-1)$-degree polynomial. However, $q$ is a very big number, and it is computationally infeasible to manage a $(q-1)$-degree polynomial. Thus, in practice, we instead use a much smaller polynomial $V(X)$ whose degree is only $n-1$. Remember that according to our TFHE setup, $n\ll q$. Therefore, we need a way to compress the big ciphertext space $\mathrm{\Delta }m+e\in {\mathbb{Z}}_q$ into a much smaller space ${\mathbb{Z}}_n$ and encode the compressed values as the exponents of $X^j$ in a proportionally correct way. For this proportional compression of ${\mathbb{Z}}_q\to {\mathbb{Z}}_n$, we will use the LWE modulus switching technique learned from §C-4.1.

D-1.8.2 Modulus Switch for Noise Boootstrapping

To avoid using the giant $(q-1)$-degree polynomial $V_q$, we will compress $q$ possible ciphertext elements $\mathrm{\Delta }m+e\in {\mathbb{Z}}_q$ into $n$ distinct exponents of the $(n-1)$-degree polynomial $V$, where each $v_j{X}^j$ term in $V$ represents a mapping from $j\to v_j$ (i.e., noisy plaintext to noise-free plaintext). However, notice that when we rotate the coefficients of the $(n-1)$-degree polynomial $V$ to the left, as $v_j{X}^j$ rotates across the boundary between $X^0$ and $X^{n-1}$ degree terms, $v_j$’s sign flips to $-v_j$ (as shown in the example of §A-5.2.1). Due to this coefficient sign flip, the $(n-1)$-degree polynomial $V$ can theoretically encode total $2n$ distinct coefficient states as follows: $(v_0,v_1,v_2,\cdots ,v_{n-1},-v_0,-v_1,\cdots ,-v_{n-1})$. To move each of these $2n$ distinct coefficients to the constant term’s coefficient position in $V$ (i.e., shifting the coefficient $v_j$ to the leftmost term in $V$), the rotating computation of $V\cdot X^{-j}$ can use $2n$ distinct $j$ values, which are $\{0,1,2,\cdots ,n-1,n,\cdots ,2n-1\}$, to move each of $(v_0,v_1,v_2,\cdots ,v_{n-1},-v_0,-v_1,\cdots ,-v_{n-1})$ coefficients to the constant term’s position. This implies that the exponent $j$ in $V\cdot X^{-j}$ can use any of the $2n$ distinct values to cover all possible $2n$ (sign-flipped) coefficient states of $V$. Also, remember that $j=\mathrm{\Delta }m+e$. Therefore, we will switch the modulo of $\mathrm{\Delta }m+e$ from $q\to 2n$. Using the LWE modulus switching technique (§C-4.1), our original LWE ciphertext ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m+e)=(a_0,a_1,\cdots a_{k-1},b)\in {\mathbb{Z}}_q^{k+1}$ (i.e., the initial input to the noise bootstrapping procedure) will be converted into the following:

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\widehat{\mathrm{\Delta }}m)=({\widehat{a}}_0,{\widehat{a}}_1,\cdots {\widehat{a}}_{k-1},\widehat{b})\in {\mathbb{Z}}_{2n}^{k+1}$

$\overrightarrow{s}=(s_0,s_1,\cdots s_k)\in {\mathbb{Z}}_2^k$ # the secret key stays the same, as each $s_i$ is binary

$\widehat{\mathrm{\Delta }}=\mathrm{\Delta }{\displaystyle \frac{2n}{q}}={\displaystyle \frac{2n}{t}}\in {\mathbb{Z}}_{2n}$

${\widehat{a}}_i=\lceil a_i{\displaystyle \frac{2n}{q}}\rfloor \in {\mathbb{Z}}_{2n}$

$\widehat{e}=\lceil e{\displaystyle \frac{2n}{q}}\rfloor \in {\mathbb{Z}}_{2n}$

$\widehat{b}=\lceil b{\displaystyle \frac{2n}{q}}\rfloor \approx \underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\widehat{a}}_i{s}_i+\widehat{\mathrm{\Delta }}m+\widehat{e}\in {\mathbb{Z}}_{2n}$

The degree of $V(X)$ and Security: If our goal were to design the minimal-degree polynomial $V$ whose coefficients map all possible values of the plaintext $m$, then it would be sufficient to design a $t$-degree polynomial $V$. Nonetheless, the reason why we choose the degree of $V$ to be $2n$ instead of $t$ is to guarantee an enough security level– the higher the polynomial degree $n$ is, the safer our scheme is against attacks.

D-1.8.3 Halving the Plaintext Space To be Used

Problematically, the LUT polynomial $V(X)$ rotates negacyclically, that is, $V(X)\cdot X^n=-V(X)$ (i.e., coefficients flip their signs with the rotation period of $n$). More generally:

$V(X)\cdot X^{-j}=V(X)\cdot X^{2n-j}=V(X)\cdot X^{4n-j}=\cdots$

$=V(X)\cdot X^{-(jmod2n)}=\{\begin{array}{c}{v}_j+v_{j+1}X+\cdots ,\text{for }0\le i<n\hfill \\ -v_j-v_{j-1}X-\cdots ,\text{for }n\le j<2n\hfill \end{array}$

, where $v_j$ denotes the constant term’s coefficient after rotating the polynomial $V(X)$ by $j$ positions to the left. Problematically, $v_j$ flips its sign whenever its rotation crosses the boundary between $X^0$ and $X^{n-1}$. Given the modulus-switched values ${\widehat{a}}_j$, $\widehat{e}$, and $\widehat{b}$, we design the following LUT polynomial $V(X)$:

$V(X)=v_0+v_1{X}^1+v_2{X}^2+\cdots +v_{n-1}{X}^{n-1}$

$=m_0{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_0}+m_0{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_1}+m_0{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_2}+\cdots +m_0{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_{\widehat{\mathrm{\Delta }}-1}}$ # total $\widehat{\mathrm{\Delta }}$ terms

$+m_1{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_0}+m_1{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_1}+m_1{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_2}+\cdots +m_1{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_{\widehat{\mathrm{\Delta }}-1}}$ # total $\widehat{\mathrm{\Delta }}$ terms

$+\cdots$

$+m_{t∕2-1}{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_0}+m_{t∕2-1}{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_1}+m_{t∕2-1}{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_2}+\cdots +m_{t∕2-1}{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_{\widehat{\mathrm{\Delta }}-1}}$ # total $\widehat{\mathrm{\Delta }}$ terms

Remember that by computing $V(X)\cdot X^{-j}$ for $j=\{0,1,\cdots ,n-1\}$, we can rotate $V(X)$’s coefficients to the left by $\{0,1,\cdots n-1\}$ positions. For each $j$-slot rotation of $V(X)$ where $j=\{0,1,\cdots ,n-1\}$, the rotated polynomial $V^{\prime }(X)$ gets the following values as the constant-term’s coefficient:

$\stackrel{V^{\prime }(X)\text{’s constant term’s coefficient for }j=\{0,1,\cdots n-1\}\text{ rotations}}{\overbrace{\stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_{\ast }}}{\underbrace{\mathrm{\Delta }{m}_0,\mathrm{\Delta }{m}_0,\cdots }}}}\stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_{\ast }}}{\underbrace{\mathrm{\Delta }{m}_1,\mathrm{\Delta }{m}_1,\cdots }}}}\cdots \stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_{\ast }}}{\underbrace{\mathrm{\Delta }{m}_{t∕2-1},\mathrm{\Delta }{m}_{t∕2-1},\cdots }}}}}}$

In the above expression, ${\widehat{e}}_{\ast }$ is a noise that can range from $[0,\widehat{\mathrm{\Delta }})$. Note that all of $\widehat{\mathrm{\Delta }}{m}_i+{\widehat{e}}_0,\widehat{\mathrm{\Delta }}{m}_i+{\widehat{e}}_1,\cdots ,\widehat{\mathrm{\Delta }}{m}_i+{\widehat{e}}_{\widehat{\mathrm{\Delta }}-1}$ exponents are designed to be mapped to the same coefficient value, $m_i$, which aligns with the fact that their underlying plaintext $m_i$ is the same when decrypted (once their associated noise ${\widehat{e}}_{\ast }$ gets eliminated). This is why each $m_i$ is redundantly used $\widehat{\mathrm{\Delta }}$ times in a row as coefficients in $V(X)$. We can view this sequential repetition of coefficients as having a robustness of mapping each $\widehat{\mathrm{\Delta }}{m}_i+{\widehat{e}}_{\ast }$ to $m_i$ against any noise ${\widehat{e}}_{\ast }\in {\mathbb{Z}}_{\widehat{\mathrm{\Delta }}}$.

So far, the above sequence of $m_0,m_1,\cdots ,m_{t∕2-1}$ coefficients is what we expect $V^{\prime }(X)$ (i.e., the rotated polynomial) to return as its constant term’s coefficient for each of $0,1,\cdots ,n-1$ rotations (where each $m_i+1=m_{i+1}$). However, the correctness of the coefficient mappings breaks when the rotation count is between $[n,2n-1)$, because their coefficients flip their signs when they cross the term’s boundary from $X^0$ to $X^{n-1}$, due to the polynomial ring’s negacyclic nature. Specifically, the constant term’s coefficient values of the rotated polynomial $V^{\prime }(X)$ are as follows for each rotation of $n,n+1,\cdots ,2n-1$ positions:

$\stackrel{V^{\prime }(X)\text{’s constant term’s coefficient after each of }n,n+1,\cdots 2n-1\text{ rotations}}{\overbrace{\stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{-\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_0+{\widehat{e}}_{\ast }}}{\underbrace{-m_0,-m_0,\cdots }}}}\stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{-\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_1+{\widehat{e}}_{\ast }}}{\underbrace{-m_1,-m_1,\cdots }}}}\cdots \stackrel{\widehat{\mathrm{\Delta }}\text{ repetitions}}{\overbrace{\underset{-\text{coeff. of }{X}^{\widehat{\mathrm{\Delta }}{m}_{t∕2-1}+{\widehat{e}}_{\ast }}}{\underbrace{-m_{t∕2-1},-m_{t∕2-1},\cdots }}}}}}$

As we can see above, the rotated $V^{\prime }(X)$’s constant term’s coefficient shows a negacyclic pattern with the rotation period of $n$, where the second $n$-rotation group’s coefficients are exactly the negated values of the first $n$-rotation group’s values. Let’s understand why this negacyclic behavior breaks the (exponent, coefficient) = $(\widehat{\mathrm{\Delta }}m+\widehat{e},m)$ mappings. Since TFHE’s plaintext and ciphertext values are defined in rings, as we rotate the LUT polynomial $V(X)$, we ideally want the rotated polynomial $V^{\prime }(X)$’s constant term’s value (i.e., mapped plaintext value) to wrap around in a circular manner, representing a ring pattern (with sequential $\widehat{\mathrm{\Delta }}$ repetitions of each value to be resistant against up to a ${\widehat{e}}_{\ast }\in Z_{\widehat{\mathrm{\Delta }}}$ noise). However, the negacyclic nature of a polynomial ring makes the constant term’s value of the second-half rotation group problematic, because they are exact negations of those of the first-half rotation group, breaking the circular wrapping-around ring pattern between the first-group values and the second-group values.

To summarize the problem, $V(X)$ has a limitation in becoming a perfect LUT, because it preserves the correct mappings of (exponent, coefficient) = $(\widehat{\mathrm{\Delta }}m+\widehat{e},m)$ only for one half of $i\in {\mathbb{Z}}_t$, not for the other half.

Solution: Good news is that we have observed that $V(X)$’s mappings of (exponent, coefficient) = $(\widehat{\mathrm{\Delta }}m+\widehat{e},\mathrm{\Delta }m)$ preserve their ring-pattern consistency if $V(X)$ is rotated no more than $n-1$ positions (i.e., the first-half rotation group). Therefore, the easiest solution to avoid the negacyclic problem of the LUT polynomial rotation is that the application of TFHE restricts $V(X)$ to be rotated no more than $n-1$ positions by design during the noise bootstrapping. To enforce this, when the TFHE application’s computation pipeline processes plaintext values (in its original plaintext computation logic before considering any homomorphic operations), the application should ensure to involve only some pre-defined continuous ${\displaystyle \frac{t}{2}}$ modulo values within ${\mathbb{Z}}_t$ as the possible inputs and outputs of each computation step. This constraint effectively ensures the possible values of $\widehat{\mathrm{\Delta }}m+\widehat{e}$ to be continuous $n$ values within ${\mathbb{Z}}_{2n}$. Since the LUT polynomial $V(X)$ gets rotated by computing $V(X)\cdot X^{-(\widehat{\mathrm{\Delta }}m+\widehat{e})}$, as the application restricts $\widehat{\mathrm{\Delta }}m+\widehat{e}$ to be at most $n-1$ (out of $2n-1$) by its application design, $V(X)$ will be rotated at most $n-1$ positions during the noise bootstrapping. Thus, we can prevent the occurrences of the problematic $\{n,n+1,\cdots ,2n-1\}$ rotations that flip the signs of coefficients.

To summarize, at the cost of halving the application’s usable plaintext values to some continuous ${\displaystyle \frac{t}{2}}$ values within ${\mathbb{Z}}_t$, we can prevent $V(X)$’s negacyclic rotation problem, and thereby preserve $V(X)$’s correct mappings of (exponent, coefficient) = $(\widehat{\mathrm{\Delta }}m+\widehat{e},m)$.

Considering all these, our final LUT polynomial $V(X)$ is as follows:

D-1.8.4 Blind Rotation

Blind rotation refers to rotating an encrypted polynomial’s coefficients so that it is not possible to know how many positions the polynomial’s coefficients are rotated, and after the rotation, it is not possible to see which coefficient has moved to which degree term. Blind rotation uses the basic polynomial rotation method 1 technique (Summary A-5.2 in §A-5.2), with the difference that the $V(X)\cdot X^{-i}$ computation is done homomorphically.

Note that $X^{\widehat{\mathrm{\Delta }}m+{\widehat{e}}_b}=X^{\widehat{b}-{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i}$, so we can rotate $V$ by computing $V\cdot X^{-(\widehat{b}-{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i)}=V\cdot X^{-\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i}$. In fact, we cannot directly compute the LWE decryption formula $-\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i$ (or $\widehat{b}-{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i$) without the knowledge of the LWE secret key $S$. Nevertheless, there is a mathematical work-around to compute $V\cdot X^{-\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i}$ without the knowledge of the secret key $S$, provided we are given ${\{\mathit{𝐺𝐺𝑆}{W}_{{\overrightarrow{S}}_{\mathit{𝑏𝑘}},\sigma }^{\beta ,l}(s_i)\}}_{i=0}^{k-1}$ at the TFHE setup stage. Note that ${\{\mathit{𝐺𝐺𝑆}{W}_{{\overrightarrow{S}}_{\mathit{𝑏𝑘}},\sigma }^{\beta ,l}(s_i)\}}_{i=0}^{k-1}$ is a GGSW encryption of the LWE secret key $S$, encrypted by the GLWE secret key ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$ (i.e., a bootstrapping key). We use ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$ to homomorphically compute $V\cdot X^{-\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i}$ (i.e., blindly rotate the coefficients of $V$ to the left by $\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i$ positions), according to the following procedure:

1.

GLWE-encrypt the polynomial $V$ with the bootstrapping key ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$ at the TFHE setup stage, so that each coefficient of $V$ gets encrypted.

2.

Compute $V_0=V\cdot X^{-\widehat{b}}$, which is basically rotating $V$’s polynomials by $\widehat{b}$ positions to the left. Since $\widehat{b}$ is a known value visible in the LWE ciphertext, we can directly compute the rotation of $V_0=V\cdot X^{-\widehat{b}}$.

3.

Compute $V_1=V_0\cdot X^{{\widehat{a}}_0{s}_0}=s_0\cdot (V_0\cdot X^{{\widehat{a}}_0}-V_0)+V_0$. This formula works for the special case where $s_0\in \{0,1\}$: if $s_0=0$, then $V_1=V_0$; else if $s_0=1$, then $V_1=V_0\cdot X^{{\widehat{a}}_0}$. Computing $s_0\cdot (V_0\cdot X^{{\widehat{a}}_0}-V_0)+V_0$ is done as a TFHE homomorphic addition and multiplication. We call this blind rotation of $V_0$, where the selection bit $s_0$ (i.e., the 1st element of the secret key vector $S$) is encrypted as a GGSW ciphertext by using ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$ (i.e. the bootstrapping key) and $V_0$ is an encrypted polynomial as a GLWE ciphertext. Multiplying GLWE-encrypted $V_0$ with $x^{{\widehat{a}}_0}$ is done by GLWE ciphertext-to-plaintext multiplication (§C-3), and subtracting the result by GLWE-encrypted $V_0$ is done by GLWE ciphertext-to-ciphertext addition/subtraction (§C-1), and multiplying the result by GGSW-encrypted $s_0$ is done by GLWE-to-GGSW multiplication (§D-1.6.2), and adding the result with GLWE-encrypted $V_0$ is done by GLWE ciphertext-to-ciphertext addition. If $s_0=1$, then the formula’s $X^{{\widehat{a}}_0}$ term gets multiplied to $V_0$, which effectively rotates $V_0$’s coefficients by ${\widehat{a}}_0$ positions to the right. Else if $s_0=0$, then $V_0$ does not get rotated and stays the same. In both cases, the resulting $V_1$ is encrypted as a new GLWE ciphertext. During this blind rotation, unless we have the knowledge of $s_0$ and ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$, it is impossible to know whether $V_0$ has been rotated or not, and also how many positions have been rotated.

4.

By using the same blind rotation method as in the previous step, compute the GLWE encryption of $V_2=V_1\cdot X^{{\widehat{a}}_1{s}_1}=s_1\cdot (V_1\cdot X_1^{\widehat{a}}-V_1)+V_1$. Note that we have the following publicly known components: ${\widehat{a}}_1$, a GLWE encryption of $V_1$, and a GGSW ciphertext of $s_1$ encrypted by using ${\overrightarrow{S}}_{\mathit{𝑏𝑘}}$.

5.

Continue to compute the GLWE encryption of $V_3,V_4,\cdots ,V_k$ in the same manner, and we finally get a GLWE encryption of $V_k$, whose computed value is equivalent to:

$V^{\prime }=V_k$

$=V_{k-1}\cdot X^{{\widehat{a}}_{k-1}{s}_{k-1}}$

$=V_0\cdot X^{{\widehat{a}}_0{s}_0}{X}^{{\widehat{a}}_1{s}_1}\cdots X^{{\widehat{a}}_{k-1}{s}_{k-1}}$

$=V\cdot X^{-\widehat{b}+{\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{k-1}{\widehat{a}}_i{s}_i}$

$=V\cdot X^{-(\widehat{\mathrm{\Delta }}m+{\widehat{e}}_b)}$

This means that the GLWE encryption of the final polynomial $V_k$ will have the coefficient $m$ in its constant term, as $V(X)$ is designed to have the mapping ($\widehat{\mathrm{\Delta }}m+{\widehat{e}}_{\ast },m$).

Note that while we restrict the application’s plaintext space usage to some continuous ${\displaystyle \frac{t}{2}}$ modulo values within ${\mathbb{Z}}_t$ (§D-1.8.3), this restriction does not exist in the ciphertext space. That is, it is okay for blind rotations to rotate $V(X)$ more than $n$ positions during the intermediate steps, because their invalid positions can be brought back to valid ones by their subsequent steps. Therefore, what matters for the noise bootstrapping correctness is only the completed state $V_k(X)$. The rotation-completed $V_k(X)$ must have been rotated $\widehat{\mathrm{\Delta }}m+\widehat{e}$ positions to the left. Therefore, we only need to ensure that $\widehat{\mathrm{\Delta }}m+\widehat{e}$ falls within our pre-defined continuous ${\displaystyle \frac{t}{2}}$ modulo range within the ${\mathbb{Z}}_t$ domain, which is equivalent to ensuring that the aggregate rotation count is at most $n-1$ positions to avoid coefficient extraction of any double-signed contradicting coefficients.

Homomorphic MUX Logic Gate: In step 3, the formula $s_0\cdot (V_0\cdot X^{{\widehat{a}}_0}-V_0)+V_0$ implements the MUX logic gate as shown in Figure 13, where in our case $s_0$ is the selection bit that chooses between the two inputs: $V_0$ and $V_0\cdot X^{{\widehat{a}}_0}$. If $s_0$ is 1, then the output is $V_0\cdot X^{{\widehat{a}}_0}$; otherwise, the output is $V_0$. In our design, the homomorphic computation of $s_0\cdot (V_0\cdot X^{{\widehat{a}}_0}-V_0)+V_0$ effectively implements a homomorphic MUX gate, where the two inputs are LWE-encrypted and the selection bit is GGSW-encrypted.

D-1.8.5 Coefficient Extraction

Finally, we use the coefficient extraction technique (§D-1.7) to extract the rotated polynomial $V^{\prime }(X)$’s constant term’s coefficient as an encryption of $m$: ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$. At this point, the original $\mathsf{\text{𝖫𝖶𝖤}}$ ciphertext’s old noise ${\widehat{e}}_b$ has gone, and the bootstrapped new ciphertext ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$ has a newly generated small noise $e_s$.

In fact, the homomorphic MUX logic in the blind rotation procedure (§D-1.8.4) involves lots of ciphertext multiplications and additions, which can accumulate additional noise until we reach the point of coefficient extraction. In order to limit the accumulating noise during the series of MUX logic, we can carefully adjust the security parameters. For example, we can design a narrower Gaussian distribution for sampling the noise $e$, while designing a sufficiently large $n$ to compensate for the reduced noise. Meanwhile, increasing $q$ rather makes the system less secure, because it becomes more vulnerable to lattice reduction attacks.

D-1.8.6 Noise Bootstrapping Summary

TFHE’s noise bootstrapping procedure is summarized as follows:

D-1.8.7 Example: Noise Bootstrapping

Suppose the GLWE security setup: $n=16$, $t=8$, $q=64$, $k=8$

${\mathbb{Z}}_{t=8}=\{-4,-3,-2,-1,0,1,2,3\}$

${\mathbb{Z}}_{q=64}=\{-32,-31,-30,\cdots ,29,30,31\}$

$\mathrm{\Delta }={\displaystyle \frac{q}{t}}={\displaystyle \frac{64}{8}}=8$

And suppose we have the following LWE ciphertext:

$\overrightarrow{s}=(1,0,0,1,1,1,0,1)={\mathbb{Z}}_2^{k=8}$

$m=1\in {\mathbb{Z}}_{t=8}$

$\mathrm{\Delta }m=1\cdot 8=8\in {\mathbb{Z}}_{q=64}$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)=(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,b)=(8,-28,4,-32,0,31,-6,7,24)\in {\mathbb{Z}}_{q=64}^{k+1=9}$

$e=2\in {\mathbb{Z}}_{q=64}$ (should be the case that $|e|<{\displaystyle \frac{\mathrm{\Delta }}{2}}=4$ for correct decryption)

$b=\underset{i=0}{\overset{7}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{s}_i+\mathrm{\Delta }m+e=(8-32+31+7)+8+2=24\in {\mathbb{Z}}_{q=64}$

Now then, the TFHE noise bootstrapping procedure is as follows:

1.

Modulus Switch: Switch the modulus of ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)$ From $q\to 2n$, which is from $64\to 32$. After the modulus switch, the original LWE ciphertext is converted as follows:

${\mathbb{Z}}_{2n=32}=\{-16,-15,-14,\cdots ,13,14,15\}$

$\overrightarrow{s}=(1,0,0,1,1,1,0,1)={\mathbb{Z}}_2^{k=8}$

$\widehat{\mathrm{\Delta }}=\mathrm{\Delta }{\displaystyle \frac{2n}{64}}=8{\displaystyle \frac{32}{64}}=4$

$\widehat{\mathrm{\Delta }}m=4\cdot 1=4\in {\mathbb{Z}}_{2n=32}$

$\widehat{e}=\lceil e{\displaystyle \frac{2n}{q}}\rfloor =\lceil 2{\displaystyle \frac{32}{64}}\rfloor =1\in {\mathbb{Z}}_{2n=32}$

$$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\widehat{\mathrm{\Delta }}m)=({\widehat{a}}_0,{\widehat{a}}_1,{\widehat{a}}_2,{\widehat{a}}_3,{\widehat{a}}_4,{\widehat{a}}_5,{\widehat{a}}_6,{\widehat{a}}_7,\widehat{b})\in {\mathbb{Z}}_{2n=32}^{k+1=9}$

$=(\lceil 8{\displaystyle \frac{32}{64}}\rfloor ,\lceil -28{\displaystyle \frac{32}{64}}\rfloor ,\lceil 4{\displaystyle \frac{32}{64}}\rfloor ,\lceil -32{\displaystyle \frac{32}{64}}\rfloor ,\lceil 0{\displaystyle \frac{32}{64}}\rfloor ,\lceil 31{\displaystyle \frac{32}{64}}\rfloor ,\lceil -6{\displaystyle \frac{32}{64}}\rfloor ,\lceil 7{\displaystyle \frac{32}{64}}\rfloor ,\lceil 24{\displaystyle \frac{32}{64}}\rfloor )$

$$

$=(4,-14,2,-16,0,16,-3,4,12)$

$$

Note that $\underset{i=0}{\overset{7}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}({\widehat{a}}_i{s}_i)+\widehat{\mathrm{\Delta }}m+\widehat{e}=(4-16+16+4)+4+1=13\in {\mathbb{Z}}_{2n=32}$

$$

$\widehat{b}=12\approx 13=\underset{i=0}{\overset{7}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}({\widehat{a}}_i{s}_i)+\widehat{\mathrm{\Delta }}m+\widehat{e}$

This small difference in $\widehat{b}$ comes from the aggregated noises of rounding ${\widehat{a}}_0,{\widehat{a}}_1,\cdots ,\widehat{e}$ during the modulus switch.

$$

2.

Blind Rotation: We assume that the application avoids the problem of negacyclic polynomial rotation by ensuring that the usable plaintext values are the following continuous ${\displaystyle \frac{8}{2}}$ modulo values within ${\mathbb{Z}}_8=\{-4,-3,-2,-1,0,1,2,3\}$, which are $\{-2,-1,0,1\}$. This implies that the only possible values of $i=\widehat{\mathrm{\Delta }}m+\widehat{e}$ in $V(X)\cdot X^i$ will be: $i=\{-8,-7,\cdots ,6,7\}$. Based on these requirements, Table 4 is the Lookup Table polynomial $V(X)$ that maps $\widehat{\mathrm{\Delta }}m+\widehat{e}$ to $\mathrm{\Delta }m$.

$V(X)=v_0+v_{1}X+v_2{X}^2+v_3{X}^3+v_4{X}^4+v_5{X}^5+v_6{X}^6+v_7{X}^7$

...... $+v_8{X}^8+v_9{X}^9+v_{10}{X}^{10}+v_{11}{X}^{11}+v_{12}{X}^{12}+v_{13}{X}^{13}+v_{14}{X}^{14}+v_{15}{X}^{15}$

....$=0+0X+0X^2+0X^3+1X^4+1X^5+1X^6+1X^7$

......$+2X^8+2X^9+2X^{10}+2X^{11}+1X^{12}+1X^{13}+1X^{14}+1X^{15}$

$i=\widehat{\mathrm{\Delta }}m+\widehat{e}$	$-8$	$-7$	$-6$	$-5$	$-4$	$-3$	$-2$	$-1$
(in $V\cdot X^{-i}$)	($110{00}_2$)	($110{01}_2$)	($110{10}_2$)	($110{11}_2$)	($111{00}_2$)	($111{01}_2$)	($111{10}_2$)	($111{11}_2$)
constant term’s	$-2$	$-2$	$-2$	$-2$	$-1$	$-1$	$-1$	$-1$
coeff. of $V\cdot X^{-i}$	${110}_2$	${110}_2$	${110}_2$	${110}_2$	${111}_2$	${111}_2$	${111}_2$	$111{00}_2$
$𝐦$ (plaintext)	$-2$	$-2$	$-2$	$-2$	$-1$	$-1$	$-1$	$-1$
$i=\widehat{\mathrm{\Delta }}m+\widehat{e}$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
(in $V\cdot X^{-i}$)	(${000}_2$)	(${000}_2$)	(${000}_2$)	(${000}_2$)	(${001}_2$)	(${001}_2$)	(${001}_2$)	(${001}_2$)
constant term’s	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
coeff. of $V\cdot X^{-i}$	$000{00}_2$	$000{00}_2$	$000{00}_2$	$000{00}_2$	$001{00}_2$	$001{00}_2$	$001{00}_2$	$001{00}_2$
$𝐦$ (plaintext)	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$

Note that $V(X)$’s coefficients for the $X^8\sim X^{15}$ terms are $\{2,1\}$ instead of $\{-2,-1\}$, so that if $V$ gets rotated by $\{-8,-7,-6,-5,4,5,6,7\}$ slots to the left, the constant term’s coefficient flips its sign to $\{-2,-1\}$due to wrapping around the boundary of the $n$ exponent.

During the actual bootstrapping, we will do a blind rotation of Table 4’s $V(X)$ (which is GLWE-encrypted) by $\widehat{b}-\underset{i=0}{\overset{7}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\widehat{a}}_i{s}_i=4$ positions to the left, which is computed as follows:

$\widehat{\mathrm{\Delta }}m+\widehat{e}=\widehat{b}-\underset{i=0}{\overset{7}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\widehat{a}}_i{s}_i=12-(4-16+16+4)=4\text{ mod 32}\in {\mathbb{Z}}_{2n=32}$

In Table 4, if the rotation count $i=4$, the corresponding constant term’s coefficient is $v_4=1=m$. As $\mathrm{\Delta }=4$, we finally get ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)=1$.

$$

The actual blind rotation is computed as follows:

$\overrightarrow{s}=(1,0,0,1,1,1,0,1)$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\widehat{\mathrm{\Delta }}m)=({\widehat{a}}_0,{\widehat{a}}_1,{\widehat{a}}_2,{\widehat{a}}_3,{\widehat{a}}_4,{\widehat{a}}_5,{\widehat{a}}_6,{\widehat{a}}_7,\widehat{b})=(4,-14,2,-16,0,16,-3,4,12)$

$V_0=V\cdot X^{-\widehat{b}}=V\cdot X^{-12}=v_{12}+v_{13}X+v_{14}{X}^2+\cdots$

$V_1=V_0\cdot X^{{\widehat{a}}_0{s}_0}=s_0\cdot (V_0\cdot X^{{\widehat{a}}_0}-V_0)+V_0=V_0\cdot X^4=v_8+v_{9}X+v_{10}{X}^2+\cdots$

$V_2=V_1\cdot X^{{\widehat{a}}_1{s}_1}=s_1\cdot (V_1\cdot X^{{\widehat{a}}_1}-V_1)+V_1=V_1=v_8+v_{9}X+v_{10}{X}^2+\cdots$

$V_3=V_2\cdot X^{{\widehat{a}}_2{s}_2}=s_2\cdot (V_2\cdot X^{{\widehat{a}}_2}-V_2)+V_2=V_2=v_8+v_{9}X+v_{10}{X}^2+\cdots$

$V_4=V_3\cdot X^{{\widehat{a}}_3{s}_3}=s_3\cdot (V_3\cdot X^{{\widehat{a}}_3}-V_3)+V_3=V_3\cdot X^{-16}=-v_8-v_{9}X-v_{10}{X}^2-\cdots$

$V_5=V_4\cdot X^{{\widehat{a}}_4{s}_4}=s_4\cdot (V_4\cdot X^{{\widehat{a}}_4}-V_4)+V_4=V_4\cdot X^0=-v_8-v_{9}X-v_{10}{X}^2-\cdots$

$V_6=V_5\cdot X^{{\widehat{a}}_5{s}_5}=s_5\cdot (V_5\cdot X^{{\widehat{a}}_5}-V_5)+V_5=V_5\cdot X^{16}=v_8+v_{9}X+v_{10}{X}^2+\cdots$

$V_7=V_6\cdot X^{{\widehat{a}}_6{s}_6}=s_6\cdot (V_6\cdot X^{{\widehat{a}}_6}-V_6)+V_6=V_6=v_8+v_{9}X+v_{10}{X}^2+\cdots$

$V_8=V_7\cdot X^{{\widehat{a}}_7{s}_7}=s_7\cdot (V_7\cdot X^{{\widehat{a}}_7}-V_7)+V_7=V_7\cdot X^4=v_4+v_{5}X+v_6{X}^2+\cdots$

$$

The final output of blind rotation is the GLWE ciphertext of $V_8$, ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_8)$, whose constant term’s coefficient is $v_4=m=1$.

$$

Each step of the actual blind rotation above is computed as the following TFHE ciphertext-to-ciphertext multiplication:

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_{i+1})={\mathsf{\text{𝖦𝖦𝖲𝖶}}}_{\overrightarrow{S},\sigma }^{\beta ,l}(s_i)\cdot ({\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_i)\cdot X^{a_0}-{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_i))+{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_i)$

$$

We will leave this computation for the reader’s exercise.

$$

3.

Coefficient Extraction: At the end of blind rotation, we finally get the following GLWE ciphertext:

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(V_8)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(\widehat{\mathrm{\Delta }}\cdot (v_4+v_{5}X+v_6{X}^2+v_7{X}^3+v_8{X}^4+v_9{X}^5+v_{10}{X}^6+v_{11}{X}^7+v_{12}{X}^8+v_{13}{X}^9+v_{14}{X}^{10}+v_{15}{X}^{11}-v_0{X}^{12}-v_1{X}^{13}-v_2{X}^{14}-v_3{X}^{15}))$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(\widehat{\mathrm{\Delta }}\cdot (1+1X+1X^2+1X^3+2X^4+2X^5+2X^6+2X^7+1X^8+1X^9+1X^{10}+1X^{11}-0X^{12}-0X^{13}-0X^{14}-0X^{15}))$

$=\left(A_0=\underset{j=0}{\overset{15}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(a_{0,0}+a_{0,1}X+\cdots ),A_1=\cdots ,A_{k-1}=\cdots ,B=\sum _{j=0}^{15}{b}_j{X}^j\right)$

Now, we extract the constant term’s coefficient of the encrypted polynomial ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(\widehat{\mathrm{\Delta }}\cdot (1+1X+1X^2+\cdots ))$ by using the coefficient extraction formula (Summary D-1.7). Specifically, we will extract the constant term’s coefficient, which corresponds to ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }{m}_0)$. We extract ${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }{m}_0)$ by computing the following:

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }{m}_0)=(a_0^{\prime },a_1^{\prime },\cdots ,a_k^{\prime },b_h)$

$$\text{, where }{a}_{n\cdot i+j}^{\prime }=\{\begin{array}{c}{a}_{i,0-j}\text{ (if }0\le j\le 0\text{)}\hfill \\ a_{i,n+0-j}\text{ (if }0+1\le j\le n-1\text{)}\hfill \end{array},b_0\text{ is obtained from the polynomial }B$$