加法準同型暗号をさらっと理解する

加法準同型暗号をさらっと理解していきます

1. そもそも加法準同型暗号とは？？

加法準同型暗号とは、暗号文のまま演算すると、平文を足し算してから暗号化したものと同じになる暗号です！

ここでの演算は何でもよいです。つまりは、暗号文のみで平文の足し算ができればいいのです。

暗号化したまんま足し算ができるので便利ってわけです。
※ちなみに掛け算が成り立つ乗法準同型暗号も存在します。詳しくは、準同型暗号をさらっと理解する。

暗号文のまま演算ができると、クライアントから送られたデータを安全に何らかの処理を施すことができます。秘匿化ブロックチェーンや機械学習、クラウドサービスなんかに応用されています。

加法準同型暗号は、乗法準同型暗号よりも複雑です。また、重大なデメリットがあります。加法準同型暗号の一つであるmodified-ElGamal暗号を使って、暗号文のまま足し算ができることを確認しましょう！

2. ElGamal暗号

いきなりmodified-ElGamal暗号は難しいので、元になったElGamal暗号について確認しましょう。modified-ElGamal暗号は、加法準同型暗号になるようにElGamal暗号を改良したものになります。
まずは、Elgamal暗号の定義を確認しましょう。

ElGamal暗号の暗号化

Elgamal暗号は、暗号化と復号で操作が変わります。まずは暗号化を確認します。

ElGamal暗号は公開鍵暗号方式の一つです。まずは、大きな素数pを決めます。すると原始元gと秘密鍵xを決めることができます。原始元は、pを法として(p-1)乗したときにはじめて1になる数のことを言います。
※pを大きくすればするほど、原始元gの候補は多くなります。

最後に、原始元gと秘密鍵x、おおきな素数pを利用してyをもとめます。
ここまでで、公開鍵と秘密鍵を作成しました。次にこの鍵を利用して暗号文C1、C2を作成します。※C1とC2はどっちも使います。

C1、C2をつくらなければならないので、暗号文は2つになります。同じ公開鍵暗号方式であるRSA暗号は一つの平文から1の暗号文なので、少しだけ効率が悪いのです。

ElGamal暗号の復号

次は、復号です

このように計算すると平文Pを得ることができます。

3. modified-ElGamal暗号

では、本題のmodified-ElGamal暗号に入ります。modified-ElGamal暗号も、ElGamal暗号と同じパラメータを利用します。鍵の決定は同じで、暗号化のみ異なります。

modified-ElGamal暗号の暗号化

ElGamal暗号と同じパラメータをしようして、以下の様に暗号化します

ElGamal暗号では平文はただ掛けるだけでしたが、modified-ElGamal暗号では、gをP乗するという形になります。

modified-ElGamal暗号の復号

ElGamal暗号の復号と同じように復号します。

さて、ここで一つ問題が発生します。同じように復号しても平文を得ることはできません。もしもpを法としてない場合は、logをとってやれば簡単に算出することができます。しかし、pを法としているので簡単に求めることはできません。これを離散対数問題といいます。
実は困ったことに、ElGamal暗号はこの離散対数問題があるから暗号として存在することができています。
では、少しElGamal暗号にもどりましょう。yは以下の様にして、定義したのでした。

このなかで、g,p,yは公開鍵です。つまり、悪意のある暗号解読者が知ることができる情報です。もしも、離散対数問題を効率よく解けるとします。すると秘密鍵xを得ることができます。そうすると簡単に暗号文を解読できてしまうのです。
ここで少し離散対数問題に向き合ってみます。

離散対数問題

離散対数問題とは、以下の状況でxを効率よく求めることができないことを言います。

離散対数問題を解くアルゴリズムとして知られているのは、列挙法とBaby-step Giant-step Algorithmがあります。

列挙法

列挙法はいたって単純です。式を満たすxを１から試していく方法になります。計算量はO(n)となります。

Baby-step Giant-step Algorithm

このアルゴリズムは、剰余の性質を利用して離散対数問題を少しだけ効率よく解くことのできるアルゴリズムです。計算量はO(√n log n)になります。
以下に簡単なアルゴリズムの説明を示します。
※難しいので、少しだけ効率よく解くことができるとわかれば大丈夫です！

雰囲気

このアルゴリズムはnを√nずつに分割して、√n回の2分探索を行うという感じです。
2分探索の計算量はO(log n)、それを√n回行うのでO(√n log n)となるわけです。

厳密な説明

まずは、以下の様な式変形を考えます。x = im + j として、

その上で、以下の操作を繰り返します。

まずは、①でリストを事前に計算します。2分探索をするためにソートも行います。その後、③で2分探索を行います。
jのことをBaby Step、iのことをGiant Stepと呼ぶので、Baby-step Giant-step Algorithmといいます。

離散対数問題で言いたかったこと

離散対数問題に触れてきました。結局、何が言いたかったというと離散対数問題は、指数が小さければそれほど問題ではないということです。つまり、秘密鍵は、離散対数問題の恩恵を十分に受け取るために、十分大きな数をとれば、さすがにO(√n log n)でも解くことは難しいです。反対に、modified-ElGamal暗号の平文は小さくしておくことで、O(√n log n)で十分早く求めることができます。

いくら小さくても離散対数問題はある程度の弊害になっているようです…

では、これから平文Ｐには以下の条件を追加しましょう

平文ＰはO(√n log n)でも十分早く求めることができる程度の大きさである。

O(n) は 10e7 ～ 10e8、O(log n)は10e9～10e12なので、
O(√n log n)は10e9～10e11くらいまでなら現実的でしょう

modified-ElGamal暗号が加法準同型暗号であること

ここまでお疲れさまでした。最後にmodified-ElGamal暗号が加法準同型暗号であることを確かめましょう！！

modified-ElGamal暗号の暗号文を２つ用意します。それぞれの暗号文の積をとってから復号したものは、平文の和になっています！以上より、暗号文を演算することで、平文の和が成立しました！

4.まとめ

加法準同型の例としてmodified-ElGalamal暗号を見てきました。ほかの加法準同型暗号も存在します。

今回は、加法準同型暗号を紹介しましたが、乗法が成り立つ乗法準同型暗号というものもあります。また、加法と乗法が成立する完全準同型暗号もあります。

これらの暗号文のまま演算ができる性質を利用することで、より安全に多くのデータを扱うことができます。これからは、こういった準同型暗号を利用した情報技術が発展していくことでしょう！