D-1.7 Coefficient Extraction

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

In TFHE, coefficient extraction is a process of extracting a coefficient of a polynomial that is encrypted as GLWE ciphertext. The extracted coefficient is in the form of LWE ciphertext (§B-2).

Note that in the GLWE cryptosystem, plaintext $M$ is encoded as a polynomial, where each coefficient encodes the plaintext value $m_0,m_1,\cdots ,m_{n-1}$.

Suppose we have a GLWE ciphertext setup as the following:
$M=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{m}_j{X}^j\in R_{⟨n,q⟩}$

$S=\left(S_0=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{s}_{0,j}{X}^j,S_1=\sum _{j=0}^{n-1}{s}_{1,j}{X}^j,\cdots ,S_{k-1}=\sum _{j=0}^{n-1}{s}_{k-1,j}{X}^j\right)$

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(\mathrm{\Delta }M)=\left(A_0=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_{0,j}{X}^j,A_1=\sum _{j=0}^{n-1}{a}_{1,j}{X}^j,\cdots ,A_{k-1}=\sum _{j=0}^{n-1}{a}_{k-1,j}{X}^j,B=\sum _{j=0}^{n-1}{b}_j{X}^j\right)$

$B=\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i+\mathrm{\Delta }M+E$

$E=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{e}_i{X}^i$

Note that:

$\mathrm{\Delta }M+E=B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i$

$=(\mathrm{\Delta }{m}_0+\mathrm{\Delta }{m}_{1}X+\cdots +\mathrm{\Delta }{m}_{n-1}{X}^{n-1})+(e_0+e_{1}X+\cdots +e_{n-1}{X}^{n-1})$

$=(\mathrm{\Delta }{m}_0+e_0)+(\mathrm{\Delta }{m}_1+e_1)X+\cdots +(\mathrm{\Delta }{m}_{n-1}+e_{n-1})X^{n-1}$

Another way to write the formula is:

$B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i$

$=(b_0+b_{1}X+\cdots +b_{n-1}{X}^{n-1})$

$-(a_{0,0}+a_{0,1}X+\cdots +a_{0,n-1}{X}^{n-1})(s_{0,0}+s_{0,1}X+\cdots +s_{0,n-1}{X}^{n-1})$

$-(a_{1,0}+a_{1,1}X+\cdots +a_{1,n-1}{X}^{n-1})(s_{1,0}+s_{1,1}X+\cdots +s_{1,n-1}{X}^{n-1})$

$-\cdots$

$-(a_{k-1,0}+a_{k-1,1}X+\cdots +a_{k-1,n-1}{X}^{n-1})(s_{k-1,0}+s_{k-1,1}X+\cdots +s_{k-1,n-1}{X}^{n-1})$

$=\left(b_0-\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^0(a_{i,0-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=1}^{n-1}(a_{i,n-j}{s}_{i,j})\right)\right)$

$+\left(b_1-\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^1(a_{i,1-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=2}^{n-1}(a_{i,n+1-j}{s}_{i,j})\right)\right)\cdot X$

$+\left(b_2-\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^2(a_{i,2-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=3}^{n-1}(a_{i,n+2-j}{s}_{i,j})\right)\right)\cdot X^2$

$\cdots$

$+\left(b_{n-1}-\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^{n-1}(a_{i,n-1-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=n}^{n-1}(a_{i,n+(n-1)-j}{s}_{i,j})\right)\right)\cdot X^{n-1}$

$▹$ Grouping the terms by same exponents

$=\underset{h=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left(b_h-\left(\sum _{i=0}^{k-1}\sum _{j=0}^h(a_{i,h-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=h+1}^{n-1}(a_{i,n+h-j}{s}_{i,j})\right)\right)\cdot X^h$

$=\underset{h=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{C}_h\cdot X^h$, where $C_h=b_h-\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^h(a_{i,h-j}{s}_{i,j})-\sum _{i=0}^{k-1}\sum _{j=h+1}^{n-1}(a_{i,n+h-j}{s}_{i,j})\right)$

In the above $(n-1)$-degree polynomial, notice that each $X^h$ term’s coefficient, $C_h$, can be expressed as an LWE ciphertext ${\mathsf{\text{𝖼𝗍}}}_h$ as follows:

$S^{\prime }=(s_{0,0},s_{0,1},\cdots ,s_{0,n-1},s_{1,0},s_{1,1},\cdots ,s_{1,n-1},\cdots ,s_{k-1,n-1})=(s_0^{\prime },s_1^{\prime },\cdots ,s_{\mathit{𝑛𝑘}-1}^{\prime })\in {\mathbb{Z}}_q^{\mathit{𝑛𝑘}}$

${\mathsf{\text{𝖼𝗍}}}_h=(a_0^{\prime },a_1^{\prime },\cdots ,a_{\mathit{𝑛𝑘}-1}^{\prime },b_h)\in {\mathbb{Z}}_q^{\mathit{𝑛𝑘}+1}$

Note that $b_h-\underset{i=0}{\overset{\mathit{𝑛𝑘}-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{s}_i^{\prime }{a}_i^{\prime }=\mathrm{\Delta }{m}_h+e_h$. This means that $C_h$ can be replaced by its encrypted version, ${\mathsf{\text{𝖫𝖶𝖤}}}_{{\overrightarrow{s}}_{{}^{\prime }},\sigma }(\mathrm{\Delta }{m}_h)$, an LWE ciphertext ${\mathsf{\text{𝖼𝗍}}}_h$ encrypting the $h$-th coefficient of $M$. Therefore, we just extracted ${\mathsf{\text{𝖫𝖶𝖤}}}_{{\overrightarrow{s}}_{{}^{\prime }},\sigma }(\mathrm{\Delta }{m}_h)$ from ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{\overrightarrow{S},\sigma }(\mathrm{\Delta }M)$. This operation is called coefficient extraction, which does not add any noise because it simply extracts an LWE ciphertext by reordering the polynomial of the GLWE ciphertext.

Once we have ${\mathsf{\text{𝖫𝖶𝖤}}}_{{\overrightarrow{s}}_{{}^{\prime }},\sigma }(\mathrm{\Delta }{m}_h)$, we can key-switch it from ${\overrightarrow{s}}_{{}^{\prime }}\to \overrightarrow{s}$ (§D-1.5).