準同型暗号

準同型暗号（じゅんどうけいあんごう）（）は、準同型性を有するような暗号方式である。RSA暗号、ElGamal暗号など整数論をベースとした多くの公開鍵暗号は、この特徴を有しており、電子投票、電子マネーなどの暗号プロトコルにおいて利用される。
性質.
二つの暗号文 formula_1 が与えられた時に、平文や秘密鍵なしで 
formula_2 を計算できる。
ここで formula_3 は、加法 formula_4 や乗法 formula_5 のような二項演算子とする。直感的に言うと、もし formula_6 が加法に関して準同型性を有するものであれば、 formula_7 と formula_8 から formula_9 を計算できる。
加法、乗法の両方の演算が可能な完全準同型性暗号は長らく見つかっていなかったが、2009年にGentryらにより発表された。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまうため、通常利用には適していない。
準同型性を有する公開鍵暗号の例.
RSA暗号.
RSA暗号の公開鍵をformula_10、秘密鍵をformula_11とする。
ここでformula_12は合成数とする。
この暗号方式では、平文formula_13の暗号文は、それぞれ
formula_14となる。この二つの暗号文からformula_15の
暗号文を構成するためには、二つの暗号文の乗算をすればよい。これは、formula_16となることからも確かめられる。
ElGamal暗号.
位数が素数formula_17であるような群formula_18上のElGamal暗号を考える。公開鍵をformula_19、秘密鍵をformula_20とする。平文formula_21の暗号文は、formula_22、formula_23となる。
この二つの暗号文を掛け合わせれば、formula_24となり、formula_25の暗号文となる。
modified-ElGamal暗号.
ElGamal暗号に若干の修正を加えれば、加法に関して準同型性を有する公開鍵暗号を構成できる。上と同じように、位数が素数formula_17であるような群formula_27上のElGamal暗号を考える。公開鍵をformula_28、秘密鍵をformula_20とする。平文formula_30の暗号文は、formula_31、
formula_32となる。
この二つの暗号文を掛け合わせれば、formula_33となり、formula_34の暗号文となる。
Paillier暗号.
平文formula_35に対するPaillier暗号()の暗号文は、formula_36である。ここでformula_37、formula_38である。この公開鍵暗号は加法に関して、準同型性を有する。すなわち、formula_39の暗号文formula_40
からformula_34の暗号文を計算することは容易である。
すなわち、formula_42とできる。
modified-ElGamalとPaillier暗号のその他の有用な性質.
準同型の性質により、これらの暗号方式においては、formula_43とformula_44から
formula_45を計算できる。
例えば、Paillier暗号ならば、formula_43とformula_36
から、formula_48とすることにより、formula_49
の暗号文を得ることができる。
準同型暗号を利用したアプリケーション.
準同型性暗号には、その性質から数多くのアプリケーションがある。その代表的なものとしては、電子マネーや電子投票などがある。また、暗号プロトコルの設計において多く利用される紛失通信()プロトコルといったものもある。