概要
縁があり秘密計算エンジニアを始めて１年が経った。これを機におそらく自分がやってきたことを備忘録的にまとめておくべきであろう。
ユーザの持つ機微データを安全に保管し活用する。
次世代型暗号の１つである準同型暗号暗号を主に用いてこのゴールを達成するために、準同型暗号を用いたプラットフォームの開発を行なってきました。
この会社に関わり始めて１年以上が経ち、秘密計算を研究、実装する取り組みを１年ほど続けてきたので、このアドベントカレンダーを機に準同型暗号を用いた秘密計算の動向と、今後どうなっていくかの予測をしてみたいと思います。
秘密計算が注目される背景
大きく分けると、秘密計算は
- 会社内の部門間でのデータ共有におけるデータセキュリティ問題
- 複数の会社間でのデータ共有におけるデータセキュリティ問題
- クラウドを用いた機密データの分析におけるデータセキュリティ問題
などの場面で有益だと考えられます。
理由は、秘密計算はデータを暗号化したまま、秘密鍵の利用なしに分析を可能にする技術だからです。したがって、データを暗号化した後に分析をそのまま行うことができ、分析時に一度データを復号してしまう従来の暗号サービスではリスクであったデータ分析時のサイバーアタックを回避することができます。また、暗号化したまま解析可能という利便性を利用して、複数のデータ所有者がデータを暗号化したまま共有し、そのまま共有されたビッグ（暗号化）データを分析に利用することができます。
秘密計算の２つの潮流
秘密計算には２つの潮流があり、
_ マルチパーティによる秘密分散をベースにしたもの
- 準同型暗号による暗号文上での演算によるもの
があります。
この中でも我々は準同型暗号を用いたアプローチにフォーカスをしています。
準同型暗号の中でも学術的にホットに研究が行われているのは格子 Learning with Error (LWE)問題をセキュリティの背景とした格子暗号です。
活発に研究が行われている格子暗号ですが、主に暗号理論そのものをよくしようとする理論的な研究と、既存の格子暗号スキームを用いて如何にそれを実用化に持っていくかというアプリケーション的な研究が行われています。我々の立ち位置としては、後者のアプリケーション寄りの様々な研究開発を行なってきました。
準同型暗号の理論的研究動向
ここでは格子暗号の理論的な研究動向について、2009年の有名なブレークスルーから現在に至るまでの簡単な研究の流れをつらつらと書いていきたいと思います。
もし次世代の暗号としてどんなものがあり、なぜ格子暗号が注目されているのかより知りたい方がいるならば、量子耐性をもつ暗号まとめ①や、量子耐性をもつ暗号まとめ②をご覧ください。
また、以下で出てくるパッキングなどを用いた高速化についてもう少し具体的なことを知りたい人がいるならば準同型暗号を用いた高速化の例をご覧ください。
さらに、更新暗号ベースの準同型暗号の有名な既存ライブラリにどのようなものがあるか知りたい方がいらっしゃったら、有名な格子暗号ライブラリの使用感をまとめてみた。をご覧ください。
Gentryによるブレークスルー
Gentryによりブートストラッピングが提案された。それまでの形式はSomewhat Homomorphic Encryption(SHE)と呼ばれノイズの増大によって実行できる演算の深さが限られていた。しかしこの論文の功績としてほとんどの格子暗号がセキュリティの基礎としている LWE問題(Regev)から生まれたLWEサンプルである暗号文の内積、繰り上げ/繰り下げにより行われる復号回路が短縮された。その結果として自身の復号回路を新しい鍵空間で実行し、ノイズを入力のノイズより小さくすることが可能となり、FHEの基礎となった。
LWEからRLWEへ
LWE問題の拡張として、Lyubashevsky, Peikert, RegevによりRLWEが提案された。これにより、ｎ個のLWEサンプルがｎ次元の環の要素として記述された。結果として円分多項式による整数環の剰余環を利用することができ、DFTによる高速化が可能になった。このあたりのDFTや、NTTライブラリの開発は長い歴史が有り、今でも様々な高速化手法（例えばLonga, Naehrig）などが研究されている。
Smart, VercauterenによってRLWEサンプルとして記述された暗号文のSIMD演算が提案された。具体的には、中国人の剰余定理を用いて暗号空間を同型性のある複数の空間の直積として表記し、それぞれの空間に平文を敷き詰める手法である。これにより、暗号空間での演算は並列化された同型空間での要素ごとの演算となるため、複数の演算を並列して行うことが可能になった。
Leveled FHE
その後、Brakskil, Gentry, Vercauteren が Leveled Fully Homomorphic Encryption LFHEを提案した。レベルの概念は、モジュラススイッチと、鍵スイッチから成る。LWEサンプルとして記述された暗号文はノイズを含み、そのノイズは演算によって増大する。演算を続けた結果ノイズが大きくなりすぎて望んだ結果に復号ができないことが起こりうる。掛け算で増えるノイズは足し算のそれより非常に大きいため、掛け算をする際にモジュラススイッチによって暗号空間のモジュラスを減らしていき、ノイズの指数的な爆発を避けている。さらに、鍵スイッチによって暗号文のサイズそのものが掛け算のあとに爆発しないようにしている。モジュラススイッチ、鍵スイッチできる回数は鍵生成（コンテクスト生成）の際に予め決められる必要が有り、それをレベルとよんでいる。
GSW方式
Gentry, Smart, Waterは2013に上のLFHEを受け、直感的でない操作である鍵スイッチなどの操作を行わない手法を提案した。
前記のブートストラッピング手法はすばらしい発想だったが、実用上はその計算量の多さが大きなボトルネックとなっていた。Genの提案から、様々な研究によりブートストラッピングを最適化、高速化する工夫が提案され、大きな成果を上げている。例えばDucas, Micciancioは、剰余環から巡回群への同型性を用い、GSW形式のブートストラッピングを高速化した。さらにChillotti, GamaらがブートストラップにもちいられるGSW形式の環同士の内積を、トーラスを導入することでTGSWとTLWEの外積として書き直し、さらなる高速化を発表した(2015)。
CKKS方式
その後、Cheon, Kim, Kim, Songらが提唱したHEAAN形式では、今までの形式では復号の際に繰り上げ/繰り下げを行って打ち消していたノイズを、計算時に生成される計算ノイズ（フロート演算などと同じように）と見立てた。この形式に関してもさらなる研究が進められており、Cheon, Han, Kimによってこの形式のブートストラップも導入された。このブートストラップでは、復号演算の内のモジュラス演算を三角関数を用いて近似し、HEAAN形式の利点を用いてそれを巧みに計算するものだった。
準同型暗号の応用的研究動向
応用的な研究として、秘密分散をベースにしたライブラリ、準同型暗号を用いたライブラリ、さらに現在はそれらを巧みに組み合わせたハイブリッド型のライブラリが様々な機関で研究され、発表されている。
始めての格子暗号の機械学習への応用
Gilad-Bachrachらによって初めて秘密計算が機械学習に応用された。この研究では準同型暗号により、平文に対して学習されたMNISTモデルを用い、入力画像を暗号化して秘密計算により予測を初めて行った。この手法では畳み込み層のあとのReLU関数（非線形関数）が準同型暗号では計算困難な問題を解決するため、擬似的な非線形関数（2乗関数）を用いてモデルを簡易化、予測を高速化した。また、SIMD計算により複数画像の同じ場所にある画像要素をパッキングし、バッチ予測により複数枚数の画像予測を高速化した。
続々と開発される機械学習への応用例
この研究を受け、最近数年でたくさんの秘密計算による機械学習予測ライブラリが研究開発されたが、Mohassel, Zhang 、Rouhani, Riazi, Koushanfar、Liu, Juuti, Luはシークレットシェアリング、ガーブレッド回路などを用いたマルチパーティ型の計算手法で計算を秘匿する方法（MPC）を主としているのに対し、Bourse, Minelli Minihold, Paillier、Juvekar, Vaikuntananthan, Chandrakasan (2018)、Jiang, Kim, Lauter (2018)、Liu, Sakuma (2017) 、Liu, Juuti, Lu (2017)、Boermer, Costache, Cammarota (2019) 、Dathathri, Saarikivi, Chen, Laine, Lauter, Badawi, Chao CaRENet (2019)などは畳み込み、全結合層などの行列演算は準同型暗号を用い、非線形の活性化関数の層やマックスプーリング層などをMPCを用いて行うハイブリッド型である。この中でも、行列計算においてどのように行列やベクトルをパッキングし、計算の高速化及び帯域幅の減少を、CRTパッキングを用いて行っているJuvekar, Vaikuntananthan, Chandrakasan (2018)、Jiang, Kim, Lauter (2018)、Badawi, Chao CaRENet (2019) 及びCRTパッキング、FBパッキングを組合せて行っている Liu, Sakuma (2017) CryptCNNと、我々は同じ取り組みをしている。また、特筆すべきは上記の殆どのライブラリが入力画像を暗号化し、モデルの重み情報などは秘匿せず平文としてエンコードしたものと演算を行っていたものに対し、Jiang, Kim, Lauter (2018)は初めてモデルの重み情報に対しても暗号化していることである。
準同型暗号をより簡単に使うためのコンパイラ開発
そして、ごく近年 Boermer, Costache, Cammarota (2019)や Dathathri, Saarikivi, Chen, Laine, Lauter (2019)の取り組みとして、格子暗号やMPCの専門家によってモデルごとにチューニング・最適化されていた暗号パラメータやブーリアン回路の構造を、モデルに応じて自動的に探索するコンパイラが開発されている。これらは素晴らしい研究である。なぜなら、例えば、我々の使用しているHElibが使うBGV形式の格子暗号ではモジュラススイッチが乗算のたびに行われ、それはノイズの絶対値を小さくし乗算ごとの爆発を防ぐ一方で、暗号空間のモジュラスを小さくしてしまうため暗号空間のキャパシティを犠牲にしてしまう。数学的モデルが入力として秘密計算をどう行うか決定するとき、このようなことを考慮しながらパラメータを決定するのはとても手間のかかることであるからである。
このように暗号理論の発展と共にそれを社会実装しようとする取り組みが行われ、アルゴリズム（計算アルゴリズム）の高速化の研究開発及び、演算のGPUなどのハードウェアを利用した計算並列化による高速化(Badawi AlexNet)など、様々な工夫が行われている。
MPC型の良さとして、非線形関数や特殊な関数であってもそれを準同型手法よりも苦手としないがある。欠点として複数のサーバにデータを分散させてリ（シークレットシェアリング）、演算関数を論理回路まで落とし込み、暗号化して複数サーバで計算しないといけないことや（ガーブレッド回路ため計算に要するサーバ間の通信量が膨大になってしまう）、入力データのサイズによる計算量、通信量の増加が準同型手法よりも影響を受けやすいことである。また、コスト削減を行うためにクラウド利用を画策し、そこに秘密計算の意義があるのに対し、複数サーバをメンテナンスするコストが嵩みクラウドを使う良さが少なくなってしまうことがある。
実社会への実装への課題
準同型暗号を用いた計算の欠点として、暗号文のデータサイズが膨大になること、演算が非常に遅いこと、現実的な時間でできる演算が限られており、いくつかの機械学習には欠かせない演算を行うことが難しいことが挙げられる。しかしながら、演算の深さに応じて指数関数的な計算の増加（MPCの場合は指数的な増加である）がないこと、SIMD計算によって行列計算の並列化を実装しやすいことは利点であるし、MPC型よりもマネージしなければならないサーバの数が少なく、それ故に元来のクラウドを用いた秘密計算のコスト的なメリットを活かせることも利点である。
したがって、さらなる機械学習層処理の高速化、最適化が必要である。HEに焦点を合わせた研究開発として、上記の改善を可能にする手法がこれからの秘密計算の社会実装を加速させていく重要な鍵となっている。
まとめ
秘密計算は、AIなどの需要が高まるにつれて必然的に高まるデータセキュリティの問題を解決する上で鍵となる技術であることは間違いない。学術的にも2009年の理論的なブレークスルーを発端として数多くのリサーチが理論的にも応用的にもなされている。これから格子暗号ベースの準同型暗号が社会実装されることに対して大事なことは、理論的な暗号スキームのアルゴリズムベースでの高速化、および応用的なパッキング手法や並列計算などの実用性を少しでも高めるための様々な工夫が必要である。我々はこれらを達成するために引き続き研究開発に取り組んでいきます。
2019年ありがとう！2020年もいろいろ頑張りたいものです！！
今回はこの辺で。以下に参考文献をたくさん載せておくので、興味のある方はお正月休みにでも目を通しましょう（嘘です、社会人の皆さんはお疲れ様でした。ゆっくり休みましょう。）
おわり。
参考文献
もし論文を読みたい方がいれば、以下を読めば大概の研究動向はわかると思います。
Lattice Theoryについての論文
Boura, Christina, Nicolas Gama, and Mariya Georgieva. "Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning." IACR Cryptology ePrint Archive 2018 (2018): 758.
Brakerski, Zvika. "Fully homomorphic encryption without modulus switching from classical GapSVP." Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012.
Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. "(Leveled) fully homomorphic encryption without bootstrapping." ACM Transactions on Computation Theory (TOCT) 6.3 (2014): 13.
Chillotti, Ilaria, et al. "Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2016.
Cheon, Jung Hee, et al. "Homomorphic encryption for arithmetic of approximate numbers." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017.
Annual International Conference on the Theor y and Applications of Cryptographic Techniques. Springer, Cham, 2018.
Ducas, Léo, and Daniele Micciancio. "FHEW: bootstrapping homomorphic encryption in less than a second." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2015.
Fan, Junfeng, and Frederik Vercauteren. "Somewhat Practical Fully Homomorphic Encryption." IACR Cryptology ePrint Archive 2012 (2012): 144.
Gentry, Craig. "Fully homomorphic encryption using ideal lattices." Stoc. Vol. 9. No. 2009. 2009.
Gentry, Craig, Amit Sahai, and Brent Waters. "Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based." Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013.
Longa, Patrick, and Michael Naehrig. "Speeding up the number theoretic transform for faster ideal lattice-based cryptography." International Conference on Cryptology and Network Security. Springer, Cham, 2016.
Lyubashevsky, Vadim, Chris Peikert, and Oded Regev. "On ideal lattices and learning with errors over rings." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2010.
Smart, Nigel P., and Frederik Vercauteren. "Fully homomorphic SIMD operations." Designs, codes and cryptography 71.1 (2014): 57-81.
Alperin-Sheriff, Jacob, and Chris Peikert. "Faster bootstrapping with polynomial error." Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
HE, MPC, Hybrid ML Application についての応用的な論文
Gilad-Bachrach, Ran, et al. "Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy." International Conference on Machine Learning. 2016.
Badawi, Ahmad Al, et al. "The AlexNet moment for homomorphic encryption: HCNN, the first homomorphic CNN on encrypted data with GPUs." arXiv preprint arXiv:1811.00778 (2018).
Chao, Jin, et al. "CaRENets: Compact and Resource-Efficient CNN for Homomorphic Inference on Encrypted Medical Images." arXiv preprint arXiv:1901.10074 (2019).
Boemer, Fabian, et al. "nGraph-HE2: A High-Throughput Framework for Neural Network Inference on Encrypted Data." arXiv preprint arXiv:1908.04172 (2019).
Bourse, Florian, et al. "Fast homomorphic evaluation of deep discretized neural networks." Annual International Cryptology Conference. Springer, Cham, 2018.
Chandran, Nishanth, et al. EzPC: programmable, efficient, and scalable secure two-party computation for machine learning. Cryptology ePrint Archive, Report 2017/1109, 2017.
Dathathri, Roshan, et al. "Chet: Compiler and runtime for homomorphic evaluation of tensor programs." arXiv preprint arXiv:1810.00845 (2018).
Halevi, Shai, and Victor Shoup. "Algorithms in helib." Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
Juvekar, Chiraag, Vinod Vaikuntanathan, and Anantha Chandrakasan. "{GAZELLE}: A Low Latency Framework for Secure Neural Network Inference." 27th {USENIX} Security Symposium ({USENIX} Security 18). 2018.
Jiang, Xiaoqian, et al. "Secure outsourced matrix computation and application to neural networks." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2018.
Naehrig, Michael, Kristin Lauter, and Vinod Vaikuntanathan. "Can homomorphic encryption be practical?." Proceedings of the 3rd ACM workshop on Cloud computing security workshop. ACM, 2011.
Lu, Wen-jie, and Jun Sakuma. "Crypt-CNN (I): Secure Two-party Computation of Large-scale Matrix-vector Multiplication." (2017).
Lu, Wen-jie, and Jun Sakuma. "Crypt-CNN (II): Crytographically Evaluate Non-linear Convolutional Neural Network." (2017).
Liu, Jian, et al. "Oblivious neural network predictions via minionn transformations." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2017.
Mohassel, Payman, and Yupeng Zhang. "Secureml: A system for scalable privacy-preserving machine learning." 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 2017.
Riazi, M. Sadegh, et al. "Chameleon: A hybrid secure computation framework for machine learning applications." Proceedings of the 2018 on Asia Conference on Computer and Communications Security. ACM, 2018.
Rouhani, Bita Darvish, M. Sadegh Riazi, and Farinaz Koushanfar. "Deepsecure: Scalable provably-secure deep learning." Proceedings of the 55th Annual Design Automation Conference. ACM, 2018.
Yasuda, Masaya, et al. "Secure pattern matching using somewhat homomorphic encryption." Proceedings of the 2013 ACM workshop on Cloud computing security workshop. ACM, 2013.