準同型暗号

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

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

性質[編集]

二つの暗号文 が与えられた時に、平文秘密鍵なしで を計算できる。 ここで は、加法 乗法 のような二項演算子とする。直感的に言うと、もし が加法に関して準同型性を有するものであれば、 から を計算できる。 ただし、加法、乗法の両方の演算が可能な完全準同型性暗号は長らく見つかっていなかったが,2009年にGentryらにより発表された[1]。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまうため、通常利用には適していない。

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

RSA暗号[編集]

RSA暗号の公開鍵を、秘密鍵をとする。 ここでは合成数とする。 この暗号方式では、平文の暗号文は、それぞれ となる。この二つの暗号文からの 暗号文を構成するためには、二つの暗号文の乗算をすればよい。これは、となることからも確かめられる。

ElGamal暗号[編集]

位数が素数であるような群上のElGamal暗号を考える。公開鍵を、秘密鍵をとする。平文の暗号文は、となる。 この二つの暗号文を掛け合わせれば、となり、の暗号文となる。

modified-ElGamal暗号[編集]

ElGamal暗号に若干の修正を加えれば、加法に関して準同型性を有する公開鍵暗号を構成できる。上と同じように、位数が素数であるような群上のElGamal暗号を考える。公開鍵を、秘密鍵をとする。平文の暗号文は、となる。 この二つの暗号文を掛け合わせれば、となり、の暗号文となる。

Paillier暗号[編集]

平文に対するPaillier暗号(en:Paillier cryptosystem)の暗号文は、である。ここでである。この公開鍵暗号は加法に関して、準同型性を有する。すなわち、の暗号文 からの暗号文を計算することは容易である。 すなわち、とできる。

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

準同型の性質により、これらの暗号方式においては、から を計算できる。 例えば、Paillier暗号ならば、 から、とすることにより、 の暗号文を得ることができる。

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

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

  1. ^ https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf