完全準同型暗号の論文を読む - まえがき

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

世間ではゴールデンウィークでしたね。12 連休が推奨されたりして、
暇を持て余した私は、今まで読もうと思って放置していた論文を読んで過ごしました。

今回は、唐突ですが、休暇中に読んだ論文を紹介したいと思います。

英語の論文でしたが、２本、GSW の論文と TFHE の論文です。
どちらも完全準同型暗号を提案する論文です。
GSW は高校数学レベルの知識で理解できますが、TFHE の論文は非常に難解で、
Twitter で @nimdanaoto 様に何度も助けていただきました。
この場をお借りしてお礼申し上げます。

元論文（参考文献）の公開場所：
GSW: https://eprint.iacr.org/2013/340
TFHE: https://tfhe.github.io/tfhe/

準同型暗号とは

まずは GSW や TFHE が何を目指しているか、お話ししましょう。
英語の論文なので、数学用語の英単語も一緒に覚えていきましょう。

最初に用途から紹介します。

プライバシーに関わる情報や、個人情報のように、流出したら困るようなデータを、
クラウドやサーバで扱うと、業者のミスやセキュリティホールなどで
秘匿データが漏洩しそうで怖いですよね。そんな時、データを暗号化したまま
計算だけできれば、嬉しいですよね。

例えば、薬の開発をするときには化合物データベースを購入して参照します。
化合物データベースを持っている会社は、購入前に全データの開示はしたくないけれども、
ユーザが検索しようとしている化合物を、他のデータベース業者よりも数多く
取り揃えていることを示したい。という相反する要望を持っています。
一方で、ユーザ側は検索キーワードを知られると、今、着目している化合物が何なのか
流出してしまい、競合他社もそれに目を付ける可能性がありうる。
という形で、お互いに困ってしまっています。
そんな時、役に立つのが「秘匿演算技術」というもので、その手段の１つが「準同型暗号」です。
参考資料：産総研：秘密計算による化合物データベースの検索技術

f:id:y-hoshizuki:20200513214655p:plain

だいたいこんなイメージです。
これができると嬉しい。それがモチベーションです。

いろいろな準同型暗号

さて、「準同型 (homomorphic)」という概念については、以前の記事
楕円曲線論おまけの一歩 - VIPPOOL開発者ブログ
で説明しました。

２つの群 (group) や体 (field) の架け橋となる写像があって、
演算と写像、どちらを先に行っても、つまり順番を入れ替えても同じ結果になる。
というもののことでした。

ここで、２つの群があって、片方は有限巡回群（これは一周期だけ見れば整数と準同型）で、
もう片方は暗号文。つまり暗号として機能するよう、簡単には逆変換できない群です。
この２つが、加法演算について準同型となっている場合、「加法準同型暗号」と呼びます。

つまり、２を暗号化した暗号文 $c_2$ と、３を暗号化した暗号文 $c_3$ があったとき、
暗号文同士、何らかの計算をして得た $c=f(c_2,c_3)$ を復号すると
${\rm decode}(c) = 5 = 2 + 3$ となる。これが加法準同型暗号です。

f:id:y-hoshizuki:20200513214722p:plain

一方、乗法演算について同じことが言える場合は、「乗法準同型暗号」と呼びます。
これは $c=f(c_2,c_3)$ としたとき、 ${\rm decode}(c) = 6 = 2 \times 3$ ということです。

完全準同型暗号とは

さて、有限巡回群を整数に見立てて、加法や乗法のみを行う、
加法準同型暗号、乗法準同型暗号は、割と古くから知られていました。

有限巡回群は、足し算を繰り返すことで整数倍ができるので、「平文の」整数倍はできます。
同じく、乗算を繰り返せば、「平文の」べき乗計算もできます。
そういうものを「加群 (module)」と呼びます。
加法が定義された群「加法群 (additive group)」とは別なので要注意です。

でも、有限巡回群の加群が準同型暗号にできても、あまり用途は広がりません。
ここはやっぱり実数体！……とまではいかなくても、加法と乗法、
両方とも自由にできる準同型暗号が欲しいところです。
それこそが、我々の求める「完全準同型暗号 (fully homomorphic encryption, FHE)」なのです。

ちなみに、加法と乗法ができても体になるとは限りません。
が、乗法の逆元が計算できるとは限らない、体の出来損ないみたいなのを、環 (ring) と呼びます。
高校数学で習う行列などは、加法と乗法はできますが、逆行列（乗法の逆元）が
計算できない場合があるので、環です。

最低限、環が準同型暗号になれば、統計処理など、応用の幅が一気に広がります。
これが、GSW や TFHE の目指す完全準同型暗号です。

まとめ

今回は完全準同型暗号とは何か？というお話をしました。
次回は GSW の論文を解説していきます。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。