Paillier暗号
Paillier暗号の特筆すべき点はその準同型性である。暗号化関数は加法的準同型性を持つ。公開鍵 pk と乱数 r を使って m を暗号化した暗号文を Epk(m; r) と表記する。
平文の加法準同型性
二つの暗号文の積は、それらの平文の和の暗号文になる E p k ( m 1 ; r 1 ) ⋅ E ( m 2 ; r 2 ) mod n 2 = E p k ( m 1 + m 2 ; r 1 r 2 ) mod n 2 . {\displaystyle E_{pk}(m_{1};r_{1})\cdot E(m_{2};r_{2})\mod n^{2}=E_{pk}(m_{1}+m_{2};r_{1}r_{2})\mod n^{2}.\,}
また以下の性質を満たす:
E p k ( m 1 ; r ) ⋅ g m 2 mod n 2 = E p k ( m 1 + m 2 ; r ) mod n 2 , {\displaystyle E_{pk}(m_{1};r)\cdot g^{m_{2}}\mod n^{2}=E_{pk}(m_{1}+m_{2};r)\mod n^{2},\,} E p k ( m , r ) k mod n 2 = E p k ( k m ; r k ) mod n 2 . {\displaystyle E_{pk}(m,r)^{k}\mod n^{2}=E_{pk}(km;r^{k})\mod n^{2}.\,}
しかし、2つの暗号文だけを与えられた場合に、秘密鍵無しで平文の積の暗号文を計算する方法は知られていない。
y , z ∈ Z n 2 ∗ {\displaystyle y,z\in \mathbb {Z} _{n^{2}}^{*}} が z = y mod n を満たしているとき、y を z の n 乗根という。またある y ∈ Z n 2 ∗ {\displaystyle y\in \mathbb {Z} _{n^{2}}^{*}} が存在して z = y mod n となっているとき、 z ∈ Z n 2 ∗ {\displaystyle z\in \mathbb {Z} _{n^{2}}^{*}} は n 乗剰余であるという。
次の定理が成立する:
定理1 G は 1 の n 乗根全体の集合である。一方 H は n 乗剰余全体の集合と一致し、H の各元の位数は λ の約数である。
証明 G の位数は n なので、G の元を n 乗すると 1 になる。したがって G の元はいずれも 1 の n 乗根である。また Z n 2 ∗ = G × H {\displaystyle \mathbb {Z} _{n^{2}}^{*}=G\times H} で H の位数は n と互いに素なので、G 以外の元を n 乗しても 1 にならない。したがって G は 1 の n 乗根全体の集合と一致する。
b を H の任意の元とする。カーマイケルの定理より b = 1 mod n なので、b の位数は nλ の約数である。