プログラマブルブートストラップの概要を整理する

Posted at 2022-12-15

この記事は EAGLYS Advent Calendar 2022 の10日目の記事です

はじめに

TFHEに触れ始めてから１年弱経ったこともあり，人に聞かれることも増え始めてきたこの頃，今回のアドカレでTFHE関連の話題を予備知識なしの状態から始めて，詳細までまとめようと思います

突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください

今回のアドカレの関連記事（気になるところから読んでください）

１日目：Torus・TLWEの概要
５日目：TRLWE・TFHEの概要
10日目（イマココ）（プログラマブルブートストラップの概要）：

11日目（TFHEの暗号化方式の詳細（前半））：
12日目（TFHEの暗号化方式の詳細（後半））：
18日目（プログラマブルブートストラップの詳細（前半））：
19日目（プログラマブルブートストラップの詳細（後半））：

15日目（multi-key TFHEの概要）：

20日目（TFHEの最新動向（理論編））：
25日目（TFHEの最新動向（実装編））：

これは，プログラマブルとブートストラップに分けることができます
前者は後で触れることにして，ブートストラップとは，大雑把には暗号文からノイズを取り除く操作を言います

TFHEの暗号化方式では，暗号文中にノイズを格納するため，例えば，暗号文の足し算を何度も行うと，ノイズが蓄積されていきます
ノイズの格納サイズには許容範囲があり，それを超えると，元の平文に復号できない可能性があります

そのため，足し算などの演算回数の操作を制限する（leveled方式）こともできますが，それだと不便すぎるので，途中でノイズを取り除けるといいよねっていう技術がブートストラップというイメージです

ブートストラップは次の3つの操作に分けることができます

次からこれらの操作の大枠を説明します（詳細は18, 19日目の記事で）

ブートストラップとは，大雑把には暗号文からノイズを取り除く操作

と書きましたが，本当に取り除こうとすると，それは復号とやっていることが変わらずあまり意味がありません

そうではなく復号できるような候補（=ノイズがない）の値を配列の形などで事前に格納しておきます
（test vector, test polynomial とか言われるやつを使います）

そして，暗号文からその値を参照して，ノイズがない場合の値に置き換えることで，ノイズを取り除く，と表現しています

しかし，値を参照する上で，暗号文に色々と細工が必要で，Rescaling, Sample Extraction, Key Switching という３つの操作を行います
＊厳密には，Rescaling は Blind Rotation の前に行いますが，これは本質ではないので今回は割愛

Sample Extraction とは，Blind Rotation で値を参照する際に，元の暗号文はTorusの元のベクトルなのですが，それがTorus上の多項式のベクトルに変わってしまいます

やりたいことは，元の暗号文のノイズを復号することでしたから，形を戻すためには，多項式を更にベクトルと見て，1つの長い（=サイズが大きい）ベクトルとみなします

Sample Extraction は実はこれしか行なっていません（だから計算量的に小さい）

Sample Extraction からベクトルを受け取りますが，そのベクトルのサイズは，元の暗号文のサイズよりも大きいので，サイズを調整する必要があります

その際に，Switch鍵（とかKey Switching Keyとか）を使って，サイズを元に戻します

ブートストラップの応用がプログラマブルブートストラップ（functional bootstrapとも言います~~っていうかこっちの方が主流らしい~~）です

こちらは test-polynomial にTorus上の任意の関数の情報を加えることができる技術になります
＊厳密にはTorus上ではないんですが（再三の繰り返し）

一般に暗号文は復号して暗号化したら元の暗号文に戻ります
そこで事前に平文から別の平文へ変換（何かしらの関数を作用させる）させることで，暗号文１→平文１→平文２→暗号文２と別の暗号文へと変換させることが可能です

これを上記のブートストラップと組合せることで，ノイズの入った暗号文からノイズの入っていない別の暗号文への変換が可能となります

また上記の「変換」には何も制約がないため，（あくまでTorus上の）任意の関数を作用させることができます

こちらも詳しいことは，19日目の記事にて

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！