準同型暗号による秘密計算の社会実装はどこまで進んでいるのか【2021年12月時点】
秘密計算
準同型暗号による秘密計算の社会実装はどこまで進んでいるのか【2021年12月時点】
SHARE
目次
概要
準同型暗号という技術についていろいろと記事を書いてきて、もう３年が経とうとしています。
今回は、準同型暗号を中心として、秘密計算の社会実装の様相や、課題などについて、
- 準同型暗号ベースの秘密計算の現状はどのような感じなのか
- どこに研究が向かおうとしているのか
- 私が考える一番の社会実装の難しさはどこにあるのか
以上の観点からまとめていきたいと思います。
初めに
準同型暗号は、
暗号化をしたまま、データそのものを公開することなく演算を行える暗号技術
として注目を高めています。
そのユースケースなどは考えることが面白いですし、数学的、ソフトウェア実装的にもまだまだ改善の余地があり、とても面白い分野だと思っています。
その一方で、まだ実社会と、現在準同型暗号を用いてできることの乖離は少なからず存在し、
実用的には程遠いアプリケーションやユースケースなどが考えられるのも事実です。
今回は、今まであまりお話ししてこなかった、機械学習モデルの準同型暗号を用いた暗号状態での学習、というトピックに関しても少し言及してみようと思っています。
今回はその中でもAIモデルの学習を暗号状態で行うということが難しいとされる理由や、
なにがどのような理由でどのくらい難しいとされているのかなどについてまとめていきたいと思います。
MLモデルの学習について
MLモデルといってもいろいろなモデルが存在し、例えば
- 線形回帰
- 非線形回帰
- ニューラルネット
- クラスタリング
- 強化学習
などいろいろなモデルや分野が存在する中で、
全てについて言及するのはここでは難しいです。
ここでは、あくまでもニューラルネットにある程度焦点を絞って考察していきます。
できるだけこの記事を読み、途中のリンクを拾うことで全体像がわかるようにしたかったため、
まずは準同型暗号にはどのような形式があり、
どのような演算が可能なのか
どのような演算が苦手なのか
演算速度はどのような肌感覚なのか
というようなところをまとめていきたいと思います。
したがって、かなりボリュームが大きくなるかもしれませんがお付き合いください。
また、準同型暗号状態で行える演算というものには制限があることを理解し、
実際のユースケースに対して考えられる運用上のシナリオに紐づく難しさについても理解したいと思います。
それを鑑みた上で線形回帰、非線形回帰、ニューラルネット
などが一般的に学術的にも準同型暗号が応用されている分野ですので、そこについてフォーカスしてまとめていこうと思います。
準同型暗号で（現実的に）可能な演算
準同型暗号を用いると、暗号に対して幾つかの演算が可能になります。
どのような演算が可能になるかは準同型暗号の種類にもよりますが、一般的に使われている格子暗号型の準同型暗号形式では
- CKKS形式
- TFHE形式（バイナリ型）
- TFHE亜種（プログラムブートストラップ型）形式
などが今のところ最先端のものです。
一つずつ、どのような演算に向いているのか、と言うところを簡単にまとめたいと思います。
CKKS 形式
大きく２つのメリットがあります。
一つ目は、実数を暗号化できると言うこと
二つ目は、ベクトルを暗号化できると言うこと
です。
例えば、BFV形式などを考えると、整数のみを暗号化可能なため、実数を暗号化したい場合何か定数をかけておき、整数部分のみを暗号化し、復号のときに元の定数で割ってあげるような操作が必要でした。
しかしながら、CKKS形式の格子暗号を使うと、まずエンコードとして、実数はVendermonde行列というものを乗算され、
格子暗号が定義されている剰余多項式のSubRingと呼ばれる空間にマッピングされます。
このとき、BFV形式などと暗号化するときに使われる（R)LWE問題については共通なため、基本的に一番大きな違いというのはこのエンコードの部分です。このエンコードした後に出てくる（平文）多項式の各係数に対して、スケーリングという操作（具体的には2^40など）の大きな数をかけてから暗号化し、復号するときにそのスケーリング定数によって割り算をします。
LWE問題に従って暗号化するとき、ノイズを平文多項式に対して加算しますが、このノイズはBFV形式の時のように復号時に完全に消去されるわけではなく、あくまでもスケーリングによって小さい値に丸め込まれます。
したがって、CKKS形式の演算はその性質上ノイズを許容し、そのノイズに対しては、普通のfloat32などを計算するときに出てくる誤差のように、「演算上で出てくる誤差」として考えます。
これはつまり、CKKS形式での演算が、Exactなものではなく、誤差を許容しているため、その誤差が実際に準同型的に行いたかった関数の振る舞いに、どのくらい影響を及ぼすか考える必要があるということです。
具体的にどのくらいの演算誤差が出てしまうのか、と疑問に思う方もいるかもしれませんが、
これらはパラメータによって決まり、一概にどのくらいというのは難しいです。
しかしながら、以前の記事で概ねこのくらい、というようなことをまとめていますので、
もし興味のある方がいらっしゃいましたら是非ご覧ください。
https://qiita.com/kenmaro/items/931835476ca8781de9f9
結論を言ってしまえば、一般的に使われるパラメータを使った場合、
演算で許容するべき誤差は、float32での演算より大きく、float16での演算での誤差より小さい。
ということになりました。この結果からも、機械学習の推論においては、（また、学習においても部分的には）
十分な演算精度があるということがわかるかと思います。
機械学習に対して、どの程度の演算精度が必要か、ということに関しては色々記事がありますが、
私がわかりやすいと思った記事のリンクを念の為貼っておきます。
https://ascii.jp/elem/000/004/014/4014066/
TFHE形式（ビット）
さて、CKKS形式について言及しましたが、CKKS形式を用いた準同型計算には、大きな弱点があります。
それは、
- 非線形演算が苦手である
- 比較演算などは基本的にできない
ということです。一つずつ簡単ではありますが解説します。
非線形演算が苦手である
苦手、といった意図としては、可能であるが、演算速度が非常に遅くなることが多い、
という意味です。
従って、CKKS形式（BFVも）を用いた演算を考えるとき、非線形演算（例えばSin関数など）に関してはなるべく実装上避けたりすることが多かったり、
一度この関数だけ、トラスト領域にデータを戻し、平文状態でこの関数だけ実行するような折衷案を取ることがほとんどです。
ここでお気づきかと思いますが、機械学習においてNNを考えた場合、
演算は「線形演算」、「非線形演算」の組み合わせから成り立っています。
線形演算によってニューロンの情報伝達を模倣し、
非線形演算によって各ニューロンが励起されるかどうかの閾値を設けています。
したがって、このように「線形演算」、「非線形演算」がミルフィーユのように重なっているNNの演算に対してCKKS形式を用いて演算を行おうとすると、非線形演算の処理に悩まされることになります。
一般的に取られる手法としては、
- NNモデルそのものを、準同型暗号で実行しやすいようなモデルに置き換える
- 非線形演算をテイラー展開して、無理やり近似する
- 非線形演算は通信を通して、トラスト領域で実行するようなシステム面で対処する
というようなアプローチとなります。
NNモデルそのものを、準同型暗号で実行しやすいようなモデルに置き換える
というアプローチですが、ReLUなどの非線形な関数をなるべく使わず、入力の各要素を２乗するだけの関数に置き換えたりなどの手法がよく取られています。（かなりナイーブに感じるかもしれませんが、この分野の最先端の研究者や実装屋さんもこのようなことをしています。）
例としましては、この論文をご一読ください。
http://proceedings.mlr.press/v48/gilad-bachrach16.pdf
実際、このアプローチをとった場合、モデルが一定値劣化することを許容することになります。
ReLU関数などであれば99.9%の精度が出ていたモデルであっても、このように２乗のみの関数を活性化関数として採用した場合、モデルの精度は劣化することがほとんどです。
もう一つ問題なのは、すでに学習済みのモデルを使うことができないため、準同型暗号による推論を行いたい、と思ったときにモデルを作り直し、学習もやり直さないといけない、と言ったような運用上の面倒くささなどです。
非線形演算をテイラー展開して、無理やり近似する
これもよく用いられる手法です。機械学習においては、学習されたモデルに対して正規化されたデータを入れるときなど、
ある程度通したい関数に対する定義域が把握できている場合がほとんどです。
したがって、この定義域の範囲でなるべく元の非線形関数に近い、３次や５次などの多項式近似を行うことがあります。
この手法を用いれば、CKKS等の格子暗号を用いても非線形関数を近似的に評価できます。
しかしながら、この近似を行うということは、暗号文同士の掛け算が大量に発生することにつながります。
暗号文同士の乗算は、CKKS形式のような「レベル」準同型暗号、つまり、鍵を作った時点で何回掛け算を許容するか前もってセッティングしておかなければならない形式において、レベルの大きさが演算時間のオーバーヘッドに大きく寄与します。
例えば、５次のテイラー近似を行う非線形層と線形の層が２層重なっている（かなり小さいモデル）であったとしても、
演算をレベル準同型暗号として通そうとすると、
(1 (線形層で必要な乗算） + 5 (非線形層の近似に必要な乗算） ) * 2 （２層） = 12となります。
CKKS形式の格子暗号ライブラリを触ったことのある人ならわかると思いますが、
１２レベルを持った構成とすると、とても演算は重くなります。
したがって、多項式近似については、とても少ない層しかもたないNNが応用領域であれば可能ですが、
層が多いDNNのようなモデルの推論に対してはかなり実用的に厳しい実行時間となるかと思います。
この辺りの格子暗号ライブラリについては記事を以前書いておりますので、もし触ってみたいという方がいらっしゃいましたら是非ご覧ください。
https://qiita.com/kenmaro/items/0654ad4d26e7a4dd919b
非線形演算は通信を通して、トラスト領域で実行するようなシステム面で対処する
このアプローチは、実行時間と、この準同型暗号を用いた演算システム自体の価値、とのトレードオフとして、現在実現が一番容易な落とし所と考えられます。
実際に、もともとのシステムの価値を、「演算の非トラスト領域（クラウドなど）へのオフロード」と考えた場合、
トラスト領域ではなるべく計算などが走らないほうがいいのですが、このように現状実用が難しい演算はトラスト領域にデータを戻してから行ってしまおう、ということはいろいろな実装で行われています。
世界の準同型暗号のリーディングをとっているMicrosoftリサーチの研究者たちも、この点に関しては
- 現在実用的に準同型暗号を用いるところ
- トラスト領域で実行するべきところ
を明確化し、それをきちんと切り分けたシステム構築に対して賛同をしています。
比較演算などは基本的にできない
これに関しては、当たり前とも取れるのですが、
もし暗号文のペアに対して比較を行うことができた場合、
簡単な挟み撃ちを繰り返すことで暗号文が秘匿している数字の特定を行えてしまいます。
したがって、基本的に暗号文に対しては比較演算はできません。
しかしながら、入力の数値に対して、特殊なエンコーディングと演算なアルゴリズムを適用することで、
二つの暗号文の比較演算を、通信を介して行うアルゴリズムが存在しています。
これにより、例えば決定木等の、比較演算を多く行うような機械学習アルゴリズムに対しても、
準同型暗号を用いて実行は可能です。
詳しくは以前の記事で言及していますので、もし興味のある方がいらっしゃいましたらご覧ください。
https://qiita.com/kenmaro/items/9a0362a6f9ab4e802aa3
また、これを用いた決定木アルゴリズムの準同型暗号を用いた実装論文に関してはこちらをご覧ください。
https://eprint.iacr.org/2019/819.pdf
TFHE形式の圧倒的メリット
さて、前置きが大変長くなってしまいましたが、
CKKS形式の大きな弱点とも言える、
- 非線形関数
- 比較演算などの関数
が実運用上実行が難しい中、TFHE形式のメリットには以下のような大きなメリットがあります。
- ブートストラップという手法を用い、ビットを暗号化したものに対してNAND回路実行できること
- 上記のNAND回路の実行が、任意回可能なこと
この二つは、ブレイクスルーを起こすレベルで画期的なことです。
理由は、
この二つの条件が揃ったとき、任意の演算回路をNAND回路の組み合わせでトランスパイルすることができれば、
任意の演算を暗号状態で実行することができるからです。
つまり、どのような演算でも可能なため、CKKS形式が苦手とした「非線形関数」、「比較演算」
等も暗号状態のものに対して可能になります。
したがって、「究極」の格子暗号であるとも言えます、しかしながら、実用上これもまた問題があります。
それは、全ての演算をビットに落とし込み、NANDゲート等のバイナリサーキットを毎回評価しないといけないことです。
ブートストラップを用いたNAND回路はどのくらい実用的なのか？
NAND回路で全ての演算を書き下す以上、根本のNAND回路の暗号状態での実行がもし遅ければ、一つの関数を通すのもとても時間がかかってしまう
と考えられます。
それでは、ブートストラップを用いたNAND回路の評価にはどのくらいの時間がかかるのでしょうか？
結論は、（現状の）世界最速の実装であっても、10msほどです。
これは、この準同型NANDを用いたときに、全ての演算が平文と比べて１万倍程度のオーバーヘッドがかかってくるということを意味しています。
高速化の目処などは立っているのか？
先程準同型NAND回路の実行時間が、最速でも１０m秒くらいだと記述しましたが、
このNAND回路をいかに早く実装できるか、もしくはアルゴリズムを改善できるか、
というところは格子暗号界隈の最先端のリサーチトピックです。
具体的には、専用のハードウェアを実装しようとする動きが一番活発です。
また、汎用GPUを用いてこのNAND回路を高速化しようとする動きもあります。
GPGPUを用いた高速化のOSSに関しては、
でも少し言及していますので是非ご覧ください。
結論を言うと、私が確認できた範囲で、GPGPUを用いた時のNAND回路の実行時間は
0.5msほど、つまりCPU実装に比べて２０倍ほどの高速が実現できているようでした。
世界的な取り組みに目を向けてみると、このハードウェアに対してはアメリカの取り組みが頭一つ抜けている印象です。
詳しくはこちらの記事などをみていただくとわかるのですが、DARPAというアメリカの国の軍事を司るエージェンシーの一大プロジェクトとして、このTFHE形式のオペレーションを高速化するために大きなお金を動かしています。
もし興味のある方がいらっしゃいましたら、調べるとこのプロジェクトに関するいくつかの記事が出てきますので是非ご覧ください。
ちなみに、
このプロジェクトに採択され、政府からの資金のもとこのハードウェア実装に動いているのは、IntelとDuality Technologyという準同型暗号等技術のリーディングをとっている組織
です。（Duality Technology）はスタートアップ企業です。
Duality Technologies は、この政府とのコラボレーション等から、投資家からの期待をとても集めており、
大規模な資金調達などにも成功しています。詳しくは以下の記事をご覧ください。
DARPAの記事によると、専用ハードウェアが実装された暁には、実行時間が１万倍近く速くなるだろうと言う試算も出ており、
それが実現すれば、準同型暗号の実世界への実装のハードルがかなり下がることが予想されます。
この未来（つまり暗号文でのNAND関数のランタイムがとても速くなった未来）が来た場合、
実運用上必要になってくるのは、
任意のプログラムをバイナリゲートへと変換し、それをTFHEライブラリの上で実行可能なプログラムに書き下すような「トランスパイラ」です。
そのトランスパイラを作るために取り組まれているのが私の知る限り、
- 京都大学チームVSP
です。Googleのトランスパイラについては記事を以前別途書きましたので是非ご覧ください。
VSPチームについてもTFHEの関連記事で何度も言及しています。
https://qiita.com/kenmaro/items/0f11340986990093c4da
TFHE亜種（プログラマブルブートストラップ型）形式
この形式については、２０２０年ごろに出てきた、とても新しい技術です。
基本的な構成についてはTFHE（バイナリ型）と変わらないものの、バイナリだけを暗号化するのではなく、
実数をトーラス上で表現するようなエンコーダを介することで、実数を直接暗号化することを可能にしています。
また、プログラマブルブートストラップ（PBS）というブートストラップの新しい解釈を用いることで、実数に対して任意のルックアップテーブルの実行を可能にしています。
このとき、LUTの参照は１NAND回路の実行と内部処理が変わらないこと（両者ともやっていることはブートストラップ処理なので）から、
先程のTFHE（バイナリ）形式のように全ての演算をNANDゲート化せずに、直接評価することができるため、非常に高速な処理をすることが可能です。
また、LUTなので非線形演算ももちろん可能ですし、LUTを組み合わせれば暗号文同士の掛け算、暗号文の比較も行うことが可能です。
（これらに関しては別記事にまとめますのでそちらを今後是非ご覧ください。）
プログラマブルブートストラップに関しては以前記事をいくつか書いていますので、是非ご覧ください。
https://qiita.com/kenmaro/items/d78f012c522594126afe
また、プログラマブルブートストラップを実装している数少ないOSSライブラリとして、私もTFHEpp (https://github.com/virtualsecureplatform/TFHEpp)
をベースに開発を進めていますので、もし興味のある方がいらっしゃいましたら是非ご覧ください。
https://github.com/kenmaro3/TFHEpp
MLモデル学習実装
以上を踏まえた上で、機械学習モデル、とりわけニューラルネットモデルの学習を行おうとした時、
どの暗号形式で実行することが運用上考えられるでしょうか。
現状考えられるのはCKKS形式を用いたモデル学習
私は、基本的に（現状での業界での実装状況を鑑みた場合）
CKKS形式での実装になると考えています。
理由は上でもお話しした通り、CKKS形式が実数をエンコードできる形式であることや、
ベクトルを暗号化できるSIMDの実装を内部に持っているからです。
言及したような、鍵生成の時点において、掛け算を何回行うかというような情報を加味し、レベル準同型暗号
として鍵生成することが一般的でありながら、システムを一度固めてしまえば、
トラスト領域なども実際に活用しながら、
フィードフォーワードの演算と、バックプロパゲーションの演算も実行することが可能です。
トラスト領域の活用はシステム上不可欠
ここで、先ほども言及しました通り、トラスト領域の活用は必ず必要になってきます。
また、その使用の頻度は、どのくらいのレベルを持った鍵を作るか、ということに依存します。
なるべく非信頼領域で準同型演算を行う（演算のオフロード量を最大化する）と、それだけ多くのレベルが必要になり、
全体のランタイムとしては膨大になる可能性があること。
信頼領域での演算をある程度許容（演算のオフロードとのトレードオフを考慮する）することにより、
暗号鍵のレベルをある程度小さく抑え、全体のランタイムがあまり膨大にならないように抑えるようなアーキテクチャ作りが必要になります。
これを考慮して、
隠れ層１層のニューラルネット学習をCKKS形式で実装した実装論文を昨年アーカイブに出展しました。
もしご興味のある方がいらっしゃいましたら是非ご覧ください。
https://arxiv.org/pdf/2012.13552.pdf
この論文の中は、
１バッチの学習フェーズを暗号状態で遂行し、１バッチを学習した後は重みパラメータをトラスト領域で復号した後再暗号化をおこなって限られたレベル鍵の元で学習を行っています。
この論文で工夫したところは、暗号化された重み行列から、復号することなく転置行列を計算するところの最適化です。
逆伝搬において重み行列の転置行列を用意し逆伝搬で戻ってくるベクトルに対してオペレーションする必要があるのですが、
この論文ではそのやり方を工夫することで、計算全体の掛け算回数を少なくすること、また、全体の掛け算回数の深さ（つまり鍵が想定するべき掛け算のレベル）を低減することで、全体のランタイムを向上させています。
近い将来可能になりそうな、TFHE形式を活用したモデル学習
CKKS形式＋トラスト領域での演算のいいところ取りをした、現在可能な落とし所の実装が現状は考えられるものの、
これからTFHE形式（バイナリ型、およびプログラマブルブートストラップ型）を活用したモデルの学習についても実装が進んでいくと考えられます。
ここまで読んでいただいた方にとっては明白かもしれませんが、TFHE型を使う一番のメリットとして、
- トラスト環境での演算の最小化
- トラスト環境での演算の必要性に伴う通信量の最小化
- CKKS形式ではそもそも通せなかった関数を実行できること
などのメリットがあります。
一方で、一番のデメリットはやはり「速度」
となります。私が「近い将来」実装可能であろう、といったわけは、
先程のDARPAなどによるハードウェアの実装などが進み、なにかしらの結果が出てくる２、３年後において
もしかしたら劇的なランタイムの改善が見られるかもしれないことを期待しているからです。
TFHEで重要になる、ブートストラップの精度について
これまでTFHE形式に関しては、ランタイムの速度、というところしか言及してきませんでした。
しかしながら、TFHE形式（とりわけプログラマブルブートストラップを用いるタイプ）において、
PBS一回で出てくる計算誤差はCKKS形式で演算をした時に出てくる誤差とは比較にならないくらい大きいです。（この誤差の大きさについては改めて別記事で記述できればと思っています。）
したがって、この誤差を小さくするために対処をしなくてはならないのですが、それは（いくつか方法があるにせよ）基本的にはLUTを大きなものにする、と言うことになります。
詳しくはプログラマブルブートストラップの解説記事をご覧いただきたいのですが、
このLUTはRTLWEというトーラス上の多項式の係数に記述されたものであり、大きなLUTを生成しようとすると、
この多項式の次元を大きくする必要があるのです。
例えば、多項式の次元が2^10であった場合、このLUTは10ビットの精度しかその性質上持つことができません。
１０ビットの精度ではとても機械学習のモデルを学習するような精度に届きませんから、モデル側を工夫すると言う選択肢を取らなかった場合、このLUTをもっと大きくすると言うことが必要になります。
つまり、多項式を大きく（例えば2^16乗まである多項式）をLUTとして定義し、半精度くらいの精度がPBSの後に保証されるようにする必要があるわけです。
（ちなみに、PBSの演算誤差は、LUTの大きさのみからくるわけではないので、他の誤差のソースに関してももっとチューニングする必要があります。）
このLUTを大きくする、ということは、如実に演算のパフォーマンスに関わります。
具体的には、
- ランタイムが線形で大きくなる
- ブートストラップ鍵も線形で大きくなる
したがって、ブートストラップを実行する時にブートストラップ鍵や、複数のLUTをロードする際、
メモリが足りなくなる可能性があることに注意する必要があります。
このように、TFHEにおけるPBSの精度を上げるには、ランタイム及びメモリサイズへの影響が伴うことになります。
モデルの重み（パラメータ）を暗号化するか、しないかで演算する内容が少し違う
ここで、推論、学習どちらに対しても当てはまるのですが、モデルの重みを暗号化するか、しないかによって、参照するLUTに違いが出ます。
まず、モデルのパラメーターを暗号化しない場合、つまりモデルに対して入力するデータのみ暗号化する場合、
モデルの各パラメータ情報がLUTとして保存され、演算の時にロードされて実際にPBSを実行する必要があります。
したがって、
基本的にモデルの重み１つに対して、LUTが一つ存在し、（例えば１００万パラメータの機械学習モデルに対しては１００万個のLUTが必要）入力の暗号データに対して、それらのLUTをひたすら参照していく、
と言うのが、モデルのパラメータを暗号化しない時の実行方法になります。
次に、重みを暗号化する場合、暗号と暗号の掛け算が必要になりますが、一般的にやり方は２種類あります。
- LUTを複数回参照して掛け算を間接的に求める方法
- 重みパラメータをTGSW形式の暗号文として記述し、TLWEの入力暗号文に対して外積をとることで掛け算を実行する方法
どちらもTFHE等に精通していれば問題なく実装できる手法なので、どちらがいいとは言えませんが、どちらかを使って暗号同士の掛け算を実行し、順伝搬、逆伝搬を実行することになります。
バックプロパゲーション時の具体的な演算がTFHEで実行可能か
逆伝搬を行うときは、ロス関数を計算した後、各ノードに対して逆伝搬を行い、非線形関数の微分をとるような作業が必要となりますが、
TFHEのPBSを持ちいれば、演算自体は可能です。
例えば、ReLU関数の微分関数はステップ関数になり、それ自体はLUTとして簡単に処理できるからです。
逆伝搬によりアップデートされる重みに対して、動的にLUTを生成する必要あり
推論を行う際は、モデルのパラメータは固定されており、参照するLUTに関してはいつも同じものを同じ場所で使えば推論をLUTを用いて完遂することが可能でした。
しかしながら、モデルの学習においては、１バッチに対して逆伝搬を行った後、モデルのパラメータをアップデートします。
先程、モデルのパラメータを暗号化するかによって、実行する演算の内容が少し変わる、
と言うふうに記述しましたが、仮にパラメータを暗号化しなかった場合、
モデルとの演算を実行する時にLUTを単純に参照していたため、モデルがアップデートされるたびにLUTも再生成することになります。
先程の例で言うと、１００万パラメータを持つモデルに対して、学習する際には、
１００万個のLUTを１バッチごとに作り替える必要があります。
また、モデルのパラメータを暗号化して学習している場合ですが、先程のどの暗号文同士の乗算方法を使っているかで対応が変わってきます。
まず、複数回LUTを用いて掛け算を実行している場合、いつも同じLUTを参照しているので、モデルのパラメータがアップデートされようとも、LUTを新しく生成する必要はありません。
次に、TGSWを用いて外積で掛け算を実行している場合、そもそもLUTは用いていなかったため、モデルのアップデートに対して再生成するLUTはありません。
マルチパーティでのモデル学習について
最後に少しだけ言及しますが、モデルを暗号を使って学習させるというシナリオにおいては、学習データの出どころが１ヶ所だけではないことがほとんどです。
例えば、どこかの会社を筆頭とし、チーム会社（とはいえデータについては互いに秘匿しないといけない）らのデータを使って１つのモデルを学習させるようなシナリオがほとんどです。
この文脈においては、連合学習などによってこのシナリオを実現することもありますが、それぞれのデータを暗号化したままクラウドで集約し、モデルの学習を行うことも考えられます。
この時、準同型暗号を用いた学習を実装しようとすると、鍵の管理をどうするか、という問題に直面することが多いです。
基本的に、準同型暗号を持ちいた演算において、鍵をそろえてから演算を行う必要があります。
したがって、各社それぞれの鍵でデータの暗号化を行なった場合、信頼されたパーティが計算できるようにそれらの暗号の鍵を揃える（巻き直しといったり、Proxy Re Encryptionと言ったりする）作業が必要になることがほとんどです。
これにより、結局トラストできるパーティが必要になってしまうので、システム上それが許容できるか問題のすり替えになってしまいます。
この問題にフォーカスするのが、マルチキーでの準同型暗号です。この手法により、異なる鍵で暗号化したデータに対して、鍵を揃えることなく演算することが可能になります。
ここでは詳細には立ち入りませんが、そのような研究がCKKS形式、TFHE形式両方で行われています。
下に参考文献を貼っておきますので、興味のある方がいらっしゃいましたら是非ご覧ください。
基本的に、マルチキー型の準同型暗号セッティングを用いると、ランタイム、鍵の大きさ、暗号文の大きさなどが膨大になる傾向があります。
https://eprint.iacr.org/2019/524.pdf
まとめ
まとめとして、
準同型暗号（格子暗号）を用いた機械学習モデル（ニューラルネットの学習）
について、
- どのような暗号形式が使われているのか
- システム構成はどのようなものなのか
- どのような研究開発が行われているのか
- 実用性と実装のタイミングは？
- マルチキーについて
というポイントに対して改めてお話ししたいと思います。
どのような暗号形式が使われているのか
CKKS形式を用いた手法が現時点では実装レベルでは使われると思います。
この時、CKKS形式は任意回の演算をサポートするものではなく、掛け算できる回数に上限がある、「レベル」準同型暗号であることから、
そのレベルを極力増やさないようにした、モデル自体の軽量化（簡易化）の工夫などが必要になります。
システム構成はどのようなものなのか
上記のような「レベル」準同型暗号であるCKKS形式を考慮すると、計算を行うサーバである程度の演算を行い、
苦手な演算や、そのレベルを超えるような演算、または、乗算回数がレベルの上限に近づいた時に再暗号化によって乗算回数をリセットするような処理を「トラスト領域」で行うようなシステム構成が不可欠になります。
この「トラスト領域」でのある程度の演算というものは、理想のシステム構造（データ所有者は計算を全て委譲し、暗号化したデータをサーバに渡すだけで良い）とは少し異なってしまうことは承知していますが、現在実装可能なのものと、今研究開発途中の技術などが作り出す理想的なシステム構成の「落とし所」として現状はこのようなシステム案が考えられることがある、というところを了承いただければと思います。
どのような研究開発が行われているのか
現在、研究が進んでいる領域といえばTFHE形式が一番ホットです。
また、CKKS形式であっても、ブートストラップ法の高速化（CKKS形式でのブートストラップはLUTを参照するようなものではなく、乗算によって溜まったノイズを除去するというブートストラップ法元来の用途で使われるものです）が研究の一番の焦点となっています。
TFHE形式に関しては、バイナリを暗号化することで任意の回路を任意回実行できるような実装が存在します。したがって、CKKS形式がトラスト領域での演算を内包しないと全体の演算を終えることが非常に難しいということに対し、TFHE形式はすべての計算を秘密鍵が存在しないアントラスト領域で実行できるということについて大きなアドバンテージを持っています。
しかしながら、ランタイムが実用可能なレベルに達していないところ、SIMD演算を用いることが難しいところなどを考慮し、ハードウェアでの高速化が現在の研究対象としては一番フォーカスされている領域になります。
まとめとして、TFHEにはPBSを実装したTFHE亜種と言うものも存在し、それはCKKSとTFHEのいいところどりのような実装になっており、このTFHE亜種も現実的な実装としてはこれから考えられると思います。
実用性と実装のタイミングは？
実用性という意味では、簡単なNNの学習や、ロジスティック回帰の学習というものであればCKKS形式で実装可能です。
また、システム構成に関しては、トラスト領域を用いたものが一般的に考えられます。
TFHE形式を用いたNNの学習については、実装が不可能ではないものの、現状の実装ではランタイムが実用的でないため、ハードウェアの開発を待つことになると考えられます。具体的には、お伝えしたDARPAプログラムなどによるハードウェアの開発が２年以内くらいになにかしらの結果を出し、その結果によってどのくらいのランタイムで学習が可能になるかが明らかになってくると思います。
また、ハードウェア実装の前にGPGPUを用いた高速化などについては、１、２年の間に何かしら結果が出るかと思われます。
この際、SEALライブラリや、TFHEppライブラリ、Concreteライブラリなどが応用先だと考えられますが、HWやGPGPUなどレイヤと、ソフトウェアのレイヤを繋ぐようなドライバの開発など、これからの研究開発もやることがたくさんあり、やればやるほど実装領域が多くなるため、とても面白い研究、実装ができるのではないかと思います。
マルチキーについて
考えられるシナリオでは、実際１パーティで完結するモデルの学習についてはあまりユースケースとして考えられず、
複数パーティが持っているデータを持ち寄り、互いに見られないようにしながら学習を実行するようなシナリオがより多くのケースで考えられます。
このケースにおいて、Nパーティがそれぞれ別々の鍵でデータを暗号化し、それぞれの鍵で暗号化されたデータに対して計算可能な計算鍵をクラウド上において計算を実行するような実装論文も存在しており、CKKS、TFHE形式どちらでも応用先として考えられるでしょう。
最後に
いろいろな研究開発が進み、３年ほどこの準同型暗号に対してコミットをしていましたが、まだまだ機械学習モデルの学習という意味ではできないことも多いですし、これからの研究開発に実装できるかどうかが大きく依存しているというところも事実です。
しかしながら、ハードウェアの開発、GPGPUでのランタイム向上、マルチキー準同型暗号によるマルチパーティでの学習実行など、
これからとても面白くなりそうだと思いますので、これからも是非この分野に対してキャッチアップしていきましょう。
今回はこの辺で。
三原
この記事を書いたメンバー
EAGLYS株式会社
三原 健太郎