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

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