はじめに

完全準同型暗号は秘密計算の一種で、暗号化したまま加算と乗算ができるという特殊な性質を持っています。この性質を利用したセキュアなデータ活用を目指し、日々研究が行われています。

前回の「完全準同型暗号①（格子暗号とは？）」では完全準同型暗号の元になる格子暗号について解説しました。この「完全準同型暗号②（完全準同型暗号とは？）」では完全準同型暗号がどのような暗号なのか解説します。

準同型暗号の種類

完全準同型暗号は準同型暗号の内の一つです。準同型暗号とは暗号文を複合することなく計算できる公開鍵暗号のことで、できる計算の種類によって分類されます。一つ目は足し算ができる加法準同型暗号です。加法準同型暗号には代表的なものとしてPaillier暗号があります。2つ目は掛け算ができる乗法準同型暗号です。代表的な乗法準同型暗号としてRSA暗号などがあります。これら二つをまとめてPHE (Partial Homomorphic Encryption) と呼ぶこともあります。

三つ目が足し算と掛け算の両方ができるものです。これらの計算両方できる暗号をさらに計算の深さで三つに分類することができます。演算に制限があるものがふたつあり、回数が暗号方式に依存するものをSHE(Somewhat Homomorphyc Encryption)、パラメータに依存するものをLHE(Leveled Homomorphic Encryption)と呼びます。制限なく計算できるものを完全準同型暗号 (FHE : Fully Homomorphic Encryption) と呼びます。SHEの方が計算は速いですが、LHEの方が乗算の回数の制限は緩くなります。

前回記事で紹介したLWE暗号は準同型暗号のベースに使われます。LWE暗号はベクトルに微小な誤差（エラー）を足して暗号文を作っていました。暗号化状態のまま演算を行うとこの誤差がどんどん大きくなります。この誤差は一定の大きさを超えると復号できなくなってしまいます。特に加法に比べて乗法は誤差が大きくなるスピードが顕著になります。そのためSHEやLHEでは乗算に回数制限があります。

ブートストラッピングとは？

前述の通りFHEは足し算と掛け算を任意の回数行うことができます。しかし、演算を繰り返すと誤差が蓄積し正しく複合できなくなってしまいます。そのため任意の回数演算を行うためには誤差が大きくなりすぎないうちにリセットする必要があります。その方法がブートストラッピングです。

言い換えればブートストラッピングを使用するのがFHE、使用しないのがSHEやLHEです。

完全準同型暗号の安全性

準同型暗号は公開鍵暗号の一つですが、もちろん安全でなければ使うことはできません。公開鍵暗号での安全性はまず秘密鍵を得ようとする攻撃者を想定し、攻撃者の環境と安全性のレベルの二つの面から強度を考えます。

今回は2種類の攻撃者の環境（攻撃モデル）と安全性のレベル（解読モデル）の一部を紹介します。

攻撃モデル

攻撃モデルでは秘密鍵を求めたい「攻撃者」と攻撃者に問題（暗号文）を渡す「挑戦者」のゲームを考えます。攻撃の種類によって攻撃者の環境を変え、その環境下で攻撃者が秘密鍵を得ることができるのか考えます。これらの環境は一見現実では起こらないように思えますが、状況によって等価な環境になり得ると考えられているものです。

CPA：Chosen Plaintext Attack（選択平文攻撃）

攻撃者は任意の平文に対応する暗号文を取得できるとする。このとき攻撃者は挑戦者から与えられた暗号文から平文を求める攻撃。

CCA2 : Adaptive Chosen-ciphertext Attack（適応的選択暗号文攻撃）

攻撃者は任意の暗号文に対応する平文を取得できるとする。このとき攻撃者は挑戦者から与えられた暗号文（これに対応する平文は取得できない）から平文を求める攻撃。

CCA2では挑戦者から暗号文が与えられた後で平文を取得する暗号文を決めることができる。

この二つの攻撃を比べるとCPAよりCCA2安全を満たす方が安全性が高いと言えます。またCPAは公開鍵暗号が満たすべき最低限の安全基準とされています。これらの環境は理論上のみの理想的な環境に見えますが、状況によってはこれらと等価な攻撃が考えられてます。

解読モデル

解読モデルでも攻撃モデルと同様な攻撃者と挑戦者のゲームを考えますが、解読モデルでは攻撃の目標によって分類します。今回紹介するのは任意の暗号文から平文のいかなる情報も得られない、という秘匿性の度合いを指すものです。これを強秘匿性と呼びます。

強秘匿性には2種類の定義があり、

IND：Indistinguishability（識別不可能性）

攻撃者は平文を二つ選び、挑戦者はそのどちらか一方を暗号化して攻撃者に返す。このとき攻撃者がどちらを暗号化したか識別できないこと。

公開鍵暗号の安全性は多くの場合IND-CPAやIND-CCA2のように攻撃モデルと解読モデルを組み合わせて表現されます。一例としてIND-CCA2モデルを考えてみましょう。ここではINDなのでまずは攻撃者が平文を二つ選び、挑戦者は攻撃モデルと解読モデルはここで紹介した以外にも複数あるので気になる方は調べてみてください。

ここからはFHEの安全性に話を戻します。結論から言うとFHEはIND-CPA安全は満たします。つまり公開鍵暗号として必要な最低限の安全性は担保されます。しかしCPA安全以上に安全とされるIND-CCA2安全は満たしません。CCA2を満たさない理由を考えてみましょう。

まず攻撃者は二つの平文 $m_1, m_2$ を選択します。挑戦者はこの二つの平文のうちどちらの平文 $m$ を暗号化しその暗号文 $c$ を攻撃者に返します。攻撃者は暗号文から平文をもらう操作を繰り返せば $0$ を暗号化した暗号文を得ることができます。FHEは加法準同型性を持つので $7, 3, 4$ を暗号化した暗号文がわかれば $7-(3+4)=0$ のような形で作ることができます。また、攻撃者は $0$ の暗号文 $c’$ を用いて$c_a=c+c’$ となるような暗号文 $c_a$ を作ることができます。この暗号文 $c_a$ に対応する平文 $m_a$ は $m_a=m+0=m$ になり、攻撃者が $m$ が $m_1$ か $m_２$ のどちらなのか知ることができます。以上の理由からFHEはIND-CCA2安全を満たしません。ここでは加法準同型性を用いましたが乗法準同型性の面でも同様な議論ができます。乗法準同型暗号では 1 を暗号化した暗号文を得ることで同様にCCA安全を満たさないと考えることができます。

すべての準同型暗号は加法もしくは乗法を行うことができます。そのため、上記のどちらかの方法で平文を得ることができます。つまりFHE に限らず準同型暗号はIND-CCA2安全を満たしません。

完全準同型暗号の歴史

完全準同型暗号は第一世代〜第三世代に分類することができます。それぞれの世代ごとに特徴があり、その特徴を追うとどのように発展したのか知ることができます。

第一世代

現在のような”使えそうな”FHEは2009年にGnetryによって初めて提案されました。FHEの構想自体は1978年のRSA暗号に関する論文で記述されて以来、ElGamal暗号やPillier暗号など様々な論文の中で言及されていました。しかし演算の過程でノイズが蓄積し正しく複合ができないという問題があったため実用的ではないと考えられていました。Gentryはブートストラッピングを提案し準同型暗号が実現しました。

この提案以外にもDGHV方式が第一世代に分類されます。これらの最初期のFHEはイデアル格子という格子を用いて構成されます。

秘密計算として使用が見込めるという意味では大きな発見でした。この第一世代以降多くの研究者がこの分野に参入し、発展していきます。しかしこの暗号は安全性や計算効率の面で懸念点が多くあり、これらをそのまま応用することは難しいと考えられていました。

第二世代

第二世代で代表的なものはDGHV方式やBGV方式と呼ばれるものです。特に第二世代で初めて提案されたLHEは、事前に乗算の回数を決めておけばブートストラッピングをしなくても良いという非常に画期的なものでした。また、第二世代のFHEは第一世代の欠点も一部改善されました。安全性の観点では、第二世代以降のFHEはLWE仮定（十分に安全と考えられている標準仮定の一つ）の下で安全とされています。

一方で演算効率の面では解決できなかった問題も多くありました。

第三世代

第三世代ではGSW方式とTFHEの2種類が非常に有名です。いずれも第二世代で問題となった演算効率を改善しています。GSW方式はLHEに分類されるものです。この方式は第二世代で演算効率の悪さの原因となった鍵変換などを不要にすることで、演算効率を改善しました。TFHEは名前にもある通りブートストラッピングを必要とするFHEの一つです。TFHEはこのブートストラッピングの処理速度を大幅に改善しました。

今回は参考文献である「現代暗号の誕生と発展」（岡本龍明著）に倣って三つの世代に分類しました。資料によっては四世代に分けているものもあります。

今後の課題

実現すれば社会的に大きな価値を生み出すと考えられるFHEですが、まだ課題も多くあります。

最も大きな課題が処理速度の遅さです。暗号化状態での演算、ブートストラッピング共に重い計算であるため処理に時間がかかってしまいます。もう一つの課題は暗号文のサイズの大きさです。暗号化状態ではサイズが大きくなってしまうため、ビッグデータなどのデータマイニング等が難しくなってしまいます。これらの二つの課題を解決するために日々世界中で研究が行われています。また、暗号文数を削減するパッキングという手法を用いる場合が多くあります。パッキングは複数の多項式を中国剰余定理によって一つの多項式にする方法を暗号文応用したものです。パッキングを使うことで一つの暗号文（暗号文配列）に複数の平文を埋め込むことができます。これによってより少ない暗号文、演算回数が実現します。

まとめ

FHEは暗号化状態で足し算と掛け算を任意の回数できる性質を持つ
任意の回数の演算にはブートストラッピングが必要である
FHEはCPA安全だがIND-CCA2安全ではない
FHEには未だ課題が残っている

参考文献

“完全準同型暗号のデータマイニングへの利用に関する研究動向”, 佐藤宏樹, 馬屋原昂, 石巻優, 今林広樹, 山名早人, FIT2016(第 15 回情報科学技術フォーラム), pp165-172
岡本龍明, 「現代暗号の誕生と発展」
森山大輔, 西巻陵, 岡本隆明, 「公開暗号鍵の数理」, 共立出版, 2011
”完全準同型暗号による安全頻出パターンマイニング計算量効率化”, 佐藤宏樹, 馬屋原昂, 石巻優, 今林広樹, 山名早人, 情報処理学会論文誌データベース Vol.10 No.1 1–12 (Mar. 2017)