kenmaro です。
秘密計算、特に準同型暗号のことについて記事を書いています。

秘密計算エンジニアとして得た全ての知見をまとめた記事はこちら。
https://qiita.com/kenmaro/items/74c3147ccb8c7ce7c60c

これから準同型暗号について勉強したいリサーチャー、エンジニアの方へのロードマップはこちら。
https://qiita.com/kenmaro/items/f2d4fb84833c308a4d29

今話題のゼロ知識証明について解説した記事はこちら。
https://qiita.com/kenmaro/items/d968375793fe754575fe

概要

格子暗号ベースの完全準同型暗号「TFHE」の研究開発を行っているフランスのスタートアップ「Zama」
が、大々的に新しいTFHEライブラリである tfhe-rs のリリースを発表していました。
読んだ方も多いのではないかと思います。

まず、彼らのリリースに沿ってどんなライブラリなのかを簡単にお伝えしたいと思います。
また、せっかくなのでチュートリアルをまずは触りつつ、実行時間についても少し計測してみたいと思います。

concrete と何が違うのか

ZamaAIといえば、concrete と呼ばれるRustで書かれたTFHEのライブラリをすでにオープンソース化していましたし、
concrete の新しいメジャーバージョンなどを発表していたため、
そんな中で新しいライブラリをリリースするのか、と驚いた方も多いかと思います。

tfhe-rs がどのようなライブラリなのかをZamaAIのブログを参照して確認してみます。

tfhe-rsは

8ビットのshort integer でのプログラマブルブートストラップを実装している
公開鍵方式のTFHEを実装している
鍵と暗号の圧縮を実装しているので、データ転送が効率である
CやWASMのAPIを実装している

数ヶ月以内に、二つの新しい機能をリリースする予定であり、それらは以下である。

8ビットのshort integer より大きいlarge integer を実装したもの
浮動小数を実装したもの

これを踏まえたうえで、

tfhe-rs にシフトすることを推奨している
concreteはconcrete-ml, concrete-numpy のベースとしてこれからもサポートされていく。４月に新しいバージョン（concrete-v2)も発表される予定である。

速度について

TFHEの実装については、tfhe-rs はAVX512を使用しており、実装はかなり速いです。（これから実測します。）
ゲートbootstrap が7ms 程度で実行されるというデータになっています。
（私の環境で実行した時は、マシンスペックなども影響したと考えられますが、この示されている値よりはかなり遅い実行時間となりました。皆さんもご自身の環境で時間を測ってみてください。）

チュートリアルの実行

チュートリアルは、

バイナリ演算（バイナリ回路を暗号状態で評価するもの）
shortInt演算（現在サポートされているのは最大uint8 まで）

の２つの形式で準備されています。

こちらをフォローしていただければ難なくチュートリアル自体は実行できるため、あまり深入りしませんが、
理解するべきポイントだけ書きたいと思います。

バイナリ演算

暗号化できるのは、[0, 1] のboolean のみです。
これらを暗号化した暗号文について、

not
or
xor
nand

などが暗号状態で計算可能です。
これらの回路の実行には、ブートストラップと呼ばれる（非常に重い）演算が使われています。
暗号化や復号にかかる時間に比べて、圧倒的にこのブートストラップの演算時間がかかります。
したがって、これらの回路を暗号状態で実行するときにも時間がかかります。

実際に触ってみると、あたりまえすがこの構成でできる演算はビット演算のみなので、暗号状態で数値計算をしようとする場合、
とんでもない量の回路を自分で実装しなければならないので、低レイヤすぎるなと感じる人が多いと思います。
例えば、整数同士の足し算を実行しようとした場合、半加算器、全加算器を自分で実装し、その回路をテストしなければなりません。

この観点より、後述するshortIntegerの実装では、最大８ビットの整数について演算が実行できるため、こちらの方が実際に使うときには使いやすく感じるでしょう。

では、なぜこのバイナリ形式のライブラリを表に出しているかと言うと、私の考察も入りますが、以下の理由があると思っています。
理由は、任意のコンパイルする言語のトランスパイラを作り、いかなるソースコードもTFHEベースの暗号で実行する、という研究がなされており、それらの研究がベースとして使用するのがこのバイナリベースのTFHEだからです。

実際、Googleなどもその研究をしており、C言語で書かれたHello, world をコンパイルしたあと、その計算をTFHE上で動かすようなチュートリアルも実際に存在します。
興味のある人は以下からアクセスしてみてください。

こちらについても、かなりアクティブに開発が行われているので、ウォッチしておいた方が良いと思います。

shortInt 演算

さて、バイナリをわざわざ使う必要がない時は、
基本的にはこちらのshortIntの実装を実際には使うことが多いと思います。

shortIntの演算については、暗号状態で整数についての

加算
乗算
シフト演算

など、たくさんのことを暗号状態で行うことができます。

チュートリアルの延長プログラム（整数の比較）

チュートリアルの延長として、整数の比較演算をして、
その条件に応じていろいろ演算を行えないかと模索してみました。

プログラムのコアは以下となります。

fn main() {

    // 鍵の生成は省略

    let p1 = 3;
    let p2 = 2;
    let p3 = 2;

    let mut d_tmp = 0;

    // データの暗号化
    let mut c1 = client_key.encrypt(p1);
    let mut c2 = client_key.encrypt(p2);
    let mut c_cond_udpate = client_key.encrypt(p3);
    println!("encrypt done");

　　 // アップデートする数字の初期化、暗号化
    let mut c_res = server_key.create_trivial(0);
    let mut c_update = server_key.create_trivial(0);

    // 暗号状態での比較演算
    let c_comp = server_key.unchecked_greater_or_equal(&c1, &c2);

    // 比較演算の結果を利用して計算
    c_update = server_key.unchecked_mul_lsb(&c_cond_udpate, &c_comp);

    // 結果のアップデート
    c_res = server_key.unchecked_add(&c_res, &c_update);

    // 結果の復号
    dec = client_key.decrypt(&c_res);
    println!("dec: {:?}", dec);
}

やりたかったこととしては、

p1, p2 （どちらも整数で、暗号）を比較演算し、どちらが大きいかを暗号状態で取得
暗号状態の結果に応じて結果をアップデートする

という内容でした。

実行してみると、実際にp1とp2の大小関係によって、復号結果が変わることがわかります。

実運用上の（大きな）問題点

一見うまくいくようにも感じたのですが、実際にいろいろ試してみると課題があることがわかります。

それはやはり、実行時間と精度のトレードオフです。
uint8 をサポートしているとは言え、平文の空間（TFHEのトーラスをどう分割するかということです）
を大きくサポートしようとすると、暗号パラメータが巨大になり、

鍵生成
暗号化や復号
演算（ここでは例えば比較演算）

の実行時間が膨大になります。
たとえばこの例では、平文空間を２、３ビットの構成で実行するのには問題なかったのですが、
８ビットフルに使おうとすると、計算が一向に終わらず、自分の環境ではプロセスを強制終了することになりました。
また時間が許すときに測定できればそのときにアップデートしてみます。

これから先ハードウェアによる高速化や、その他の高速化や運用上の工夫により、
TFHEが難なく実システムで動く日も遠くはないとは思う一方で、
現実的には

いろいろな格子暗号スキーム（例えばCKKS形式）
格子暗号に限らない他暗号スキーム（例えばペリエ暗号）
暗号に限らない他の秘密計算スキーム（例えばTEE）

などを駆使した活用の仕方が必須ではあるな、と改めて考えさせられました。

まとめ

今回は新しいTFHEライブラリである tfhe-rs についてチュートリアルを実行し、
自分でもやってみたい演算をプラスアルファとして実行してみました。

格子暗号を用いた完全準同型暗号のライブラリの中では

非常に高速
使いやすい

という意味でこれからも勉強する必要があると思いますし、
興味があればいろいろな演算をTFHEで行ってみようと思いました。

一方で、現状の演算の制約や現実的な実行時間や精度について考えさせられました。

皆さんも機会があればぜひチュートリアルを実行し、自分で回路や演算をカスタマイズしてみて実行してみることをおすすめします。

これからもぜひキャッチアップしていきましょう。

今回はこの辺で。

@kenmaro