準同型暗号 TFHE 方式徹底解説 -3（TFHE 方式の流れ）

目次

1. 完全準同型暗号と TFHE 方式
2. TLWE と TRLWE
3. TFHE 方式の流れ ← 本記事はココ
4. TFHE 方式のブートストラッピング -1 (TRGSW と Blind Rotation)
5. TFHE 方式のブートストラッピング -2 (Sample Extract Index と Key Switching)

はじめに

本記事では TFHE 方式の大きな流れについて解説します。
TFHE 方式では任意の論理演算を評価することができます。本記事では、その全ての演算に対し、どのように実現するのかについても解説します。

記事中に誤りがあれば、ぜひご指摘いただけると幸いです。

TFHE の流れ

まず最初に、TFHE における処理全体の流れを図で確認します。
以下は、TFHE において 1 回の論理演算がどのように処理されるかを示したものです。

この図が表しているように、TFHE の処理は大きく見ると前半の線形結合と後半のブートストラッピングに分かれます。これらの処理は以下のような役割を持ちます。

• 線形結合：複数の入力暗号文に対して線形演算（TLWEの加法準同型性によって実現可能）を行い、評価したい論理ゲートの出力を判定できる形に整えます。
• ブートストラッピング：増大したノイズを除去しながら、論理ゲートの出力値を持つ新しい暗号文を生成します。

以下では、それぞれの処理の詳細について掘り下げて説明します。

平文エンコーディング

TFHE では、論理値（ビット）をトーラス上の値として表現します。具体的には、次のエンコーディングを採用しています。

$$0 \mapsto -\frac{1}{8}, \quad 1 \mapsto \frac{1}{8}$$

前の記事では、TLWE の復号について「ノイズ $e$ が十分小さければ $\phi_s(\mathbf{c}) = \mu + e$ から元の平文 $\mu$ を復元できる」と説明しました。TFHE では、この復元を $\mu + e$ の値を最も近い平文エンコード値へ丸めるによって実現します。

上記のエンコードでは隣接する 2 つの平文値の距離が $1/4$ であるため、ノイズが $|e| < 1/8$ を満たす限り、復号によって元の論理値を正しく復元できます。なお、このエンコードは最適な選択であることが知られていますが、その詳細については別の機会に取り上げます。

線形結合

二つの入力暗号文に対する線形演算によって、出力暗号文の平文の符号と期待する論理ゲートの結果（0 / 1）を対応させます。

2 つの TLWE 暗号文 $\mathbf{c}_1 = \mathrm{TLWE.Enc}_s(\mu_1),\; \mathbf{c}_2 = \mathrm{TLWE.Enc}_s(\mu_2)$ に対し、整数係数 $\alpha_1, \alpha_2 \in \mathbb{Z}$ とオフセット項 $(0, \delta)$ を用いて次の暗号文を計算します。なお、この線形結合は TLWE の加法準同型性によって実現できます。

$$\tilde{\mathbf{c}} = \alpha_1 \cdot \mathbf{c}_1 + \alpha_2 \cdot \mathbf{c}_2 + (0, \delta)$$

ここで、オフセット項 $(0, \delta)$ は平文 $\delta \in \mathbb{T}$ をノイズなしで保持するTLWEの形のものであり、trivial sample と呼ばれます。

$\tilde{\mathbf{c}}$ の平文である $\alpha_1 \mu_1 + \alpha_2 \mu_2 + \delta$ の符号が、評価したいゲートの出力と一致するように $\alpha_1, \alpha_2$ と $\delta$ を設計します。つまり、論理演算の結果が 1 のときに位相が正、0 のときに負になるようにします。

NAND を例として

NAND の場合、$\alpha_1 = \alpha_2 = -1$、$\delta = 1/8$ と設定し、以下のように線形結合を行います。

$$\tilde{\mathbf{c}}_{\mathrm{NAND}} = -\mathbf{c}_1 - \mathbf{c}_2 + \left(0,\; \frac{1}{8}\right)$$

エンコードで各入力の組み合わせに対する位相の符号を確認すると、次のようになります。

$(\mu_1, \mu_2)$ への対応	$\phi_{\mathbf{s}}(\tilde{c}_{\mathrm{NAND}}) = -\mu_1 - \mu_2 + 1/8$	符号	NAND の期待出力
$(0, 0)$	$3/8$	$+$	$1$
$(0, 1),\; (1, 0)$	$1/8$	$+$	$1$
$(1, 1)$	$-1/8$	$-$	$0$

NAND の出力が $1$ となる入力では位相が正、$0$ となる場合には位相が負になっていることが確認できます。AND、OR、XOR などの他のゲートでも、$\alpha_i$ と $\delta$ を適切に選ぶことで同様の対応関係を実現できます。

この段階で得られる TLWE 暗号文は、TLWE 暗号文の線形結合によってノイズが増大しています。そのため、このままでは正確に次の準同型演算を行えるとは言えません。

この問題を解決するために、ブートストラッピングを行います。

ブートストラッピング（Bootstrapping）

ブートストラッピングは、線形結合後によってノイズが増大した TLWE 暗号文を、次のゲート評価に使えるようにするために、ノイズの少ない TLWE 暗号文へと作り直す処理です。

具体的には、TLWE暗号文の平文の符号（正か負か）だけに着目し、

• 符号が正 → 平文 $+1/8$ を持つ TLWE 暗号文
• 符号が負 → 平文 $-1/8$ を持つ TLWE 暗号文

を生成します。重要なのは、この操作が暗号化されたまま行われるという点です。

ブートストラッピングは内部的に次の 3 ステップで構成されます。以下、内容がイメージしづらいかもしれませんが、雰囲気だけでもつかんでもらいたいです。

1. Blind Rotation：線形結合後の TLWE 暗号文を用いて、その位相の符号に対応した期待出力値（$\pm 1/8$）を平文の定数項に持つ TRLWE 暗号文を得る。
2. Sample Extract Index：Blind Rotation の出力である TRLWE 暗号文から、平文多項式の定数項を暗号化した TLWE 暗号文を作成する。ただし、この時点で得られる TLWE 暗号文の秘密鍵は TRLWE 秘密鍵由来（TRLWE 秘密鍵の各係数を並べたベクトル）であるため、元の TLWE 秘密鍵 $\mathbf{s}$ で暗号化された暗号文とそのまま準同型演算することはできません。
3. Key Switching：前ステップで得た TLWE 暗号文の秘密鍵を、平文はそのままの状態のままで、TRLWE 秘密鍵由来のものから元の TLWE 秘密鍵 $\mathbf{s}$ へと変換します。これにより出力暗号文が入力と同じ形式に揃い、ゲートを連続して評価できるようになります。

おわりに

本記事では TFHE 方式の大きな流れを確認しました。今後、今なんのための処理について書いているのかがわからなくなった時に参照して大きな流れをつかんでください。
次の記事では、ブートストラッピングの中核である Blind Rotation について解説します。