プログラムマブルブートストラップ
Gentry による格子暗号のブートストラップ
格子暗号はノイズを利用しているため、計算するとノイズが増大する弱点が存在 この弱点は格子暗号の本質に関わるもので何ともし辛い ブートストラップ
暗号に付加されるノイズを取り除く
ノイズが爆発する前に、また演算できる
任意回演算できる
ブートストラップ手順
1. 格子暗号の秘密鍵$ k_1を別の秘密鍵$ k_2で暗号化 これをブートストラップ鍵$ k_{\rm bs}とする
2. 復号の時に行う演算を$ k_{\rm bs}を用いて準同型演算する
復号の時に行う演算は、復号化の中に含まれる部分的な計算？
出力結果は$ k_2で暗号化されている
3. $ k_1で複合できるように鍵スイッチングする
２のステップは、復号演算をs2の暗号空間で準同型演算する、というところがミソです。
よく例えられるのは、結んだ紐（暗号）を紙袋の中に入れ（s2による再暗号）、紙袋の中で結んだ紐を解く（復号回路の準同型演算）ことで２重にした暗号の、内側のみ復号するというオペレーションです。
プログラマブルブートストラップ
任意の演算に対してブートストラップをカスタマイズする
任意の演算を実行可能にする
素敵ポイント
深層学習の非線形演算を暗号文に対して適用できる
ResNetのような畳み込みを１００層程度持った、実際の画像認識モデルでもよく使われるようなシチュエーションの演算を、完全秘匿した状態で数秒から数分のオーダーで計算完了した報告がされています。
CGGI方式によるブートストラップ
高速
最初期の数時間かかっていたブートストラップを 0.1 秒程度で可能にする
トーラス上に定義されたビットを暗号化
XOR / OR / NOT 等をブートストラップで演算可能
実質どんな演算もどんな深さでもできる
ビットごとに暗号化が必要
データの塊で演算できる手法と比べて速度で劣る
Zama によるプログラマブルブートストラップ
Zama はフランス拠点のスタートアップ
考え方
既存のブートストラップの出力を恒等変換を記載した LUT と見なす LUT の中身を任意の出力に書き換えると任意の演算を LUT に埋め込める 元になった CGGI が高速なのでその恩恵を受けられる