完全準同型暗号の論文を読む - TFHE 編 (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は TFHE の論文の位置づけについて解説しました。
今回からは、その中身の解説に移りたいと思います。

TFHE はとても難解なので、まずは基本となる道具について見ていきます。

トーラス？いいえ、円周群です。

TFHE の T は論文中でトーラスのことです。
少し数学をかじった方だと「あ、ドーナツのやつだ！」と思うかもしれませんが、
この論文で言うトーラスとは、円周群のことです。

円周群とは何かというと、数直線の 0 から 1 の区間を切り出して、
わっかのように 0 と 1 をつないだものです。

0 から実数の解像度で 1 まで進んで、1 になるとまた 0 に戻るわっかです。

f:id:y-hoshizuki:20200515213653p:plain

ざっくりと、位数が無限大の有限巡回群と考えてしまった方が、
後の解説はしやすくなりますのでそういうことにしてしまいましょう。

元論文では $\mathbb{T}$ と表記されています。

これを何に使うかというと、次回説明する TLWE 暗号の平文の世界にします。
要するに、TLWE 暗号文は、平文として 0～1 の区間の実数を扱います。
そして、TLWE 暗号文同士の加算は、平文である 0～1 の区間の実数同士の加算になる、
つまり加法準同型暗号になるように、TLWE 暗号を設計します。

多項式環

$n$ 次の多項式は一般的に $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0$ と表されます。
これらすべての集合は、多項式同士の和 $f(x)+g(x)$ に対して可換群をなします。
また、多項式同士の積 $f(x)g(x)$ は、可換群に近いですが逆元が存在するとは限りません。
逆元が存在するとは限らない群のことをモノイドと呼びます。
そして、多項式同士の和と積に対しては分配法則が成り立ちます。
$f(x)\{g(x)+g'(x)\}=f(x)g(x)+f(x)g'(x)$
そのため、多項式を要素として、多項式同士の和、積を定義すると、
「環 (ring)」をなします。
これを、「多項式環 (polynomial ring)」と呼びます。

数式で書く時は係数が整数 $\mathbb{Z}$ の場合、 $\mathbb{Z}[X]$ と書きます。
元論文では多項式の係数は円周群なので、 $\mathbb{T}[X]$ です。

しかし、一口に多項式と言ってしまうと、次数が無限に増えていってしまい、
メモリがいくらあっても足りません。そこで次の概念です。

多項式環の剰余環

TFHE では、多項式の剰余環というものを扱います。
元論文では $\frac{\mathbb{T}[X]}{(X^n+1)}$ と書いてあります。

これ自体は説明が難しいので、係数を整数として、つまり $a_i \in \mathbb{Z}$ で、
$n=2$ として説明します。
$X^3+2X^2+3X+3=(X^2+1)(X+2)+(2X+1)=2X+1$
例えば多項式をこのように $\mathbb{Z}[X] (X^n+1) + \mathbb{Z}[X]$ という形に分解して、
剰余の部分だけ取り出します。こうして剰余だけかき集めると、
これもまた環となります。これを剰余環と呼びます。

これで、係数を $\mathbb{T}$ としたものが、元論文で使われているものです。

こちらは、次回説明する TRLWE 暗号の平文となります。
環 (ring) なので、頭文字の R が追加されています。
TFHE のキモとなっている、Gate Bootstrapping の途中で一旦この形式の暗号文が出てきます。
なぜかというと、多項式環の剰余環は、以下のとても便利な性質があるからです。

多項式環の剰余環の性質

$\frac{\mathbb{T}[X]}{(X^n+1)}$ の元（要素）として、任意の $\mu \in \mathbb{T}$ を用いて
$\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X+\mu$ を取り出します。

これに $X$ を掛けると
$\mu X^n+\mu X^{n-1}+\cdots+\mu X^2+\mu X$
$=\mu(X^n+1)+\mu X^{n-1}+\cdots+\mu X^2+\mu X-\mu$
$=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2+\mu X-\mu$
という感じで一番下の項の符号が反転します。

もう一度 $X$ を掛けると
$\mu X^n+\mu X^{n-1}+\cdots+\mu X^2-\mu X$
$=\mu(X^n+1)+\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2-\mu X-\mu$
$=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2-\mu X-\mu$
という風に、もう１つ下の項の符号が反転します。