エクセルで理解するTFHE暗号（part1/2 理論編）

本記事の著者は秘密計算のベンチャー企業で働いております.  
一方, 今年から暗号に触れた素人でもあり, 勉強の一環として本記事を書いています. 
誤字・脱字から暗号理論の技術的詳細まで, 記事に誤りがありましたら, 
ご指摘いただけますと幸いです. 

本記事は, 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!