Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity

Abstract

Multi-key homomorphic encryption is a generalized notion of homomorphic encryption supporting arbitrary computation on ciphertexts, possibly encrypted under different keys. In this paper, we revisit the work of Chen, Chillotti and Song (ASIACRYPT 2019) and present yet another multi-key variant of the TFHE scheme.

The previous construction by Chen et al. involves a blind rotation procedure where the complexity of each iteration gradually increases as it continuously operates on ciphertexts under different keys. Hence, the complexity of gate bootstrapping grows quadratically with respect to the number of associated keys.

Our scheme is based on a new blind rotation algorithm which consists of two separate phases. We first split a given multi-key ciphertext into several single-key ciphertexts, take each of them as input to the blind rotation procedure, and obtain accumulators corresponding to individual keys. Then, we merge these single-key accumulators into a single multi-key accumulator. In particular, we develop a novel homomorphic operation between single-key and multi-key ciphertexts to instantiate our pipeline. Therefore, our construction achieves an almost linear time complexity since the gate bootstrapping is dominated by the first phase of blind rotation which requires only independent single-key operations. It also enjoys with great advantages of parallelizability and key-compatibility.

We implement the proposed scheme and provide its performance benchmark. For example, our 16-key gate bootstrapping takes about 5.65 s, which is 4.38x faster compared to the prior work.

Appendices

A Multi-key TFHE Variant Using Different Gadget Decompositions

We provide the algorithms of our new MK-TFHE scheme with different gadget decompositions. The encryption and decryption algorithms are the same as given in Sect. 4.3.

$\bullet ~\underline{\texttt {Setup}(1^\lambda )}$: Given the security parameter $\lambda$, return the following parameters:

• An LWE dimension n, a key distribution $\chi '$ over ${\mathbb Z}^n$, and an error variance $\alpha > 0$.

• An RLWE dimension N, a key distribution $\chi$ over $R={\mathbb Z}[X]/(X^N+1)$, and an error variance $\beta > 0$.

• A CRS $\textbf{a}\leftarrow T^{d_{uni}}$.

• 4 pairs of gadget decompositions and gadget vectors.

  • A gadget decomposition $h_{ksk}$ of key-switching key and the corresponding gadget vector ${\textbf{g}}_{ksk}$ with base $B_{ksk}$ and degree $d_{ksk}$.

  • A gadget decomposition $h_{gsw}$ of RGSW encryption and the corresponding gadget vector ${\textbf{g}}_{gsw}$ with base $B_{gsw}$ and degree $d_{gsw}$.

  • A gadget decomposition $h_{lev}$ of RLEV encryption and the corresponding gadget vector ${\textbf{g}}_{lev}$ with base $B_{lev}$ and degree $d_{lev}$.

  • A gadget decomposition $h_{uni}$ of uni-encryption and the corresponding gadget vector ${\textbf{g}}_{uni}$ with base $B_{uni}$ and degree $d_{uni}$.

$\bullet ~\underline{\texttt{KeyGen}(i)}$: A party i generates its secret and public keys as follows.

• Sample LWE secret key ${\textbf{z}}_i = (z_{i, 0}, \dots , z_{i, n-1}) \leftarrow \chi$.

• Sample RLWE secret key $s_i = s_{i,0} + s_{i,1}X + \cdots + s_{i, N-1}X^{N-1} \leftarrow \chi '$ and error ${\textbf{e}}\leftarrow {\psi }^{d_{uni}}$. Compute ${\textbf{b}}_i = -s_i \cdot \textbf{a}+ {\textbf{e}}\pmod 1$ and set the public key as $\textsf{pk}_i = {\textbf{b}}_i$.

$\bullet ~\underline{\texttt{BootKeyGen}(i)}$: A party i generates and publishes a blind rotation key $\textsf{brk}_i$, a relinearization key $\textsf{rlk}_i$ and a key-switching key $\textsf{ksk}_i$ as follows.

• Sample $t_i \leftarrow \chi '$ and generate $\textsf{brk}_{i,j} \leftarrow \texttt{RGSW}.\texttt{Enc}_{h_{gsw}}(t_i;z_{i,j})$ for $0 \le j < n$. Set the blind rotation key $\textsf{brk}_i = \{\textsf{brk}_{i,j}\}_{0 \le j < n}$.

• Generate the relinearization key $\textsf{rlk}_i \leftarrow \texttt{UniEnc}_{h_{uni}}(s_i;t_i)$.

• Let $(s^*_{i, 0}, \dots , s^*_{i, N-1}) = (s_{i,0}, -s_{i, N-1}, \dots , -s_{i, 1})$. Sample ${\textbf{A}}_{i,j} \leftarrow {\mathbb T}^{d_{ksk}\times n}$ and ${\textbf{e}}_{i,j} \leftarrow {\psi }'^{d_{ksk}}$ for $0 \le j < N$, and let $\textsf{ksk}_{i,j} = [{\textbf{b}}_{i,j}|{\textbf{A}}_{i,j}]$ where ${\textbf{b}}_{i,j} = -{\textbf{A}}_{i,j} \cdot {\textbf{s}}_i + {\textbf{e}}_{i,j} + s^*_{i,j} \cdot {\textbf{g}}_{ksk}$. Set the key-switching key $\textsf{ksk}_i = \{\textsf{ksk}_{i,j}\}_{0 < N}$.

$\bullet ~\underline{\texttt{HomNAND}(\{(\textsf{pk}_i, \textsf{brk}_i, \textsf{rlk}_i, \textsf{ksk}_i)\}_{i \in [k]};\overline{\textsf{ct}}_1, \overline{\textsf{ct}}_2)}$: Given two $\textsf{LWE}$ ciphertexts $\overline{\textsf{ct}}_1$, $\overline{\textsf{ct}}_2$ and key-quadruple $\{(\textsf{pk}_i, \textsf{brk}_i, \textsf{rlk}_i, \textsf{ksk}_i)\}_{i \in [k]}$ of associated parties, perform the following steps:

• 1. Compute $\overline{\textsf{ct}}\leftarrow (\frac{5}{8}, 0, \dots , 0) - \overline{\textsf{ct}}_1 - \overline{\textsf{ct}}_2 \pmod 1$.

• 2. Compute $\overline{\textsf{ct}}\leftarrow \texttt{BlindRotate}(\{(\textsf{pk}_i, \textsf{brk}_i, \textsf{rlk}_i)\}_{i \in [k]};\overline{\textsf{ct}})$ where $\texttt{BlindRotate}(\cdot )$ is the blind rotation algorithm in Algorithm 3.

• 3. Compute $\overline{\textsf{ct}}\leftarrow (\frac{1}{8}, 0, \dots , 0) + \overline{\textsf{ct}}\pmod 1$ and return $\textsf{ct}= (b, \textbf{a}_1, \dots , \textbf{a}_k) \in {\mathbb T}^{kN+1}$ where b is the constant term of $\overline{\textsf{ct}}_0$ and $\textbf{a}_i$ is the coefficient vector of $\overline{\textsf{ct}}_i$ for $i \in [k]$.

• 4. Perform the key-switching process: Compute $(b'_i, \textbf{a}'_i) = \sum _{j=0}^{N-1} h'(a_{i,j}) \cdot \textsf{ksk}_{i,j} \pmod 1$ for $i \in [k]$ and $b' = b + \sum _{i\in [k]} b'_i$. Return $\textsf{ct}' = (b', \textbf{a}'_1, \dots , \textbf{a}'_k) \in {\mathbb T}^{kn+1}$.

Algorithm 3

. New Blind Rotation using Different Gadget Decompositions

B Proofs for the Noise Analysis

First we define $\textsf{GdErr}_{gsw}$, $\textsf{GdErr}_{lev}$ and $\textsf{GdErr}_{uni}$, the gadget decomposition error of $h_{gsw}, h_{lev}$ and $h_{uni}$ respectively.

Proof of Lemma 1 (T-RLEV Multiplication)

Proof

By definition, we have

$$\begin{aligned} \varphi _s(c \odot {\textbf{C}}) &= \left\langle h_{lev}(c), \varphi _s({\textbf{C}})\right\rangle \\ &= \left\langle h_{lev}(c), \mu \cdot {\textbf{g}}_{lev}+ \textsf {Err}({\textbf{C}})\right\rangle \\ &= \mu \cdot c + \mu \cdot \textsf{GdErr}_{lev}(c) + \left\langle h_{lev}(c), \textsf {Err}({\textbf{C}})\right\rangle \pmod 1. \end{aligned}$$

Therefore $e = \mu \cdot \textsf{GdErr}_{lev}(c) + \left\langle h_{lev}(c), \textsf {Err}({\textbf{C}})\right\rangle$. Since $h_{lev}(c)$ and $\textsf {err}({\textbf{C}})$ are vectors of length $d_{lev}$, we get

$$\textsf {Var}(e) = \Vert \mu \Vert _2^2\epsilon _{lev}^2 + d_{lev}N V_{lev}\textsf {Var}\textsf {Err}({\textbf{C}})$$

   $\square$

Proof of Lemma 2 (RLWE-RGSW Multiplication)

Proof

Let ${\textbf{c}}= (b, a)$ and $\textsf {Err}({\textbf{C}}) = \begin{bmatrix} {\textbf{e}}_0 \\ {\textbf{e}}_1 \end{bmatrix}$ where ${\textbf{e}}_0, {\textbf{e}}_1 \in T^{d_{gsw}}$. Then we can obtain

$$\begin{aligned} \varphi _s({\textbf{c}}\otimes \overline{\textbf{C}}) &= \left\langle h_{gsw}({\textbf{c}}), \varphi _s(\overline{\textbf{C}})\right\rangle \\ &= \left\langle h_{gsw}(b), \mu \cdot {\textbf{g}}_{gsw}+{\textbf{e}}_0\right\rangle +\left\langle h_{gsw}(a), \mu \cdot s\cdot {\textbf{g}}_{gsw}+{\textbf{e}}_1\right\rangle \\ &= \mu \cdot \varphi _s({\textbf{c}})+\mu \cdot (\textsf{GdErr}_{gsw}(b)+\textsf{GdErr}_{gsw}(a)s)+\left\langle h_{gsw}({\textbf{c}}), \textsf {Err}(\overline{\textbf{C}})\right\rangle \pmod 1. \end{aligned}$$

Therefore, we can get the following error variance.

$$ \textsf {Var}(e) = (1 + N/2) \Vert \mu \Vert _2^2\epsilon _{gsw}^2 + 2d_{gsw}N V_{gsw}\textsf {Var}\textsf {Err}(\overline{\textbf{C}}).$$

   $\square$

Proof of Corollary 1 (RLEV-RGSW Multiplication)

Proof

An RLEV ciphertext can be seen as a column vector of RLWE ciphertexts. Therefore, this corollary can be shown directly from the previous lemma.    $\square$

For efficiency, we prove Lemma 4 first, and then prove Lemma 3.

Proof of Lemma 4 (New Hybrid Product)

Proof

We shall use ${\textbf{e}}_0 = {\textbf {0}}$ and the same temporary variables as in the algorithm description for the easier notation. Let ${\textbf{u}}= (u_0, \dots , u_k)$ and ${\textbf{w}}= (w_0, w_1)$. Then we have $\varphi _{\overline{{\textbf{s}}}}(\overline{\textsf{ct}}') = \varphi _{\overline{{\textbf{s}}}}({\textbf{u}}) + \varphi _{s_i}({\textbf{w}}) \pmod 1$. The first term is

$$\begin{aligned} \varphi _{\overline{{\textbf{s}}}}(u) &= \sum _{j=0}^k \left\langle h_{uni}(c_j), r\cdot \textbf{a}+ \mu \cdot {\textbf{g}}_{uni}+ {\textbf{e}}_{i, 1}\right\rangle \cdot s_j \\ &= \mu \cdot \varphi _{\overline{{\textbf{s}}}}(\overline{\textsf{ct}}) + \mu \cdot \sum _{j=0}^k\textsf{GdErr}_{uni}(c_j) \cdot s_j + r\cdot \sum _{j=0}^k\left\langle h_{uni}(c_j), s_j \cdot \textbf{a}\right\rangle \\ &+ \sum _{j=0}^k\left\langle h_{uni}(c_j), {\textbf{e}}_{i, 1}\right\rangle \cdot s_j \pmod 1 , \end{aligned}$$

and the second term is

$$\begin{aligned} \varphi _{s_i}({\textbf{w}}) &= \left\langle h_{uni}(v), {\textbf{F}}_{i, 0}\right\rangle + \left\langle h_{uni}(v), {\textbf{F}}_{i, 1}\right\rangle \cdot s_i \\ &= \left\langle h_{uni}(v), r\cdot {\textbf{g}}_{uni}+ {\textbf{e}}_{i, 2}\right\rangle \\ &= r\cdot v + r \cdot \textsf{GdErr}_{uni}(v) + \left\langle h_{uni}(v), {\textbf{e}}_{i, 2}\right\rangle \pmod 1. \end{aligned}$$

Now, from the fact that

$$\begin{aligned} v + \sum _{j=0}^k \left\langle h_{uni}(c_j), s_j \cdot \textbf{a}\right\rangle &= \sum _{j=0}^k (\left\langle h_{uni}(c_j), {\textbf{b}}_j\right\rangle + \left\langle h_{uni}(c_j), s_j \cdot \textbf{a}\right\rangle ) \\ &= \sum _{j=1}^k \left\langle h_{uni}(c_j), {\textbf{e}}_j\right\rangle \pmod 1 , \end{aligned}$$

it follows that $e = \varphi _{\overline{\textbf{s}}} (\overline{\textsf{ct}}') - \mu \cdot \varphi _{\overline{\textbf{s}}} (\overline{\textsf{ct}})$ is

$$\begin{aligned} &\mu \cdot \sum _{j=0}^k\textsf{GdErr}_{uni}(c_j) \cdot s_j + \sum _{j=0}^k\left\langle h_{uni}(c_j), {\textbf{e}}_{i, 1}\right\rangle \cdot s_j + \\ r \cdot &\textsf{GdErr}_{uni}(v) + \left\langle h_{uni}(v), {\textbf{e}}_{i, 2}\right\rangle + r\cdot \sum _{j=1}^k\left\langle h_{uni}(c_j), {\textbf{e}}_j\right\rangle . \end{aligned}$$

Therefore, we have

$$\begin{aligned} \textsf {Var}(e) &= \Vert \mu \Vert _2^2 (1 + kN/2)N \epsilon _{uni}^2 + (1+kN/2)d_{uni}NV_{uni}\beta ^2 \\ & + (N/2)\epsilon _{uni}^2 + d_{uni}NV_{uni}\beta ^2 + kd_{uni}(N^2/2)V_{uni}\beta ^2 \\ &\approx \frac{k}{2}\Vert \mu \Vert _2^2N^2\epsilon _{uni}^2 + kd_{uni}N^2 V_{uni}\beta ^2. \end{aligned}$$

   $\square$

Proof of Lemma 3 (Hybrid Product)

Proof

The only difference of the error variance of $\texttt{HbProd}$ to the error variance $\texttt{NewHbProd}$ is the error from $w_{j, 0}$ and $w_{j, 1}$’s, which is $k+1$ times bigger than $\texttt{NewHbProd}$. Therefore, we get the error variance of

$$\begin{aligned} \textsf {Var}(e) &= \Vert \mu \Vert _2^2 (1 + kN/2)N \epsilon _{uni}^2 + (1+kN/2)d_{uni}NV_{uni}\beta ^2 \\ & + (k+1)(N/2)\epsilon _{uni}^2 + (k+1)d_{uni}NV_{uni}\beta ^2 + kd_{uni}(N^2/2)V_{uni}\beta ^2 \\ &\approx \frac{k}{2}\Vert \mu \Vert _2^2N^2\epsilon _{uni}^2 + kd_{uni}N^2 V_{uni}\beta ^2. \end{aligned}$$

   $\square$

Proof of Corollary 2 (Blind Rotation of CCS19)

Proof

We first analyze the line 6. Let $\overline{{\textbf{c}}}_{i, j} = \texttt{HbProd}(\{\textsf{pk}_j\}_{j\in [k]}, (X^{\tilde{a}_{i, j}}-1)\cdot \textsf{ACC}, \textsf{BK}_{i, j})$ and ${\textbf{e}}_{i, j}$ be the error solely from the $\texttt{HbProd}$. Then,

$$\begin{aligned} \varphi _{\overline{{\textbf{s}}}}(\textsf{ACC}+ \overline{{\textbf{c}}}_{i, j}) &= \varphi _{\overline{{\textbf{s}}}}(\textsf{ACC}) + \varphi _{\overline{{\textbf{s}}}}((X^{\tilde{a}_{i, j}}-1)\cdot \textsf{ACC})+{\textbf{e}}_{i, j} \\ &= \varphi _{\overline{{\textbf{s}}}}(X^{\tilde{a}_{i, j}z_{i, j}}\cdot \textsf{ACC}) + {\textbf{e}}_{i, j}\pmod 1. \end{aligned}$$

Note that during the i-th iteration, $\textsf{ACC}$ should be regarded as a multi-key $\textsf{RLWE}$ ciphertext with i parties since $i+1, \dots , k$-th indices remains zero. Therefore,

$$\begin{aligned} \textsf {Var}({\textbf{e}}_{i, j}) &\approx \frac{i}{2}\Vert z_{i, j} \Vert _2^2N^2\epsilon _{uni}^2 + id_{uni}N^2 V_{uni}\beta ^2 \\ &= \frac{i}{4}N^2\epsilon _{uni}^2 + id_{uni}N^2 V_{uni}\beta ^2 \end{aligned}$$

Since $X^{\tilde{a}_{i, j}z_{i, j}}$ is a monomial, the variance adds up every iteration in the inner loop (line 5–7) and therefore an error variance of $\frac{i}{4}nN^2\epsilon _{uni}^2 + id_{uni}nN^2 V_{uni}\beta ^2$ is added for every iteration in the outer loop (line 4–8). Therefore we get the error variance of

$$ \frac{k(k+1)}{8}nN^2(\epsilon _{uni}^2 + 4d_{uni}V_{uni}\beta ^2). $$

   $\square$

Proof of Lemma 5 (Generalized External Product)

Proof

Let us follow the notations from the algorithm description. First, by Lemma 1 we obtain

$$\begin{aligned} \varphi _{\overline{{\textbf{s}}}}(\overline{{\textbf{x}}}+ \overline{{\textbf{y}}}\cdot t) = \sum _{j=0}^{k} (x_j + y_j \cdot t) \cdot s_j &= \sum _{j=0}^{k} \varphi _t(c_j\odot {\textbf{C}}_i) \cdot s_j \\ &= \mu \cdot \varphi _{\overline{{\textbf{s}}}}(\overline{\textsf{ct}}) + \sum _{j=0}^{k} e_j \cdot s_j\pmod 1. \end{aligned}$$

where $e_j = \varphi _t(c_j \odot {\textbf{C}}_i) - \mu \cdot c_j (0\le j \le k)\pmod 1 \in T$ with variance

$$ \textsf {Var}(e_j) = \Vert \mu \Vert _2^2 \epsilon _{lev}^2 + d_{lev}N V_{lev}\textsf {Var}\textsf {Err}({\textbf{C}}_i).$$

Let $\overline{{\textbf{y}}}' = \texttt{NewHbProd}(\{{\textbf{b}}_j\}_{j\in [k]}, \textsf{ct}, \textsf{rlk}_i)$. By Lemma 4, $\varphi _{\overline{\textbf{s}}}(\overline{{\textbf{y}}}') = t \cdot \varphi _{\overline{\textbf{s}}}(\overline{{\textbf{y}}}) + e'$ for some $e'\in T$ with variance

$$\begin{aligned} \textsf {Var}(e') &\approx \frac{k}{2}\textsf {Var}(\Vert t\Vert _2^2)N^2\epsilon _{uni}^2 + kd_{uni}N^2 V_{uni}\beta ^2 \\ &= \frac{k}{4}N^3\epsilon _{uni}^2 + kd_{uni}N^2 V_{uni}\beta ^2. \end{aligned}$$

Therefore, we get

$$\begin{aligned} \varphi _{\overline{{\textbf{s}}}}(\overline{\textsf{ct}}') = \varphi _{\overline{{\textbf{s}}}}(\overline{{\textbf{x}}}) + \varphi _{\overline{{\textbf{s}}}}(\overline{{\textbf{y}}}') &= \varphi _{\overline{{\textbf{s}}}}(\overline{{\textbf{x}}}) + \varphi _{\overline{{\textbf{s}}}}(\overline{{\textbf{y}}})\cdot t + e' \\ &= \mu \cdot \varphi _{\overline{{\textbf{s}}}}(\overline{\textsf{ct}})+\sum _{j=0}^{k} e_j \cdot s_j + e'\pmod 1. \end{aligned}$$

Therefore the variance of error $e = \sum _{j=0}^k e_j \cdot s_j + e'$ be

$$\begin{aligned} \textsf {Var}(e) \approx & (1+kN/2) \left[ \Vert \mu \Vert _2^2\epsilon _{lev}^2 + d_{lev}N V_{lev}\textsf {Var}\textsf {Err}({\textbf{C}}_i) \right] \\ & + \frac{k}{4}N^3\epsilon _{uni}^2 + kd_{uni}N^2 V_{uni}\beta ^2. \end{aligned}$$

   $\square$

Proof of Theorem 1 (Our Blind Rotation)

Proof

We start from analyzing line 7 of the algorithm. By Corollary 1,

for some ${\textbf{e}}_{i, j} \in T^{d_{lev}}$ with the common variance of rows $(1 + N/2)\Vert \mu z_{i, j}\Vert _2^2 \epsilon _{gsw}^2 + 2d_{gsw}N V_{gsw}\textsf {Var}\textsf {Err}(\textsf{BK}_{i, j})$. Therefore, with each iteration within the for loop 6–8, the error variance increases by $V_{ACC} = (1 + N) \epsilon _{gsw}^2 + 2d_{gsw}N V_{gsw}\beta ^2$. Hence, the error variance of the resulting RLEV ciphertext $\textsf{ACC}'_i$ of the for loop is $n\cdot ((1 + N) \epsilon _{gsw}^2 + 2d_{gsw}N V_{gsw}\beta ^2 )$ with message $X^{\sum _{j=1}^n \tilde{a}_{i, j}z_{i, j}}$.

Note that only $0, \dots , i$-th indices of the MK-RLWE ciphertext $\textsf{ACC}$ are non-zero after the $i-th$ iteration of the for loop 4–10, hence it can be regarded as an MK-RLWE encryption of i parties. Now we let $\textsf{ACC}_i$ be $\textsf{ACC}$ after the $\texttt{ExtProd}$, then by the Lemma 5, we have

$$\begin{aligned} \varphi _{\overline{\textbf{s}}}(\textsf{ACC}_i) = X^{\left\langle \tilde{\textbf{a}}_i, {\textbf{z}}_i\right\rangle }\cdot \varphi _{\overline{\textbf{s}}}(\textsf{ACC}_{i-1}) + e_i (1\le i \le k) \end{aligned}$$

where

$$\begin{aligned} \textsf {Var}(e_i) &\approx (1+iN/2) \left[ \epsilon _{lev}^2 + d_{lev}N V_{lev}V_{ACC} \right] + \frac{i}{4}N^3\epsilon _{uni}^2 + id_{uni}N^2 V_{uni}\beta ^2. \end{aligned}$$

Since $X^{\tilde{\textbf{a}}_i, {\textbf{z}}_i}$ is a monomial, the error variance adds up every iteration and thus the error variance of the final output of our new blind rotation algorithm is

$$ \frac{k(k+1)}{8} \left[ 2d_{lev}nN^3 V_{lev}\cdot \left( 2d_{gsw}V_{gsw}\beta ^2 + \epsilon _{gsw}^2 \right) + N^3\epsilon _{uni}^2 + 4d_{uni}N^2 V_{uni}\beta ^2 \right] . $$

   $\square$