準同型暗号
RSA暗号の公開鍵を ( e , n ) {\displaystyle (e,n)} 、秘密鍵を ( d , n ) {\displaystyle (d,n)} とする。 ここで n {\displaystyle n} は合成数とする。 この暗号方式では、平文 m 1 , m 2 ∈ Z n ∗ {\displaystyle m_{1},m_{2}\in \mathbb {Z} _{n}^{*}} の暗号文は、それぞれ m 1 e mod n , m 2 e mod n {\displaystyle m_{1}^{e}{\bmod {n}},m_{2}^{e}{\bmod {n}}} となる。この二つの暗号文から m 1 × m 2 {\displaystyle m_{1}\times m_{2}} の 暗号文を構成するためには、二つの暗号文の乗算をすればよい。これは、 ( m 1 × m 2 ) e mod n {\displaystyle (m_{1}\times m_{2})^{e}{\bmod {n}}} となることからも確かめられる。
準同型の性質により、これらの暗号方式においては、 k {\displaystyle k} と E n c ( m ) {\displaystyle {\rm {Enc}}(m)} から E n c ( k m ) {\displaystyle {\rm {Enc}}(km)} を計算できる。 例えば、Paillier暗号ならば、 k {\displaystyle k} と g m ⋅ r n mod n 2 {\displaystyle g^{m}\cdot r^{n}{\bmod {n^{2}}}} から、 ( g m ⋅ r n ) k = g k m ⋅ ( r k ) n {\displaystyle (g^{m}\cdot r^{n})^{k}=g^{km}\cdot (r^{k})^{n}} とすることにより、 k m {\displaystyle km} の暗号文を得ることができる。