//
これは、セキュリティ・キャンプ全国大会2020【暗号ファジングトラック】暗号のままで計算しようゼミ
の応募課題に対して、自分で勉強したことをまとめ、発信するために書いた記事です。
//

#0. 自己紹介
SFC20のささしゅんです。
これは8/25に書いた記事なんですが、限定公開にする理由ももうないな、と思ったため、アドベントカレンダーに貼り付けて置きます。
まぁ、忙しくてアドベントカレンダー書く暇なかったのでこれを公開しておけばええやろ、って気持ちもありますが。
では、次から本題です。
#1.ElGamal暗号とは

準同型暗号を説明するにあたり、ElGamal暗号について説明しておいたほうが都合がよいため、まずはElGamal暗号から説明する。

#1.1鍵生成・暗号化・復号方法
ある公開された定数gとpと、ランダムな整数xを用いて、

y := g^x \quad mod p

を計算する。そして、$y$が公開鍵、$x$が秘密鍵となる。

平文$m$を先程生成された公開鍵$y$を用いて暗号化する方法は、

Enc(m):=(g^r,my^r)

とし、この$Enc(m)$が暗号化された文となる。

$Enc(m)$ を受け取った側が、秘密鍵$x$を用いて平文$m$に復号する方法は、

Dec(Enc(m)):=(\frac{my^r}{g^r})^x

を計算する。
すると、

 (\frac{my^r}{gr})^x = \frac{mg^{rx}}{g^{rx}} = m

となり、平文$m$に復号することができる。

#1.2補足

g, \quad p,\quad g^a \quad mod p, \quad g^b mod p

が与えられたときに


 g^{ab} \quad mod p

を求めるのを、DH問題といいます。
そして、DH問題が難しいという仮定をCDH仮定といいます。

ElGamal 暗号は CDH 仮定のもとで秘密鍵を知らない人は復号できないことが知られています。なお，暗号化するときに乱数 $r $を使っているので同じ $m $を暗号化しても $Enc(m)$ は毎回異なる暗号文を出力します。ですから ElGamal 暗号は確率的アルゴリズムです.

#1.3弱点
ElGamal暗号では、暗号文から平文を秘密鍵なしで推定するのは難しい、ということがわかっています(詳しくはElGamal暗号 DDH問題などで検索)。今回準同型暗号を説明するにあたりこれは解くに関係ないので詳しい説明は省きます。

しかし、暗号文から平文を推定するのが困難だとしても、攻撃者が暗号文を改変して受信者に送信したとしたらどうなるでしょうか。
例えば次のように改変したとします。

正しい元の文


Enc(m):=(c_1,c_2)

を、攻撃者が

Enc(m):=(c_1,2c_2)

と改変した場合、受信者が復号すると、


Dec(Enc(m)):=\frac{2my^r}{g^{rx}}=2m

と正しい平文の2倍になってしまいます。
これでは、攻撃者によって悪質な解読はされないものの、平文の改竄をされてしまう恐れがあります。
これがElGamal暗号の弱点です。(この弱点がない性質を頑強性とか非展性といいます。)

以上が、最低限準同型暗号を理解するにあたって必要なElGamal暗号の性質です。
#2準同型暗号
ElGamal暗号は秘密鍵や平文を知らなくても暗号文を何倍かできてしまうという弱点がありました。この弱点についてもう少し考察してみます。
#2.1準同型暗号の基本
2 個の平文 $m1$と $m2$ がありそれぞれ別の乱数 $r1$, $r2$ を選んで暗号化したとします。


Enc(m1) := (g^{r_1} , m_1y^{r_1} )\\

Enc(m2) := (g^{r_2} , m_2y^{r_2} )

暗号化されたものの要素をそれぞれ掛けると


(g^{r_1+r_2},m_1m_2y^{r_1+r_2})

となります.これは平文 $m1m2 $を乱数 $r1 + r2$ で暗号化したものとみなせます。これを $Enc(m1) Enc(m2)$ と書くことにすると

Enc(m1) Enc(m2) = Enc(m1m2)

が成立します。平文$ m1$, $m2$ を暗号化したまま 2 個の平文の積 $m1m2 $を得られたこの性質を乗法準同型暗号と言います。

さらに適当な整数 $h$ をとり$ m $の代わりに $h^m$を暗号化してみます.

Enc′(m) := Enc(h^m) = (g^r, h^my^r).

すると 2 個の平文 m1、 m2 に対しては


Enc′ (m1 ) Enc′ (m2 ) = Enc(h^{m_1} ) Enc(h^{m_2} ) \\
= Enc(h^{m_1}h^{m_2} ) \\
= Enc(h^{m_1+m_2} ) \\
= Enc′(m1 + m2)

が成立します。よって、

Enc′(m1) + Enc′(m2) = Enc′(m1 + m2)

が成り立つことがわかりました。
これを加法準同型暗号と呼びます。
加法準同型暗号と乗法準同型暗号が成り立つ暗号を完全準同型暗号と呼びます。

これから得られるとても重要な情報は、


\sum_{i}Enc(m_i) = Enc(\sum_{i}m_i)

が成り立つということです。
つまり、サーバーに平文ではなく暗号文を送ったとしても、その和などを暗号文のまま計算できるということです。

#2.2弱点と準同型暗号の種類
以下は有限体$p$上で考えます。
$s$を$n$次元ベクトル、誤差$e$をある確率にしたがって選ばれる$m$次元ベクトル、$A$を$n×m$次行列($m ≥ n$)とします。このとき
「$A$、$As+e$が与えられたときに $s$ を求めよ.」
という問題をLWE問題といいます。これは、$e=0$ならただの連立方程式を解くだけなのでそこまで複雑ではなく、計算処理によって求めることができます。
しかし、この条件だけでは変数6つに対して4つの連立方程式なので解を一意に求めることができません。
なので、仮にここで$e$が±1のどちらかと定めてあげると、それぞれの範囲が決まるためsを求めることができるようになります。(気になる方はやってみてください)

しかし、これは変数が多くなると考える範囲の組み合わせが大きくなるため量子コンピュータでさえも解くのが困難と言われています。
さらに、$p$、$n$、$m$ を適切にとるとLWE問題は格子上の短い長さのベクトルを求める問題に帰着されることが知られています。

そして、この応用として、RLWE問題というのがあります。RLWE問題とは
「
$ R_p := F_p[x]/(x^n +1) $ から $s $をランダムに選び，適当な回数だけ
$a_i ∈ R_p $をランダムに，$e_i ∈ R_p $をある確率にしたがって選ぶ誤差としたとき，
${ (a_i,a_is + e_i) }$
が $(R_p)2 $からランダムに選んだ $(a_i, b_i) $と区別が付けられるか
」

という問題です。これはパラメタを適切に取ると解くのが難しい、ということがわかっています。

これを利用して、加法HE、FEH、SHEと呼ばれる準同型暗号があります。(まだ仕組みについては理解できていない状態なので、すぐに理解して追記しようと思います。ここから先も仕組みを追えてない状態なので事実だけを並べます。)
そして、一般に準同型暗号は非常に処理が重たいです。処理が軽い準同型暗号(加法HEやSHE)は、乗算回数に制限があったりして、完全準同型暗号ではありません。乗算回数に制限がない完全準同型暗号のFHEはとても処理が重たいです。
以下がそれを表す表となっています。

[引用:クラウドを支えるこれからの暗号技術]

#2.3応用先についての考察
まず、参考文献に記載している本に書いてあるとおり、準同型暗号は
クラウドサービスとの相性がとてもいい
ことがわかります。暗号化されたデータの中身を知らないままで暗号化したまま足したり掛けたりできるため、秘匿検索技術などに応用されます。
また、サービス利用者は、サービスを利用するにあたって、サービスの管理者に少なくとも様々な情報が送られています。例えば身長や体重を送信したとしたら、自分のプライバシーを晒していることになります。このとき、サービス管理者には自分の身長や体重を知られることはないが、サービス利用者全体の身長や体重の平均を計算してもらうことができます。このように、個人のプライバシーを今まで以上に守ることができると考えています。
また、Googleの写真クラウドサービスを利用したいけど、この写真をGoogleに見られるのは嫌だ...というのもあるでしょう。しかし、Google側はユーザーが送ってくれた写真をどうしても画像認識の学習データに用いたいと思っています。
この両者の問題を解決してくれるのも準同型暗号です。準同型暗号は暗号化したまま演算ができるため。暗号化したまま画像認識の学習データに用いることができます。ユーザー側も写真が暗号化されているのでその写真を見られていないという安心に繋がります。
さらに、Kaggleなどの企業がビックデータを提供してくれて、それを利用してデータ分析をするコンペティションなどにも非常に有効であると考えられます。企業としてはビックデータを色んな人に解析して精度を向上させたいが、そもそもビックデータを提供するのは嫌だ、と思っているでしょう。しかし、加法準同型暗号でビックデータを暗号化したデータを公開して、それを利用して解析してもらうことにより、お互いのニーズを満たすことができます。

このようなのが準同型暗号の応用先と考えられます。

#3.0参考文献
クラウドを支えるこれからの暗号技術