kenmaroです。
秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。
また、最近準同型暗号の中の格子暗号、という次世代高機能暗号が、
３年以内にISO標準となる可能性が高まった、
という記事を書きましたのでそちらもご覧ください、
格子暗号で新ブレイクスルー！！ プログラマブルブートストラップを解説！！
プログラマブルブートストラップという長いパワーワードですが、
**「プログラマブル」・「ブートストラップ」**で区切ります。
そのままの意味ですが、プログラム可能なブートストラップ法なのでこう呼ばれていますが、
どういう意味なのかを理解するための記事にしたいと思います。
まずはブートストラップとはなんなのか、その後、 何がプログラム可能なのか、ということについて解説したい と考えています。
記事の流れ
- ブートストラップとはなんなのか
- TFHEスキームとは
- プログラマブルとはなんなのか
- 何がすごいのか
- 実装されると何が可能になるのか
この流れで解説していきます。
ブートストラップとはなんなのか
準同型暗号、その中でも格子暗号は、
準同型性と量子コンピュータ耐性を併せ持つなど、
次世代高機能暗号として期待されている技術です。
準同型暗号のなかでも、制限された回路のみ暗号状態で計算できるものを
Somewhat Homomorphic Encryption (SHE) と呼んだり、
Leveled Homomorphic Encryption(Leveled HE) と呼んだりします。
これに対して、任意の演算に対して準同型性を担保している暗号を、
Fully Homomorphic Encryption (FHE) と呼びます。
ブートストラップ法 とは、格子暗号にてこのFHEを達成するためのアルゴリズムのことです。
ブートストラップと私
何かのポエムの題名みたい。。
格子暗号の研究は、2008年のGentryによるブートストラップという技術の発明によって大きく進みました。
格子暗号は、LWE問題という数学の問題の解読困難性を暗号の基盤としています。
この問題は高次元の格子上（mod空間）で連立線形方程式にノイズを付与したときの求解困難性に基づくもの、という非常にシンプルなものです。
しかしながら、ノイズの乗った暗号文に対して準同型演算を行う際、
この暗号の解読困難性のために付与したノイズが増大してしまう、という本質的な問題がありました。
この本質的な問題に解決方法を提案したのが、ブートストラップ だったわけです。
ブートストラップのアルゴリズムにより、ノイズを持つ暗号文に対して適用することで
暗号に付加されるノイズを取り除くことができるため、適用された暗号はノイズが爆発する前に、また演算をすることが可能になります。
したがって、一定のタイミングでブートストラップを適用し続けることで、 任意の深さの演算を可能にさせるという点で非常に秀逸でした。
このブートストラップのアルゴリズム込みの格子暗号スキームを、先ほど紹介したように 完全準同型暗号 と呼びます。
それに対して、ノイズが爆発するまでの限定回数だけ演算を実行できる格子暗号スキームのことを レベル準同型暗号 と呼びます。
このブートストラップ手法の提案以降、
完全準同型暗号をの実装を目指したライブラリの開発の活発化がこの１０年で進み、
格子暗号ベースの秘密計算の社会実装の先駆けとなりました。
10年もの間、主な研究対象はGentryのブートストラップをいかに改善するか、というところに大きくフォーカスされていきます。
ブートストラップの手順
Gentryのアイディアは、（非常に簡単にいうと）以下のようなステップです。
- 格子暗号で使う秘密鍵(s1)を、別の秘密鍵(s2)で２重に暗号化し、ブートストラップ鍵(bsk)を生成します。（秘密鍵(s1)自体を暗号化）
- 復号の時に行う演算（フェーズと呼ばれる内積計算）を、ブートストラップ鍵(bsk)を用いて準同型演算します。
- ２で出力される暗号はs2で暗号化されているものなので、もともとのs1で復号できるように鍵スイッチングという演算を適用する。
２のステップは、復号演算をs2の暗号空間で準同型演算する、というところがミソです。
よく例えられるのは、結んだ紐（暗号）を紙袋の中に入れ（s2による再暗号）、紙袋の中で結んだ紐を解く（復号回路の準同型演算）ことで２重にした暗号の、内側のみ復号するというオペレーションです。
TFHEスキームとは
Gentryの提唱したブートストラップは素晴らしいアイディアでしたが、初めは数10ギガのメモリを使い、数時間かけて行うものだったため、とても実用には耐えれないものでした。
ブートストラップをいかに高速化、省メモリ化して行えるかということに関して研究者が取り組み、そのなかで発案された格子暗号スキームが、 GSW や **CGGI(TFHE) ** などと呼ばれるものです。
TFHEはトーラス上で定義された多項式環を使う形式です。近年全ての格子暗号スキームを発明者の頭文字で呼ぶ風潮もあるので、これ以降はCGGI形式と書きます。
また、数々の他の格子暗号スキーム（例えば CKKS ）が台頭し、
そのスキームにおいてもブートストラップの実現について議論されたり、速度改善などが行われてきました。
現在、CGGI(TFHE)スキームが最速のブートストラップが可能 とされるスキームであり、
最初期の数時間かかっていたブートストラップを 0.1秒程度 で可能にしています。
CGGI(TFHE)はトーラス上に定義されたビットを暗号化する手法であり、XORやOR,NOTゲートなどのベースとなるバイナリゲートをブートストラップを行うことで演算することができる ため、実質いかなる演算も任意の深さで実行することができます。
しかしながら、CGGI方式は前述の通りビットごとに暗号化が必要 であり、実際の数値演算を行う際には、 CKKSやBFV方式などの、intやVecをそのまま暗号化できる手法に対して実装上の速度面でのデメリットがあるのが現状 です。
プログラマブルとはなんなのか
プログラマブル、プログラム可能とはいったいどういう意味なのか、について書いていきます。
これは、カスタマイズ可能、と言い換えてもらえればわかりやすいかな、と思っています。
FPGA(field-programmable gate array)にもプログラマブルという言葉が使われていますが、
FPGAも実行したい演算に対して、回路をリアルタイムでカスタマイズ可能なため、プログラマブルと呼ばれています。
プログラマブルブートストラップに関しても、ブートストラップをカスタマイズすることで、行いたい任意の演算を実行可能にする、と読み替えてもらえればいいかと思います。
先程のCGGI方式では、実行したい演算（例えば乗算）をバイナリ回路まで落とし込み、
そこの一つ一つブートストラップ演算を行うことで実行できるので、CGGI方式もある意味でプログラマブルなブートストラップが実装されている、と言えます。
何がすごいのか（今回の本題）
このCGGI方式のバリアント（つまり亜種）を発表し、そこでプログラマブルブートストラップについて解説したのが、Zamaというフランス拠点のスタートアップです。
Zamaは準同型暗号のペリエ暗号を発案したことで非常に有名なペリエ博士が率いるスタートアップです。
以下ではこのZamaベースのCGGI暗号方式を Zama方式 と呼びます。
Zamaのホームページはこちら
https://zama.ai/
プログラマブルブートストラップの原論文はこちら
（とても読みやすい部類だと思います。是非チャレンジしてみてください。）
https://eprint.iacr.org/2021/091.pdf
Zama方式がCGGI方式と異なるところは、ざっくりいうと暗号化する前のエンコーディング方法です。
CGGI方式のシンプルな拡張にはなるのですが、トーラス上に０、１のビットをエンコードしていたCGGI方式に対して、トーラスを量子化（分割）し、浮動少数(float)をエンコードするため、実際のデータを非常にエンコードしやすい手法になっています。
また、CGGI方式でのブートストラップの概念も拡張し、プログラマブルブートストラップと呼んでいます。
これは、既存のブートストラップの出力を恒等変換を記載したLUT（ルックアップテーブル）だと解釈し、
そのLUTの中身を任意の出力に書き換えることで、任意の演算をLUTに一度埋め込み、それを暗号文に対して適用可能にしました。
つまり、今までのブートストラップは、プログラマブルブートストラップのLUTを恒等変換で書いた特殊な例であり、LUT自体は実行したい演算に置き換えることができるわけです。
実装されると何が可能になるのか
詳しくはZamaの上記の論文を参考にして欲しいのですが、
LUTを任意の出力に対して書くことができる、ということは、今までの格子暗号スキームの弱点を克服します。
それは、AIモデルでの 非線形演算を可能にする ということです。
今まで、CKKSやBFV方式でのベクトルの暗号化などにより、AIでの全結合層や畳み込み層などの線形変換（アフィン変換）に関しては、暗号状態で容易に実行可能でした。
しかし、ReLU関数やMaxPooling層などの非線形層（if文を実行する層と考えて良い）は、準同型暗号では実行が難しく、
- 一度復号して平文で一回一回非線形層を実行する
- ビットに一度エンコーディングして、CGGI方式を用いて無理やり演算する
などの手法を取ることが必要でした。
１の解決策に関しては、非線形層に遭遇するたびに暗号分を通信させ、セキュリティ上安全な環境下で演算を行う必要があったので、通信がなるべく少なくて済む、また、安全な計算実行環境を極力必要としないとする準同型暗号ベースのサービスとしては、準同型暗号本来のメリットが薄れてしまという欠点になっていました。
２の解決策に関しては、上記の従来の準同型暗号のメリットに関しては担保できる一方で、全てのバイナリ回路に対してブートストラップを施す手法は速度への影響が甚大であり、演算の実行時間が現実的な許容時間に収まらない、という欠点につながっていました。
しかしながら、Zama方式のプログラマブルブートストラップは、任意のLUTを作成可能 なので、
ReLU関数をLUTの出力としてエンコードしておけば、バイナリ回路まで暗号分を落とし込まなくても実行が可能になります。
したがって、２の解決策のように速度を犠牲にしなくても、また、１のように一旦安全な実行環境に暗号文を送らなくても、AIモデルの推論を一気通貫で暗号状態で実行することが可能になるということです。
また、全体の実行時間もCGGI方式のブートストラップの高速化の恩恵を受けつつ、Zama方式のエンコーディングにより浮動小数の演算の便利さの恩恵も受けることができるので、演算が非常に高速に、簡単に実行できます。
上記の論文では、ResNetのような畳み込みを１００層程度持った、実際の画像認識モデルでもよく使われるようなシチュエーションの演算を、完全秘匿した状態で数秒から数分のオーダーで計算完了した報告がされています。
最後に、このZama方式はRust言語で実装され、OSS化されています。
Zamaのエンジニアによって開発され、これからも大きくなっていくライブラリだと考えられます。
guideというフォルダの中にexampleコードがありますので、是非実行してみてください。
また、まだ私もさわりたてではありますが、
concreteライブラリのexampleなどをまとめていろいろいじってみたコードをgit上にあげていますので、興味のある方は是非ご覧ください（メンテナンスなどは全くやっておらず、exampleを羅列しただけなのでご容赦ください）
最後に
今回は、プログラマブルブートストラップについて解説 をしてみました。
プログラマブルブートストラップにて任意のLUT演算が可能になるということは、実装上の大きなブレークスルーだと感じています。
理論的にはCGGI方式のブートストラップの（解釈の）拡張なので、大きな変更というわけでは無いかもしれませんが、それゆえにCGGI方式の強みであった超高速なブートストラップを享受できている、といった利点も持ち合わせています。
これから格子暗号ベースの秘密計算が、このプログラマブルブートストラップによりさらなる社会実装を推し進めるのでは無いかと感じております。
Zamaに関しても、concreteライブラリに関しても、これからもキャッチアップしていきたいと思います。
今回はこの辺で。
kenmaro