はじめに
みなさんこんにちは。
VIPPOOL でエンジニアをやっています、星月です。
前回は TFHE の暗号システムで用いる道具をいくつかご紹介しました。
TFHE では、3つの暗号アルゴリズムを巧みに組み合わせて構成するので、
今回はその3つをご紹介したいと思います。
基本の暗号文 TLWE
上の要素として、一様分布な乱数を 個集めたベクトル
を用意します。 の二値を 個集めた秘密鍵 を用意します。平均値が平文 、
分散が事前に決めた になるようなガウス分布の乱数を としたとき、
の組を TLWE 暗号の暗号文の1例とします。
乱数を持ちいて暗号化するため、同一の秘密鍵と平文に対して、
いろいろなバリエーションの暗号文が対応します。
なお、 は復号する関数として働きます。
元論文では、確率空間全体で定義して議論を進めていますが、
それは誤差成分の分散などを計算したいためであって、
実際の実装ではその分布の中の1サンプルを採集すれば OK です。
さらに、元論文では 関数の性質についていろいろ述べられていますが、
特筆しておくべきことは、 は自明な暗号文(暗号化されていない)で
あることに留意してください。
なぜなら、 だからです。
また、TLWE は加法準同型暗号でもあります。
2つの TLWE 暗号文 と をそのまま足して、
としたものを に入力すると、
となるため、復号すると2つの平文の和が出てきます。
ただし、平文が なので、0.6+0.6=1.2 ではなく 0.2 となることに要注意です。
これも重要ですので忘れないようにしていただきたく。
TFHE では、「TLWE 暗号文で加法演算を行って、Gate Bootstrapping を行う。」ということを
繰り返していくことで様々な演算を実現します。
多項式環を用いた TRLWE
環 (ring) で構成したバージョンの TLEW なので、頭文字の R が加わっています。
前回の記事で紹介した の環の元をランダムに選びます。
実際には、 次多項式の係数 個を 上から一様分布な乱数で選出して作ります。
多項式の次数が なら剰余とか考えなくていいので( で割れないので)、
これを多項式 とします。
秘密鍵をまた の二値から 個集めて、
秘密鍵の多項式 を組み立てます。
個の乱数 を、平均値が平文 になり、分散が となるガウス分布の乱数として、
これらから多項式 を組み立てます。
多項式 と分解した を計算して、
を、TRLWE 暗号の暗号文の1例とします。
こちらも TLWE と同様に乱数を用いて暗号化するため、同一の秘密鍵、平文に対して
無数の暗号文が対応します。
また、TLWE と同様に として、
が の元となるように を定めたものが、復号関数として働きます。
さらに、加法準同型暗号なのも TLWE と同じです。
これは、Gate Bootstrapping の途中で一時的に使うだけですが、
前回説明した、特殊な多項式が有限巡回群をなす、
という性質を利用するため、とても重要な役割を果たします。
Gadget Decomposition
これは暗号のアルゴリズムではないですが、次で説明する TGSW で必要なので先に説明します。
GSW の論文で 関数を解説しましたが、それの円周群 バージョンです。
TRLWE 暗号文のサンプルで用いている多項式の係数である、円周群の要素は、
0 以上 1 未満の実数なので、小数部分しかありません。
これを二進数表記で、何ビットかずつに分解する操作を、Gadget Decomposition、
と定義します。
例えば、小さなサイズで例を書いてみます。
TRLWE 暗号文の多項式の次数を として、分割の 1 単位を で、
要素に分解します。この時、各要素は から の間に入るようにします。
TRLWE 暗号文は、2 つの多項式の組み合わせでしたので、
これを多項式を要素とする 2 次元のベクトルとみなします。
と書けます。
これを分解すると円周群上では 0.75=-0.25 なので
と分解できるため、 となります。
逆に、ベクトルから暗号文に戻す作用素 も定義します。
今回の例だと、
という行列が逆変換の作用素です。
に戻ることが確認できると思います。
今回はキリのいい値を使ったので厳密に戻りますが、実際には下の方のビットは
四捨五入して丸めます。
つまり、TRLWE 暗号文 に対して、 が最小化となる を得るのが
Gadget Decomposition となります。
この概念を利用して、次の TGSW 暗号を定義します。
GSW の拡張?TRGSW。
を、平文ベクトルがすべて 0 の TRLWE 暗号文とします。
つまり、 の係数すべてが平均値 0 となり、分散は となる多項式でできた
という暗号文です。
これを 個、生成して、平文 を以下のように暗号化します。
これを、TRGSW 暗号文と定義します。
型が若干あってないような感じがしますが、TLWE 暗号文を多項式を要素とする 2 次元のベクトルと
みなせば、まぁあっていないこともないでしょう。
復号の方法は元論文でも言及されていません。数式的には形式上 として書き表しますが、
実際に計算することはありません。
これは、Gate Bootstrapping に用いるデータとして、秘密鍵を暗号化しておくために使います。
Bootstrapping Key とも呼びます。なぜ秘密鍵を TGSW で暗号化しておくか、
というのは追々解説します。
まとめ
今回は、TFHE で用いる暗号アルゴリズムを3つ、ご紹介しました。
TFHE では、これらを組み合わせて完全準同型暗号を構成します。
次回はこれらを使って TFHE の構成を見ていきます。
今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。