本記事の著者は秘密計算のベンチャー企業で働いております.
一方, 今年から暗号に触れた素人でもあり, 勉強の一環として本記事を書いています.
誤字・脱字から暗号理論の技術的詳細まで, 記事に誤りがありましたら,
ご指摘いただけますと幸いです.
本記事は, 2回連載(第1回:理論編, 第2回:実践編-ハンズオン-)の第1回.
連載の目的は, エクセルを利用した, TFHEの要点解説です.
TFHEとは, 暗号方式の一種です(トーラスを用いた完全準同型暗号).
少し唐突ですがTFHEを理解するうえで, 次の問Aは有益です(問Aは@0917laplaceさん, エクセル利用は@daikumatanさん, のideaです):
問A：
「平文をm, その暗号文をEnc(m), で表すとします.
TFHEでは, どのような方法で,
Enc(m)から暗号状態で(=復号せずに)Enc(m^2)を計算するのか？」
問Aはシンプルですが, その回答は複雑です.
そこで本連載では, 問Aの回答を理解するために, より簡単な問Bを考えます：
問B：
「TFHEでは, どのような方法で, 平文mから平文m^2を計算するのか？」
勿論, 平文の場合, 例えばm=0.3の時, m^2=0.09と直接計算できます.
しかし, 直接計算という手法は,暗号状態でのEnc(m)からEnc(m^2)の計算へ応用できません. なぜなら, Enc(m)を復号しないと, mの値は分からないためです.
本連載では, 暗号状態でのEnc(m)からEnc(m^2)の計算へ応用可能な,
平文状態でのmからm^2の計算手法について,
第1回：理論編では, 高校数学程度の数式を用いて解説します.
第2回：実践編では, エクセルを用いてハンズオン解説します.
本連載を通じて, TFHEの理解向上の一助になりましたら幸いです.
本連載エクセルハンズオンの続編にあたる
「エクセルを利用した, 暗号状態でのEnc(m)からEnc(m^2)の計算」は,
弊社第2回暗号勉強会にて体験していただける「予定！」です.
https://connpass.com/event/341101/
よろしかったらご参加ください.
繰り返しで恐縮ですが, 本記事の著者はTFHE暗号の専門家ではありませんので,
厳密に理解されたい方は, 原著論文や解説論文をご一読ください.
それでは本連載第1回の内容に入ります. 本記事の流れは以下の通りです:
1.暗号の基礎(平文, 暗号文, 暗号化, 復号化);
2.準同型暗号・完全準同型暗号;
3.TFHEの要点;
4.TFHEの計算方針.
4.が最も重要です(問Bに回答します).
1., 2., 3.を読まなくとも, 4.を読んで理解することは可能です.
本連載では, 平文状態での計算のみを扱いますが,
TFHEの特徴の理解のため, 1.-3.では, 暗号の一般論を解説します.
1.暗号の基礎:
必要最小限の解説に留めます.
「暗号とは, ある情報(平文)を,
特別な情報(鍵)を用いて, 他人に簡単には読めない情報(暗号文)に変換して,
必要な人が特別な情報(秘密鍵)を用いて, 元の情報(平文)に戻せる仕組みです.」
本連載において, 平文, 暗号文のとりうる範囲は,
実数またはその部分集合と思っていただいて構いません. また,
暗号化： 平文 → 暗号文
復号化： 暗号文 → 平文
暗号化/復号化では, 鍵を利用しますが,
本連載では, 問Bへの回答が目的のため, 鍵の記述は省略します.
(同様な理由により, encode/decode, LWE暗号, RLWE暗号, RGSW暗号などについても省略します).
2.準同型暗号(HE)・完全準同型暗号(FHE)
2.1.準同型暗号(Homomorphic Encryption)
Encをある暗号方式とします.
つまり, 平文mに対して, その暗号文をEnc(m)で表すとします.
Encが加法準同型暗号とは, 全ての平文m, nに対して,
Enc(m) + Enc(n) = Enc(m+n)
を満たすことをいいます.
同様に, Encが乗法準同型暗号とは, 全ての平文m, nに対して,
Enc(m) × Enc(n) = Enc(m×n)
を満たすことをいいます.
2.2.完全準同型暗号(Fully Homomorphic Encryption)
Encをある暗号方式とします.
Encが完全準同型暗号(FHE)とは, 以下の2条件を満たすことを言います：
(1)Encが加法かつ乗法準同型暗号;
(2)暗号文の加法と乗法を「任意の回数(何回でも!)」実行できる.
3.TFHEの要点
3.1.TFHEの直訳
TFHEとは, 原著論文に従うと, 以下の略です:
(Fast) Fully Homomorphic Encryption over the Torus.
つまり, TFHEの直訳は, Torus上の完全準同型暗号(FHE)です.
直訳に従い, 以下では, Torusの定義の説明から始めます.
個人的な意見ですが, Torusは手段であって, 目的ではないように思います.
つまり「Torusの定義」を理解すること以上に,
「Torusを利用して何を実現したいか(以下の3.3(2))」を理解することが重要です.
3.2.Torusの定義
「トーラス(Torus)とは, 0以上1未満の実数の集合.
ただし, 整数部分は無視する(1の加法減法は無視する）」
厳密には, トーラスとは実数体を整数環で割った商加群のこと.
トーラスをTで表すとします. 例えば, Tでは,
0.1 = 1.1 = 2.1 = 3.1 = ...(Tでは, 1の加法減法を無視)
が成り立ちます.
またTでは, 足し算, 引き算, スカラー倍が定義されています：
0.3 + 0.8 = 1.1 = 0.1 (Tでは, 1の加法減法を無視）
0.3 - 0.7 = -0.4 = -0.4 + 1 = 0.6 (Tでは, 1の加法減法を無視）
3・0.4 = 0.4 + 0.4 + 0.4 = 1.2 = 0.2 (Tでは, 1の加法減法を無視）
Tでは, 少なくとも以上と同様には, 乗法除法は定義できないです.
理由を考えてみてください. ひとまずTの説明は以上です.
3.3.TFHEが満たす性質
EncをTFHE暗号とします. この時, Encは以下の性質を満たします:
(1)Encは完全準同型暗号;
(2)f：T → Tを任意の1変数関数とします
(n倍, n乗, 1変数多項式関数, 絶対値関数, sin関数など何でも良い!).
mを平文とします(特に, m, f(m)はTに属しています). この時,
Enc(m)から暗号状態で(=復号せずに), Enc(f(m))を計算できる.
TFHEの特徴は(2)に凝縮されていると思いましたので,
本連載では(2)を具体例・ハンズオンを通して要点解説します.
分かりやすさのため, 以下では「f=2乗関数」の場合を考えます.
「f=2乗関数」とする理由は, 以下で述べるPBSが必要となる関数fのなかで,
最も簡単だからです. 2倍関数の場合, PBSは不必要です(2.1より分かります).
4.TFHEの計算方針
4.1.Programmable Bootstrapping
冒頭で述べました問A, Bを再掲します：
問A：
「Enc(m)をTFHE暗号方式とします.
TFHEでは, どのような方法で,
Enc(m)から暗号状態で(=復号せずに)Enc(m^2)を計算するのか？」
問B：「TFHEでは, どのような方法で, 平文mから平文m^2を計算するのか？」
問A, Bの回答は, どちらも,
Programmable Bootstrapping (PBS)
という計算方法です.
より詳細には, PBSは次の4操作を合成した操作です(右から順に行う):
Programmable Bootstrap
= (Key Switch) ○ (Sample extract) ○ (Blind Rotate) ○ (Rescale)
PBSにおいて最も重要な操作は Blind Rotation です. 本連載では,
「PBSを用いた暗号状態でのEnc(m)からEnc(m^2)の計算」を理解するため,
「PBSを用いた平文状態でのmからm^2の計算」を要点解説します.
勿論, 平文の場合, 例えばm=0.3の時, m^2=0.09と直接計算できますが,
直接計算という手法は暗号状態でのEnc(m)からEnc(m^2)の計算へ応用できません.
以下では, 暗号状態でのEnc(m)からEnc(m^2)の計算へ応用可能な,
平文状態でのmからm^2の計算手法を解説します.
4.2.PBSを用いた平文mから平文m^2の計算(トイモデル)
平文空間を, 0.00, 0.01,0.02, ... , 0.99までの100パターンとします.
Step.1.Look up tablesの作成:
ある特定の平文mを入力する前に,
全ての平文mに対して, 平文の演算結果m^2を用意した表を作成します.
この表は Look up tables と呼ばれます:
| i | m | m^2 |
|---|---|---|
| 1 | 0.00 | 0.0000 |
| 2 | 0.01 | 0.0001 |
| 3 | 0.02 | 0.0004 |
| 4 | 0.03 | 0.0009 |
| … | … | … |
| 30 | 0.30 | 0.0900 |
| 31 | 0.31 | 0.0961 |
| 32 | 0.32 | 0.1024 |
| … | … | … |
| 100 | 0.99 | 0.9801 |
Step.2.平文の入力:
平文mをPBSに入力します.
以下では, m=0.31の場合を考えます.
Step.3.指数の決定:
上の表の第2列に位置する入力mに対応した, 第1列の指数iが定まります.
例えば, 平文m=0.31の場合, 指数i=31となります.
Step.4.Rotate(回転)：
Step.3で定まった指数iを利用して,
「表の第3列の各値の位置を指数iだけ上にずらした列」を第4列に作成します.
第3列から第4列を作成することは Rotate(回転) と呼ばれます.
暗号文状態で行う際は, Blind Rotate と呼ばれます.
例えば, 平文m=0.31の場合, 指数i=31となり, Rotateは以下の通りです:
| i | m | m^2 | Rotate (shifted up by 31) |
|---|---|---|---|
| 1 | 0.00 | 0.0000 | 0.0961 |
| 2 | 0.01 | 0.0001 | 0.1021 |
| 3 | 0.02 | 0.0004 | … |
| 4 | 0.03 | 0.0009 | |
| … | … | … | … |
| 30 | 0.30 | 0.0900 | |
| 31 | 0.31 | 0.0961 | |
| 32 | 0.32 | 0.1024 | … |
| … | … | … | … |
| 100 | 0.99 | 0.9801 | 0.0900 |
Step.5.Sample Extract(抽出):
表の第4列i=1の値を取り出します(Sample Extractに対応).
例えば, m=0.31の時, 表の第4列i=1である0.0961が取り出せます.
この0.0961は, PBSの出力です.
以上をまとめると, PBS(という操作または関数)に,
0.31を入力した時, 0.0961が出力されたことになります.
実際に (0.31)^2=0.0961 を満たします. 他の値でも同様です.
計算手続きは面倒ですが, PBSは2乗関数の役割を果たしていることが分かります.
以上が数式を用いた「PBSを用いた平文mからm^2の計算」の要点解説でした.
これにて, 本連載第1回：理論編 が終了です.
読者の方は, 貴重なお時間をありがとうございました.
本連載第2回：実践編では, 以上をエクセルを用いてハンズオン解説します.
それではまた明日!
Have a nice Christmas!