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