kenmaroです。
秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。
今回は極めて最近パブリックとなった、Googleによる格子暗号トランスパイラのライブラリ
を紹介する記事にしようと思います。
全編として、ビルド、チュートリアルまで自身で試しています。
また、秘密計算、特に格子暗号に対して初めての方に対してGoogleがこのようなトランスパイラの取り組みをしている経緯についてもまとめていますのでぜひ最後までご覧ください。
そもそもトランスパイルとはなんなのか
以下の記述を見つけました。
コンパイラは、ある言語で記述されたソースコードを取得し、他の言語で（または多数の）出力ファイルを生成するプログラムを説明する包括的な用語です。実際には、主にこの用語を使用して、入力としてCコードを取り込み、出力としてバイナリ実行可能ファイル（マシンコード）を生成するgccなどのコンパイラを説明します。
トランスパイラは、ソースからソースへのコンパイラとしても知られています。したがって、本質的には、ソースコードファイルを取り込み、それを他の言語または異なるバージョンの別のソースコードファイルに変換するコンパイラのサブセットです。出力は一般に人間に理解されます。この出力は、マシンで実行できるようにするために、コンパイラーまたはインタープリターを経由する必要があります。
つまり、トランスパイラはコンパイラの部分集合であり、あるソースコードを入力とし、一般に人間が読める（gccなどが出力する機械語バイナリに変換するものではない）異なる言語のソースコードを出力とする変換器、
と言えます。
これを踏まえて、今回のこのGoogleのトランスパイラは、
C++のソースコード（人間が読めるもの）を入力とし、
TFHEライブラリ（後述するビットを暗号化し暗号状態でビット演算を可能にするライブラリ）のソースコードへを出力とする
変換を行うことのできるライブラリ。
ということです。
これはすごいぞ、、、
格子暗号トランスパイラ出現の経緯
BFV, CKKS, CGGI
今まで出してきた解説記事にて、CKKS, BFV, CGGI 形式の格子暗号などを紹介しました。
BFV形式は整数を暗号化し、暗号文同士、もしくは暗号文と平文の足し算や掛け算などを特定回数実行できる、
Leveled Homomorphic Encryption （レベル準同型暗号）でした。
CKKSについても同様にレベル準同型暗号と考えて概ね差し支えないですが、CKKSは整数だけでなく実数をエンコードできる点において実用性が高く、実際の数値計算やデータ解析、AIモデルを使った推論を暗号状態で行いたい時はCKKSが好まれていたのが最近の研究の流れでした。
BFVやCKKS形式に関してはSIMD演算が実装されており、数値を複数個まとめて１つの暗号文に詰め込み、演算をそれぞれに対して一括で行うことができます。この手法はパッキング（またはバッチング）と呼ばれ、例えばベクトルの内積をとったり、行列とベクトルの線形演算を行うときなど、パッキングの仕方をうまく工夫し、少ない掛け算回数で演算を行えるか、なども応用的な研究としては行われてきました。
ブートストラップ
CGGI形式に関してはブートストラップというアルゴリズムがキーワードになります。
BFVやCKKS形式などのレベル準同型暗号が先述の通り、暗号同士の演算回数が特定回数に限られていたのは、暗号文に付加されているノイズの増大が理由でした。ノイズはセキュリティを担保するために加えられているのですが、演算を実行するたびにノイズ同士が足されたり掛け算され、演算とともに増大していき、最後には暗号が復号不可能なレベルまで増大してしまいます。
CGGI形式はブートストラップを実装し、演算を任意回行えるという点において非常に強みがありました。
実際はBFVやCKKSにおいてもブートストラップは理論提唱されており、HElib、HEAAnライブラリなどに関しては実装も存在しています。
しかしながら、CGGI形式のブートストラップは非常に高速であり、既存の実装に関しては最速のブートストラップを持つ格子暗号形式となっています。
このブートストラップは、もともとは演算を重ねるたびに増大していく暗号文に含まれるノイズを除去するアルゴリズムとして考えられていましたが、CGGI形式のように整数や実数ではなくビットを暗号化する手法において、工夫するとXOR、OR、AND、NANDなどのプリミティブなブーリアン回路を暗号状態で計算可能であることがわかりました。
また、それらの回路からの暗号状態の出力ビットは、ブートストラップを通っているため、ノイズもゲートを通るたびに一定に抑えることができます。したがって、任意回、XORゲートなどを暗号に対して実行可能になるため、実質CGGIを使うことでどんな回路（コード）であっても演算可能となったわけです。
実際問題としては、実行時間の問題は一番の問題点です。ブートストラップがいかにCGGI形式で高速実装されているとはいえ、
最速の実装でもCPU時間で１NAND回路１０ミリ秒程度かかります。この辺りの世界最速実装は、（TFHEやTFHEppをご覧ください）
2021年になってからは、Zama ai という期待のスタートアップからプログラマブルブートストラップという手法が提唱されました。
Zama形式（中身はCGGIの亜種と呼ばれます。）はCGGI形式の高速なブートストラップ手法の恩恵を受けつつも、CKKSのような実数のエンコーダを備えた手法であり、ルックアップテーブルをブートストラップを使用して暗号状態で参照することができることを利用し、非常に実運用しやすい実装となっています。また、C++にとって変わるとされているRustでの実装がなされているというところも注目ポイントです。
基礎研究、応用研究
このようなまだまだ伸び代のある格子暗号についての研究において、最近の研究の流れとしては以下の二つになります。
- CGGI形式、CKKS形式などの最速実装を駆使し（恩恵を受けつつ）、社会実装への可能性を探る方向
- ブートストラップそのもの（特にCGGI形式）をアルゴリズム、ハードウェアを駆使して高速化を極める方向
後者に関してはビッグネームや学術界による研究開発（マイクロソフトなど）が顕著ですが、米国スタートアップ企業のDualityなどもIntelと共同で格子暗号専用チップの開発に着手し、アメリカ政府（及びミリタリー関連）が巨額出資をしている、というニュースは新しいものです。
今回のトランスパイラの焦点
前置きが大変長くなりましたが、今回のGoogleからのトランスパイラは前者となります。
C++のコードをこのトランスパイラによってバイナリ回路に落とし込み、TFHEライブラリで走るように変換できる機能を持っています。
レポジトリのREADMEには、以下のような使い方が書かれています。
準同型暗号を使う一番のモチベーションとして、計算の委託をしつつ、自身の送るデータや計算結果、及び計算過程のいかなる情報も委託先に漏れることがない、ということが挙げられます。
それを踏まえた上で、このトランスパイラは以下のように使用することができます。
ユーザはC++でコードを書き、トランスパイラで暗号文を受け付けるバイナリへと変換します。
変換されたバイナリを計算サーバに置きます。
計算の入力となるデータをビット毎に暗号化し、サーバに送信します。
サーバは受け取った暗号文と、計算用のトランスパイルされたバイナリを元に計算を実行し、結果を得ます。
サーバは結果を送り返します。
ユーザは受け取った結果を復号し、結果を得ます。
実装上の苦しみ
上のクライアント、サーバのやり取りのシナリオは、準同型暗号を用いた秘密計算を考える上ではとても基本的なものです。
しかしながら、このシナリオを実行することは容易ではなく、実運用でのセキュリティにも問題がありました。
例えば、このようにデータを秘匿化し、かつ計算を委託したいユーザと、格子暗号などのソリューションに詳しい専門家がいたとすると、実現するためにはいくつかのハードルがありました。
ユーザが秘密計算を行う時の開発は、（ほぼ）フルカスタムとなる
専門家はクリプト全般、準同型暗号について精通していますが、専門家は既存のライブラリを使ってユーザの行いたいアルゴリズムを準同型暗号で実行可能な形でコーディングする必要があり、そのコーディング自体は汎用性から考えると基本的にフルカスタムとなります。
つまり、プロジェクト化するにあたっても工数が膨大になる可能性があります。ユーザの使用する計算は極めて限定的になる可能性がある
CKKSやBFVを用いる場合、そもそも数値化されたデータの処理のみが暗号状態で実行可能になります。
AIのモデルなど、使われる数学が比較的限定的な場合はある程度汎用性を持たせることが可能ですが、一般的にカスタムされた計算アルゴリズムはカスタムが必要になります。専門家は、ユーザのアルゴリズムを把握する必要がある
これに関しては明らかに、専門家は既存のライブラリを使ってユーザの行いたいアルゴリズムを準同型暗号で実行可能な形でコーディングしなければならないため、アルゴリズムを細部まで理解する必要があります。
ユーザによっては使っているアルゴリズム自体を秘匿したい、たとえばそのアルゴリズムがどう計算を行っているか専門家に知られたくない場合、秘密計算化を行うことは頓挫する可能性が非常に高くなります。
- 暗号パラメータのチューニングが非常に難解である どの形式にも共通しますが、とりわけプログラマブルブートストラップなどを実装したCGGI形式など、エンコーダからくるノイズと、計算から来るノイズを同時にチューニングしなければならず、計算を最初から最後まで求められた計算精度を担保したまま実行することは非常に難しくなります。
以上の格子暗号を用いた際の、秘密計算の適用の実現に際する苦しみを和らげるものとして、
今回のトランスパイラなどの研究が行われている、というわけです。
それでは、Google先生のトランスパイラについてもう少しだけ詳細を見てみます。
トランスパイラのデザイン
５つのステップに沿ってトランスパイラを実現していると記述されています。
- XLS ステージ
このステージにおいてC++で記述されたコードをXLS Intermediate Representation へと変換します。
XLS Intermediate Representation の詳細は https://google.github.io/xls/ir_semantics/ ここにドキュメントがあります。
この辺りは私に知識が足りずに説明することはできませんが、
XLSは高位合成ツールチェインを持ち、C++等の上位言語から、VerilogなどのRTLプログラム（ハードウェア言語）に変換する時に使われるツールです。
XLSはそういう意味で言語であり、かつ高位合成をしてくれる変換器も持ち合わせているわけです。
Optimization ステージ
XLS Intermediate Representation へと変換されたものが、すでにビットレベルにまで落とされているわけではないと推察しますが、
このステージにおいて、すでにビット演算への変換を加味し、例えば計算が必要ないもの（すでに０か１かわかっている出力など）を前もって把握しておくことで、無駄な演算を極力減らし必要なものだけを計算するような変換が可能になるようです。（この辺は勉強します。。）Bitwise ステージ
XLS Intermediate Representation を、ビットレベルに変換し、演算も全てビット演算（OR、AND、XORなど）で表記します。FHE IR Transpiler ステージ
ビットに変換されたXLS Intermediate Representation をついにFHE-C++に変換します。
この時のFHE-C++ とは、TFHEを依存関係としてコンパイルし実行できる形式のことで、ここがGoogleによるTFHEのラッパーのようになっていると推察されます。The TFHE testbench ステージ
実行したい計算については、もうステージ４によってTFHEにより実行できる形になっているので、暗号化したデータを送る部分、暗号化状態で出力された結果を復号する部分等、testbenchによって（ここはシナリオによって実装方法が変わるので個々人で実装する）実装します。
以上により、ユーザクライアントシナリオに的するCGGI形式格子暗号による秘密計算が、C++ソースコードをベースとしてトランスパイルできます。
テスト関数をトランスパイル
Googleにより、いくつかのテスト関数がC++で用意され、それらが実際にTFHE下で暗号状態で実行できるように用意されています。
https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler/examples
上のリンクのフォルダの中にいろいろ試せる関数及びプログラムが用意されていますが、
実際に自分でも試してみました。
transpiler フォルダの中に、ビルドの仕方についてREADMEに解説されていますが、
Option B: Use Docker to install the transpiler
のDockerを用いたビルド方法で成功しました。
（Linux環境のみ現在サポート中との記述があり、自身のUbuntu18.04環境でdockerを使わない形で試してみたのですが、BazelでのビルドにFailedしたため一旦断念しました、、）
その後自身のMacOS環境にてDockerを使ってビルドしたところ１時間ほどで完了し、Hangmanのチュートリアルを走らせることができました。
Hangmanは単語当てゲームであり、挑戦者側が指定試行回数の範囲内でアルファベットを１文字ずつ試行し、相手側の単語を当てることができたらチャレンジ成功、というゲームです。試行回数が１回増えるたびに、首吊りの絵が描かれていき、それが完成してしまうと（試行回数が規定回数を超えてしまうと）アウトで、チャレンジ失敗となります。
このHangmanチュートリアルに関しては、ユーザがどのアルファベットを試行したか、ユーザの試行回数のステータス、正解の単語、全てに対して、ゲームがホストされているサーバサイドには秘匿されている状態となっています。
これ、地味にすごいと思いました。。Hangmanのゲーム自体も面白かったです。。
他にも簡単な演算をするcalculatorのチュートリアルなども載っていました。
exampleコードはある程度あるため、後述の、自身のカスタム関数に対しても実装してみることができるのではないかと思っています。
実際のカスタム関数をC++からトランスパイルしてみる
以下の build_your_own_demo.md にて詳細にカスタム関数のトランスパイルの仕方について記述されています。
https://github.com/google/fully-homomorphic-encryption/blob/main/transpiler/docs/build_your_own_demo.md
これについては、後編にて実際に自分でカスタム関数を作り、トランスパイルして秘密計算の実行までやってみたいと思っています。
まとめ
今回はGoogle先生によるC++を格子暗号状態で実行可能なソースコードにするトランスパイラについての記事を書いてみました。
今回はビルドするところ、チュートリアルを実行するところまで完了し、次の後編としてカスタム関数に対してトランスパイラを実行してみたいなと考えています。
なぜこのようなトランスパイラが必要か、ということに関しても、私の秘密計算スタートアップでの経験を生かしなるべく詳細に解説してみました。
この他にも私が秘密計算について解説した記事がございますので、ぜひご覧ください。
いかにオススメの記事も載せておきます。
格子暗号で新ブレイクスルー！！ プログラマブルブートストラップを解説！！
ついに来るか？主要格子暗号スキームのISO標準化
有名な格子暗号ライブラリの使用感をまとめてみた。