準同型暗号

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

性質

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

準同型性を有する公開鍵暗号の例

RSA暗号

RSA暗号の公開鍵を $(e,n)$ 、秘密鍵を $(d,n)$ とする。ここで $n$ は合成数とする。この暗号方式では、平文 $m_{1},m_{2}\in \mathbb {Z} _{n}^{*}$ の暗号文は、それぞれ $m_{1}^{e}{\bmod {n}},m_{2}^{e}{\bmod {n}}$ となる。この二つの暗号文から $m_{1}\times m_{2}$ の暗号文を構成するためには、二つの暗号文の乗算をすればよい。これは、 $(m_{1}\times m_{2})^{e}{\bmod {n}}$ となることからも確かめられる。

ElGamal暗号

位数が素数 $q$ であるような群 $G=\langle g\rangle$ 上のElGamal暗号を考える。公開鍵を $(g,y=g^{x})$ 、秘密鍵を $x$ とする。平文 $m_{1},m_{2}\in G$ の暗号文は、 $(g^{r_{1}},y^{r_{1}}\cdot m_{1})$ 、 $(g^{r_{2}},y^{r_{2}}\cdot m_{2})$ となる。この二つの暗号文を掛け合わせれば、 $(g^{r_{1}+r_{2}},y^{r_{1}+r_{2}}\cdot (m_{1}m_{2}))$ となり、 $m_{1}m_{2}$ の暗号文となる。

modified-ElGamal暗号

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

Paillier暗号

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

modified-ElGamalとPaillier暗号のその他の有用な性質

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