D-1.9 TFHE on a Discrete Torus

- Reference: Guide to Fully Homomorphic Encryption over the [Discretized] Torus [11]

Torus $𝕋$ is a continuous real number domain between 0 and 1 that wraps around, that is $[0,1)$.

A discrete torus ${𝕋}_t$ is a finite real number set: $(0,{\displaystyle \frac{1}{t}},{\displaystyle \frac{2}{t}},\cdots ,{\displaystyle \frac{t-1}{t}})$

In the previous subsections, we explained the TFHE scheme based on the following setup:

$m\in {\mathbb{Z}}_t$ $\overrightarrow{s}={\{0,1\}}^k$ $e\in {\mathbb{Z}}_q$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)=(a_0,a_1,\cdots ,a_k,b)\in {\mathbb{Z}}_t^{k+1}$

However, the original TFHE scheme is designed based on a discrete torus:

$m\in {𝕋}_t,\overrightarrow{s}\in {\{0,1\}}^k,e\in {𝕋}_q$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(m)=\mathsf{\text{𝖼𝗍}}=(a_0,a_1,\cdots ,a_k,b)\in {𝕋}_q^{k+1}$

$b=\underset{i=0}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(a_i{s}_i)+m+e\in {𝕋}_q$

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }^{-1}(\mathsf{\text{𝖼𝗍}})=\lceil b-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(a_i{s}_i){\rfloor }_{\frac{1}{t}}=\lceil m+e{\rfloor }_{\frac{1}{t}}=m$, given $e<{\displaystyle \frac{1}{2t}}$

# where $\lceil x{\rfloor }_{\frac{1}{t}}$ means rounding $x$ to the nearest multiple of ${\displaystyle \frac{1}{t}}$

The original TFHE’s difference is that all values (either polynomial coefficients or vector elements) are computed in a floating point modulo 1 (i.e., $[0,1)$) instead of a big integer (i.e., $[0,q)$). This means the plaintext also has to be encoded as values within $[0,1)$ instead of integers within $[0,q)$. Note that in the original TFHE scheme, there is no need for the scaling factor $\mathrm{\Delta }$, because the continuous domain of torus $[0,1)$ provides a floating-point precision up to $q$ discrete decimal values, and its decryption process can successfully blow away the noise $E$ as far as each coefficient (or vector element) $e_i$ in $E$ is smaller than ${\displaystyle \frac{1}{2t}}$.

Both the torus-based and integer-ring-based TFHE schemes are built based on the same fundamental principles.