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

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

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

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

暗号したまんま演算が可能なので便利ってわけですね。

暗号文のまま演算ができるようになると、クライアントから送られてきたデータに何かの処理を施すことができます。また、秘匿化ブロックチェーンなんかでもこの概念の応用が使われてます。

次は、有名な乗法準同型暗号であるRSA暗号と、ElGamal暗号を使って、暗号文のまま掛け算ができることを確認しましょう！

2. RSA暗号の場合

RSA暗号は乗法準同型暗号の1つです。まずは、RSA暗号の定義を確認します。

実際にRSA暗号文を掛け算してみます。

上にあるように2つの暗号文の積は、2つの平文の積を暗号化したものと等しくなっています。やったー！！

3. ElGamal暗号

ElGamal暗号も乗法準同型暗号の１つです。ElGamal暗号は、暗号化と複号で操作が変わるので2つに分けて簡単に確認していきます！

まずは暗号化から紹介します。

原始元というのは、pを法として、(p - 1)乗したときにはじめて1になる数のことを言います。例えば、3を法にした場合、2が原始元になります。※大きな素数pの場合、この原始元はたくさんあります。

この暗号化の際に1つの平文に対して2つの暗号文を作成します。

次に複号を紹介します。

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

では最後に、掛け算をしてみます。

2つの暗号文の組の積を複合したら、平文の積を得ることができました。やったー！

4. まとめ

乗法準同型暗号の例としてRSA暗号と、ElGamal暗号を見てきました。もっと他の乗法準同型暗号もあります。

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