準同型暗号

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

性質
二つの暗号文  が与えられた時に、平文や秘密鍵なしで 
 を計算できる。
ここで  は、加法  や乗法  のような二項演算子とする。直感的に言うと、もし  が加法に関して準同型性を有するものであれば、  と  から  を計算できる。加法または乗法のいずれかの演算のみが可能な準同型暗号を部分準同型暗号と呼ぶ。
加法、乗法の両方の演算が可能な完全準同型性暗号は長らく見つかっていなかったが、2009年にGentryらにより発表されたhttps://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまう(malleability(英語版)を有する)ため、定義からIND-CCA2(英語版)を満たさず、通常利用には適していない。

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

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

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

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

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

その他の部分準同型性を有する公開鍵暗号の例
:en:Okamoto–Uchiyama cryptosystem
:en:Naccache–Stern cryptosystem
:en:Damgård–Jurik cryptosystem
Sander–Young–Yung encryption scheme
Boneh–Goh–Nissim cryptosystem
Ishai–Paskin cryptosystem 
Joye-Libert cryptosystem
Castagnos–Laguillaumie cryptosystem

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

 脚注 

 外部リンク 
 林卓也：「準同型暗号を用いた秘密計算とその応用」、システム/制御/情報、Vol.63, No.2, pp.64–70（2019）。
 公開鍵暗号型の高機能暗号の研究動向:  
 量子コンピュータの脅威を考慮した高機能暗号：格子問題に基づく準同型暗号とその応用: 

Category:暗号技術
Category:数学に関する記事