A Practical TFHE-Based Multi-Key Homomorphic Encryption with Linear Complexity and Low Noise Growth

Abstract

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties. In this paper, we propose a new variant of MKHE instantiated with the $\textsf{TFHE}$ scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5–$6.9\times$, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our seven setups, each running $1\,000$ trials.

This work was supported by the MESRI-BMBF French-German joint project UPCARE (ANR-20-CYAL-0003-01). Find the full version at https://ia.cr/2023/065.

A Technical Description of \(\textsf{TFHE}\)

We provide a technical description of the $\textsf{TFHE}$ scheme in a form of self-descriptive algorithms. Parameters and secret keys are considered implicit inputs.

Given security parameter $\lambda$, generate parameters for:

• $\textsf{LWE}$ encryption: dimension n, standard deviation $\alpha > 0$ (of the noise);

• $\textsf{LWE}$ decomposition: base $B'$, depth $d'$;

• set up $\textsf{LWE}$ gadget vector: $\textbf{g}' \leftarrow (\nicefrac {1}{B'}, \nicefrac {1}{{B'}^2}, \ldots , \nicefrac {1}{{B'}^{d'}})$;

• $\textsf{RLWE}$  encryption: polynomial degree N (a power of two), standard deviation $\beta > 0$;

• $\textsf{RLWE}$  decomposition: base B, depth d;

• set up $\textsf{RLWE}$  gadget vector: $\textbf{g}\leftarrow (\nicefrac {1}{B}, \nicefrac {1}{B^2}, \ldots , \nicefrac {1}{B^d})$.

Other input parameters of the Setup algorithm may include the maximal allowed probability of error, or the plaintext space size (for other than Boolean circuits).

Generate secret keys for:

• $\textsf{LWE}$ encryption: $\textbf{s}{\mathop {\leftarrow }\limits ^{\$}}\mathbb {B} ^n$;

• $\textsf{RLWE}$  encryption: $z {\mathop {\leftarrow }\limits ^{\$}}\mathbb {B} ^{(N)}[X]$, (alternatively $z_i {\mathop {\leftarrow }\limits ^{\zeta }} \{-1,0,1\}$ for some distribution $\zeta$).

For $\textsf{LWE}$ key $\textbf{s}\in \mathbb {B} ^n$, we denote $\bar{\textbf{s}} {:}{=}(1,\textbf{s}) \in \mathbb {B} ^{1+n}$ the extended secret key, similarly for an $\textsf{RLWE}$  key $z\in \mathbb {Z} ^{(N)}[X]$, we denote $\bar{\textbf{z}} {:}{=}(1,z) \in \mathbb {Z} ^{(N)}[X] ^2$.

Given message $\mu \in \mathbb {T}$, sample fresh mask $\textbf{a}{\mathop {\leftarrow }\limits ^{\$}}\mathbb {T} ^n$ and noise $e {\mathop {\leftarrow }\limits ^{\alpha }} \mathbb {T}$. Evaluate $b \leftarrow -\langle \textbf{s}, \textbf{a}\rangle + \mu + e$ and output $\bar{\textbf{c}} = (b, \textbf{a}) \in \mathbb {T} ^{1+n}$, an $\textsf{LWE}$ encryption of $\mu$. This algorithm is used as the main encryption algorithm of the scheme. We generalize this as well as subsequent algorithms to input vectors and proceed element-by-element.

Given message $m \in \mathbb {T} ^{(N)}[X]$, sample fresh mask $a {\mathop {\leftarrow }\limits ^{\$}}\mathbb {T} ^{(N)}[X]$, unless explicitly given. If the pair $(a,z_{in})$ has been used before, output $\bot$. Otherwise, sample fresh noise $e \in \mathbb {T} ^{(N)}[X]$, $e_i {\mathop {\leftarrow }\limits ^{\beta }} \mathbb {T}$, and evaluate $b \leftarrow -z_{in} \cdot a + m + e$. Output $\bar{\textbf{c}} = (b, a) \in \mathbb {T} ^{(N)}[X] ^2$, an $\textsf{RLWE}$  encryption of m. In case a is given, we may limit the output to only b.

Given $\mathsf {(R)LWE}$  sample $\bar{\textbf{c}}$, evaluate and output $\varphi \leftarrow \langle \bar{\textbf{s}}, \bar{\textbf{c}} \rangle$, where $\bar{\textbf{s}}$ is respective $\mathsf {(R)LWE}$  extended secret key.

Set $\mu = \pm \nicefrac {1}{8}$ for b true or false, respectively. Output $\mathtt{LweSymEncr(\mu )}$.

Output $\mathtt{LwePhase(\bar{\textbf{c}})} > 0$, assuming $\mathbb {T} \sim [-\nicefrac {1}{2},\nicefrac {1}{2})$.

Given $m\in \mathbb {Z} ^{(N)}[X]$, evaluate $\textbf{Z}\leftarrow \mathtt{RLweSymEncr(\textbf{0})}$, where $\textbf{0}$ is a vector of 2d zero polynomials (i.e., $\textbf{Z}\in (\mathbb {T} ^{(N)}[X])^{2d\times 2}$). Output $\textbf{Z}+ m\cdot \textbf{G}$, an $\textsf{RGSW}$  sample of m.

Given $\textsf{RGSW}$  sample $\textsf{BK}$ of $s\in \mathbb {Z} ^{(N)}[X]$, and $\textsf{RLWE}$  sample (b, a) of $m\in \mathbb {T} ^{(N)}[X]$, evaluate and output:

(14)

which is an $\textsf{RLWE}$  sample of $s \cdot m \in \mathbb {T} ^{(N)}[X]$; in $\textsf{TFHE}$ also referred to as the external product.

Given $\bar{\textbf{c}} = (b, a_1, \ldots , a_n) \in \mathbb {T} ^{1+n}$, an $\textsf{LWE}$ sample of $\mu \in \mathbb {T}$ under key $\textbf{s}\in \mathbb {B} ^n$; $(\textsf{BK} _i)_{i=1}^n$, $\textsf{RGSW}$  samples of $\textbf{s}_i$ under $\textsf{RLWE}$  key z (aka. blind-rotate keys); and $\textsf{RLWE}\,\,_z(tv) \in \mathbb {T} ^{(N)}[X] ^2$, (usually trivial) $\textsf{RLWE}$  sample of $tv \in \mathbb {T} ^{(N)}[X]$ (aka. test vector), evaluate:

Output $\textsf{ACC} = \textsf{RLWE}\,\,_z(X^{\tilde{\varphi }} \cdot tv)$, an $\textsf{RLWE}$  encryption of test vector “rotated” by $\tilde{\varphi }$, where $\tilde{\varphi } = \lfloor 2Nb \rceil + s_1 \lfloor 2Na_1 \rceil + \ldots + s_n \lfloor 2Na_n \rceil \approx 2N (\bar{\textbf{s}} \cdot \bar{\textbf{c}}) \approx 2N\mu$.

Given $\textsf{RLWE}$  key $z\in \mathbb {Z} ^{(N)}[X]$, output $\textbf{z}^* \leftarrow (z_0, -z_{N-1},\ldots ,-z_1)$.

Given $\textsf{RLWE}$  sample $(b,a) \in \mathbb {T} ^{(N)}[X] ^2$ of $m\in \mathbb {T} ^{(N)}[X]$ under $\textsf{RLWE}$  key $z\in \mathbb {Z} ^{(N)}[X]$, output $\textsf{LWE}$ sample $(b', \textbf{a}') \leftarrow (b_0, a_0, \ldots ,a_{N-1}) \in \mathbb {T} ^{1+N}$ of $m_0 \in \mathbb {T}$ (the constant term of m) under the extracted $\textsf{LWE}$ key $\textbf{z}^* = \texttt{KeyExtract}(z)$.

For $j \in [1,N]$, evaluate and output a key-switching key for $z_j$ and $\textbf{s}$: $\textsf{KS} _j \leftarrow \texttt{LweSymEncr}\bigl ( \textbf{z}_j^* \cdot \textbf{g}' \bigr )$, where $\textbf{z}^* \leftarrow \texttt{KeyExtract}(z)$. $\textsf{KS} _j$ is a $d'$-tuple of $\textsf{LWE}$ samples of $\textbf{g}'$-respective fractions of $\textbf{z}_j^*$ under the key $\textbf{s}$.

Given $\textsf{LWE}$ sample $\bar{\textbf{c}}' = (b',a'_1,\ldots ,a'_N) \in \mathbb {T} ^{1+N}$ (extraction of an $\textsf{RLWE}$  sample), which encrypts $\mu \in \mathbb {T}$ under the extraction of an $\textsf{RLWE}$  key $\textbf{z}^* = \texttt{KeyExtract}(z)$, and a set of key-switching keys for z and $\textbf{s}$, evaluate and output

$$\begin{aligned} \bar{\textbf{c}}'' \leftarrow (b',\textbf{0}) + \sum _{j=1}^N \textbf{g}'^{-1}(a'_j)^T \cdot \textsf{KS} _j , \end{aligned}$$

(15)

which is an $\textsf{LWE}$ sample of the same $\mu \in \mathbb {T}$ under the $\textsf{LWE}$ key $\textbf{s}$.

Given $\textsf{LWE}$ sample $\bar{\textbf{c}}$ of $\mu \in \mathbb {T}$ under $\textsf{LWE}$ key $\textbf{s}$, test vector $tv\in \mathbb {T} ^{(N)}[X]$ that encodes a $\textsf{LUT}$, and two sets of keys for blind-rotate and for key-switching (aka. bootstrapping keys – the evaluation keys of $\textsf{TFHE}$), evaluate:

Output $\bar{\textbf{c}}''$, which is an $\textsf{LWE}$ sample of—vaguely speaking—“evaluation of the $\textsf{LUT}$ at $\mu$”, under the key $\textbf{s}$, with a refreshed noise. Details on the encoding of the $\textsf{LUT}$ are out of the scope of this paper.

Output $\overline{\textbf{c}}_1 + \overline{\textbf{c}}_2$, which encrypts the sum of input plaintexts. Using just “$+$”.

Given encryptions of bools $b_1$ and $b_2$ under $\textsf{LWE}$ key $\textbf{s}$, and bootstrapping keys for $\textbf{s}$ and z, set the test vector as $tv \leftarrow \nicefrac {1}{8} \cdot (1 + X + X^2 + \ldots + X^{N-1})$. Output $\bar{\textbf{c}}'' \leftarrow \texttt{Bootstrap}\bigl ( \nicefrac {1}{8} - \overline{\textbf{c}}_1 - \overline{\textbf{c}}_2, tv, \{\textsf{BK} _i\}_{i=1}^n, \{\textsf{KS} _j\}_{j=1}^{N} \bigr )$, which is an encryption of $\lnot (b_1 \wedge b_2)$ under the key $\textbf{s}$.