はじめに
みなさんこんにちは。
VIPPOOL でエンジニアをやっています、星月です。
世間ではゴールデンウィークでしたね。12 連休が推奨されたりして、
暇を持て余した私は、今まで読もうと思って放置していた論文を読んで過ごしました。
今回は、唐突ですが、休暇中に読んだ論文を紹介したいと思います。
英語の論文でしたが、２本、GSW の論文と TFHE の論文です。
どちらも完全準同型暗号を提案する論文です。
GSW は高校数学レベルの知識で理解できますが、TFHE の論文は非常に難解で、
Twitter で @nimdanaoto 様に何度も助けていただきました。
この場をお借りしてお礼申し上げます。
元論文（参考文献）の公開場所：
GSW: https://eprint.iacr.org/2013/340
TFHE: https://tfhe.github.io/tfhe/
準同型暗号とは
まずは GSW や TFHE が何を目指しているか、お話ししましょう。
英語の論文なので、数学用語の英単語も一緒に覚えていきましょう。
最初に用途から紹介します。
プライバシーに関わる情報や、個人情報のように、流出したら困るようなデータを、
クラウドやサーバで扱うと、業者のミスやセキュリティホールなどで
秘匿データが漏洩しそうで怖いですよね。そんな時、データを暗号化したまま
計算だけできれば、嬉しいですよね。
例えば、薬の開発をするときには化合物データベースを購入して参照します。
化合物データベースを持っている会社は、購入前に全データの開示はしたくないけれども、
ユーザが検索しようとしている化合物を、他のデータベース業者よりも数多く
取り揃えていることを示したい。という相反する要望を持っています。
一方で、ユーザ側は検索キーワードを知られると、今、着目している化合物が何なのか
流出してしまい、競合他社もそれに目を付ける可能性がありうる。
という形で、お互いに困ってしまっています。
そんな時、役に立つのが「秘匿演算技術」というもので、その手段の１つが「準同型暗号」です。
参考資料：産総研：秘密計算による化合物データベースの検索技術
だいたいこんなイメージです。
これができると嬉しい。それがモチベーションです。
いろいろな準同型暗号
さて、「準同型 (homomorphic)」という概念については、以前の記事
楕円曲線論おまけの一歩 - VIPPOOL開発者ブログ
で説明しました。
２つの群 (group) や体 (field) の架け橋となる写像があって、
演算と写像、どちらを先に行っても、つまり順番を入れ替えても同じ結果になる。
というもののことでした。
ここで、２つの群があって、片方は有限巡回群（これは一周期だけ見れば整数と準同型）で、
もう片方は暗号文。つまり暗号として機能するよう、簡単には逆変換できない群です。
この２つが、加法演算について準同型となっている場合、「加法準同型暗号」と呼びます。
つまり、２を暗号化した暗号文 と、３を暗号化した暗号文
があったとき、
暗号文同士、何らかの計算をして得た を復号すると
となる。これが加法準同型暗号です。
一方、乗法演算について同じことが言える場合は、「乗法準同型暗号」と呼びます。
これは としたとき、
ということです。
完全準同型暗号とは
さて、有限巡回群を整数に見立てて、加法や乗法のみを行う、
加法準同型暗号、乗法準同型暗号は、割と古くから知られていました。
有限巡回群は、足し算を繰り返すことで整数倍ができるので、「平文の」整数倍はできます。
同じく、乗算を繰り返せば、「平文の」べき乗計算もできます。
そういうものを「加群 (module)」と呼びます。
加法が定義された群「加法群 (additive group)」とは別なので要注意です。
でも、有限巡回群の加群が準同型暗号にできても、あまり用途は広がりません。
ここはやっぱり実数体！……とまではいかなくても、加法と乗法、
両方とも自由にできる準同型暗号が欲しいところです。
それこそが、我々の求める「完全準同型暗号 (fully homomorphic encryption, FHE)」なのです。
ちなみに、加法と乗法ができても体になるとは限りません。
が、乗法の逆元が計算できるとは限らない、体の出来損ないみたいなのを、環 (ring) と呼びます。
高校数学で習う行列などは、加法と乗法はできますが、逆行列（乗法の逆元）が
計算できない場合があるので、環です。
最低限、環が準同型暗号になれば、統計処理など、応用の幅が一気に広がります。
これが、GSW や TFHE の目指す完全準同型暗号です。
まとめ
今回は完全準同型暗号とは何か？というお話をしました。
次回は GSW の論文を解説していきます。
今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。