Torus・TLWEの概要を整理する

Last updated at 2022-12-09Posted at 2022-12-05

この記事は 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で割った余りをとる」で実用上は十分でしょう