この記事は EAGLYS Advent Calendar 2024 の4日目の記事です
突貫で書いてしまった部分もあるので、大いに誤りを含む可能性があります。誤字・脱字レベルでも構いませんので、ご指摘ください。
また、予告なしに内容の加筆や構成の変更を行うことがありますが、読みやすくするためのものですので、ご容赦ください
自己紹介
秘密計算のスタートアップで働いている社会人２年目です
普段は、秘密計算の研究や社会実装を行なっています
最近は、外部に向けた勉強会もやっています
近々、第2回が開催されますので、皆さん是非ご参加ください
第1回 EAGLYS暗号勉強会
学生時代は、耐量子計算機暗号（特に符号ベース暗号）を研究していました
今でも細々と続けています
Qiita だけでなく、X や Zenn でも活動しています、もしよろしければ
X のアカウント
Zenn のアカウント
何をするのか
２年前に こちらの連載（「プログラマブルブートストラップの原著論文を理解する回」を理解する回 1/4） を投稿し，
昨年に こちらの連載（（リメイク）「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4（前半）） を書きました
今年はそれらのまとめとして，TFHE に関する主要な内容を理解するのに必要な理論・実装を全てまとめます
＊TFHEpp の理論解説 の2番煎じと言われたらそれはそう， とは違った角度からお届けします
基本編の目標は次になります
- 準同型暗号の暗号文状態での掛け算は遅いってよく聞くけど、高速化の工夫なしだとどのぐらい遅いの？を検証
主に参考にするのは Programmable Bootstrap の原論文 と TFHE の原論文 です
記事の構成
基本的に
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
の流れで、各トピックの内容を解説します
イメージ：そのトピックでやりたいことの概要を説明
前提：そのトピックを理解するのに必要な知識や定義のまとめ
理論：そのトピックを厳密に理解できるような説明
具体例：理論で展開した説明に対して、具体的な数値例
アルゴリズム：理論でのアルゴリズムの疑似コードおよび漸近計算量の議論
実装：Python スクリプトを用いて、具体例で与えた数値が正しいことを確認
各回のアウトプットとしては、
- イメージ・前提・理論・アルゴリズムをまとめたスライド
- 理論の概要・具体例・実装をまとめた Notebook
になります
全8回通しでの目次
＊PBS: Programmable Bootstrap の原論文
＊TFHE: TFHE の原論文
第１回：数学の準備とエンコード
- 数学の準備（PBS：2.1節, TFHE：2章前説）
- Torus
- 加群
- 実数から整数への丸め
- Encode/Decode（PBS：３章前節・3.1節）
- イメージ
- cleartext と plaintext
- 前提
- ギリシャ文字と花文字
- $\hat{\mathbb{Z}}$ と $\hat{\mathbb{T}}$
- lift, Upper 関数
- 理論
- エンコード
- デコード
- 具体例
- エンコード
- デコード
- アルゴリズム
- エンコード
- デコード
- 実装
- エンコード
- デコード
- イメージ
第２回：LWE問題＋共通鍵版TLWE暗号方式
- 数学の準備（PBS：2.1節・2.2節, TFHE：2.1説）
- 計算量理論の概要
- 離散一様分布と正規分布
- LWE問題
- イメージ
- 理論
- 具体例
- 共通鍵版TLWE暗号方式（PBS：APPENDIX A）
- イメージ
- 前提
- TLWE問題
- 理論
- 具体例
- アルゴリズム
- 実装
- 共通鍵版TLWE暗号方式の暗号文の演算
- イメージ
- 理論
- 足し算
- 引き算
- スカラー倍
- 具体例
- 足し算
- 引き算
- スカラー倍
- アルゴリズム
- 足し算
- 引き算
- スカラー倍
- 実装
- 足し算
- 引き算
- スカラー倍
第３回：公開鍵版TLWE暗号方式＋TRLWE暗号方式
- 数学の準備（PBS：2.1節・2.2節, TFHE：2.1説）
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 公開鍵版TLWE暗号方式
- イメージ
- 理論
- アルゴリズム
- 実装
- 公開鍵版TLWE暗号方式の暗号文の演算
- イメージ
- 理論
- 足し算
- 引き算
- スカラー倍
- 具体例
- 足し算
- 引き算
- スカラー倍
- アルゴリズム
- 足し算
- 引き算
- スカラー倍
- 実装
- 足し算
- 引き算
- スカラー倍
- 共通鍵版TRLWE暗号方式（PBS：3.2節, TFHE：3.1説）
- イメージ
- 理論
- TRLWE問題
- 具体例
- アルゴリズム
- 実装
- 共通鍵版TRLWE暗号方式の暗号文の演算（PBS：3.3節）
- 理論
- 足し算
- 引き算
- スカラー倍
- 具体例
- 足し算
- 引き算
- スカラー倍
- アルゴリズム
- 足し算
- 引き算
- スカラー倍
- 実装
- 足し算
- 引き算
- スカラー倍
- 理論
第４回：gadget decomposition＋TRGSW暗号方式
- 数学の準備（PBS：2.1節・2.2節, TFHE：2.1説）
- aa
- 数に対する gadget decomposition（PBS：3.3節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- 多項式に対する gadget decomposition（PBS：3.3節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- 多項式のベクトルに対する gadget decomposition（PBS：3.3節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- 共通鍵版TRGSW暗号方式（PBS：3.3節）
- イメージ
- 前提
- 理論
- TRGSW問題
- 具体例
- アルゴリズム
- 実装
第5回：External Product＋CMux gate
- External Product（PBS：3.3節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- CMux gate（PBS：3.3節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
第６回：Gate bootstrap前半（Blind Rotation）
- Gate Bootstrap の概要（PBS：4.1節）
- Rescaling（PBS：4.1節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- Blind Rotation（PBS：4.1節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
第７回：Gate Bootstrap後半（Sample Extraction＋Public Key Switch）
- Sample Extraction（PBS：4.1節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- Public Key Switch（PBS：4.1節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- GBS（PBS：4.1節）
- 理論まとめ
- アルゴリズムまとめ
- 実装まとめ
第８回：Programmable Bootstrap
- Programmable Bootstrap（PBS：4.2節）
- イメージ
- 前提
- 理論
- 具体例
- アルゴリズム
- 実装
- 様々な演算に対する PBS
- 掛け算
- Relu
- exp
今後考えている連載シリーズを2つほど
1.今回の続きの発展編
- Horizontal/Vertical Packing
- Deterministic weighted finite Automata
- Bit Sequence Representation
- Circuit bootstrap
2.準同型暗号の理論まとめ
- 数学の準備（代数系・線型代数・統計・計算量理論）
- LWE問題
- LLL基底簡約アルゴリズム
- LWE Estimator
- FFT/NTT
前提知識
なるべく丁寧に解説することは心がけますが，
- （素朴）集合論（$\neq$ 公理的集合論）：全射・単射・全単射・直積
- 線型代数：行列の和や積・行列式
- 確率・統計：確率分布・確率密度関数
- 代数：Abel群・可換環・体の定義
- 初等整数論：mod
- 計算量理論：クラスPとNP
ぐらいは前提知識とします．知らなくてもググればどうにかなるかもです．
＊こちらの記事 も参照してみてください，「3. 準同型暗号の複雑なアルゴリズム（bootstrapとか）の実装に必要・理論を６割ほど理解したい」まで知っていれば十分です
他に必要なものは，論文解説で使用するものは本文中，補足で必要なものは折りたたみで必要になったときに定義します．
また，次の記号を使います（使わないものもあるかもですが）:
- $\mathbb{N}$ : 自然数全体の集合，0を含む
- $\mathbb{Z}$ : 整数全体の集合
- $\mathbb{Q}$ : 有理数全体の集合
- $\mathbb{R}$ : 実数全体の集合
- $\mathbb{C}$ : 複素数全体の集合
- $\mathbb{B} = {0, 1 }$
- $x \overset{$}{\leftarrow} X$ : 集合 $X$ から要素 $x$ をランダムに取る
- Def : 定義
- Thm : 定理
一応過去に記載していた参考文献を本記事の最後に乗せます
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
完走するぞ！！！
参考文献（過去に載せたものそのまま）
↓ステマではないです
集合論
初学者向け
集合と位相空間
かなりまとまっている本
集合と位相(増補新装版)(数学シリーズ)
線型代数
初学者向け
線型代数
数学書っぽい雰囲気を味わいたい方向け，あとは加群を見据えて単因子論をやりたい方向け
線型代数入門
確率・統計
実用性のコスパ的には一番良い気がします
統計学入門
代数
群の初学者向け（たぶん）
代数学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」・「psueudorandom」・「zero-knowledge」がかなり丁寧に書かれていて，これらを読むだけでも相当な実力になるかと（お陰でくどいし長い）
Foundations of Cryptography v1
６冊目
５冊目の続き，徹底的にセキュリティを定式化するって感じです（上もそうですが，厳密に暗号を扱いたい方向けかなと）
Foundations of Cryptography
まとめ
何回か同じことを今まで書いているので、今回で決定版にしたいですねー
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！