この記事は EAGLYS Advent Calendar 2022 の５日目の記事です

はじめに

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つの多項式環とTRLWE，そしてTFHEについて扱います

多項式環

多項式の集合であって，足し算と掛け算ができる，という認識で十分です
＊環の定義はググれば出てきますが，細かいところに突っ込むクリティカルなところは扱わないので，足し算と掛け算ができる，ぐらいでひとまず今回はいいです

以下で少し補足します
まず，どこの多項式で考えるのか（整数なのか実数なのかTorusなのか）が色々ありますが，ひとまず一般の環（足し算と掛け算ができる集合）で考えます

このとき，その環上の多項式全体の集合も，また環になっています
ですから，整数全体の集合 $\mathbb{Z}$ や実数全体の集合 $\mathbb{R}$ の多項式全体を $\mathbb{Z}[X], \mathbb{R}[X]$ と書くと，これらは多項式環です
また，$q$ を素数べきとして，$\mathbb{Z} / q \mathbb{Z}$ 上の多項式全体の集合も多項式環になります（係数同士の足し算・掛け算は $\mathbb{Z} / q \mathbb{Z}$ で行う）

また，環 $R$ に対して，$R_N[X]$ で $R$ 上の $N - 1$ 次以下の多項式環を表すことにします
例えば，$N = 3$ のとき，$2 - 9 X + 5 X^2 \in \mathbb{Z}_3[X]$ ですね

ここで１つ注意ですが，Torusでは掛け算を考えない（Torus・TLWEの概要を整理する「Torus Torusの演算掛け算」）ので，Torus 上の多項式でも掛け算は考えません
よって，Torus 上の多項式全体の集合は多項式環になりません

TRLWE

＊本当はTorusを離散化する必要があるのですが，今回は割愛します
TRLWE とは，Torus 上の Ring-LWE 問題のことです

TLWE問題の多項式バージョンです，この問題もTLWE問題と同様にNP完全な問題です

$\mathbb{B}_N[X]$ : {0, 1}上の $N - 1$ 次以下の多項式全体の集合（多項式環）
$\mathbb{R}_N[X]$ : 実数上の $N - 1$ 次以下の多項式全体の集合（多項式環）
$\mathbb{T}_N[X]$ : Torus 上の $N - 1$ 次以下の多項式全体の集合（多項式環でない）

この問題を背景としたTFHE暗号化方式を次で紹介します

TFHE

＊本当はTorusを離散化する必要があるのですが，今回は割愛します
TFHEの暗号化方式とは次のようなものです

見た目からわかるように，TRLWE問題をもろに使っていて，TFHEの安全性はTRLWE問題の求解困難性に帰着することができます

TFHEの暗号文では足し算や他の方式の暗号文との掛け算を行うことができます（詳細は11, 12日目の記事で）

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！