@kenmaroです。
普段は主に秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。
概要
今回は、
TFHEppというライブラリを使って、格子暗号を用いた暗号に対して、
暗号状態でどのような計算ができるのかをテストプログラムなどを通じて解説していきたいと思います。
TFHEppライブラリとは
TFHEppライブラリは、
@nindanaoto さんらが開発する、TFHE形式の格子暗号を実装したライブラリのことです。
概要のところで貼ったリンクは、私@kenmaroがフォークしているTFHEppです。
このフォークライブラリでは、@kenmaro と @akakou がメインとなって開発しています。（開発内容については後で言及します。）
世界的にTFHEを実際に実装しているライブラリはあまり多くなく、私が知る限り、
- TFHEの原著論文著者らによる（公式？）実装 （C++) https://github.com/tfhe/tfhe
- MIT, Duality Technology による実装 Palisade (C++) https://gitlab.com/palisade/palisade-development
- ZamaAI によるプログラマブルブートストラップを実装したTFHE亜種ライブラリ (Rust) https://github.com/zama-ai/concrete
- @nindanaoto さんらによる今回紹介しているTFHEpp(C++)
です。
それぞれ素晴らしい実装となっていますが、
私個人としてはTFHEppを推しています。
理由は以下の通りです。
- ソースコードがよく整理され、コード量も追える範囲の量である
- 実装者本人による解説講義資料が存在する
- C++での実装である（私としてはRustよりC++の方がまだ精通しているので、、）
- cuFHEというGPGPUを用いたハードウェアへの架け橋となる実装も整備されており、参考にできる
- 日本人による実装なのでなんとなく思い入れがある
「ソースコードがよく整理され、コード量も追える範囲の量である」
に関しては、原著論文の作者たちによるTFHEライブラリが非常にコード量が多く、
個人的には開発をこの上から行おうと思うとかなり大変になるかな、と感じています。
Palisade については私はそこまでまだ終えていないのですが、かなり丁寧にまとまっていて追うことのできる実装になっているとは思います。ただ、ライブラリ自体がCKKSや他の形式も全て実装されているため、追うときは全て追おうとせず、TFHE関連の機能にフォーカスしたいのであれば、そこだけ切り出して開発すると良いでしょう、でなければ全体を追うのは厳しいと思います。
実際に動かしてみて、ライブラリ自体には手を出さず、リンクするだけの用途として使う分にはおそらく問題ないと思います。その点、TFHEppは全てを追おうとするともちろん大変だとは思いますが、
具体的なコアとなる関数（たとえばブートストラップ関数）に絞って理解しようとした場合、理論さえしっかりわかっていればソースコードが比較的追いやすいと感じています。
「実装者本人による解説講義資料が存在する」
この点に関しては、非常に賞賛すべきポイントだと思います。
以前、
この記事で初学者がプログラマブルブートストラップを理解する上で読むべき資料の一つとして紹介させていただきましたが、
この資料はTFHEppを開発されているnindaさんが、実際にセキュリティキャンプの講義で教える時に使われている資料です。彼の講義はスクラッチでTFHEを実装するために理論を理解し、実際にコーディングを行うというところにフォーカスされており、非常に丁寧にまとめられています。
私の上のロードマップの記事にも書いている通り、
もし格子暗号そのものを勉強し始めた人に対しては、キータ記事や初学者向けの簡単な講義資料（詳しくは上の記事を見てください）
を簡単に勉強し、何をやっているのかを理解した上で、プルグラマブルブートストラップの原著論文にチャレンジし、TFHEの原著論文をバイブルとしながら、並行してこの講義資料を読み込むと、かなり理解が深まるのではないかと思っています。
TFHEのオリジナルのライブラリが、実際に論文のアルゴリズムと少し違うやり方で実装が行われていたり、
元論文とのつながりを理解するのに骨が折れるのに対して、
TFHEppはこの資料があるため、理論と実装のつながりを理解しやすくなっていると感じています。
C++での実装である
現状TFHEの実装に関しては、C++とRustでの実装が存在している（他言語にもあるかもしれないが、有名どころでいうとこの二つ）
のですが、おそらく大多数の学生の方や研究者のかたは、C++の方が言語的に知識がある人が多いと思うので、その意味でTFHEppやPalisadeの実装が追いやすいでしょう。
@akakou は私とTFHEppのフォークライブラリを開発しているのは前述しましたが、彼はRustにもかなり詳しく、彼曰くConcreteの実装は「非常に」丁寧で、ドキュメント等もしっかりしているため、Rustがわかる人、もしくはRustの勉強も兼ねてTFHEライブラリの開発にチャレンジしてみたい人は、Concreteはおすすめです。
cuFHEというGPGPUを用いたハードウェアへの架け橋となる実装も整備されており、参考にできる
上のcuFHEは、繰り返しとなりますが、nindaさんらがTFHEppをGPGPUでの実装をされている
ライブラリのフォークになります。
現時点で、TFHEをGPUで高速化するような取り組みはいくつかありますが、実装が公開されており、
実際に私が動作することを検証してきちんと動いていることを確認したものは
cuFHEのみです。
TFHEではなく、CKKS等の格子暗号にもGPU実装をしているライブラリなどはあまり確認できず、
上のPalisadeの実装に関しても私はまだ動作確認できていません。（今度やってみます）
この意味で、実際にGPU上で動くプログラムが存在し、それをベースに自分で何か付け加えたりする開発をスタートできる、という意味でcuFHEはスタート地点としておすすめできます。
cuFHEは依存関係としてもちろんTFHEppを使っていますので、そちらからまず理解する必要があります。
日本人による実装なのでなんとなく思い入れがある
これは本質ではないと思いますが、MITやマイクロソフト、欧州のスタートアップが開発するライブラリが有名な一方で、日本人が作っているライブラリというところは、このライブラリ使ってみるか、と思う一つのモチベーションになるのも事実です。
フォークライブラリでは何をしているのか
長くなりましたが、TFHE形式の格子暗号の実装はいくつか存在し、それぞれ素晴らしい実装であり、
どれを選んでもいいと思いますが、私がTFHEppを現時点で使っている理由は上のような理由であると理解していただけたかと思います。
では、私と@akakou がTFHEppをベースに何をしているかというところを簡単に言及します。
追加で開発している部分というのは、プログラマブルブートストラップを管理するクラス（具体的にはエンコーダクラス）と、実際にプログラマブルブートストラップを実行する関数とその応用、
です。
どういう意味か少しだけ補足します。
TFHEにはバイナリタイプ（オリジナルのもの）と、亜種（ZamaによるPBSをメインとしたもの）がある
TFHEはそもそも、トーラス上で円分多項式による剰余環を定義し、バイナリ（すなわち０、１）を暗号化し、
ブートストラップを利用することで暗号文に対するNAND回路などを実装し、
任意の演算に対して暗号状態での実装を可能にするものでした。
つまり、人似の円座に対してそれらをバイナリ回路へと変換し、それをもとにTFHEライブラリを用いてコンパイルすることができれば、任意のソースコードに対して暗号状態での実行ができることになります。
この意味でのC言語等をTFHEで実行可能なようにするトランスパイラなどに、nindaさんは取り組まれています。
この取り組みにたいしてはMITやDuality社なども取り組んでおり、最近ではGoogleも、
C言語の実装をオリジナルのTFHEをもとにして暗号状態で実行できるようなトランスパイラを公開しています。
詳しくは以前記事を書いたので是非ご覧ください。
前置きが長くなりましたが、フォークライブラリで実装しているものは、
ZamaによるTFHE亜種（プログラマブルブートストラップをメインとしたもの）に必要なパーツを、
ベースとなるTFHEppの実装に付け加える作業であり、
そのPBSによって考えられる応用的なプログラムを実装することです。
TFHE亜種に関しては、根本の関数はTFHEと同じであり、
違うところはエンコーダの実装が必要であるというところと、汎用的なテストベクター（PBSで参照するLUTと考えて良い）を生成する関数を整備する必要がある、
というところです。
私たちはそこに一旦フォーカスをして実装を行なっています。
ZamaによるConcreteライブラリはPBSについての実装をメインとしており、私たちのフォークライブラリに関しては、機能としてはConcreteと同じになります。
実装している関数もConcreteの実装から引っ張ってきたものも多いです。
実装上のConcrete とTFHEpp（フォーク）の違い
前述のPBSに必要なエンコーダやカスタムテストベクターの関数等、TFHEpp(フォーク）はConcreteを基本的には踏襲していますが、
一部異なる実装を行なっています。
どのあたりが少し異なるのか少し言及します。
- padding ビットは使用せず、暗号化を施した時点から３２ビットをフル活用してエンコードする
- 暗号文と平文の演算（加減乗除）に対してもPBSを用いて演算をする仕様にしている
この２点です。
以前
この記事で少し言及したのですが、Concreteの実装だと、padding bit というものをエンコーダに渡す必要があります。
このpadding bit は、離散トーラス上に平文をエンコードする時に、どれだけビット数を使用するか（例えばint32を使いエンコードし、padding bit を４としたときは、28ビットを用いてエンコードし、４ビットは後の演算に対してとっておく）
指定する必要があります。
これはやりたいことはとてもわかるのですが、いくつかユーザ目線から使いにくいことがあります。
たとえば、暗号文に対して平文を掛け算するときは、このパディングビットを使用して、PBSを用いずに演算を行うことができるのですが、その演算の精度はパディングビットを上限とした精度しかありません。
もし４ビットのパディングビットを用意した場合、平文と掛け算しようとすると４ビットの精度でしか演算を行うことができないため、そのような精度での演算は現実的に行うタイミングがないのかなと思っています。
また、一度でもPBSを暗号文に対して実行すると、パディングビットは全て消費されることを考えると、
わざわざ構造を複雑化してパディングビットを消費するような演算を定義しておくよりも、
平文との演算は全てPBSを経由して行うようにしておいた方がわかりやすいと感じたため、パディングビットは基本的に最初から０にしてエンコードを実行するような仕様にしています。
TFHEppのフォークライブラリを用いて、PBSを使うことで、
暗号文に対して任意のLUTを参照することができるため、いろいろな計算ができます。
また、暗号文同士の足し算、LUTを用いた暗号文同士の乗算、
暗号文と平文の加減、乗算等もPBSを通して実行するような設計にしています。
具体的なテストプログラムの解説
現状、TFHEpp（フォーク）はあくまで開発段階であり、そこまで綺麗なテストコード（チュートリアルコード）が存在しているわけではないですが、
現時点で用意しているチュートリアルコードについて言及したいと思います。
mytest.cpp
このテストの前半部分では、
エンコーダを用いた実数の暗号化、
PBSの実行、暗号文同士の足し算を行なっています。
また、後半部分では、PBS関数の中にIdentity Key Switching を含めているものと、あえて含めずにlvl1の鍵で復号を実行し、PBSの中での KeySwitching による誤差がどの程度寄与してくるかという実験を行うことのできるものにしています。
mytest2.cpp
このプログラムでは、単層のNNを、TFHEppを用いて実行しています。
入力データは暗号化され、重み等のパラメータは平文として入力の暗号文に対してオペレーションされます。
この際の掛け算などの実行は前述の通り、PBSを用いて行われます。
プログラムの最後には、暗号状態での演算結果と、平文のみを用いて行なった結果の差を確認し、どの程度の精度劣化があるかどうか確認できるようにしています。
mytest3.cpp
このプログラムでは、mytest2と似ていますが、
隠れ層１層のNNを、mytest2と同じ条件で行なっています。
mytest4.cpp
このプログラムでは、暗号文に対して、PBSを繰り返し行い、
どの程度PBSによる誤差が生まれるかを確認しています。
後半では、Concteteが実装している手法を用い、
２つの暗号文に対してmaxを取る関数を実施し、制度について確認しています。
mytest5.cpp
このプログラムでは、暗号文や鍵のシリアライズ、デシリアライズいついてテストしています。
システムを考えようとすると、実際に暗号を送信したり、鍵を送信したりするような機構が必要となるため、このようなシリアライズなどが必要になるためです。
mytest6.cpp
このプログラムでは、Concreteに実装されているアルゴリズムを用いて、
暗号文同士の乗算をPBS経由で行い、その結果について精度を確認しています。
まとめ
今回は、後半のテストコード解説が少し尻すぼみになってしまいましたが、
TFHEppライブラリとそのフォークを用いてどのような演算を実際に暗号文に対して行えるか、
ということについて解説しました。
記事の前半については、TFHEpp自体の紹介と、その他のライブラリに言及しました。
TFHEppは比較的ビルドなどやりやすいですし、Dockerfile なども整備されているので、動かしやすい方だと思います。
もし興味のある方がいらっしゃいましたら、是非ビルドして上記のテストコードを走らせてみてください。
注意
現在PBSを通じて許容可能な精度を求める場合、８０ビットセキュリティの設定でビルドすることをお勧めします。
今回はこの辺で。