この記事は EAGLYS Advent Calendar 2022 の1日目の記事です
はじめに
TFHEに触れ始めてから１年弱経ったこともあり，人に聞かれることも増え始めてきたこの頃，今回のアドカレでTFHE関連の話題を予備知識なしの状態から始めて，詳細までまとめようと思います
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
今回のアドカレの関連記事（気になるところから読んでください）
TFHEの概要
１日目（イマココ）：Torus・TLWEの概要
５日目（TRLWE・TFHEの概要）：
10日目（プログラマブルブートストラップの概要）：
TFHEの詳細
11日目（TFHEの暗号化方式の詳細（前半））：
12日目（TFHEの暗号化方式の詳細（後半））：
18日目（プログラマブルブートストラップの詳細（前半））：
19日目（プログラマブルブートストラップの詳細（後半））：
multi-key TFHEの概要
15日目（multi-key TFHEの概要）：
TFHEの最新動向
20日目（TFHEの最新動向（理論編））：
25日目（TFHEの最新動向（実装編））：
TFHEについて
まずは１・５日目でTFHEの概要を整理します
TFHE は，Torus上のRLWE問題を安全性の根拠とする暗号化方式です
これらを理解するには
- Torus
- TLWE
- 多項式環
- TRLWE
の順で理解すると良いと思います
今回は上2つのTorusとTLWEについて扱います
Torus
＊Torusは $\mathbb{R}/\mathbb{Z}$ のこと，と書いて分かる方や剰余類をご存知の方は，ここは飛ばしていただいて構いません
＊Torusの幾何的な性質には触れません
実用上はTorusは「0以上1未満の実数全体の集合で，足し算とスカラー倍が定義されている」ぐらいの理解で十分です
Torusについて
＊数学的に厳密でない箇所もあるのでご了承ください
例えば，整数に対して，2で割ったときの余りは0か1しかありません
もう少し深く考えてみると，整数を2で割った余りが0ならその整数はいわゆる偶数ですし，余りが1なら奇数です
逆に，偶数を2で割った余りは0であり，奇数を2で割った余りは1です
すると，「2で割ったときの余りは0か1」といったとき，この0を整数の0ではなく，偶数全体を表す集合の記号だと思うことができます
つまり，その集合を分かりやすく$\overline{0}$と表記すると，$\overline{0}$は0, 2, -6, 10 などの元をもつ集合であり，これは偶数全体を含む（偶数を尽くしている）ので，$\overline{0}$を偶数全体の集合だと思えます
また，$\overline{1}$で奇数全体の集合と表します
このように考えると，整数全体の集合は$\overline{0}$と$\overline{1}$に分割することができます
整数は偶数か奇数のどちらかですので，$\overline{0}$か$\overline{1}$に属さない整数は存在しません
また，偶数かつ奇数という整数は存在しないため，$\overline{0}$と$\overline{1}$の共に属する整数も存在しません
以上をまとめると，「整数に対して，2で割ったときの余りは0か1」という事実から，「整数全体を2で割ったときの余りが0か1になる集合に分割できる」ことがわかります
整数全体を2で割ったときの余りが0になる集合の要素，つまり，2で割ったときの余りが0になる整数を普段は偶数と呼んでいるわけです
このとき，実数全体の集合のうち，1で割ったときの余り全体の集合を考えます
例えば，0とか0.2とか0.99とかですね
整数のときと同様に考えると，$\overline{0.2}$ で実数を1で割ったときに0.2余る実数の集合だと思うと，「実数全体を1で割ったときの余りが1未満になる集合に分割できる」ことになります
そのような集合をTorusといい，$\mathbb{T}$と書きます
＊つまり，$\displaystyle \mathbb{T} = \cup_{x \in [0, 1)} \overline{x}$ です
言ってしまえば，Torusは「集合の集合」なわけです
つまり，Torusの元は厳密には集合となります
Torusの演算
上記で与えられるTorusに入る演算について考えてみます
足し算や掛け算がどう定義されるかについてで，例えば「集合と集合を足し算する」というのは非自明な演算ですから，しっかりと定義する必要があります
足し算
と言っても難しいことを考える必要はなく，実は，0以上1未満の実数 $x, y$ に対して，$\overline{x}, \overline{y} \in \mathbb{T}$ を取ると，$\overline{x} + \overline{y} = \overline{(x + y) \ \mathrm{mod} \ 1}$ となります（集合として等しい，という意味の等号）
$\overline{x}, \overline{y}$ はともに集合なので，集合の足し算は次のように定めています:
まず，$\overline{x}$ と $\overline{y}$ から任意に元を取り，それぞれ $\tilde{x}, \tilde{y}$ とします
つまり，$\tilde{x}, \tilde{y}$ は，共に1で割ると余りが $x, y$ それぞれを1で割ったときの余りと同じ実数です
そして，これら $\tilde{x}, \tilde{y}$ を動かした際の $\tilde{x} + \tilde{y}$ 全体の集合が $\overline{x}$ と $\overline{y}$ になります
まとめると，$\overline{x} + \overline{y} = ${$\tilde{x} + \tilde{y} \ | \ \tilde{x} \in \overline{x}, \tilde{y} \in \overline{y}$} です
この集合が $\overline{(x + y) \ \mathrm{mod} \ 1}$ と一致する，ということです
＊$\overline{x} + \overline{y} \subseteq \overline{(x + y) \ \mathrm{mod} \ 1}$ とその逆を確かめればOKですが，今回は省略
大雑把には，「普通に足して1で割った余りをとる」で実用上は十分でしょう
掛け算
足し算と同様に考えて，0以上1未満の実数 $x, y$ に対して，，$\overline{x}, \overline{y} \in \mathbb{T}$ を取ると，$\overline{x} \cdot \overline{y} = \overline{(x \cdot y) \ \mathrm{mod} \ 1}$ になるかを考えます
＊$x, y$ は0以上1未満なので，右辺は $\overline{x \cdot y}$ でもいいのですが，本質じゃない
しかし，実は一般にこれは成り立ちません
$\overline{x} \cdot \overline{y} \subseteq \overline{(x \cdot y) \ \mathrm{mod} \ 1}$ も $\overline{(x \cdot y) \ \mathrm{mod} \ 1} \subseteq \overline{x} \cdot \overline{y}$ も一般には成り立たないためです
なんですが，掛け算が定義できない，というのとは少し違います
まあこの辺はあんまり深く悩んでもしょうがない（本当はしょうがなくない）ので，掛け算については考えないこととします
＊ill-defiendってやつです，not defiend とは異なります
スカラー倍
ここでいうスカラーは実数全体のことです
$r$ を任意の実数としたとき，$r \cdot \overline{x} = \overline{(r \cdot x) \ \mathrm{mod} \ 1}$ と定義します
集合に対するスカラー倍は次のように定義します:
まず，$\overline{x}$ から任意に元を取り，$\tilde{x}$ とします
つまり，$\tilde{x}$ は，1で割ると余りが $x$ を1で割ったときの余りと同じ実数です
そして，この $\tilde{x}$ を動かした際の $r \cdot \tilde{x}$ 全体の集合が $r \cdot \overline{x}$ になります
まとめると，$r \cdot \overline{x} = ${$r \cdot \tilde{x} \ | \ \tilde{x} \in \overline{x}$} です
この集合が $\overline{(r \cdot x) \ \mathrm{mod} \ 1}$ と一致する，ということです
＊$r \cdot \overline{x} \subseteq \overline{(r \cdot x) \ \mathrm{mod} \ 1}$ とその逆を確かめればOKですが，今回は省略
大雑把には，「普通に実数を掛けて1で割った余りをとる」で実用上は十分でしょう
Torus のまとめ
色々書きました（剰余類とかwell-definedとか）が，よく分からんって方は初めの「0以上1未満の実数全体の集合で，足し算とスカラー倍が定義されている」だけ押さえてください
掛け算云々の話をしたいときぐらいしか，Torusの元は本当は集合，というのを意識しないと思います
TLWE
TLWE とは，Torus上のLWE問題のことです
分布の識別の形だと扱いづらいので，次のように変形します
この問題はNP完全なので，とても難しい（こなみかん）です
どのぐらい難しいのかのイメージは 「プログラマブルブートストラップの原著論文を理解する回」を理解する回 2/4「TLWEとTRLWE」 をご参照ください
まとめ
今回はTFHEの準備のためにTorusとTLWEを扱いました
Torusは色々書きましたが，Torusのまとめの箇所を押さえていれば，実装上とかは困らないのかなと思っています
次回はTRLWEとTFHEの暗号化方式を扱います
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
参考文献
縫田 光司 : 耐量子計算機暗号, 森北出版, 2020.
I. Chillotti, M. Joye, P. Paillier: ``Programmable bootstrapping enables efficient homomorphic inference of deep neural networks'', In: International Symposium on Cyber Security Cryptography and Machine Learning. Springer, Cham, pp. 1-19, 2021.