この記事はEAGLYS Advent Calendar 2021の7日目の記事です。
昨年リアルタイムで追っていたカレンダーをまさか自分が書く側になるとは・・・．
自己紹介
耐量子計算機暗号（特に符号ベース暗号）を研究している修士１年です．
普段Qiitaでは量子関連（まだ量子アルゴリズムのスクラッチ実装と量子ブロックチェーンの勉強したての記事のみですが・・・）を扱い，
Zennでは，古典関連（耐量子暗号やプログラマブルブートストラップの解説記事）を扱っています（唐突な宣伝）．
プログラマブルブートストラップの原著論文を理解する回 1/4
何をするのか
秘密計算の会社の記事，ということで，Qiitaですが古典の内容を投稿します．
以下の記事を連載中です．
プログラマブルブートストラップの原著論文を理解する回 1/4
プログラマブルブートストラップ(programmable bootstrap)とは，秘密計算という分野で，主に使われている手法です．
格子暗号のTFHE方式の暗号文に少し手を加えて任意の演算を可能にしつつもそこに生じるノイズを取り除く技術のことです．
その元となったプログラマブルブートストラップの論文の理論を解説する記事です．かなりしっかり目に書いたんですが，如何せん長い．
折り畳みまで全て読むと１発目の記事だけで4万字を超えます．印税ほしい．
というわけで，上記の記事の地の文＋少しばかりの折り畳みの要約を扱います．
ある程度しっかりした解説を読みたいけど，しっかりしすぎも困るという方向けです．
これから投稿していく記事を参照すれば，論文中の理論は理解できるようにします．
ただ，ちょっとした数学的な背景や理論の深掘りも含めて知りたい方はZennの記事を参照してください．
Qiitaの方では割とさらっと書いたりしますし，Zennを全て読むのはしんどいと思われるので，気になった部分を斜め読みとかがいいかもしれません．
また，以下の内容は共通で扱いません．
- プログラマブルブートストラップの直感的な説明
- プログラマブルブートストラップの発展過程やこの先どこへ向かうのか
- プログラマブルブートストラップの実装に向けた話
- ニューラルネットワークなどAI系への応用
- 美味しいラーメン屋の紹介
まず１と２に関しては，下記の記事が詳しいです．分かりやすい！
3についてもこちらの連載の記事が詳しいです（理論解説のため実装まで踏み込めない）．これも分かりやすい！
続いて4ですが，この原著論文の第５章を参考にしてください．
5は何なら僕に教えてください．
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
全４回通しでの目次
第１回（イマココ）
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 2.2 Probability Distributions
- 離散一様分布と正規分布
- 実数から整数への丸め
第２回
- Appendix A : Complexity Assumptions Over the Real Torus
- TLWEとTRLWE
- 3章前説
- 3章の流れ
- ギリシャ文字と花文字
- $\hat{\mathbb{Z}}$ と $\hat{\mathbb{T}}$
- 3章前説の議論
- 3.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
第３回
第４回
さて，今回は記念すべき（何の？）第１回目ということで，
2. Preliminaries
2.1 Torus and Torus Polynomials
2.2 Probability Distributions
を扱います．
具体的な内容としては，次のようになります:
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 2.2 Probability Distributions
- 離散一様分布と正規分布
- 実数から整数への丸め
今回は本題というより，準備ということで，数学的な内容が多めです．本論文の議論の流れやこの記事を読むにあたっての前提知識にも触れます．
何に注意して議論を解説するかなどは次回整理します．
それでは早速見ていきましょう．
本論文全体の流れ
- どういう背景や課題・モチベーションがあって，
- どのようなアイディアのもとで，
- どのような結果が得られたのか
を整理します．
背景・課題
完全準同型暗号を達成する暗号として格子暗号ベースが考えられています．
格子暗号は簡単には暗号文にノイズを付与することで，安全性を保証しており，
暗号文を何度も演算するとノイズが増大する問題は，ブートストラップと呼ばれる技術で解消できます．
このブートストラップを実用性のあるものにすべく，TorusベースのTFHE方式（提唱者の頭文字をとってCGGI方式とも）が考えられました．
しかし，このTFHE方式の暗号化では，暗号文に任意の演算，特に非線型演算($\exp$とか)を与えるのが難しいとされていました．
アイディア
従来のブートストラップにleveled operation（演算回数に制限をつける）で解決です
結果
暗号文で任意の演算が可能になりました．やったね！
それらを元に各章を整理すると，次のようになります:
1章：イントロ
2章：前提知識
3章：TFHE方式
4章：ブートストラップとプログラマブルブートストラップ
5章：Neural Network への応用
つまり，３章と４章の前半までが「準備段階」で，４章の後半が一番言いたいことになります．
ただ，発想自体は別に難しいものではなく，むしろ「準備段階」が一番難しいため，今回の記事を書くに当たったというわけです．
前提知識と進め方
なるべく丁寧に解説することは心がけますが，
- （素朴）集合論（$\neq$ 公理的集合論）：全射・単射・全単射・直積
- 線型代数：行列の和や積・行列式
- 確率・統計：確率分布・確率密度関数
- 代数：Abel群・可換環・体の定義
- 初等整数論：mod
- 計算量理論：クラスPとNP
ぐらいは前提知識とします（サイレント修正の可能性あり）．知らなくてもググればどうにかなるかもです．
また，次の記号を使います（使わないものもあるかもですが）:
- $\mathbb{N}$ : 自然数全体の集合，0を含む
- $\mathbb{Z}$ : 整数全体の集合
- $\mathbb{Q}$ : 有理数全体の集合
- $\mathbb{R}$ : 実数全体の集合
- $\mathbb{C}$ : 複素数全体の集合
- $\mathbb{B} =$ {$0, 1$}
- $x \overset{$}{\leftarrow} X$ : 集合 $X$ から要素 $x$ をランダムに取る
- Def : 定義
- Thm : 定理
＊Zennの記事では，主に参考にした書籍をずらずら載せていますが，今回は最後に参考文献の形で紹介しています
Torus
トーラスと聞くと，「ドーナツ（本当は浮き輪）の形」を思い浮かべる方もいらっしゃるかもしませんが，
分野が暗号ということで，幾何的なイメージよりも代数的な操作を意識します．
だいぶ大雑把ではありますが，Torus（群）の理解は次で十分でしょう．
Torusとは0以上1未満の実数全体で，和を考えるときは整数部分は無視する
$\underline{\mathrm{Def(Torus)}}$
Torus とは $\mathbb{R} / \mathbb{Z}$ なる集合のことであり，$\mathbb{T}$ と表す．
この集合は，0以上1未満の実数全体の集合とみなせて，$x, y \in \mathbb{T}$ に対して，演算 $+$ が $x + y \ \mathrm{mod} \ 1$ のようにして定まっている．
$(\mathbb{T}, +)$ はAbel群になっている
$x, y \in \mathbb{T}$ に対して，とは，$\mathbb{T}$ の任意の変数 $x, y$ に対して，という意味です．
「みなせて」の部分について
小数点以下が一致する実数は１つの集合にまとめて，その集合を1つの実数とみなす，ということです．
$x$ を0以上1未満の実数とするとき，それに対応する $\mathbb{T}$ の元 $\overline{x}$ は，{$ x + n \ | \ n \in \mathbb{Z}$} という集合を表しています．
ただし， $\overline{x}$ という集合を扱うところを，$\mathbb{T}$ の元として，もしくは，$\mathbb{T}$ 内での足し算を扱う際にはその集合の元 $x$，特に0以上1未満になるような $x$ で議論を進めても問題ないので，あまり深く意識する必要はありません．
上記では $\mathbb{T}$ 内の足し算を定義しましたが，一方で$\mathbb{T}$ 内の掛け算は「上手くいかない」（well-defined ではない）ので，実用上では考える必要がありません．
加群
しかし，$\mathbb{T}$ は積だと上手くいかないね，残念だねで終わってしまうのではなく，$\mathbb{Z}$加群の構造が入ることに注目します．
要するに，$\mathbb{T}$ での積っぽいものとして，スカラー倍を考えます．すると，和とスカラー倍に関して，分配法則を含めた良い感じの代数構造が入り，それを加群と言います．
以下，環といったら零環ではなく，また，単位元を持つものとします．また，簡単のため可換環の場合のみを考えます．
$\underline{\mathrm{Def(加群)}}$
$R$ を可換環，$M$ を空でない集合として，$R$ 加群 $M$ とは，$(M, +)$ は Abel 群であり，以下の演算が定義されている:
R \times M \ni (r, x) \mapsto rx \in M \\
M \times R \ni (x, r) \mapsto xr \in M
このとき，$a, b \in R, \ x , y \in M$ として，次の４つの条件を満たすものとする:
\begin{align}
& (1) \hspace{10pt} 1 x = x \\
& (2) \hspace{10pt} a (bx) = (ab) x \\
& (3) \hspace{10pt} (a + b) x = a x + b x \\
& (4) \hspace{10pt} a (x + y) = a x + a y \\
\end{align}
小学校のとき $3 + 3 + 3 + 3 + 3$ のことを $3 \times 5$ と書くのが掛け算というのをやったはずです．
スカラー倍はそれと同じことで，複数回の足し算を一々書くのがめんどくさいのでスカラー倍を導入しています．なにか難しいことをやっているわけではありません．
一般に和で閉じている集合の要素 $t$ への $K$ 倍は，
整数 $K$ が自然数なら，$t$ を $K$ 回足すこと
整数 $K$ が負の整数なら，$- t$ を $- K$ 回足すこと
に対応します．
今回の $\mathbb{T}$ は $\mathbb{Z}$ 加群になっています．
多項式環
次に多項式環というものを考えます．特に１変数の場合です．多項式の次元についても導入します．
多項式を元とする環を考えます．
$\underline{\mathrm{Def(多項式環)}}$
可換環$R$に対して，文字 $X$ を不定元とする，$R$ 係数の($R$ 上の)多項式とは，
$$\begin{align*}
\displaystyle a_n X^n + a_{n - 1} X^{n - 1} + \cdots + a_1 X + a_0 = \sum_{i = 0}^n a_i X^i \hspace{10pt} a_i \in R
\end{align*}$$
なる形のものである．
多項式として0のもの（$f(X) = 0$ なる $f$）を零多項式と呼び，零多項式以外の$R$ 係数の($R$ 上の)多項式 $f(X)$ について
\begin{align*}
\displaystyle \mathrm{max} \{ 0 \leq i \ | \ a_i \neq 0 \}
\end{align*}
なる整数が存在し，これを多項式 $f(X)$ の次数と呼び，$\mathrm{deg} \ f(X)$ と書く．
ここで，零多項式の次数は $- \infty$ とする．即ち，$\mathrm{deg} \ 0 = - \infty$ である．
大雑把には，多項式の次数はそれぞれの項のうち，最大の次数のものを表します．
例としては，実数係数の多項式 $f(X) = X^2 + x + 1$ において，$\mathrm{deg} \ f(X) = 2$ です．
$- \infty$ は任意の整数より小さい整数，というイメージでいいと思います．急に$- \infty$ が出てきて意味わからんかもしれませんが，そう定義すると都合の良い場面があるからです．意識する場面は少ないですが・・・．
既約多項式と円分多項式
既約多項式は大雑把には「これ以上割り切れない多項式」で，
円分多項式は 「$X^M - 1$ を割り切る $M - 1$ 次以下の既約多項式」のことです．
$\underline{\mathrm{Def(既約多項式)}}$
$R$ 係数の多項式 $f(X)$ が既約多項式であるとは，次数が $\mathrm{deg} \ f(X)$ 未満の $R$ 係数の多項式で割り切れないことである．
$\underline{\mathrm{Def(円分多項式)}}$
$M$ を正整数とするとき，$M$ 次の円分多項式 $\Phi_M(X)$ とは，既約多項式であって，$X^M - 1$ を割り切るが，任意の $k < M$ で $X^k - 1$ を割り切らない多項式のことである．
既約多項式は考える $R$ によって既約かどうか異なることに注意しましょう．
例えば，$x^2 + 1$ という多項式は $\mathbb{R}$ 上では（実数係数では）既約多項式ですが，$\mathbb{C}$ 上では（複素係数では）既約多項式ではありません．$(x + \sqrt{-1})(x - \sqrt{-1})$ と因数分解できるからです．
円分多項式を次数が小さい順に列挙すると，$\Phi_1(X) = X - 1, \ \Phi_2(X) = X + 1, \ \Phi_3(X) = X^2 + X + 1, \ \Phi_4(X) = X^2 + 1$ です．
定義から自明ではありませんが，$M$ 次の円分多項式は一意に定まります．すごい！
Torus上の多項式
2.1 最後です．Torus上の多項式を考えます．
自然数 $N$ を取って，次の多項式環を考えます:
\begin{align*}
\mathbb{R}_N[X] & := \mathbb{R}[X] / (X^N + 1) \\
\mathbb{Z}_N[X] & := \mathbb{Z}[X] / (X^N + 1)
\end{align*}
元を具体的に書くと，$r_0, r_1, \cdots, r_{N - 1} \in \mathbb{R}$ として，
r_0 + r_1 X + \cdots + r_{N - 1} X^{N - 1} \in \mathbb{R}_N[X]
であり，$z_0, z_1, \cdots, z_{N - 1} \in \mathbb{Z}$ として，
z_0 + z_1 X + \cdots + z_{N - 1} X^{N - 1} \in \mathbb{Z}_N[X]
です．
イメージとしては，$\mathbb{Z}$ 上の多項式全ては計算機には扱えないから，多項式の次数を有限に抑える感じです．
さて，Torus上の多項式を次のように表します:
$$\mathbb{T}_N[X] := \mathbb{R}_N[X] / \mathbb{Z}_N[X]$$
よって，$\mathbb{T}_N[X] = \mathbb{T}[X] / (X^N + 1)$ です．
これも元を具体的に書くと，$t_0, t_1, \cdots, t_{N - 1} \in \mathbb{T}$ として，
t_0 + t_1 X + \cdots + t_{N - 1} X^{N - 1} \in \mathbb{T}_N[X]
です．$t_0, t_1, \cdots, t_{N - 1}$ は全て0以上1未満の実数と考えても問題ないです．
$\mathbb{T}$ は
- 和でAbel群
- 整数のスカラー倍を考えられる
と同様に，$\mathbb{T}_N[X]$ は
- 和でAbel群
- 整数のスカラー倍を考えられる
ことに注意しましょう．
ただし，先ほどのTorusと同じように掛け算を考えてもあまり意味はないので，$\mathbb{T}[X]$ は環ではありません．
離散一様分布と正規分布
ここから2.2で確率分布に入っていきます．
離散一様分布と正規分布を扱います．
$\underline{\mathrm{Def(離散一様分布)}}$
$N$ を正整数とする．確率変数 $X$ の確率密度関数が
\begin{align*}
\displaystyle
\forall x \in \{ 1, 2, \cdots, N \}, \ f(x) = \frac{1}{N}
\end{align*}
のとき，$X$ は集合 {＄1, 2, \cdots, N$} 上の離散一様分布に従う，という．
$\underline{\mathrm{Def(正規分布)}}$
パラメータ $\mu, \sigma$ で，確率変数 $X$ の確率密度関数が
\begin{align*}
\displaystyle
f(x) = \frac{1}{\sqrt{2 \pi} \sigma} \exp \left \{ - \frac{(x - \mu)^2}{2 \sigma^2} \right \}
\end{align*}
のとき，$X$ は $N(\mu, \sigma)$ の正規分布に従う，という．
正規分布は実数上で考えていますが，離散一様分布は整数上で考えています．正規分布は中々に「性質が良い」のですが，計算機上で扱うには実数を整数へ「丸め」る必要があります．
実数から整数への丸め
上記では正規分布を考えましたが，実際に扱うのは実数ではなく整数ですので，実数を整数へと「丸める」必要があります．そのときにどういうものを想定するかというと，「四捨五入」だと思います．
本論文でも四捨五入を使っていますが，$x$を実数としたとき，$\lfloor x \rceil$ という記号を使っています．これはなんなのでしょうか．
$\underline{\mathrm{Def(floor \ function)}}$
$x$を実数としたとき，$\lfloor x \rfloor$ を $x$ の floor function といい，次のように定める:
\begin{align*}
\lfloor x \rfloor = \mathrm{max} \{ n \in \mathbb{Z} \ | \ n \leq x \}
\end{align*}
$\underline{\mathrm{Def(ceiling \ function)}}$
$x$を実数としたとき，$\lceil x \rceil$ を $x$ の ceiling function といい，次のように定める:
\begin{align*}
\lceil x \rceil = \mathrm{min} \{ n \in \mathbb{Z} \ | \ x \leq n \}
\end{align*}
いわゆる，floor function が「切り捨て」で，ceiling function が「切り上げ」です．
$\lfloor x \rceil$とは，これらを組み合わせた記号のことです．四捨五入，と定義してもいいのですが，上記の floor function なりを用いると，次のように定式化できます．
$\underline{\mathrm{Def(round \ function)}}$
$x$を実数としたとき，$\lfloor x \rceil$ を $x$ の round function といい，次のように定める:
\begin{align*}
\displaystyle
\lfloor x \rceil = \lfloor x + \frac{1}{2} \rfloor (= \mathrm{max} \left \{ n \in \mathbb{Z} \ | \ n \leq x + \frac{1}{2} \right \} = \mathrm{min} \left \{ n \in \mathbb{Z} \ | \ x - \frac{1}{2} < n \right \})
\end{align*}
具体的に本論文では，どのように丸めているかを紹介します．
$q$ を正整数として，$(\mathbb{Z} / q \mathbb{Z})^{\prime}$ という集合を 次のように取ります:
\begin{align*}
\displaystyle
(\mathbb{Z} / q \mathbb{Z})^{\prime} = \left \{ \lceil - \frac{q}{2} + 1 \rfloor + nq , \cdots , \lceil \frac{q}{2} \rfloor + nq \right \}
\end{align*}
そして，任意の整数 $n$ を $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right] \bigcap \mathbb{Z}$ 上の整数に対応させる操作を $\mathrm{mod}^{\prime} \ q$ と書くことにします．
＊なぜ半開区間なのかというと，「この端点だと全ての $q$ で半開区間の場合のみ $\mathrm{mod} \ q$ での異なる $q$ 個の代表元を含むから」です
例えば，$q = 5$ のとき，$11 \equiv 1 \ \mathrm{mod}^{\prime} \ 5$, $13 \equiv -2 \ \mathrm{mod}^{\prime} \ 5$ です．
＊上では通常の $\mathrm{mod}$ を通して， $11 \equiv 1 \equiv -4 \mathrm{mod} \ 5$ と $13 \equiv 3 \equiv -2 \mathrm{mod} \ 5$ で，$[-2, 2]$ に属するものを考えています．
このとき，実数値 $X$ と正整数 $q$ を取ります．そのとき整数値 $Z$ を $Z = \lfloor X q \rceil \ \mathrm{mod}^{\prime} \ q$ で定めます．この $Z$ は，$(\mathbb{Z} / q \mathbb{Z})^{\prime}$ の元ですので，$X$ を「整数に丸めた」値となっています．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
参考文献
集合論
初学者向け
集合と位相空間
かなりまとまっている本
集合と位相(増補新装版)(数学シリーズ)
線型代数
初学者向け
線型代数
数学書っぽい雰囲気を味わいたい方向け，あとは加群を見据えて単因子論をやりたい方向け
線型代数入門
確率・統計
実用性のコスパ的には一番良い気がします
統計学入門
代数
群の初学者向け（たぶん）
代数学1 群論入門
環・環上の加群・Galois理論の初学者向け（環以外は少し読みづらいかも）
代数学2 環と体とガロア理論
群・環・環上の加群を復習したい方むけ（初学はかなりきつそう）
代数入門(新装版): 群と加群 (数学シリーズ)
環上の加群（あまり読んでないです）
代数学〈2〉環上の加群 (大学数学の入門)
体・Galois理論の初学者向け（薄いけど例もきっちり書かれています）
代数学〈3〉体とガロア理論 (大学数学の入門)
＊環上の加群，は「ホモロジー代数」を扱った本でも良いと思います（僕はそれで読んだ）
初等整数論
上の代数学シリーズの数論版（代数もまとまっているのでこれだけで良い感はある()）
整数論1: 初等整数論からp進数へ
個人的にはこっちの方が好きです（僕の大学の先生方も関わっています）
初等整数論 ―数論幾何への誘い― (共立講座 数学探検 6)
計算量理論
代数とか計算量理論が載っている暗号の本
マジの聖書（耐量子計算機暗号に多かれ少なかれ関わっている方はもちろん，数学的に量子計算や高機能暗号を捉えたい方に勧められます．量子計算機の共通鍵暗号への影響もちらっとだけ触れられていて，本当に痒いところに手が届く本です）
（ですが，計算量や代数は載っているもののかなりさらっと書かれているので，初学向けではないです）
耐量子計算機暗号
代数だけならつい最近にいい感じの本が出ましたね
暗号から学ぶ代数学 (数学のみかた,考え方)
以下は洋書ですが良い本が多いです
１冊目は「正統派」な本で，
２冊目は「代数」・３冊目は「計算量・ロジック」・４冊目は「アルゴリズムなどの手法」から暗号を眺める本です．
５冊目・６冊目は僕が勉強するときに使っていた（今でも読んでいる）本です
１冊目
暗号の授業をしろ，と言われたらこれを参照するかなと（古典的な内容は網羅されています）
Understanding Cryptography: A Textbook for Students and Practitioners
２冊目
ここの要望に応えてくれる本
代数・初等整数論も計算量も書かれていて，格子も割と充実しています，英語に抵抗のない暗号理論の初学者に１冊薦めるならこれです
An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics)
３冊目
ロジックの視点から始まり，NL完全とかPPなど計算量の観点から眺める本（代わりに代数はあっさり）
Complexity Theory and Cryptology
４冊目
アルゴリズム以外も色々書いてあります，体の拡大とか必要なんか？（計算量の記述が少ないのが惜しい）
Cryptography Made Simple (Information Security and Cryptography)
５冊目
「one-way」・「psuedorandom」・「zero-knowledge」がかなり丁寧に書かれていて，これらを読むだけでも相当な実力になるかと（お陰でくどいし長い）
Foundations of Cryptography v1
６冊目
５冊目の続き，徹底的にセキュリティを定式化するって感じです（上もそうですが，厳密に暗号を扱いたい方向けかなと）
Foundations of Cryptography