FHEが気になる人が読むと良さげな資料

本記事は旧ブログから移行しました

完全準同型暗号（FHE）と言う暗号がある

Fully Homomorphic Encryption.

Craig Gentry氏が2009年に考案した、暗号化した文同士の加算・乗算相当演算を復号せずに処理できる画期的な暗号の提案になる。

この暗号を用いることで、プライバシーの配慮が必要なデータの保持者が手元で暗号化し、データの中身を見られることなく外部に計算作業を任せられ、暗号化された計算済みデータが返ってくれば、秘密鍵で復号してデータを得るといったユースケースが実現できる。 ただし、キーポイントである加算・乗算相当演算の部分で計算時間が大分掛かる。

完全準同型暗号との出会い

学士修士合わせて3年ほど研究対象として扱わねばならなかったので自分なりに学習することになった。

入門レベルの勉強資料が少なめであること、特に日本語での資料が限られていることが気になったので、完全準同型暗号への理解が深まりそうな日本語の文献の紹介をしていきたい。

資料紹介

  • Fully Homomorphic Encryption Using Ideal Lattices
    • 発案者のCraig Gentry氏の代表作。2020/06/09現在の引用数6508。10ページほどの論文になる。
  • A FULLY HOMOMORPHIC ENCRYPTION SCHEME
    • Craig Gentry氏のスタンフォード大博士論文。209ページの大作になるが、一つ一つ丁寧な章立てがあり、輪講しつつ理解を深めるのにちょうど良さそう。
  • 暗号文のままで計算しよう - 準同型暗号入門
    • よく見かける。研究で使用したプログラムの中にこのスライドの著者の先生のcommitも含まれていたので、きっとお世話になっている。
    • スライドはイメージを掴むのに良い。他の話題も少し混じっている印象を受ける。31ページ以降が本題。
    • 8ページのカップアンドボールの喩えはマジシャン的にはちょっと混乱しかねない。
  • イデアル格子暗号入門
    • 個人的にはこれを読んで欲しいが為にこの記事を書いている。特に準同型な暗号というイメージが付かないフェーズの時に是非読んで欲しい。Gentry氏論文タイトルの"Using Ideal Lattices"とあるように数学の概念をいくつか理解しないといけない部分があるが乗り越えたいところ。
    • これを読んでから完全準同型暗号の説明で出てくる多項式ベースのといった言葉や菱形の妙なマス目の絵の消化が少し良くなった気がした。
    • 著者の有田先生には個人的にも大変お世話になった先生である。先生も含む各暗号研究者達が執筆した「暗号理論と楕円曲線」をまだ読み切れていないものの、第1章から心踊る気配がしたのでいつかもう一度格闘したい。
  • 電子情報通信学会 Vol.99 No.12 (2016.12) - IEICE会誌 試し読みサイト
    • 電子情報通信学会の学会誌が完全準同型暗号をテーマにした特集を実施し、複数の研究者が寄稿したことがある。私は運良くたまたま雑誌形態で手に入れることになったが、これがなければもっとも重要で大変なBootstrapの作業の理解が出来なかったと思う。（もう今は忘れたけど…）
    • 現在試し読みサイトからの閲覧も可能なので、この機会に是非。
  • HElib
    • 完全準同型暗号の実装ライブラリのうち著者にもっとも近い実装がHElib。Gentry氏が所属するIBMのもの。（ちなみにさらにフォークしたshaih/HElibが自分がお世話になっていたやつだったような気がする…）
    • あまり自分は詳しくないが、最近は他にも様々な実装ライブラリが考案されている模様。
    • FHEを使ったコンテストを目にすることもあるので、意外とわいわいしているのかもしれない。なお私は参加しようかなと一瞬思いかけたが無理だと判断した。そんな人生がちょっぴり悲しいので、やっても良かったのかもしれない。
  • その他日本語論文・プレスリリース・プロジェクト
    • 日本語になった時点で数が少ないので、正直現時点では追いかけられる量な気がしている。

何だか眠くなってきたのでこの辺で。