秘密計算エンジニアを始めて1年が経った。あり秘密計算エンジニアを始めて1年が経った。これを機におそらく自分がやってきたことを備忘録的にまとめておくべきであろう。ユーザの持つ機微データを安全に保管し活用する。次世代型暗号の1つである準同型暗号暗号を主に用いてこのゴールを達成するために、準同型暗号を用いたプラットフォームの開発を行なってきました。この会社に関わり始めて1年以上が経ち、秘密計算を研究、実装する取り組みを1年ほど続けてきたので、このアドベントカレンダーを機に準同型暗号を用いた秘密計算の動向と、今後どうなっていくかの予測をしてみたいと思います。複数の会社間でのデータ共有におけるデータセキュリティ問題クラウドを用いた機密データの分析におけるデータセキュリティ問題などの場面で有益だと考えられます。理由は、秘密計算はデータを暗号化したまま、秘密鍵の利用なしに分析を可能にする技術だからです。したがって、データを暗号化した後に分析をそのまま行うことができ、分析時に一度データを復号してしまう従来の暗号サービスではリスクであったデータ分析時のサイバーアタックを回避することができます。暗号化したまま解析可能という利便性を利用して、複数のデータ所有者がデータを暗号化したまま共有し、そのまま共有されたビッグ(暗号化)データを分析に利用することができます。準同型暗号による暗号文上での演算によるものがあります。この中でも我々は準同型暗号を用いたアプローチにフォーカスをしています。(LWE)問題をセキュリティの背景とした格子暗号です。活発に研究が行われている格子暗号ですが、主に暗号理論そのものをよくしようとする理論的な研究と、既存の格子暗号スキームを用いて如何にそれを実用化に持っていくかというアプリケーション的な研究が行われています。我々の立ち位置としては、後者のアプリケーション寄りの様々な研究開発を行なってきました。準同型暗号の理論的研究動向ここでは格子暗号の理論的な研究動向について、2009年の有名なブレークスルーから現在に至るまでの簡単な研究の流れをつらつらと書いていきたいと思います。次世代の暗号としてどんなものがあり、なぜ格子暗号が注目されているのかより知りたい方がいるならば、量子耐性をもつ暗号まとめ1や、量子耐性をもつ暗号まとめ2をご覧ください。以下で出てくるパッキングなどを用いた高速化についてもう少し具体的なことを知りたい人がいるならば準同型暗号を用いた高速化の例をご覧ください。更新暗号ベースの準同型暗号の有名な既存ライブラリにどのようなものがあるか知りたい方がいらっしゃったら、有名な格子暗号ライブラリの使用感をまとめてみた。GentryによるブレークスルーGentryによりブートストラッピングが提案された。Encryption(SHE)と呼ばれノイズの増大によって実行できる演算の深さが限られていた。LWE問題(Regev)から生まれたLWEサンプルである暗号文の内積、繰り上げ/繰り下げにより行われる復号回路が短縮された。その結果として自身の復号回路を新しい鍵空間で実行し、ノイズを入力のノイズより小さくすることが可能となり、FHEの基礎となった。RegevによりRLWEが提案された。これにより、n個のLWEサンプルがn次元の環の要素として記述された。結果として円分多項式による整数環の剰余環を利用することができ、DFTによる高速化が可能になった。Naehrig)などが研究されている。VercauterenによってRLWEサンプルとして記述された暗号文のSIMD演算が提案された。具体的には、中国人の剰余定理を用いて暗号空間を同型性のある複数の空間の直積として表記し、それぞれの空間に平文を敷き詰める手法である。これにより、暗号空間での演算は並列化された同型空間での要素ごとの演算となるため、複数の演算を並列して行うことが可能になった。レベルの概念は、モジュラススイッチと、鍵スイッチから成る。LWEサンプルとして記述された暗号文はノイズを含み、そのノイズは演算によって増大する。演算を続けた結果ノイズが大きくなりすぎて望んだ結果に復号ができないことが起こりうる。掛け算で増えるノイズは足し算のそれより非常に大きいため、掛け算をする際にモジュラススイッチによって暗号空間のモジュラスを減らしていき、ノイズの指数的な爆発を避けている。鍵スイッチによって暗号文のサイズそのものが掛け算のあとに爆発しないようにしている。モジュラススイッチ、鍵スイッチできる回数は鍵生成(コンテクスト生成)の際に予め決められる必要が有り、それをレベルとよんでいる。Waterは2013に上のLFHEを受け、直感的でない操作である鍵スイッチなどの操作を行わない手法を提案した。前記のブートストラッピング手法はすばらしい発想だったが、実用上はその計算量の多さが大きなボトルネックとなっていた。Genの提案から、様々な研究によりブートストラッピングを最適化、高速化する工夫が提案され、大きな成果を上げている。Micciancioは、剰余環から巡回群への同型性を用い、GSW形式のブートストラッピングを高速化した。GamaらがブートストラップにもちいられるGSW形式の環同士の内積を、トーラスを導入することでTGSWとTLWEの外積として書き直し、さらなる高速化を発表した(2015)。Songらが提唱したHEAAN形式では、今までの形式では復号の際に繰り上げ/繰り下げを行って打ち消していたノイズを、計算時に生成される計算ノイズ(フロート演算などと同じように)と見立てた。Kimによってこの形式のブートストラップも導入された。このブートストラップでは、復号演算の内のモジュラス演算を三角関数を用いて近似し、HEAAN形式の利点を用いてそれを巧みに計算するものだった。研究として、秘密分散をベースにしたライブラリ、準同型暗号を用いたライブラリ、さらに現在はそれらを巧みに組み合わせたハイブリッド型のライブラリが様々な機関で研究され、発表されている。始めての格子暗号の機械学習への応用Gilad-Bachrachらによって初めて秘密計算が機械学習に応用された。この研究では準同型暗号により、平文に対して学習されたMNISTモデルを用い、入力画像を暗号化して秘密計算により予測を初めて行った。この手法では畳み込み層のあとのReLU関数(非線形関数)が準同型暗号では計算困難な問題を解決するため、擬似的な非線形関数(2乗関数)を用いてモデルを簡易化、予測を高速化した。SIMD計算により複数画像の同じ場所にある画像要素をパッキングし、バッチ予測により複数枚数の画像予測を高速化した。(2019)などは畳み込み、全結合層などの行列演算は準同型暗号を用い、非線形の活性化関数の層やマックスプーリング層などをMPCを用いて行うハイブリッド型である。CryptCNNと、本論文は同じ取り組みをしている。(2018)は初めてモデルの重み情報に対しても暗号化していることである。本論文で実装したものもモデルの秘匿化を想定したものである。(2019)の取り組みとして、格子暗号やMPCの専門家によってモデルごとにチューニング・最適化されていた暗号パラメータやブーリアン回路の構造を、モデルに応じて自動的に探索するコンパイラが開発されている。これらは素晴らしい研究である。我々の使用しているHElibが使うBGV形式の格子暗号ではモジュラススイッチが乗算のたびに行われ、それはノイズの絶対値を小さくし乗算ごとの爆発を防ぐ一方で、暗号空間のモジュラスを小さくしてしまうため暗号空間のキャパシティを犠牲にしてしまう。数学的モデルが入力として秘密計算をどう行うか決定するとき、このようなことを考慮しながらパラメータを決定するのはとても手間のかかることであるからである。AlexNet)など、様々な工夫が行われている。MPC型の良さとして、非線形関数や特殊な関数であってもそれを準同型手法よりも苦手としないがある。欠点として複数のサーバにデータを分散させてリ(シークレットシェアリング)、演算関数を論理回路まで落とし込み、暗号化して複数サーバで計算しないといけないことや(ガーブレッド回路ため計算に要するサーバ間の通信量が膨大になってしまう)、入力データのサイズによる計算量、通信量の増加が準同型手法よりも影響を受けやすいことである。コスト削減を行うためにクラウド利用を画策し、そこに秘密計算の意義があるのに対し、複数サーバをメンテナンスするコストが嵩みクラウドを使う良さが少なくなってしまうことがある。準同型暗号を用いた計算の欠点として、暗号文のデータサイズが膨大になること、演算が非常に遅いこと、現実的な時間でできる演算が限られており、いくつかの機械学習には欠かせない演算を行うことが難しいことが挙げられる。演算の深さに応じて指数関数的な計算の増加(MPCの場合は指数的な増加である)がないこと、SIMD計算によって行列計算の並列化を実装しやすいことは利点であるし、MPC型よりもマネージしなければならないサーバの数が少なく、それ故に元来のクラウドを用いた秘密計算のコスト的なメリットを活かせることも利点である。したがって、さらなる機械学習層処理の高速化、最適化が必要である。HEに焦点を合わせた研究開発として、上記の改善を可能にする手法がこれからの秘密計算の社会実装を加速させていく重要な鍵となっている。まとめ秘密計算は、AIなどの需要が高まるにつれて必然的に高まるデータセキュリティの問題を解決する上で鍵となる技術であることは間違いない。学術的にも2009年の理論的なブレークスルーを発端として数多くのリサーチが理論的にも応用的にもなされている。これから格子暗号ベースの準同型暗号が社会実装されることに対して大事なことは、理論的な暗号スキームのアルゴリズムベースでの高速化、および応用的なパッキング手法や並列計算などの実用性を少しでも高めるための様々な工夫が必要である。我々はこれらを達成するために引き続き研究開発に取り組んでいきます。2019年ありがとう!2020年もいろいろ頑張りたいものです!!今回はこの辺で。以下に参考文献をたくさん載せておくので、興味のある方はお正月休みにでも目を通しましょう(嘘です、社会人の皆さんはお疲れ様でした。