完全準同型暗号の論文を読む - TFHE 編 (1)

はじめに

みなさんこんにちは。

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

前回は GSW の論文について解説しました。
次は TFHE の論文についてお話ししたいところですが、
こちらはとても難解なので、まずは先に、TFHE が発表される前の、
歴史のお話をしようかと思います。

TFHE 前夜の完全準同型暗号の研究界隈とその動向

TFHE 自体も、何度もバージョンアップを続けて改良され続けてきたものですが、
その原型となるものができる前のお話です。

まえがきでお話しした通り、加法のみが行える加法準同型暗号や、
乗法のみが行える乗法準同型暗号は、古くから知られていました。

加法準同型暗号だけでも、平文を乗算することはできたので、
平均値やフーリエ変換など、それなりの計算はできましたが、
やはり加法・乗法、両方やりたいということで、完全準同型暗号の
研究が進められてきました。

そして、格子暗号と呼ばれるものや、NTRU と呼ばれるもの、GSW で用いた LWE 暗号などを
ベースとした、加法・乗法の両方が可能な暗号技術が発表されていました。
この辺りは名前だけ出しましたが、特に中身については触れません。

ところが、GSW の説明でも解説した通り、どの手法も「平文に誤差が累積する」
という問題がありました。誤差が累積するにしても、その上限を押さえることが
できれば、演算回数に制限のある完全準同型暗号、Somewhat 準同型暗号として
利用価値はあるのですが、ディープラーニングのように演算段数のかさむものは、
どうしてもパラメータや鍵が大きくなりすぎて使い物にならない、という感じでした。

一方、それならば誤差を小さくする処理を加えればいいのではないか！という発想から、
bootstrapping と呼ばれる仕組みも考案されました。
加法や乗法により、平文に誤差が累積しますが、うまく処理することで、
その誤差を再度小さい状態の暗号文に戻そう、というわけです。

ところが、この bootstrapping にも問題がありまして、
bootstrapping を行うために用いるデータが 1GB くらいになったり、
処理に数分かかったり。これでは全く使い物になりません。

また、加法と乗法だけじゃまだ足りない、という話もありました。
そこで、0 と 1 のみを暗号化して、論理演算を実現することで、
加法・乗法に限らず、論理回路で実現可能なすべての演算を実現する試みもありました。

これが、TFHE 前夜の状況です。

まとめると
・加法・乗法が行える準同型暗号はいろいろ提案されていた
・しかし、誤差が累積する問題はどうしてもつきまとう
・Somewhat 準同型暗号で十分な場面もあるが、やはり不十分である
・bootstrapping はとてもリソースが必要で現実的ではない
・論理演算ベースにすると加法・乗法に限らずすべての演算ができて素敵
こんな感じの状況です。