準同型暗号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

準同型暗号(じゅんどうけいあんごう)は、準同型性を有するような暗号方式である。RSA暗号ElGamal暗号など整数論をベースとした多くの公開鍵暗号方式は、この特徴を有しており、電子選挙電子現金などの暗号プロトコルにおいて利用される。

性質[編集]

二つの暗号文 {\rm Enc}(m_1), {\rm Enc}(m_2) が与えられた時に、平文秘密鍵なしで {\rm Enc}(m_1\circ m_2) を計算できる。 ここで \circ は、加法 +乗法 \times のような二項演算子とする。直感的に言うと、もし {\rm Enc} が加法に関して準同型性を有するものであれば、 {\rm Enc}(3){\rm Enc}(2) から {\rm Enc}(5) を計算できる。 ただし、加法、乗法の両方の演算が可能な準同型性暗号はまだ知られていない。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまうため、通常利用には適していない。

準同型性を有する公開鍵暗号の例[編集]

RSA暗号[編集]

RSA暗号の公開鍵を(e, n)、秘密鍵を(d, n)とする。 ここでnは合成数とする。 この暗号方式では、平文m_1, m_2\in\mathbb{Z}_n^*の暗号文は、それぞれ m_1^e\bmod n, m_2^e\bmod nとなる。この二つの暗号文からm_1\times m_2の 暗号文を構成するためには、二つの暗号文の乗算をすればよい。これは、(m_1\times m_2)^e\bmod nとなることからも確かめられる。

ElGamal暗号[編集]

位数が素数qであるような群G = \langle g\rangle上のElGamal暗号を考える。公開鍵を(g, y = g^x)、秘密鍵をxとする。平文m_1, m_2\in Gの暗号文は、(g^{r_1}, y^{r_1}\cdot m_1)(g^{r_2}, y^{r_2}\cdot m_2)となる。 この二つの暗号文を掛け合わせれば、(g^{r_1+r_2}, y^{r_1+r_2}\cdot (m_1m_2))となり、m_1m_2の暗号文となる。

modified-ElGamal暗号[編集]

ElGamal暗号に若干の修正を加えれば、加法に関して準同型性を有する公開鍵暗号を構成できる。上と同じように、位数が素数qであるような群G = \langle g\rangle = <h>上のElGamal暗号を考える。公開鍵を(g, h, y = g^x)、秘密鍵をxとする。平文m_1, m_2\in \mathbb{Z}_q
の暗号文は、(g^{r_1}, y^{r_1}\cdot h^{m_1})(g^{r_2}, y^{r_2}\cdot h^{m_2})となる。 この二つの暗号文を掛け合わせれば、(g^{r_1+r_2}, y^{r_1+r_2}\cdot h^{m_1+m_2})となり、m_1+m_2の暗号文となる。

Paillier暗号[編集]

平文m\in\mathbb{Z}_nに対するPaillier暗号(en:Paillier cryptosystem)の暗号文は、g^m\cdot r^n \bmod {n^2}である。ここでg\in\mathbb{Z}_{n^2}^*r\in\mathbb{Z}_n^*である。この公開鍵暗号は加法に関して、準同型性を有する。すなわち、m_1, m_2の暗号文g^{m_1}\cdot {r_1}^n, g^{m_2}\cdot {r_2}^n \bmod {n^2} からm_1+m_2の暗号文を計算することは容易である。 すなわち、g^{m_1}\cdot {r_1}^n\times g^{m_2}\cdot {r_2}^n \bmod {n^2}
= g^{m_1+m_2}\cdot(r_1r_2)^n\bmod nとできる。

modified-ElGamalとPaillier暗号のその他の有用な性質[編集]

準同型の性質により、これらの暗号方式においては、k{\rm Enc}(m)から {\rm Enc}(km)を計算できる。 例えば、Paillier暗号ならば、kg^m\cdot r^n \bmod {n^2} から、(g^m\cdot r^n)^k = g^{km}\cdot (r^k)^nとすることにより、km の暗号文を得ることができる。

準同型暗号を利用したアプリケーション[編集]

準同型性暗号には、その性質から数多くのアプリケーションがある。その代表的なものとしては、電子現金電子選挙などがある。また、暗号プロトコルの設計において多く利用される紛失通信(en:Oblivious transfer)プロトコルといったものもある。