はじめに

前回の「完全準同型暗号②（完全準同型暗号とは？）」では完全準同型暗号の概要について記述しました。

今回はFHEを応用する場面で使われる主要な方式を３つ紹介します。これらの手法はすべて「完全準同型暗号①」で紹介したLWE問題をベースに構成されています。

1. BGV方式

BGV方式は2013年に発表されたもので、第二世代に分類されます。BGV方式は筆者の３名のイニシャルを取ったもので原論の題名は”（Leveled）Fully Homomorphic Encryption without Bootstrapping”です。題名から分かる通りBGV方式は事前に乗算の回数を決める代わりにブートストラッピングを要しないLHEです。乗算の回数のことを深さといいます。この計算の深さは、同じ計算でもある程度調整することができます。ここでは深さを調整できる例として、90を計算する場合の深さの違いをみてみましょう。

左側の計算方法では深さが４ですが右側では深さが３です。このようにしてできるだけ浅い深さの計算を選びます。

BGV方式ではmodulus chainとよばれる $L+1$ 個の整数の法のパラメータ $q_L>q_{L-1}>…>q_0$ と $\mathbb{A}=\mathbb{Z}(x)/\phi_m(x)$ を定義します。$\phi_m$ はm次の円分多項式を指します。 $L$ は乗算の深さの数です。平文空間は $\mathbb{A}t=\mathbb{A}/t\mathbb{A}$ 、暗号文空間は $\mathbb{A}{q_i}=\mathbb{A}/q_i\mathbb{A}$ です。暗号化状態での演算を繰り返すと同時に、法を $q_i$ から $q_{i-1}$ に一つづつ小さくしていきます。これをmodulus switchingと呼び、乗算を行う前に毎回行います。modulus switchingを行うと、ノイズを $q_{i-1}/q_i$ の比で小さくすることができます。このようにしてブートストラッピングしないままノイズの大きさを調整し、LHEを実現しています。

BGV方式はGitHubでライブラリが公開されているので誰でも試すことができます。

BGV方式でははじめてLHEが提案されているという点で大きな進歩でした。乗算の回数が少ないものであれば計算の重いブートストラッピングをしなくても良いというのは大きなメリットです。また、SHEと比べるとLHEの方が乗算の回数の制限がゆるいのでより応用の幅が広がりました。一方でまだまだ演算処理効率が悪く、特に第三世代以降の物に比べてかなり時間がかかってしまうというデメリットがあります。

2. GSW方式

GSW方式は第三世代のFHEです。GSW方式では行列の固有値、固有ベクトルとLWE問題を組み合わせて暗号を作ります。

行列を $A$ とするとき、$A\nu = \lambda \nu$ となるような $\nu$ を固有ベクトル、 $\lambda\in\mathbb{Z}$ を固有値と呼びます。この式の右辺に微小な誤差 $e$ を足し $A\nu = \lambda \nu+e$ という式を作ります。この式はLWE問題に帰着することができます。 $A$ を公開しても $A$ から $\nu, \lambda, e$ を求めることはできません。これを利用して暗号を構成します。

GSW では固有値 $\lambda$ を平文、固有ベクトル $\nu$ を秘密鍵、行列 $A$ を暗号文とします。 $A$ と同じ固有ベクトルを持つ行列 $B$ を考えます。ここでは $B$ の固有値を $\sigma$ とします。すると

$$ A\nu = \lambda \nu $$

$$ B\nu = \sigma \nu $$

の二つの式を作ることができます。この２つの式を使って加法と乗法を考えてみましょう。

①加法

平文同士の足し算が暗号文でも成り立つことは以下のようにして確かめることができます。

$$ (\lambda+\sigma){\nu} = \lambda{\nu} + \sigma{\nu} = {A}{\nu} + {B}{\nu} =({A}+{B}){\nu} $$

②乗法

平文同士の掛け算が暗号文でも成り立つことは以下のようにして確かめることができます。

$$ (\lambda\sigma){\nu} = \sigma(\lambda{\nu}) = \sigma( {A}{\nu}) = {A}(\sigma{\nu}) ={A} ({B}{\nu})=({A} {B}){\nu} $$

実際の暗号化状態では左辺に誤差 $e$ が足されていますが、平文である固有値は必ず整数です。この条件をもとにすると $e$ がある程度小さければ正しく復号することができます。あまりにも大きくなってしまう場合にはFlattenという方法を使います。Flatten( $A$)は行列 $A$ の横ベクトルを二進数とみなして $k$ 個にまとめ、それをまた二進数にする操作です。しかしFlattenを使っても乗算の回数は初めに定めるパラメータによる制限があるため、GSW方式もLHEです。

GSW方式もBGV方式と同じく、ブートストラッピングをしなくても乗算ができるというLHEの利点を持っています。さらに演算効率も改善されています。GSW方式以前のFHEには乗算のためにパラメータを用意する必要がありましたが、GSW方式ではその必要がなくなりました。これにより時間計算量は増えましたが、空間計算量を減らすことができます。しかし、乗算回数の多い演算には対応できない、実用化できるほどの処理速度ではないなどがデメリットとしてあげられます。

3. TFHE : Fast Fully Homomorphic Encryption over the Torus

三つ目はGSWと同じ第三世代に分類されるTFHEです。TFHEの特筆すべき点はブートストラッピングが高速なことです。プログラマブルブートストラッピングとよばれる手法で、従来のものより大幅に処理時間が削減されています。初期のTFHEはbit毎に暗号化するbit-wise型のものでしたが、整数をそのまま暗号化するinteger-wise型のものも提案されています。bit-wise型の利点は

暗号のベースとなるのはTLWE暗号、TGLWE暗号です。これらの特徴はトーラスという上で構成されるという点です。

まずはトーラス $\mathbb{T}$ を定義します。

$$ \mathbb{T}:=\mathbb{R}/\mathbb{Z} $$

実数の小数部分の集合のことです。また、トーラスの部分群 $\mathbb{T}_q:=\{\frac{i}{q} \mod{1} | i\in \mathbb{Z}/q\mathbb{Z}\}= \{ 0, \frac{1}{q}, \cdots, \frac{q-1}{q} \}$ と定義します。トーラスの元同士は足し算ができますが、掛け算は定義できません。ただし、整数との掛け算は定義できます。また、トーラスは円周群で環ではありません。

次にトーラス上のLWEを定義します。

TLWE：LWE problem over the discretised torus

$q, n\in \mathbb{N}, s = (s_1,s_2 \cdots , s_n) \gets \{0, 1\}^n, \hat{x}$ が $\mathbb{Z}/q\mathbb{Z}$ 上の誤算分布とする。

$({a}, r)$ が与えられた時以下の$D_0, D_1$のどちらなのかを判定する問題です。

$ D_0 = \{({a}, r)| {a}\gets \mathbb{T}_q^n, r\gets \mathbb{T}_q $
$ D_1=\{({a}, r)|{a} = (a_1, a_1,\cdots,a_n)\gets \mathbb{T}q^n, r = \sum{j=1}^n s_ja_j+e, e\gets\hat{x}\} $

TLWEをもとに暗号を構成します。今回紹介するのは平文 $\mu$ のワンタイムパッドを作成する方法です。

①鍵生成

セキュリティパラメータ $\lambda$ 、正整数 $m, n$ 、$p$ が $q$ の約数となるような正整数 $p, q$ 、誤差分布 $\hat{\chi}$ に従って選ばれたエラー $e$ 、ランダムなベクトルの組 ${s}=(s_1, s_2 \cdots , s_n) \gets \mathbb{Z}^n$ を得る。平文空間を $\rho = \mathbb{T}_p$ 、秘密鍵を ${s}$ とします。$\{m,n,p,q\}$ は公開パラメータです。

②暗号化

平文 $\mu \in \rho$ としたとき $\mu$ の暗号文 c は以下で生成される。

$$ c = TLWE_s(\mu)=\sum^n_{j=1}s_ja_j+\mu +e \in\mathbb{T}^{n+1}_q $$

③復号

暗号文 $c = (a_1, a_2, \cdots , a_n, b$) の復号はまず以下の $\mu^*$ を作る。

$$ \mu^* = b-\sum^n_{j=1}s_ja_j $$

$\mu^*$ に最も近い $\rho$ の元をもとの平文 $\mu \in \rho$ として出力する。

次にトーラス多項式を定義します。

$$ \mathbb{T}[x]:=\mathbb{R}[x]/\mathbb{Z}[x] $$

トーラス多項式を具体的に書くと以下のようになります。つまり係数がトーラスの要素となるような多項式の集合です。

$$ \mathbb{T}_N[x] = \{t_0+t_1x+t_2x^2+\cdots+t_nx^N|t_1, t_2, \cdots t_n \in \mathbb{T} \} $$

$\mathbb{T}[x]$上で$は\mathbb{T}$と同じく加法を定義することはできますが、乗法はできません。しかし $\mathbb{Z}[x]$ との掛け算は定義することができます。また $\mathbb{T}[x]$ も環ではありません。また、トーラスの部分群 $\mathbb{T}_{N,q}[x]=\{t_0+t_1x+t_2x^2+\cdots+t_nx^N|t_1, t_2, \cdots t_n \in \mathbb{T}_q\}$ とします。

次にトーラス多項式の集合上でLWE問題を定義します。

TGLWE

$N, q, k\in \mathbb{N}$ 、 $N$は2の累乗とする。${s} = \{s_1, s_2, \cdots , s_k\}\gets \mathbb{B}_N[x]^k$、$\hat{x}$ は$q^{-1}\mathbb{Z}_N[X]$ 上の誤差分布 、$e \gets \hat{x}$ とする。$({a}, r)$ が与えられた時以下の$D_0, D_1$のどちらなのかを判定する問題です。

$D_0 = \{({a}, r)|{a}\gets \mathbb{T}{N, q}[x]^k, r \gets \mathbb{T}{N,q}[x]\} $
$ D_1=\{({a}=(a_1, a_2,\cdots, a_k)\gets \mathbb{T}{N,q}[x]^k, r = \sum{j=1}^ks_ja_j+e, e\gets\hat{x}\} $

TGLWEをもとに暗号を構成します。ここでもTLWEと同じく平文 $\mu$ のワンタイムパッドの作成方法を紹介します。

①鍵生成

セキュリティパラメータ $\lambda$ 、整数の組 $(N, k)$ （$N$は2の冪乗）、正整数の組 $(p, q)$ （ $p$ は $q$ の約数）を選びます。$q^{-1}\mathbb{Z}_N[X]$上の誤差分布を $\hat{\chi}$ とし、$\hat{\chi}$ に従えって選ばれた誤差を $e$ 、$s=(s_1, \cdots ,s_k) \gets \mathbb{B}N[X]^k$ とします。ただし $\mathbb{B}=\{0, 1\}$ です。平文空間は $P_N[X] = \mathbb{T}{N, p}[X]$ 、公開パラメータは $\{k, N, p, q\}$ です。

②暗号化

平文 $\mu \in P_N[X]$ とした時 $\mu$ の暗号文 $c$ は以下で生成されます。

$$ c=TGLWE(\mu) = \sum^k_{j=1}s_ja_j+\mu+e $$

③復号

暗号文 $c = (a_1, a_2, \cdots , a_n, b$) の復号はまず以下の $\mu^*$ を作る。

$$ \mu^* = b-\sum^k_{j=1}s_ja_j $$

$\mu^*$ に最も近い $P$ の元をもとの平文 $\mu \in \rho$ として出力する。

TLWEはTGLWEが $N=0$ の時の形です。しかし、わざわざ分けている最も大きな理由はブートストラッピングの実装に差があるからです。また、平文が複数の時の扱いやすさや暗号文の長さなどそれぞれに良し悪しがあるため、状況によって使い分けできるようになっています。

これらの暗号の構成方法では平文を $\mathbb{T}$ （もしくは $\mathbb{T}[x]$）から選んでいました。エンコードを施せばビット列や整数を暗号化することもできます。

TFHEの仕組みは一部が非常にややこしく理解しにくい部分も多いですが、Guide to Fully Homomorphic Encryption over the Discretized Torus という解説論文が比較的読みやすいものになっています。詳しい仕組みが知りたい方は挑戦してみてください。またTFHEもライブラリが公開されており、誰でも使うことができます。

参考文献

• 佐藤宏樹, 馬屋原晃, 石巻優, 山名早人 ”完全準同型暗号による秘密計算回路のループ最適化と最近傍法への適応” DBSJ Japanese Journal Vol.16-J Article No.12, March 2018
• 佐藤宏樹, 馬屋原晃, 石巻優, 山名早人, 今林宏樹, “完全準同型暗号のデータマイニングへの利用に関する研究動向” 第15回情報科学技術フォーラム pp165-172
• Marc Joe “Guide to Fully Homomorphic Encryption over the [Discritized] Torus” October 14 2021
• 山口百合, 小口正人 “完全準同型暗号を用いた秘匿委任計算システムの動作ログデータのマイニングへの応用” DEIM Forlum 2019 I5-2
• Zavika Brakersky, Craig Gentry, Vinod Vaikuntanathan, “(Leveled) Fully Homomorphic Encryption without Bootstrapping” ACM Transactions on Computation Theory, Vol. 6, No. 3, Article 13, Publication date: July 2014.
• 完全準同型暗号の論文を読む – GSW編（２）https://blog.vippool.net/entry/2020/06/01/143002
• 草川恵太, 西巻陵, “完全準同型暗号とその応用” , July 22 2016