kenmaro です。
秘密計算、特に準同型暗号のことについて記事を書いています。
秘密計算エンジニアとして得た全ての知見をまとめた記事はこちら。
https://qiita.com/kenmaro/items/74c3147ccb8c7ce7c60c
これから準同型暗号について勉強したいリサーチャー、エンジニアの方へのロードマップはこちら。
https://qiita.com/kenmaro/items/f2d4fb84833c308a4d29
今話題のゼロ知識証明について解説した記事はこちら。
https://qiita.com/kenmaro/items/d968375793fe754575fe
概要
今回は、
格子暗号の中でもFHE（完全準同型暗号）と呼ばれる形式である、
TFHE暗号形式を超える形式がついに発表された、
ということについて記事を書いてみます。
超える、ということが意味することは、ここでは
- 演算がより高速
- メモリ消費がより小さい
という点において、
現状知られている中でSoTA（State of the Art) を出したということです。
今回は、この新形式（NGS形式） について、原論文である
こちらの概要を、わかりやすい言葉で理解できるように解説していきます。
また、この著者の一人であるZamaAI所属の研究者はブログでもこの論文を言及しています。
論文自体には定式化とセキュリティ分析において多くの数式が登場しますが、
この記事では数式を使うことなく、
何をどう工夫してこのスキームが生まれたのか、ということに特化して
お話ししたいと思います。
内容には私の解釈も入っていますので、まずは一回記事を読んで概要を理解した後に、
論文の中の数式と照らし合わせながら確認していただければと思います。
忙しい人のためのまとめ
- NGS形式はTFHEが使用していたLWE問題ではなく、NTRU問題をベースにしているよ
- NTRU問題ベースだと暗号文が１つ（LWEベースだと２つ）なので、（乱暴に言えば）２倍早くて２倍軽い（はず）だよ
- と思ったけどNTRUベースのみだと実は少し遅くて重くなってしまったよ
- LWEとNTRUをいいとこ取りした形式にしたら、TFHEを超えたよ
それでは、内容に入っていきます。
FHE（完全準同型暗号）とは
FHE(Fully Homomorphic Encryption) は、日本語だと完全準同型暗号と呼ばれる暗号のことです。
私の以前の記事でも何回か言及しましたが、このFHE形式の暗号を使うと
暗号状態で任意の演算（つまりどんな複雑な計算でも）暗号状態で理論上実行可能
となるため、FHEの誕生は準同型暗号の研究において非常に大きなブレークスルーでした。
FHEはGentryという研究者が2009年くらいに提案をして以来、
如何にしてFHEの形式をより速く実行し、より軽量な暗号で構成できるか、
という研究が盛んに行われてきました。
既存手法でのSoTAはTFHE形式
その中で、現在一番高速なものが 「TFHE」形式と呼ばれるものでした。
TFHE形式の「T」は、数学のトーラスから来ています。
トーラスで表される数字を係数に持った多項式の剰余で表される、環上の加群と呼ばれる代数体で形成されるTFHE形式は、
FHEの構成に欠かすことのできない
「ブートストラップ」という演算を0.1秒程度で実行することができ 、
Gentryが当初提案した手法の約１万倍高速化を達成していました。
NTRUとは
上述のTFHEは、格子という数学の代数幾何問題を数学上の求解困難な問題（NP困難問題）である
- LWE問題
- Ring-LWE問題
を利用し、暗号の堅牢性と一方向性を担保しています。
一方で、FHEの構成には、この二つの問題以外にも
- NTRU問題
- 近似型のGCD問題
を使う手法も存在していました。
耐量子暗号として注目を集めるNTRU
その中でもNTRUを使う問題については、
近年耐量子暗号の標準化にNTRUが候補として残っている
というように注目を集めていましたが、
あくまでもNTRUの構成は「準同型暗号」という観点からではなく、
- PKE（公開鍵暗号方式）
- KEM（鍵カプセル化メカニズム）
としての使用用途でした。
脆弱性が指摘されたNTRU由来のFHE構成
準同型性を持った「FHEとしての」NTRUは提案されていたものの、
そこで決定された暗号パラメータは 「Over streached parameter」 と呼ばれ、
２０１６年に、それらのパラメータでは NTRU格子の部分格子を利用した攻撃に脆弱性があるという研究結果 が出ました。
それ以降、NTRUを使用した準同型暗号は難しいのでは、、？ という話になっていました。
今回のこの論文では、この「FHEの構成」という点においては
LWE問題に遅れをとっていた
NTRUについて、再度スポットライトを当てる研究結果を発表した、
と理解していただければと思います。
NTRUを使う利点
LWE問題とか、NTRU問題とか格子暗号の求解困難問題にはいくつかある
のはわかったけど、どちらの方がいいとか、優劣はあるのか？
といった疑問が聞こえてきそうですが、今回のFHEを構成するにあたり
NTRUを使うことにはメリットがあります。
暗号文の大きさがNTRUだと小さくて済む
それは、
暗号文が１つの多項式で構成されている
ということです。
TFHE（LWEベース）の形式だと、
暗号文は２つの多項式（LWEペアと呼ばれます）
から構成されていました。
したがって、単純計算では
NTRUの方が演算は２倍速く、メモリ消費は1/2で済むのでは、
と考えられます。
事実として以前NTRUを用いて構成されたFHEスキーム、
YASHEはそのことを裏付けるように他スキームに対してかなり高速でした。
従って、効率性と高速性を追求するのであれば、
NTRUをベースにFHEを構成しようとする研究はモチベーションがあるわけです。
NTRUの問題
NTRUを使うメリットはあるものの、FHEを構成しようとして設定したパラメータには脆弱性があることがわかりました。
先述した 「Over Streached Parameter」 に対する部分格子攻撃手法です。
格子問題を扱う時は多項式が登場しますが、その多項式に制約をかける際に
２つのパラメータを設定する必要があります。
それらは、
- 暗号空間のモジュラスと呼ばれる大きな整数q（多項式の係数に制約をかけます）
- 多項式の長さn（多項式の長さは格子における次元の大きさになります）
で表されます。
パラメータのストレッチ問題
NTRUを使用すると、
暗号空間のモジュラスqが多項式の大きさnに対して指数的に大きくしなければならないという制約がかかることが知られていました。
このとき、nを固定した状態でqを大きくしていき「ストレッチ」すると、
NTRU格子の密な部分格子を利用してNTRUの求解が容易になるということが研究として発表されました。
これにより、
実質FHEを構成するためのその時のパラメータ選定では、セキュリティを十分なだけ確保できないという結論になったのです。
実際問題としてqをストレッチするにつれて、どのように部分格子を用いた攻撃が有効になるか、という分析は難解でした。
しかしながら、最近の研究でqとnの対応関係がより明らかになってきた背景から、
この論文の著者たちはNTRUを用いてFHEを構成するために再度チャレンジしたというわけです。
以上が今回のNGSが誕生した（簡易的ですが）研究の背景になります。
今回の提案スキームの核
今回の提案スキームの核となるポイントを箇条書きにしました。
- NTRU問題におけるqとnの対応関係の理解が深まったことから、NTRUを用いたFHEの構成について再考することができた
- ブートストラップ手法を高速化するための既存手法、「FHEW」や「TFHE」をNTRUでも同様に構成するため、NTRU問題の行列表記「MNTRU問題」を定義した
- 一般化されたMNTRUにより、GSW形式をNTRUベースで構成した
- 選定された暗号パラメータは、ストレッチされたパラメータ（以前脆弱性があると指摘された領域）の外側に位置し、セキュリティの問題がクリアになった
- 最終的に、今までのLWEベースの暗号と、今回のNGS形式を組み合わせることで、最速となる構成を提案した（ハイブリッド形式）
NTRU問題について
NTRU問題の内容を詳しく理解したい人は
NTRU問題の数式での説明は原論文の Definition2 (NTRU)を見ていただければと思います。
大事なのは、格子と呼ばれる代数体を用いて、TFHEが使用していたLWE問題とは異なるNTRU問題というものを暗号のバックグラウンドに選択することが可能だということです。
言葉で説明すると、多項式を２つ(f, g)用意して、その多項式を代数体の上で掛け算します。
そのあとに、大きい整数でモジュラスを取ります。
その結果から、もとのf, g を推測するのは困難だという問題です。
なんとなく、RSA暗号における大きな数の素数での因数分解問題に似ていますね。
MNTRU問題について
NTRUを用いて構成した暗号には、
復号に多項式の掛け算が必要となります。
上記のNTRUでf, g の掛け算が存在しているからです。
これは、復号にはベクトルの内積を計算するだけでよかったLWEと比べてややこしいことになります。
理由は、
「ブートストラップ」と呼ばれる手法は復号回路を別の暗号状態のまま実行するためのアイディアであり、
これをNTRUベースの暗号に対して実行しようとすると、
LWEベースの時には内積計算だけで済んでいた復号回路の計算を
多項式演算というより複雑な計算を行わなければならないからです。
それを解決するために拡張されたNTRUが、「MNTRU」です。
行列で再定義されたNTRU: MTRU
この内容はTFHEのGSW形式を聞いたことがある人は理解できると思われますが、そうでない人は飛ばして差し支えありません。
MTRUを定義することで、復号回路が多項式の掛け算ではなく、ベクトルの内積で表すことができるため、
計算を楽にすることができた、ということだけ理解すれば大丈夫です。
多項式同士の演算が畳み込みでn成分同時に実行されるところを、
あえて１成分ずつ内積で計算するように行列に展開します。
TFHEの内容を理解している人であれば、Ringで表記されたRLWEを、各要素ごとに抽出する「Sample Extract」したように、１成分ごとのLWEで表記するようなイメージです。
MNTRUでは、NTRU多項式に対して、全成分に平文を詰めて暗号するのではなく
１成分（定数の場所だけ）平文を詰めて暗号化することにします。
これに従って、NTRU問題は今行列バージョンのNTRU問題で定義されることになります。（MNTRU）
繰り返しになりますが、この場合F（秘密鍵となる多項式）は行列で記述されます。
これにより、復号演算は多項式の乗算ではなく、LWEのようなシンプルな内積計算で表すことができます。
すなわち、復号はcという多項式の係数をベクトル表記したものと、Fの０列目のベクトルの「内積」で記述できる。
こうすることにより、「ブートストラップ」の演算下において暗号状態で多項式演算をするのではなく、内積計算をするだけで良くなったので、ブートストラップをする準備が整いました。
NTRUのGSW形式（NGS形式）
ここもGSW形式を聞いたことのある人は読んでもいいですし、飛ばしても大丈夫です。
大事なのは、NTRUをベースにして既存のTFHE形式と同じ構成を作ることができる、という提案だということです。
FHEWのブートストラップ構成は、RLWEに則ったGSW形式を用いることで、
復号演算を効率的に、また、ノイズの増加を抑えながら評価することを可能にしていました。
これを踏襲し、
NTRUベースの暗号においてもGSW形式を定義し、それをNGS形式と呼ぶことにします。
これにより
NGSは平文となる多項式を２つの方法で暗号化することができます。
- １つ目はスカラー、先ほどのMNTRUを定義した時に、多項式の定数部分にだけ平文を詰めた暗号
- ２つ目はベクター、これは基数展開を施してl（エル）個の暗号として一つの暗号を表したもの
ここで特筆しておきたいのは、
NGSのベクター形式の暗号（LWEのGSWに対応した暗号）は、l（エル）個の多項式から構成されていることです。
TFHEで使用した基数展開を利用して、１つの暗号をl（エル）個にあえて分解してベクトル化したものです。
NGS形式の外積
ここもGSW形式を聞いたことのある人は読んでもいいですし、飛ばしても大丈夫です。
大事なのは、NTRUをベースにしたGSW形式（NGS形式）を構成すると、
LWEベースの時より効率の良い「外積」と呼ばれる演算を定義できるということです。
NGSはNTRUベースのGSW形式であり、
上述の２つの暗号タイプは 「外積」 と呼ばれる演算を定義することができます。
GSW形式とLWE形式の間で外積を定義し、その結果がLWE形式に戻るように定義したように、
ベクター形式もスカラー形式と外積を定義し、結果はスカラー形式に戻ることになります。
NGSの基数展開する桁数をl（エル）、LWEのそれをl’（エルプライム）と表記すると、
NGSの外積に必要な多項式同士の乗算回数はl（エル）回であり、LWE形式では４l’（エルプライム）回でした。
理由はLWE形式が２つの多項式をペアとして暗号を持っていたためです。
従って、NGSベースのものは性質としてLWE形式よりも高速に外積を計算することができる（必要な多項式同士の乗算回数が少ない）たえ、
復号回路を計算するアキュミュレーターとして利用することは有用であると考え、 論文ではその構成を実証しています。
NGS形式とCMUX
TFHE形式を聞いたことのある人は読んでもいいですし、飛ばしても大丈夫です。
大事なのは、非常に大事なCMUXと呼ばれる暗号文を入出力とする関数を、NTRUを使う時は再定義しなければならないということです。
NGSのスキームを利用すると、上記の外積の演算高速化により、
LWEでGSWを定義してTFHEを構成したのと同様に、MNTRUのみで構成したTFHEと同等（もしくはそれより高速な）FHEを構成することが可能となります。
しかし、ここで１つ着目すべきことがあります。
今回NTRUでは 秘密鍵fは 「tenary」 で構成されているため、
tenary に対応したCMUXを定義する必要があるということです。
tenaryの鍵は、バイナリ構成の鍵[0, 1]とは異なり、[-1, 0, 1]を要素として持ちます（３成分あります）
TFHEの構成では、LWEの秘密鍵sはバイナリ配列であったため、
CMUXと呼ばれる関数 CMUX（s, a, b) を外積１回の構成で定義できていました。
CMUX とは、暗号の入力の値に対して出てくる暗号がスイッチングされる関数のこと。TFHEでは暗号文であるsが０か１かによって出力される暗号が異なる関数を、sの要素をGSW暗号とし、a, bをLWE暗号とすることで構成していました。
今回扱うNTRUは「tenary」タイプの鍵がデフォルトなので、CMUXはLWEの時より少しだけ複雑になります。
論文では、tenary に対応したCMUXはNTRUに限った話ではなく、
TFHEをtenary 鍵で構成するような形式も提案されているため、このtenary CMUXを定義しておくことは独立問題としても有用である、と言及されています。
つまり、tenaryタイプの鍵についてのCMUXを定義したことは何もNTRUに限った話ではなく有用だという主張です。
剰余多項式の選定について
少し複雑なので飛ばしても差し支えないです。
ここで、NTRUを２の冪数の円分多項式に対して定義してもいいですが、
それをすることでパラメータ選定はより制約を受けることになることに注意します。
６００程度の次元を持てばセキュリティ的には問題ない格子問題において、２の冪乗を考えると2^10あたりを考えることになり、
あえて重い構成を選ばなくてはならなくなるからです。
実際２の冪数でない円分多項式を選ぶことでこの問題は解決できます。
それにより多項式はanti-circularの性質を失うことになりますが、
これは実際はブートストラップの速度を飛躍的に向上させ、暗号化パラメータを小さくすることに役立つことになります。
これについては論文では５章で詳しく書かれています。
既存TFHE形式と純NTRU形式、そしてその先へ。
純NTRU形式だとTFHEより高速化はできない
上記でNTRUを用いたGSW方式（NGS形式、もしくは純MTRU形式と呼ぶ）を定義できるということに言及しました。
実際にこの構成でもTFHEと同等もしくはそれ以上の速度が出せる暗号構成になっていると考えていましたが、
実はそうではありませんでした。
当初、純にMNTRUで構成したFHE暗号は、外積が少ない多項式乗算回数で実装可能であるから、
もともとのTFHEよりFFTを実行する回数が少なくより高速なブートストラップを搭載できると考えていました。
理由はNTRUのパラメータがLWEパラメータより大きい必要があるから（格子次元が大きい必要がある）
しかしながら、NTRU問題に準じたセキュリティパラメータを使うと、LWEのそれよりもnを大きくする必要がありました。
それにより、結局のところほとんど同じ回数FFTを演算しないといけないことがわかったのです。
言い換えると、
効率の良い外積が実行できるメリットは、より大きな多項式次元を使わなければならないというNTRU問題の制約により打ち消された
ということでした。
論文の中では、テーブル１に、NTRUとLWEで各々必要な格子のパラメータが表記されています。
解決するために生まれたハイブリッド方式
LWEとNTRUのいいとこ取り
これを解決するために、MNTRUスキームと、既存のLWEスキームの融合を考え出しました。
これは、
- 元々の暗号スキームはLWE形式とし
- 復号回路を計算するGSWの構成をNGSに取っ替えた
ものだと説明できます。これにより、
- LWE由来のnを今まで通り比較的小さく抑えた小さな暗号パラメータの活用
- NGS由来の外積に必要なFFT演算の削減による効率の良さ
の両者のメリットを継承できます。
まさに、「瞬間、こころ、重ねて」ですね。
結論づけると、
このハイブリッド手法構成は従来のTFHEと同じ回数の外積を実行しますが、
１回の外積に対して従来よりも少ないFFT回数で演算を完結することができるため、
結果としてブートストラップ全体に必要なFFTの回数を削減できます。
さらに、この構成だと鍵の大きさも小さくできます。
ハイブリッドするために必要なLWEとNTRU形式の鍵交換手法の提案
ここで、ブートストラップの最中のNGSの外積の出力はもちろんNGSのスカラー形式となります。
これを鍵交換をすることによってNTRU暗号文をLWE暗号文に戻す
ことにより、ブートストラップを完結させる手法を提案しました。
実測値の比較
論文の７章からは実装による速度の測定値の話になっています。
C++での実装で今回の
- 純MNTRU手法
- LWE＋NGS手法
- 従来のTFHE手法
に対してブートストラップにかかる時間や鍵の大きさを測定して、結果をテーブル２にまとめてあります。
結論としては、速度と省メモリ化は、
LWE+NGS > TFHE > 純MNTRU
の順で優位性があるとなっています。
論文のその他の章のまとめ
何をやっているか、という話だけだとコアとなる話は上記でまとめた分になりますが、
数学的な安全性の分析、ノイズの分析、完全性の評価
などは他の章にまとめられています。以下は他の章でどのようなことが書かれているのかの簡単な箇条書きです。
表記に関すること
- 量子化されたガウシアン分布について
- 基数展開について
と続く。
さらに、
- NTRU問題
- MNTRU問題
- MNTRU問題を基盤とした暗号スキーム
- 復号時の精度分析
と続く。
次に、
- NTRUベースのGSW形式構成（NGS)
- NGSの外積の定義
- 外積時のノイズ分析
- 外積後のスカラータイプからベクタータイプへの鍵交換スキーム
と続く。
ここから、
- tenary 型CMUXの定義
- tenary型CMUXを利用したブートストラップの定義及びブートストラップ鍵の生成方法
- ブートストラップ時のノイズ分析
と続く。
最後に、
- LWE形式との融合をする上でのブートストラップのアルゴリズム
- NTRUからLWE形式への鍵交換アルゴリズム
- 上記方法のノイズ分析
と続く。
８章はまとめの章となっていますが、
著者のNTRUに対する愛（と情熱）が感じられる文が最初の段落に見られました。
２段落目ではNTRUを構成するf, gの多項式をそれぞれ異なる分布からとることで、セキュリティパラメータをより効率化できるはずだ、
ということが言及されていました。
具体的には、そうすることでより大きなqを選択することができるため、基数展開の基数をより大きな値とすることができ、
結果としてFFTとアダマール積の回数を削減することにつながります。
しかしながら、この構成での厳密なセキュリティ分析は行われていないことから、今回はこの実装は見送ったということでした。
最後の段落では、THE形式においてLWEを入力とし、GSWを出力としたサーキットブートストラップ法に対して、同じようにNGS形式応用するという研究もありそうだ、と言及されていました。
まとめ
以上、少し長くなってしまいましたが、
TFHEよりも高速な手法が提案された論文
についてどのような暗号形式なのかということを数式は使わずに概念だけをなるべく伝えるべくまとめてみました。
NTRUについては耐量子暗号として標準化のファイナリストとして残っていることからも注目が集まっていましたが、
このタイミングでFHEを構成する格子問題としても再度注目されることだと思います。
また、構成自体でLWEよりも（理論的には）高速化でき、ハイブリッド方式なども提案され、それが実測までされて注目されていることにはワクワクしますね。
TFHEが長年最速な構成だと思われてきた、と私は理解していましたが、
まだまだ理論的にも改善が進む余地がありそうですね。
みなさんも是非キャッチアップしていただければと思います。
今回はこの辺で。