準同型暗号
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/08/02 13:17 UTC 版)
準同型暗号(じゅんどうけいあんごう)(英: Homomorphic Encryption, HE)は、準同型性を有するような暗号方式である。RSA暗号、ElGamal暗号など整数論をベースとした多くの公開鍵暗号は、この特徴を有しており、電子投票、電子マネーなどの暗号プロトコルにおいて利用される。
性質
二つの暗号文 が与えられた時に、平文や秘密鍵なしで を計算できる。 ここで は、加法 や乗法 のような二項演算子とする。直感的に言うと、もし が加法に関して準同型性を有するものであれば、 と から を計算できる。加法または乗法のいずれかの演算のみが可能な準同型暗号を部分準同型暗号と呼ぶ。 加法、乗法の両方の演算が可能な完全準同型性暗号は長らく見つかっていなかったが、2009年にGentryらにより発表された[1]。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまうため、通常利用には適していない。
部分準同型性を有する公開鍵暗号の例
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[2]
- Castagnos–Laguillaumie cryptosystem[3]
準同型暗号を利用したアプリケーション
準同型性暗号には、その性質から数多くのアプリケーションがある。その代表的なものとしては、電子マネーや電子投票などがある。また、暗号プロトコルの設計において多く利用される紛失通信(en:Oblivious transfer)プロトコルといったものもある。
脚注
- ^ https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf
- ^ Benhamouda, Fabrice; Herranz, Javier; Joye, Marc; Libert, Benoît (2017). “Efficient cryptosystems from 2k-th power residue symbols”. Journal of Cryptology 30 (2): 519–549. doi:10.1007/s00145-016-9229-5. hdl:2117/103661 .
- ^ Castagnos, Guilhem; Laguillaumie, Fabien (2015). “Linearly Homomorphic Encryption from DDH” (PDF). In Nyberg, Kaisa (ed.). Topics in Cryptology – CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, San Francisco, CA, USA, April 20–24, 2015. Proceedings. Lecture Notes in Computer Science. Vol. 9048. Springer. pp. 487–505. doi:10.1007/978-3-319-16715-2_26. ISBN 978-3-319-16714-5.
外部リンク
- 林卓也:「準同型暗号を用いた秘密計算とその応用」、システム/制御/情報、Vol.63, No.2, pp.64–70(2019)。
- 公開鍵暗号型の高機能暗号の研究動向: [1]
- 量子コンピュータの脅威を考慮した高機能暗号:格子問題に基づく準同型暗号とその応用: [2]
準同型暗号と同じ種類の言葉
Weblioに収録されているすべての辞書から準同型暗号を検索する場合は、下記のリンクをクリックしてください。

- 準同型暗号のページへのリンク