準同型暗号のソースを表示

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

==性質==
二つの暗号文 <math>{\rm Enc}(m_1), {\rm Enc}(m_2)</math> が与えられた時に、[[平文]]や[[鍵 (暗号)|秘密鍵]]なしで 
<math>{\rm Enc}(m_1\circ m_2)</math> を計算できる。
ここで <math>\circ</math> は、[[加法]] <math>+</math> や[[乗法]] <math>\times</math> のような二項[[演算 (数学)|演算子]]とする。直感的に言うと、もし <math>{\rm Enc}</math> が加法に関して準同型性を有するものであれば、 <math>{\rm Enc}(3)</math> と <math>{\rm Enc}(2)</math> から <math>{\rm Enc}(5)</math> を計算できる。
加法、乗法の両方の演算が可能な完全準同型性暗号は長らく見つかっていなかったが、2009年にGentryらにより発表された<ref>https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf</ref>。準同型性は暗号プロトコルを構成する上で非常に有用な性質ではあるが、暗号文のみから、平文の操作を可能としてしまうため、通常利用には適していない。

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

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

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

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
<references />

== 外部リンク ==
* 公開鍵暗号型の高機能暗号の研究動向: [https://www.imes.boj.or.jp/citecs/symp/18/ref3_seitou.pdf] 
* 量子コンピュータの脅威を考慮した高機能暗号：格子問題に基づく準同型暗号とその応用: [https://www.imes.boj.or.jp/research/papers/japanese/18-J-07.pdf]

{{DEFAULTSORT:しゆんとうけいあんこう}}
[[Category:暗号技術]]
[[Category:数学に関する記事]]