準同型暗号

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

Summarize Timeline Top Qs Fact Check

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

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

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

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

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

• 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]