TFHE
Zamaの解説記事のメモ
Notation
https://scrapbox.io/files/66963d07bbccdb001d68b009.png
TFHEを理解するにあたり、三種類のcipher textを理解する必要がある。
GLEW:LEWとRLEWを一般化したもの
GLev:GLEWを二次元に拡張したもの
GSGSW:GLEWを三次元に拡張したもの
なので基本的にGLEWを理解できればよく、一連の記事においてGLEWをベースに解説がなされている。
GLWE
A GLWE ciphertext :$ (A_0, \ldots, A_{k-1}, B) \in GLWE_{\vec{S}, \sigma}(\Delta M) \subseteq \mathcal{R}_q^{k+1}
mask:$ (A_0, \ldots, A_{k-1})
body:$ B = \sum_{i=0}^{k-1} A_i \cdot S_i + \Delta M + E \in \mathcal{R}_q
encoding of M: $ \Delta M
メッセージを暗号化するたびに、新しいランダムネス(マスクとノイズエラー)をサンプリングするので、暗号化するたびに(同じメッセージであっても)他の暗号化とは異なる。
ecnrypt
https://scrapbox.io/files/6696406392aa0f001c18e831.png
暗号化はsecret key $ \vec{S} = (S_0, \ldots, S_{k-1}) \in \mathcal{R}^kで行われる
decrypt
https://scrapbox.io/files/669645d43b4da7001d042056.png
$ B - \sum_{i=0}^{k-1} A_i \cdot S_i = \Delta M + E \in \mathcal{R}_q
$ M = \lfloor (\Delta M + E)/\Delta \rceil
LWE & RLWE
https://scrapbox.io/files/669714f5867f48001d0f7e69.png
https://scrapbox.io/files/669714fce68d76001d496711.png
GLev
GLWE 暗号文と GGSW 暗号文の中間的なタイプの暗号文を識別し、同時に GGSW 暗号文をより理解しやすくするために、CLOT21 で初めて GLev という名前が使われました。
redundancy
$ \left( GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^1} M\right) \times \ldots \times GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^\ell} M\right) \right) = GLev^{\beta, \ell}_{\vec{S}, \sigma}(M) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.
https://scrapbox.io/files/669716f9a08ea1001d30e046.png
GGSW
$ \left( GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_0 M) \times \ldots \times GLev^{\beta, \ell}_{\vec{S}, \sigma}(-S_{k-1} M) \times GLev^{\beta, \ell}_{\vec{S}, \sigma}(M) \right) = GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}.
https://scrapbox.io/files/6697188e37779c001c6c536c.png
TFHEでは、ノイズはLSB(最下位ビット)に加えられる。 このため、MSB(最上位ビット)にメッセージを配置しないエンコードを使用する必要があります。
encording
modulo演算が入るので別にそのまま演算をしても良い。
例えば、$ q = 2^{32},$ p = 2^7,$ \Delta = 2^{25}だとすれば以下のようになる。(MSBがqでLSBが0)
https://scrapbox.io/files/669728405de279001d21235c.png
このような計算はleveled operations (additions and multiplications by constants)にて実用的とされている。
ここでMSBにpadding bitsをつけるとより正確な演算が可能になる。
これはexact leveled operations (additions and multiplications by constants)にて有効である、
bit数が繰り上がることによって消費される分を予め予測する必要がある。
https://scrapbox.io/files/66972834e68d76001d4a7178.png
このパディングはブートストラップの話に繋がるらしい
また、$ m \approx m + eとした場合、特殊なエンコーディングが得られる。
これはmとeを一つの情報と定義したもので、approximate leveled operations (additions and multiplications by constants) にて有効
https://scrapbox.io/files/66972abeb86de9001ca56575.png
多項式係数が大きければ大きいほど、乗算における係数は大きくなってしまう。
(bにおけるeがrとかかる)
https://scrapbox.io/files/669732b5e9bf10001d449f36.png
そこで以下のように大きな定数を小さなsmall base bでdecomposeする
$ \gamma = \gamma_1 \frac{q}{\beta^1} + \gamma_2 \frac{q}{\beta^2} + \ldots + \gamma_\ell \frac{q}{\beta^\ell}
https://scrapbox.io/files/669736142c5191001c23b31f.png
1/2, 1/4(=1/2*1/2),1/8(=1/2*1/2*1/2)...って感じ
分解された要素が小さいため、暗号文と掛け算を行ってもノイズへの影響は小さい。
メッセージ ( M ) と (\gamma) の積を得るためには、分解の逆操作を行い、再構成する必要がある。
分解された要素をGLWE暗号化した ( M ) の各要素と掛け合わせる代わりに、分解基底の異なるべき乗に対応するGLWE暗号化を使用する。
$ \overline{C} = (C_1, \ldots, C_\ell) \in \left( GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^1} M\right) \times \ldots \times GLWE_{\vec{S}, \sigma}\left(\frac{q}{\beta^\ell} M\right) \right) = GLev^{\beta, \ell}_{\vec{S}, \sigma}(M) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.
分解された各要素と対応するGLWE暗号文の各要素を掛け合わせ、それをすべて合計する内積のような操作を行う。
実際には内積のような演算を行うので、分解の各要素にGLevの対応する要素を掛け合わせ、それらをすべて足し合わせる
$ \langle \mathsf{Decomp}^{\beta,\ell}(\gamma), \overline{C} \rangle = \sum_{j=1}^\ell \gamma_j \cdot C_j \in GLWE_{\vec{S}, \sigma'}\left(\gamma \cdot M\right) \subseteq \mathcal{R}_q^{k+1}
https://scrapbox.io/files/66974635bc7ce1001c9bfe86.png
ノイズ管理: GLWE暗号化では、乗算や加算の影響がノイズに対して小さいため、ノイズの増加が緩やかになります。
使用制限: 出力されたGLWE暗号文には \Delta がなく、新しいメッセージが \mathbb{Z}_q 全体を占有する可能性があるため、単独では使用されません。
応用: このプロセスは、キーの切り替えや暗号文間の同型乗算などの複雑な操作の基礎として使用されます。
先ほどの例では完全に分解していたが、近似された形で分解(Approximate decomposition)して一定の精度を保つこともできる
$ \beta^\ell = qではなく$ \beta^\ell < qを使う
https://scrapbox.io/files/669749049747ba001d5cd6e0.png
分解パラメータが適切に選択されていれば計算の正しさには影響しない。 なぜなら、LSB部分には常にノイズが存在し、我々が保持したい情報(メッセージ)はMSB部分に存在するからである。
key switching key
複数の同型計算を行うとノイズが大きくなってしまい復号できなくなってしまう。
そこでKey Switchingという手法を使う(Bootstrappingは後述)
これにより、同じメッセージを異なる鍵でRe-encryptできるようになる
key switching key(KSK)
$ \mathsf{KSK}_i \in \left( GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^1} S_i\right) \times \ldots \times GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^\ell} S_i\right) \right) = GLev^{\beta, \ell}_{\vec{S}', \sigma_{\mathsf{KSK}}}(S_i) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.
In practice, the key switching is performed as follows:
$ C' = \underbrace{\overbrace{(0, \ldots, 0, B)}^{\text{Trivial GLWE of } B} - \sum_{i=0}^{k-1} \overbrace{ \langle \mathsf{Decomp}^{\beta,\ell}(A_i), \mathsf{KSK}_i \rangle}^{\text{GLWE encryption of } A_i S_i} }_{\text{GLWE encryption of } B - \sum_{i=0}^{k-1} A_i S_i = \Delta M + E}\in GLWE_{\vec{S}', \sigma'}(\Delta M) \subseteq \mathcal{R}_q^{k+1}.
右辺は今まで見てきたdecryptの初段$ B - \sum_{i=0}^{k-1} A_i \cdot S_i = \Delta M + E \in \mathcal{R}_qと変わらない。
前の段落で示した、GLev暗号文のDecomposeと内積を組み合わせたトリック(大きな多項式どうしをそのまま乗算するとエラーが大きくなるので一定の精度を保つ近似を行うこと)は、より複雑な演算、特に暗号文同士の乗算を定義するのに非常に役立っていることもわかる。
なので、あとはこの式を計算しdeltaをとれば復号化できる。
https://scrapbox.io/files/6697ab9457031e001d8d7bcf.png
ポイントはメッセージはそのままで、鍵を交換したという点。
何度も暗号化をラッピングしているわけではないので注意。
復号化は一回で済むし、そのために必要な鍵も一つ
つまり$ \vec{S}で作成した以下のような暗号文がある時、この秘密鍵をキャンセルし、新しい秘密鍵$ \vec{S}'で暗号化する。
$ B - \sum_{i=0}^{k-1} A_i \cdot S_i = \Delta M + E \in \mathcal{R}_q
新しい鍵は$ \mathsf{KSK}_i \in \left( GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^1} S_i\right) \times \ldots \times GLWE_{\vec{S}', \sigma_{\mathsf{KSK}}}\left(\frac{q}{\beta^\ell} S_i\right) \right) = GLev^{\beta, \ell}_{\vec{S}', \sigma_{\mathsf{KSK}}}(S_i) \subseteq \mathcal{R}_q^{\ell \cdot (k+1)}.なので暗号文でもある(が、ただ単に秘密鍵として使う)
FHEの中では全ての計算がhomomorphicallyなのでこれもまたhomomorphicallyである。
いくつかkey-swithcingのパターンがはあるらしい。
https://scrapbox.io/files/6697b40cf478f3001dc7e53a.png
https://scrapbox.io/files/6697b41125b7c3001d087549.png
https://scrapbox.io/files/6697b4167a51c3001c773635.png
https://scrapbox.io/files/6697b41c734651001de3f170.png
Extgernal Product
外積の目的は、同型的に2つの暗号文を乗算し、その結果としてメッセージの積を暗号化することです。(内積に関しては後述)
大きな定数を暗号文に乗算する場合、定数を分解して、GLev(Generalized Level)として再構成する必要があります。また、GLWE(General Learning With Errors)暗号文は大きな定数のリストです。この2つのアイデアを組み合わせて乗算を行います。
External Product:
Key Switching にGLWE暗号文を追加したもの。
キーを切り替えないKey Switchingと類似。
同じ秘密鍵を使用して暗号化する。
Functional Key Switching:
異なる秘密鍵を使用。
暗号化された定数による乗算とキーの切り替えを同時に行う。
具体的な手法としてキー切り替えのアプローチを使用します。1つの暗号文をGLWEとして(これを分解する暗号文)、もう1つの暗号文をGLev暗号文のリストとして扱います。キー切り替えの場合、最初の暗号文のマスクだけをGLevで暗号化された秘密鍵と乗算しましたが、今回はマスクとボディの両方を乗算します。
GGSW(Generalized Gentry-Sahai-Waters)暗号文を用いることで、目的に適した暗号文を作成できます。
GLWEとdecomposeを考慮したGGSWの暗号文を以下のように記述する
前者はM_1を暗号化しており、後者はM_2を暗号化している。
$ C = (A_0, \ldots, A_{k-1}, B) \in GLWE_{\vec{S}, \sigma}(\Delta M_1) \subseteq \mathcal{R}_q^{k+1}
$ \overline{\overline{C}} = (\overline{C}_0, \ldots, \overline{C}_{k-1}, \overline{C}_k) \in GGSW^{\beta, \ell}_{\vec{S}, \sigma}(M_2) \subseteq \mathcal{R}_q^{(k+1) \times \ell (k+1)}
https://scrapbox.io/files/66986928087a54001dd6ecd7.png
Internal product
外積:
GLWE暗号文と外部のGGSW暗号文を必要とするため「外部」と呼ばれます。
GLWE暗号文同士の内積は存在しない(B/FVではKey Switchingのような操作が必要)。
内積:
GGSW暗号文同士の間に存在し、外積から定義される。
GGSW暗号文は実際にはGLWE暗号文のリストであり、外積がGLWEとGGSW暗号文の間で行われることを利用。
内積は、入力されたGGSW暗号文の一つと、もう一方のGGSWを構成するすべてのGLWE暗号文との間の外積のリストとして定義される。
これらの外積の結果が、新しいGGSW暗号文を構成する。
https://scrapbox.io/files/6697e10dd99beb001cb6f09d.png
外積は内積よりもはるかに効率的だが合成可能(composable)ではない。
つまり内積の結果は別の内積の入力として使用できるが、外積の結果(GLWE暗号文)は別の外積(GLWE暗号文)の2つの入力のうち1つにのみ使用でき、もう1つ(GGSW暗号文)には使用できない。 TFHEはLWEから同型的にGGSW暗号文を構築する技術を提案しており、これは回路ブートストラッピングと呼ばれています。
TFHEでは主に外積を使用し内積はできるだけ使用しません
Modulus Switching
modulusを$ qから$ \omegaに置き換える
LWEにおけるaは$ \tilde{a}_i = \left\lfloor \frac{\omega \cdot a_i}{q} \right\rceil \in \mathbb{Z}_\omega.となる
$ \tilde{c} = (\tilde{a}_0, \ldots, \tilde{a}_{n-1}, \tilde{a}_n = \tilde{b}) \in LWE_{\vec{s}, \sigma}(\tilde{\Delta} m) \subseteq \mathbb{Z}_\omega^{n+1}.
この時$ p < \omega < qであり、$ \tilde{\Delta} = \frac{\omega \cdot \Delta}{q} = \omega/pである。
また、power of 2でない場合はroundingを施す。
この結果、下の図のようにmessageはそのままでerrorを削減できた。
https://scrapbox.io/files/66986ec74fb3e0001c39ad2c.png
Sample Extraction
多項式メッセージを暗号化したGLWE暗号文を入力とし、メッセージの係数の1つの暗号化をLWE暗号文として抽出する操作
https://scrapbox.io/files/6698710fcfc717001c367110.png
定数のリストから一つの定数を抜き出すようなイメージか
GLWEは以下のように定義されるわけで
$ C = \left(A_0 = \sum_{j=0}^{N-1} a_{0,j} X^j, \ldots, 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) \in GLWE_{\vec{S}, \sigma}(\Delta M) \subseteq \mathcal{R}_q^{k+1}
ここでMのh($ 0 \leq h < N)番目の係数を抜き出す
https://scrapbox.io/files/669872bc04aefa001caafca5.png
Blind Rotation
Blind Rotationによってif conditionを構成することができる
多項式の係数のブラインドでローテーションする。
トーラス上の暗号化された値を、暗号化されたビットに応じて回転させます。
この操作は、暗号文のノイズを増加させるため、ブートストラッピングの一部としても使用されます。
pi positionのmをrotateする例
多項式 ( M ) に対して ( X^{-\pi} ) を掛ける操作を行い、係数を左にシフトする。
最終的な結果は ( X^N + 1 ) に対してモジュロを取ることによって、多項式の次数を ( N ) 以下に保ちます。
この操作により、多項式のシフトが正常に行われ、再び有効な暗号文となります。
https://scrapbox.io/files/6698cf3808a867001c8720cd.png
https://scrapbox.io/files/6698d205410b55001da6a563.png
最終的な難易度の追加:
値\piを暗号化してBlind Rotationを実現する。
TFHEでの操作:
CMux操作を反復的に使用する。
CMux操作は、2つのGLWE暗号文と1つのGGSW暗号文(選択ビットを暗号化したもの)を入力として受け取る。
選択ビットの使用:
\piの値が選択ビットとして使用される。
\piは整数値であるため、二進数分解により表現する必要がある。
具体的な操作
CMux操作は、選択ビットに基づいて2つのGLWE暗号文のいずれかを選択する。
これにより、\piの二進数分解を使用して、Blind Rotationが実行される。
piはintなのでbinary decompositionする。
$ \pi = \pi_0 + \pi_1 \cdot 2 + \pi_2 \cdot 2^2 + \ldots + \pi_\delta \cdot 2^\delta,$ \delta = \log_2(N)とした時
$ \begin{aligned} M \cdot X^{-\pi} &= M \cdot X^{-\pi_0 -\pi_1 \cdot 2 -\pi_2 \cdot 2^2 + \ldots -\pi_\delta \cdot 2^\delta} \\ &= M \cdot X^{-\pi_0} \cdot X^{-\pi_1 \cdot 2} \cdot X^{-\pi_2 \cdot 2^2} \cdot \ldots \cdot X^{-\pi_\delta \cdot 2^\delta}. \\ \end{aligned}
$ X^{-\pi_j \cdot 2^j}に関して注目すると、piはbinaryなので
$ M \cdot X^{-\pi_j \cdot 2^j} = \begin{cases} M &\text{ if } \pi_j = 0 \\ M \cdot X^{-2^j} &\text{ if } \pi_j = 1 \\ \end{cases}
これはまさにif条件であり、これを入力として受け取るCMuxとして評価できることを見てきた
GGSW encryption of $ \pi_j as selector;
a GLWE encryption of$ M as the "0" option;
$ Mtimes $ X^{-2^j}(rotation of a clear number of positions) as the "1" option.
https://scrapbox.io/files/6698d77bd6b8e9001c5911f8.png
CMuxの結果は、次のCMuxの新しいメッセージ・オプションになる
https://scrapbox.io/files/6698d7826ab670001c166a1b.png
Bootstrapping
noiseを減らすぞー!
以下のようにdeltaで割ってm+e/dを得ると、下のような羅列になる。
$ \Delta 0 + eはネガティブなのでmodule qのq-1,q-2..と上がる
https://scrapbox.io/files/6699001abb87e3001df3f0a3.png
同じ値の繰り返しを複数含むブロックをmega-casesと呼ぶ。
$ \mathbb{Z}_qに$ \Delta m + eが定義されており、$ \mathbb{Z}_pに$ mが定義されている
https://scrapbox.io/files/66990193024aa2001dcac2b4.png
多項式の係数を読みたいときは係数の位置に行くのではなく、係数が定位置に来るまで多項式を回転させるのである。
(緑の位置に来るようにローテートする?)
TFHEにおけるLUT(Look-Up Table)の評価方法は、多項式の回転によって行います。この方法は、冗長なLUTの全ての要素を一つの多項式にまとめ、その多項式を\Delta m + e位置だけ回転させるというものです。具体的には、多項式をX^{-(\Delta m + e)}倍することで回転させます。この回転により、メガケース(複数の同じ値が繰り返されるブロック)の要素の一つが、多項式の定数項に位置づけられます。
この定数項の位置が「読み取り位置」となります。したがって、多項式の特定の係数を読み取る際には、その係数が定数項に来るように多項式を回転させることで読み取ります。
詳細
• LUTの要素: 冗長なLUTの全要素を多項式にまとめます。
• 多項式の回転: \Delta m + e位置だけ回転させるために、X^{-(\Delta m + e)}倍します。
• 読み取り位置: 多項式の定数項の位置を「読み取り位置」とし、特定の係数を読み取るために多項式を回転させます。
この方法により、TFHEでは効率的に暗号化されたデータを操作し、復号の際に必要な値を正確に取得することができます。
https://scrapbox.io/files/669908b5a97972001c590f89.png
TFHEで扱う多項式は X^N + 1 でモジュロを取るため、N 個の係数しか含まれません。実際には、N は q よりもずっと小さいため、情報を圧縮してモジュロ q に収める必要があります。このために前述のモジュラススイッチングを使用します。
さらに、単項式 X は X^N \equiv -1 および X^{2N} \equiv 1 となるため、2Nの順序を持ちます。これにより、多項式の N 個の係数を固定することで、残りの N 個の係数は最初の N 個の係数の符号反転で表されます。この特性をネガサイクリックプロパティと呼びます。
以下の図はBlind rotationを表している
https://scrapbox.io/files/669908e60e9b8c001dcfafcb.png
プロセスは以下の順で進む
1. Module Swithing
回転させるにはメッセージを圧縮する必要がある
2. Blind rotation
LUTを使用し、Bootstrapping Keyによって可能になる
3. Sample extraction
https://scrapbox.io/files/66a1a1a9a8ea14001cfc77d2.png
zamaの解説に基づいて、TFHEのブートストラッピングプロセスの各ステップについて説明します。
Modulus Switching:
目的
暗号文のノイズを減少させ、より多くの演算を可能にする。
処理:
大きな法(modulus)から小さな法への変換を行う。
暗号文の精度を調整し、ノイズレベルを管理する。
Blind Rotationの準備段階として機能する。
Blind Rotation:
目的
暗号化されたままでの条件付き演算を実行する。
処理:
Bootstrapping Key (BK) を使用して、Look-Up Table (LUT) を回転させる。
入力暗号文の値に応じてLUTを適切に位置合わせする。
この操作により、暗号化されたまま関数評価が可能になる。
Sample Extraction:
目的:
Blind Rotationの結果から必要な情報を取り出す。
処理
回転されたLUTから特定のサンプル(通常は最初の要素)を抽出する。
この抽出されたサンプルが、ブートストラッピングの主要な出力となる。
Key Switching:
暗号文を元の暗号化スキームに戻す。
処理:
Blind RotationとSample Extractionの結果得られた暗号文を、元のキーで暗号化された形式に変換する。
これにより、後続の演算や処理が可能になる。
参照