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

はじめに

みなさんこんにちは。

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

前回は、駆け足で TFHE の全体像を見ました。
今回からは、bootstrapping の手順を1つずつきちんと見ていこうと思います。

bootstrapping key の組み立て

TLWE 暗号文に使う秘密鍵 \vec{s}n 次とします)とは別に、
bootstrapping に使うために \vec{s} を暗号化するための鍵、
\vec{s'} を二進数で選びます。このベクトルの次数は、あとで出てくる
テストベクタ多項式 T(X) の次数とそろえる必要があります。

そして、\vec{s} の各要素ごとに、TRGSW の暗号文を作ります。

まず、Gadget Decomposition から元に戻す作用素H としました。
\vec{s'} で復号すると \phi_{s'}(Z_j)=0 となる TRLWE 暗号文を 2 \ell 個だけ作成します。
そうして TRGSW 暗号文の構成通り、
{\rm BK}_i=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right) +s_i \cdot H
とします。この TRGSW 暗号文を n 個用意したセットを bootstrapping key と呼びます。

{\rm BlindRotate} に必要な道具、{\rm CMux}

先ほど作った TRGSW 暗号文 {\rm BK}_i と TRLWE 暗号文 d外積を、
{\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i と定義します。

Gadget Decomposition は、\|d-\vec{v} \cdot H\| を最小化する \vec{v} だったので、
\vec{v}={\rm Dec}(d) と誤差 (\epsilon_a(X),\epsilon_b(X)) を用いて、
\vec{v} \cdot H = d + (\epsilon_a(X),\epsilon_b(X)) と書けます。

すると、
{\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i
=\vec{v} \cdot \left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+s_i \times \vec{v} \cdot H
となり、左半分は内積を計算し、右半分は先ほどの式を代入すると、
=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times (d + (\epsilon_a(X),\epsilon_b(X)))
=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times d + s_i \times (\epsilon_a(X),\epsilon_b(X))
となり、3つの暗号文、
c_1=\sum_{j=1}^{2 \ell} v_j \times Z_j
c_2=s_i \times d
c_3=s_i \times (\epsilon_a(X),\epsilon_b(X))
の和を計算したことと同じになります。

TRLWE 暗号も加法準同型の性質を持つため、暗号文同士の和を取ると、
平文同士の和を取ったことになります。

このうち、c_1Z_j を何倍かして足したものなので、
平文 \phi_{s'}(c_1) の期待値は 0 になります。

また c_3 を復号した \phi_{s'}(c_3) は、
平文の絶対値の大きさをシステムパラメータで制約できるため、
この後の演算も含めて十分に小さくなるように設定します。

そうすると、\phi_{s'}({\rm BK}_i \times d)=\phi_{s'}(s_i \times d) となりますが、
s_i が 0 であっても 1 であっても、計算結果は3つの暗号文の和になっているため、
単純な比較では s_i がどちらなのか判別がつかないところが重要なポイントです。

さて、ここまでできればあとは簡単な話で、2つの平文 \mu_0 \mu_1 に対応する
TRLWE 暗号文 d_0 d_1 があるとして、d=d_1-d_0 と代入して、
最後に d_0 を加算すれば、{\rm CMux} の完成です。

{\rm CMux}({\rm BK}_i,d_1,d_0)={\rm BK}_i \times (d_1-d_0)+d_0={\rm Dec}(d_1-d_0) \cdot {\rm BK}_i+d_0

何をしているかというと、s_i が 0 なら \mu_0、1 なら \mu_1 の暗号文を、
復号することなく選択します。C 言語風に書けば s_i?\mu_1:\mu_0 です。

\mu_0 もしくは \mu_1 の暗号文を計算はできるけれども、どちらを選択したのかわからない。
それが {\rm CMux} 関数です。{\rm BlindRotate} のコアとなる重要なパーツです。

{\rm BlindRotate} を計算する

前回説明した通り、平文 \Phi秘密鍵 \vec{s} で暗号化された TLWE 暗号文 c があるとします。

X をかけ続けると位数 2N の有限巡回群をなす、N 次の多項式
F(X)=\mu X^{N-1}+\mu X^{N-2}+\cdots+\mu X+\mu
X^{\frac{N}{2}} を掛けた多項式をテストベクタ T(X)=F(X) \cdot X^{\frac{N}{2}} とします。
なお、\mu=\frac{1}{8} とします。

c=(\vec{a},b) として、\vec{a} の各要素と b2N 倍してから四捨五入します。
そうして作った暗号文 c'=(\vec{a'},b') を復号すると、
\Phi'=\phi_s(c') \approx 2N \times \phi_s(c)=2N\Phi となります。
この時の誤差も後できちんと考慮する必要がありますが、
N が大きくなるほど誤差は小さくなります。

テストベクタ T(X) を平文とする自明な TRLWE 暗号文 (0,T(X)) を用意して、
A_0=X^{-b'} \times (0, T(X))=(0,X^{-b'} \times T(X)) とします。

以降、{\rm BK}_i を用いて、順番に A_i={\rm CMux}({\rm BK}_i,X^{a'_i} A_{i-1},A_{i-1}) を計算します。

すると、s_i が 0 の時はそのまま、つまり X^0 が、1 の時は X^{a'_i} が順番に乗算されていくので、
\phi_{s'}(A_0)=X^{-b'} T(X)
\phi_{s'}(A_1)=X^{s_1 a'_1 - b'} T(X)
\phi_{s'}(A_2)=X^{s_2 a'_2 + s_1 a'_1 - b'} T(X)
と繰り返すと、
\phi_{s'}(A_n)=X^{\sum_{i=1}^n s_i \times a'_i - b'} T(X)
となり、X の肩に乗っているのは、復号関数 \phi_s(c') と等しいので
\phi_{s'}(A_n)=X^{-\phi_s(c')} T(X)
となります。

要するに、A_n は、T(X)X^{-1}\Phi' 回乗算した多項式の暗号文となります。

この時、平文の多項式の定数項だけ見ると、
\phi_s(c')\frac{N}{2} 以上、\frac{3N}{2} 未満の場合、つまり \phi_s(c)\frac{1}{2} \pm \frac{1}{4} の場合、定数項は \mu となり、
それ以外、つまり \phi_s(c)\pm \frac{1}{4} の場合、定数項が -\mu となるのは
前回説明した通りです。

まとめ

今回は {\rm CMux} を組み立ててから {\rm BlindRotate} を計算して、
平文として「定数項に都合のいい係数を持つ多項式」を持つ TRLWE 暗号文を作成しました。
次回はこの平文多項式の定数項を平文とする TLWE 暗号文に変換します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

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

はじめに

みなさんこんにちは。

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

前回は、TFHE で用いる暗号アルゴリズムを3つ紹介しました。
また、その途中で Gadget Decomposition というものについても触れました。

今回は、これらを用いてどんな風に完全準同型暗号を構成するのかを、
お話していこうと思います。

最終的に作りたいもの

前回解説した TLWE は、\mathbb{T} を平文として持ちます。
つまり、0 以上 1 未満の実数が平文となるわけです。

そこで、0 と 0 以外の数(便宜上 \mu と呼びます)のどちらかを
暗号化した暗号文同士の演算、NAND を実現します。

NAND とは、論理回路で出てくる NAND 回路と同じ演算で、
\mu\mu を入力とした時だけ 0 となり、それ以外では \mu となる演算です。

なぜ NAND かというと、\{{\rm NAND}\} という感じに NAND だけを含む集合は、
「完備集合」と呼ばれており、「どんな演算も実現可能」な演算の集合だからです。

もちろん、加算も乗算も、NAND 演算だけの組み合わせで実現可能です。
これで完全準同型暗号を構成します。

TLWE 暗号文同士の NAND 演算

\mu は 0 と区別できれば何でもいいのですが、この後の設計上の都合から、
\mu=\frac{1}{4} とします。TLWE は平文に誤差を含むため、
その最大誤差を \pm \frac{1}{16} とします。

すると、前回説明した通り、TLWE は加法準同型暗号なので、引き算もできます。
そして自明な暗号文(暗号化されていない)として \frac{5}{8} から2つの暗号文を引く、
つまり c=(\vec{0},\frac{5}{8})-c_1-c_2 を計算すると、その平文は以下のようになります。

\phi_s(c_1) \phi_s(c_2) \phi_s(c)
\pm \frac{1}{16} \pm \frac{1}{16} \frac{5 \pm 1}{8}
\frac{1}{4} \pm \frac{1}{16} \pm \frac{1}{16} \frac{3 \pm 1}{8}
\pm \frac{1}{16} \frac{1}{4} \pm \frac{1}{16} \frac{3 \pm 1}{8}
\frac{1}{4} \pm \frac{1}{16} \frac{1}{4} \pm \frac{1}{16} \frac{1 \pm 1}{8}

というわけで、\pm \frac{1}{4} の範囲の平文を \pm \frac{1}{16} に、\frac{1}{2} \pm \frac{1}{4} の範囲の平文を \frac{1}{4} \pm \frac{1}{16} に、
つまり元の入力の値域に戻すことができれば、出力をさらに別の NAND 演算の入力とし、
無制限に何度でも NAND 演算ができるようになります。
(平文は \mathbb{T} なので、0 と 1 がつながっていることに注意!)

このように、誤差を小さくする操作を bootstrapping と呼び、
「こんなものあったらいいね!」という構想自体は完全準同型暗号の研究の初期からあり、
様々な手法がかなり古くから提案されてきました。
しかし、bootstrapping に必要なデータが 1GB ほどになったり、計算量が多すぎて、
なかなか実用には程遠い……と思われていました。

それを劇的に改善したのが、TFHE という位置づけになります。
具体的には、bootstrapping に必要なデータが 16MB、
処理時間は 1 コア CPU で 13ms と論文にあります。

TFHE の bootstrapping

TFHE では、\pm \frac{1}{4} の範囲の平文を \pm \frac{1}{16} に、\frac{1}{2} \pm \frac{1}{4} の範囲の平文を \frac{1}{4} \pm \frac{1}{16} にするために、
3段階の処理を行います。

詳細な処理手順については次回以降、順番に解説しますが、まずは全体の流れを把握するため、
多少強引ですが、「こんな便利な関数があったら」という感じで話を進めます。

第一段階:{\rm BlindRotate}

多項式環の剰余環の話をしたときに、
F(X)=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X+\mu
という多項式は、X をかける操作を続けると、位数 2n の有限巡回群をなす、
というお話をしました。

元論文中ではこれにさらに X^{\frac{n}{2}} を掛けた多項式 T(X)=F(X) \cdot X^{\frac{n}{2}}
「テストベクタ」と呼んでいます。なお、\mu=\frac{1}{8} としておきます。
これで後でつじつまが合います。

で、入力される TLWE 暗号文は先ほど c としたので、
その秘密鍵\vec{s} の要素をそれぞれ別の秘密鍵 \vec{s'} を用いて、
TRGSW で暗号化した暗号文を予め用意しておきます。

c=(\vec{a},b) なので、各要素を 2n 倍して四捨五入して整数化した c'=(\vec{a'},b') を作ると、
\phi_s(c') \approx 2n \times \phi_s(c) となります。これは \phi_s が線形性という性質を
持っているからですが、平たく言えば、大体 2n 倍の値で計算すれば、
出力も大体 2n 倍になるよね、って感じの話です。

そして、テストベクタ T(X) を平文とする自明な TRLWE 暗号文 t=(0,T(X)) から、
X^{-\phi_s(c')} を乗算した TRLWE 暗号文を「復号することなく」計算する魔法のような関数、
c_r={\rm BlindRotate}(t,c') を計算します。この中身は次回解説します。

すると、その TRLWE 暗号文 c_r を復号して出てくる多項式 \phi_{s'}(c_r) を見ると、
下位の項から数えて \frac{n}{2}-\phi_s(c') 個の項は、係数が -\mu となり、
負になった場合、さらに上の項から順に係数が -\mu になります。

ということは、この TRLWE 暗号文を復号して、平文の定数項を見ると、
\phi_s(c')\frac{n}{2} 以上、\frac{3n}{2} 未満の場合、
つまり \phi_s(c)\frac{1}{2} \pm \frac{1}{4} の場合、定数項は \mu となります。
それ以外、つまり \phi_s(c)\pm \frac{1}{4} の場合、定数項が -\mu となります。

この平文の定数項、都合がいいですね。というわけで、自明な TRLWE 暗号文 (0,\mu) を加えて、
定数項を 0 もしくは 2\mu=\frac{1}{4} にしてから次の段階へ進みます。

第二段階:{\rm SampleExtract}

TRLWE 暗号文 c_r の平文多項式の定数項が、都合よく 0\frac{1}{4} になりました。
なので、これまた「復号することなく」、定数項を平文とする TLWE 暗号文に変換します。

これを、c_s={\rm SampleExtract}(c_r) と呼びます。これも次回以降説明します。

第三段階:公開鍵スイッチング

元の TLWE 暗号文 c秘密鍵 \vec{s} で暗号化されていますが、
{\rm SampleExtract} で出てくる TLWE 暗号文 c_s は、
\vec{s} を TRGSW で暗号化した時に使った鍵、\vec{s'} で暗号化されています。

そこで、平文を変えることなく、鍵だけ差し替えます。
これも、復号することなく行います。

ここまで処理を行うと、元と同じ秘密鍵 \vec{s} で暗号化された TLWE 暗号文に戻っており、
平文は \pm \frac{1}{4} の範囲なら 0 に、\frac{1}{2} \pm \frac{1}{4} の範囲なら \frac{1}{4} になっています。
また、誤差の最大値は c に依存せず、システムパラメータによって固定された値になるため、
誤差の最大値が \pm \frac{1}{16} となるようにシステムパラメータを設定します。

これで、何度でも NAND 演算ができるようになり、
加算も乗算も、それどころかすべての演算が可能になるのです。

まとめ

今回は、少し長めになりましたが、TFHE の構成の全体像をまとめました。
次回以降は、各段階で使用した道具について順番に見ていきます。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

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

はじめに

みなさんこんにちは。

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

前回は TFHE の暗号システムで用いる道具をいくつかご紹介しました。
TFHE では、3つの暗号アルゴリズムを巧みに組み合わせて構成するので、
今回はその3つをご紹介したいと思います。

基本の暗号文 TLWE

\mathbb{T} 上の要素として、一様分布な乱数を N 個集めたベクトル
\vec{a} を用意します。 \{0, 1\} の二値を N 個集めた秘密鍵 \vec{s} を用意します。平均値が平文 \mu
分散が事前に決めた \alpha になるようなガウス分布の乱数を e としたとき、
( \vec{a}, \vec{s} \cdot \vec{a} + e) の組を TLWE 暗号の暗号文の1例とします。

乱数を持ちいて暗号化するため、同一の秘密鍵と平文に対して、
いろいろなバリエーションの暗号文が対応します。

なお、 \phi_s( (\vec{a},b) )=b-\vec{s} \cdot \vec{a}=e は復号する関数として働きます。

元論文では、確率空間全体で定義して議論を進めていますが、
それは誤差成分の分散などを計算したいためであって、
実際の実装ではその分布の中の1サンプルを採集すれば OK です。

さらに、元論文では \phi_s 関数の性質についていろいろ述べられていますが、
特筆しておくべきことは、(\vec{0},\mu) は自明な暗号文(暗号化されていない)で
あることに留意してください。
なぜなら、\phi_s( (\vec{0},\mu) )=\mu-\vec{s} \cdot \vec{0}=\mu だからです。

また、TLWE は加法準同型暗号でもあります。
2つの TLWE 暗号文 (\vec{a},b)(\vec{a'},b') をそのまま足して、
(\vec{a}+\vec{a'},b+b') としたものを \phi_s に入力すると、
\phi_s( (\vec{a}+\vec{a'},b+b') )=(b+b')-\vec{s} \cdot (\vec{a}+\vec{a'})
=(b-\vec{s} \cdot \vec{a})+(b'-\vec{s} \cdot \vec{a'})
=\phi_s( (\vec{a},b) )+\phi_s( (\vec{a'},b') )
となるため、復号すると2つの平文の和が出てきます。
ただし、平文が \mathbb{T} なので、0.6+0.6=1.2 ではなく 0.2 となることに要注意です。
これも重要ですので忘れないようにしていただきたく。

TFHE では、「TLWE 暗号文で加法演算を行って、Gate Bootstrapping を行う。」ということを
繰り返していくことで様々な演算を実現します。

多項式環を用いた TRLWE

環 (ring) で構成したバージョンの TLEW なので、頭文字の R が加わっています。

前回の記事で紹介した \frac{\mathbb{T}[X]}{(X^n+1)} の環の元をランダムに選びます。
実際には、n-1多項式の係数 n 個を \mathbb{T} 上から一様分布な乱数で選出して作ります。
多項式の次数が n-1 なら剰余とか考えなくていいので(X^n+1 で割れないので)、
これを多項式 a(X) とします。

秘密鍵をまた \{0, 1\} の二値から n 個集めて、
秘密鍵多項式 s(X)=s_{n-1} X^{n-1}+s_{n-2} X^{n-2}+\cdots+s_1 X+s_0 を組み立てます。

n 個の乱数 e_i を、平均値が平文 \mu_i になり、分散が \alpha となるガウス分布の乱数として、
これらから多項式 e(X)=e_{n-1} X^{n-1}+e_{n-2} X^{n-2}+\cdots+e_1 X+e_0 を組み立てます。

多項式 s(X) \cdot a(X)+e(X)=f(X)(X^n+1)+b(X) と分解した b(X) を計算して、
(a(X), b(X)) を、TRLWE 暗号の暗号文の1例とします。

こちらも TLWE と同様に乱数を用いて暗号化するため、同一の秘密鍵、平文に対して
無数の暗号文が対応します。

また、TLWE と同様に \phi_s((a(X),b(X)))=b(X)-s(X) \cdot a(X)+g(X)(X^n+1) として、
\phi_s\frac{\mathbb{T}[X]}{(X^n+1)} の元となるように g(X) を定めたものが、復号関数として働きます。

さらに、加法準同型暗号なのも TLWE と同じです。

これは、Gate Bootstrapping の途中で一時的に使うだけですが、
前回説明した、特殊な多項式が有限巡回群をなす、
という性質を利用するため、とても重要な役割を果たします。

Gadget Decomposition

これは暗号のアルゴリズムではないですが、次で説明する TGSW で必要なので先に説明します。

GSW の論文で {\rm BitDecomp} 関数を解説しましたが、それの円周群 \mathbb{T} バージョンです。
TRLWE 暗号文のサンプルで用いている多項式の係数である、円周群の要素は、
0 以上 1 未満の実数なので、小数部分しかありません。
これを二進数表記で、何ビットかずつに分解する操作を、Gadget Decomposition、
{\rm Dec} と定義します。

例えば、小さなサイズで例を書いてみます。
TRLWE 暗号文の多項式の次数を n=2 として、分割の 1 単位を {\rm Bg}=2^2 で、
\ell=3 要素に分解します。この時、各要素は -\frac{\rm Bg}{2} から \frac{\rm Bg}{2} の間に入るようにします。

TRLWE 暗号文は、2 つの多項式の組み合わせでしたので、
これを多項式を要素とする 2 次元のベクトルとみなします。
c=\{0.75X^2+0.125X+0.5,0.25X^2+0.5X+0.375\} と書けます。

これを分解すると円周群上では 0.75=-0.25 なので
c=\{-0.25X^2+0.125X+0.5,0.25X^2+0.5X+(0.25+0.125)\}
=\{0.25 \times (-X^2+2) + 0.25^2 \times 2X + 0.25^3 \times 0, 0.25 \times (X^2+2X+1) + 0.25^2 \times 2 + 0.25^3 \times 0\}
と分解できるため、{\rm Dec}(c)=\{-X^2+2,2X,0,X^2+2X+1,2,0\} となります。

逆に、ベクトルから暗号文に戻す作用素 H も定義します。

今回の例だと、
H=\left(\begin{array}{cc} 0.25 & 0 \\ 0.25^2 & 0 \\ 0.25^3 & 0 \\ 0 & 0.25 \\ 0 & 0.25^2 \\ 0 & 0.25^3 \end{array}\right)
という行列が逆変換の作用素です。
{\rm Dec}(c) \cdot H=c に戻ることが確認できると思います。

今回はキリのいい値を使ったので厳密に戻りますが、実際には下の方のビットは
四捨五入して丸めます。
つまり、TRLWE 暗号文 c に対して、\|c-\vec{v} \cdot H\| が最小化となる \vec{v} を得るのが
Gadget Decomposition となります。

この概念を利用して、次の TGSW 暗号を定義します。

GSW の拡張?TRGSW。

Z_i を、平文ベクトルがすべて 0 の TRLWE 暗号文とします。
つまり、e(X) の係数すべてが平均値 0 となり、分散は \alpha となる多項式でできた
Z=(a(X),b(X)) という暗号文です。

これを 2 \ell 個、生成して、平文 \mu を以下のように暗号化します。
C=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+\mu \times H
これを、TRGSW 暗号文と定義します。

型が若干あってないような感じがしますが、TLWE 暗号文を多項式を要素とする 2 次元のベクトルと
みなせば、まぁあっていないこともないでしょう。

復号の方法は元論文でも言及されていません。数式的には形式上 {\rm msg}(C) として書き表しますが、
実際に計算することはありません。

これは、Gate Bootstrapping に用いるデータとして、秘密鍵を暗号化しておくために使います。
Bootstrapping Key とも呼びます。なぜ秘密鍵を TGSW で暗号化しておくか、
というのは追々解説します。

まとめ

今回は、TFHE で用いる暗号アルゴリズムを3つ、ご紹介しました。
TFHE では、これらを組み合わせて完全準同型暗号を構成します。
次回はこれらを使って TFHE の構成を見ていきます。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

完全準同型暗号の論文を読む - 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
という風に、もう1つ下の項の符号が反転します。

全部で n 回繰り返すと、
-\mu X^{n-1}-\mu X^{n-2}-\cdots-\mu X-\mu
と全部マイナスの項になり、さらに繰り返すともう一度下の項から符号が反転します。
というわけで、全部で 2n 回繰り返すと元に戻ります。

つまり、この多項式は、\frac{\mathbb{T}[X]}{(X^n+1)} という環の中で、
位数 2n の有限巡回群になっているわけです。

TFHE の Gate Bootstrapping ではこの性質をうまく利用します。

まとめ

今回は、TFHE で用いられているトーラスという単語の意味について、
また、多項式環とその剰余環について説明した上で、
ある多項式X をかけ続けることで有限巡回群を構成することをお話ししました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

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

はじめに

みなさんこんにちは。

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

前回は GSW の論文について解説しました。
次は TFHE の論文についてお話ししたいところですが、
こちらはとても難解なので、まずは先に、TFHE が発表される前の、
歴史のお話をしようかと思います。

TFHE 前夜の完全準同型暗号の研究界隈とその動向

TFHE 自体も、何度もバージョンアップを続けて改良され続けてきたものですが、
その原型となるものができる前のお話です。

まえがきでお話しした通り、加法のみが行える加法準同型暗号や、
乗法のみが行える乗法準同型暗号は、古くから知られていました。

加法準同型暗号だけでも、平文を乗算することはできたので、
平均値やフーリエ変換など、それなりの計算はできましたが、
やはり加法・乗法、両方やりたいということで、完全準同型暗号の
研究が進められてきました。

そして、格子暗号と呼ばれるものや、NTRU と呼ばれるもの、GSW で用いた LWE 暗号などを
ベースとした、加法・乗法の両方が可能な暗号技術が発表されていました。
この辺りは名前だけ出しましたが、特に中身については触れません。

ところが、GSW の説明でも解説した通り、どの手法も「平文に誤差が累積する」
という問題がありました。誤差が累積するにしても、その上限を押さえることが
できれば、演算回数に制限のある完全準同型暗号、Somewhat 準同型暗号として
利用価値はあるのですが、ディープラーニングのように演算段数のかさむものは、
どうしてもパラメータや鍵が大きくなりすぎて使い物にならない、という感じでした。

一方、それならば誤差を小さくする処理を加えればいいのではないか!という発想から、
bootstrapping と呼ばれる仕組みも考案されました。
加法や乗法により、平文に誤差が累積しますが、うまく処理することで、
その誤差を再度小さい状態の暗号文に戻そう、というわけです。

ところが、この bootstrapping にも問題がありまして、
bootstrapping を行うために用いるデータが 1GB くらいになったり、
処理に数分かかったり。これでは全く使い物になりません。

また、加法と乗法だけじゃまだ足りない、という話もありました。
そこで、0 と 1 のみを暗号化して、論理演算を実現することで、
加法・乗法に限らず、論理回路で実現可能なすべての演算を実現する試みもありました。

これが、TFHE 前夜の状況です。

まとめると
・加法・乗法が行える準同型暗号はいろいろ提案されていた
・しかし、誤差が累積する問題はどうしてもつきまとう
・Somewhat 準同型暗号で十分な場面もあるが、やはり不十分である
・bootstrapping はとてもリソースが必要で現実的ではない
・論理演算ベースにすると加法・乗法に限らずすべての演算ができて素敵
こんな感じの状況です。

TFHE の世界

さて、ここで TFHE が登場します。

TFHE は完全準同型暗号として、2019 年に発表された論文です。
ほぼ最新の研究ですね。

TFHE は、様々なテクニックを駆使して、いくつかの問題をまとめて解決しました。

まず、ベースとなっているのは LWE 暗号です。

そして、0 と非 0 の2値を暗号化することで論理演算を実現し、
論理回路で構成可能な、すべての演算を実現しました。

そしてここが一番重要なポイントなのですが、bootstrapping の手法を
劇的に改善することで、bootstrapping 用のデータを 16MB 程度まで削減し、
bootstrapping 1回の処理を CPU 1core で 13ms にまで高速化しました。

これが、TFHE のすごいところです。

まとめ

今回は、TFHE 発表前の研究界隈の状況と、TFHE が何を成し遂げたのかをお話ししました。
次回から TFHE の中身について解説していきたいと思います。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

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

はじめに

みなさんこんにちは。

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

前回は GSW で提案された完全準同型暗号の大まかな仕組みについて説明しました。
今回はその問題点と解決方法について検討していきます。

おさらい - GSW の原型

同じ固有ベクトルを持つ行列が2つあるとき、その2つの行列の和と積は、
固有ベクトルが変わらずに、固有値が和や積になるという性質がありました。

それを利用して、 Av=\lambda v+e と誤差を加えることで LWE 問題として、
暗号文として解読できないようにしました。

問題点:誤差が累積していく

同じ秘密鍵固有ベクトル)を持つ暗号文 AA' があるとき、
平文(固有値)は \lambda\omega としておきます。それぞれの誤差は e_1 e_2 とします。

A+A' を復号すると
(A+A')v=Av+A'v=\lambda v+e_1+\omega v+e_2=(\lambda+\omega)v+(e_1+e_2) となり、
誤差は e_1+e_2 となります。

A \cdot A' を復号すると(途中計算は省略します。元論文を参照してください)、
\lambda \omega v に加わる誤差は、 v の次数を Ne の絶対値の最大値を B として、
最大で (N+1)B^2 になります。

これはどういうことかというと、例えば多項式の項 x^m を計算しようとすると、
誤差は最大で (N+1)^{m-1} B^m まで大きくなるということです。

誤差の累積は LWE 問題ベースの完全準同型暗号では必ず付きまとう問題で、
過去に様々な解決策が提示されてきましたが、GSW では一風変わった解決策を取ります。

解決策の準備 - {\rm BitDecomp}{\rm BitDecomp}^{-1}

これまで、行列の要素は実数体で考えていましたが、
実数体と準同型である、有限体を要素にもつ行列で考えます。

その時、例えば、位数 13 の有限体であれば、せいぜい 4 bit あれば表現できます。
位数 q の有限体の要素を表すのに必要なビット数は L=\lfloor \log_2 q \rfloor + 1 で求められます。
好きな自然数 k 倍の大きさ N=kL を行列やベクトルの次数とします。

k 次元の横方向ベクトル a' = (a_0, a_1, \cdots, a_{k-1}) のそれぞれの要素を2進数で書き直す操作を
{\rm BitDecomp}(a') と定義します。

例えば、位数 q=13 の場合、 L=\lfloor 3.7 \rfloor + 1 = 4 となります。 k はとりあえず 3 としましょう。
3 次元横ベクトル a' = ( 10, 8, 4 ) を 12 次元横ベクトル
a = ( 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0 ) と分解します。
L=4 要素単位で2進数が逆方向に k=3 つ並んでいます。

この逆の操作を {\rm BitDecomp}^{-1}(a) とします。

{\rm BitDecomp}{\rm BitDecomp}^{-1} の性質

秘密鍵ベクトル(今回は固有ベクトルではない/縦ベクトル)を、 k 個の 0 か 1 で設定します。
とりあえず s = (s_0, s_1, \cdots, s_{k-1})^{\mathrm{T}} としておきます。

L bit 分の 2 のべき数を k 個並べた縦ベクトルを
b_{iL+j} = 2^j, i \in \{ 0, \cdots, k-1 \}, j \in \{ 0, \cdots, L-1 \} とします。
今回の例だと b=(1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8)^{\mathrm{T}} となりますね。

v_{iL+j}=b_{iL+j} \times s_i とした v固有ベクトルとします。

すると、
a \cdot v = \sum_{i=0}^{k-1} \sum_{j=0}^{L-1} s_i \times a_{iL+j} \times 2^j
 = \sum_{i=0}^{k-1} s_i \sum_{j=0}^{L-1} a_{iL+j} \times 2^j
 = \sum_{i=0}^{k-1} s_i \times a'_i = a' \cdot s
というわけで、a \cdot v = a' \cdot s および {\rm BitDecomp}(a') \cdot v = a' \cdot s が成り立ちます。

ここで、左辺にのみ a'={\rm BitDecomp}^{-1}(a) を代入すると、
{\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a' \cdot s
で、前段落前半の式の右辺が同じなので、 {\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a \cdot v です。

何を言っているかというと、 {\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) という処理を加えても、
v との内積は変わらない。という話になります。

この {\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) を、元論文では {\rm Flatten}(a) と書いています。

{\rm Flatten}(a) の意味するところ

{\rm BitDecomp}^{-1}(a) は、a の横ベクトルを2進数と解釈して k 個の値にまとめ上げる処理でした。
{\rm BitDecomp}(a') は、a' の横ベクトルを2進数として書き直す処理でした。

つまり、例えば L=4, k=2 としたとき、a = ( 2, 0, 3, 0, 5, 0, 0, 1 ) は、
{\rm BitDecomp}^{-1}(a) = ( 14, 13 ) となり、{\rm Flatten}(a) = ( 0, 1, 1, 1, 1, 0, 1, 1 ) ということです。
2進数として解釈してまとめあげて、再度2進数として書き直す。

この処理を行っても、固有ベクトル v との内積の値は変わらない。
Av=\lambda v+e ならば、Av={\rm Flatten}(A)v=\lambda v+e なのです。

それなのに、行列の要素はすべて 0 もしくは 1 になります。
これのおかげで嬉しいことがあります。

で、 {\rm Flatten}(a) は何が嬉しいの?

超うれしいです。今回の前半で、誤差の累積の話をしましたが、
乗算の時、 x^m を計算すると誤差は最大で (N+1)^{m-1} B^m となりましたが、
乗算のたびに Flatten を行うことで、 (N+1)^{m-1} B に抑えることができます。

B の階乗が消えましたね。これは行列の要素が 0 もしくは 1 に限定されたおかげです。
Be の要素の絶対値の最大値なので、e の要素の絶対値を大きくしても
誤差が指数関数的に増えていくことはなくなるわけです。

前回の内容から、 \frac{(N+1)^{m-1} B}{v_i} が、-0.5~0.5 の間に収まっていることが
復号できる条件なので、極力小さくするため i には L の倍数 - 1 を選びます。
つまり、位数 q を表す2進数の最上位ビットです。これは k 個あるはずなので、
その中からさらに s_i が 1 であるもの、つまり v_i=2^{L-1} を選ぶことにします。

すると、 -0.5 < \frac{(N+1)^{m-1} B}{2^{L-1}} < 0.5 となるよう、
また、なるべく B が大きくなるよう、q, k, B を選択すればいいことになります。

{\rm Flatten} のおかげで、 B^mB に変わっており、m に対して定数になっているため、
B の大きさは乗算回数の影響を受けない、というのが大きなポイントとなっています。

これって完全準同型暗号??

このシステムでは、選択したパラメータによって乗算の回数に制限ができます。
なぜなら、まだ (N+1)^{m-1} が残っているからです。

とはいえ、最初から計算する内容が決まっている案件であれば、これでも十分実用できます。
こういうものを、Somewhat 準同型暗号 (SHE) と呼びます。

汎用性には若干欠けるところがありますが、これはこれでいろいろ使えます。

まとめ

今回は若干長くなりましたが、GSW の全体像を解説しました。
ちょっとトリッキーで面白くないでしょうか?
次回は SHE ではなく演算回数に上限がない、TFHE の解説を始めようと思います。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

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

はじめに

みなさんこんにちは。

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

さて、前回予告した通り、今回は GSW の論文の解説をします。

前回は完全準同型暗号とはどういうものなのか解説しました。
そして、GSW はその完全準同型暗号の手法の1つとして 2013 年に提案された論文です。

こちらは高校数学レベルの線形代数(行列・ベクトル)の知識があれば理解できますので、
先に高校数学レベルの行列とベクトルの要点だけおさらいしておきましょう。
GSW の仕組みのカギとなる、固有値固有ベクトルの性質について簡単にまとめます。

大変申し訳ないのですが、基本的な定義や計算などについては高校数学についての
参考書的なサイトがいくつもありますので、そちらも参考にしてみてください。

固有値固有ベクトル

行列 A とベクトル v と実数 \lambda があるとき、
Av=\lambda v が成り立つ v固有ベクトル\lambda固有値と呼びます。

要するに、固有ベクトル v を行列 A で線形変換した時、
元のベクトル v の長さが \lambda 倍になって、方向は変わらない。ということです。

行列 A を主体で考えると、A による線形変換で、
向きが変わらずに長さだけ変わる方向が、固有ベクトルで、
その拡大率が固有値。と言い換えることもできます。

ここで注目したいのは、共通の固有ベクトル v を持つ行列 AB があり、
それぞれの固有値\lambda\omega としたとき、
(A+B)v=Av+Bv=\lambda v+\omega v=(\lambda+\omega)v
が成り立つため、行列 A+B固有ベクトルv のまま変わらず、固有値は和になります。
(A \cdot B)v=A(Bv)=A(\omega v)=\omega(Av)=\omega(\lambda v)=\lambda \omega v
と計算できるため、行列 A \cdot B固有ベクトルv のまま変わらず、固有値は積になります。

共通の固有ベクトルを持つ行列が2つあると、
その積も和も、固有ベクトルは変化せず、固有値は積や和になります。

勘のいい方はこの辺で、どうやって完全準同型にするのか、
想像がつくのではないでしょうか。

そうです、固有値を平文、固有ベクトル秘密鍵、行列を暗号文としてしまうのです。

LWE 問題

さて、完全準同型「暗号」というからには、暗号文から平文に戻すのが
難しくなければなりません。

このままでは、暗号文である行列から固有値固有ベクトルを計算するのは容易です。

そこで出てくるのが LWE 問題(Learning With Errors Problem)です。

まず、n 個の変数でできた一次方程式が、特定の条件で n 個あれば連立方程式として解けます。

n 個の連立方程式を行列の形で Ax=b と書き直して
An \times n 正方行列、x, bn 次元ベクトル)、
A^{-1} を求めることができれば(これが「特定の条件」)、 x=A^{-1}b で解けます。

では、ここに変数を1つ加えましょう。
Ax+e=ben 次元ベクトル)。

これだけで、 e を知らない人にとっては x を求めることはできなくなります。
この e は小さい値で十分です。要するに誤差成分ですね。連立方程式に誤差を加えた問題。
これを LWE 問題と呼びます。この問題は量子コンピュータを使っても解けません。
つまり量子耐性がある問題なのです。

秘密の情報を知らないと解けない問題。これは暗号に使えますね。
というわけで、これを応用するのが LWE 暗号です。

GSW の原型を組み立てる

行列を暗号文、固有値を平文、固有ベクトル秘密鍵とする考え方をそのままに、
元の式、Av=\lambda v に誤差成分を足します。Av=\lambda v+e と。

この e が存在することによって、 A からは v\lambda も、求められなくなります。

復号するには、 A から好きな行を取り出して、秘密鍵 v との内積を取ります。
そして、 v の同じ行の要素で割ります。すると得られるのが \frac{A_i \cdot v}{v_i}=\lambda+\frac{e_i}{v_i}

\lambda が復号で得たい平文なので、平文λは常に整数だという制約を加えた上で、
\frac{e_i}{v_i} の部分が -0.5~0.5 の間に収まっていれば
\lambda+\frac{e_i}{v_i} を四捨五入することで平文 \lambda が得られます。

e の要素が小さすぎると、 A から固有値固有ベクトルの近似値が求まってしまうので、
ある程度 v の要素を大きくして、 \frac{e_i}{v_i} を小さいままに e を大きくする必要があります。

まとめ

今回は GSW の論文で提案されている完全準同型暗号の原型まで解説しました。
次回はこのアルゴリズムの問題点と制限についてお話します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。