Paillier暗号
また b は H の元であり、しかも H の位数は (p − 1)(q − 1) なので、b の位数は (p − 1)(q − 1) の約数でもある。よって b の位数は nλ と (p − 1)(q − 1) の公約数である。n と (p − 1)(q − 1) は互いに素であり、しかも λ は (p − 1)(q − 1) の約数なので、nλ と (p − 1)(q − 1) の最大公約数は λ である。以上の議論より H の任意の元の位数は λ の約数である。
y を Z n 2 ∗ {\displaystyle \mathbb {Z} _{n^{2}}^{*}} の任意の元とするとき、 Z n 2 ∗ = G × H {\displaystyle \mathbb {Z} _{n^{2}}^{*}=G\times H} なので、ある G の元 a とある H の元 b が存在し、y = ab となる。G の位数は n なので、y = (ab) = b ∈ H となる。よって n 乗剰余は必ず H に属する。
次に b を H の任意の元とする。λ と n は互いに素なので、m = n mod λ が存在する。b の位数は λ の約数なので、(b) = b = 1 mod n (k ∈ R)。よって H の任意の元 b は n 乗根 b を持つ。すなわち H の各元は n 乗剰余である。以上の議論より H は n 乗剰余全体の集合と一致する。
p, q を素数とし、N = pq とする。
Paillier暗号は、次の性質が成り立つ事を利用している(証明は後述)。
( 1 + N ) M = 1 + M N mod N 2 {\displaystyle (1+N)^{M}=1+MN{\bmod {N}}^{2}\,} ...(1)
上の式で、右辺から 1 を引いて N で割れば M が求まる。
そこで (1 + N) を乱数 R でマスクしたデータ
C = ( 1 + N ) M R mod N 2 {\displaystyle C=(1+N)^{M}R{\bmod {N}}^{2}\,}
を M の暗号文とみなせば、2つの暗号文 C = (1 + N)R, C′ = (1 + N)R′ の積は、
C C ′ = ( ( 1 + N ) M R ) ⋅ ( ( 1 + N ) M ′ R ′ ) = ( 1 + N ) M + M ′ R ′′ mod N 2 {\displaystyle CC'=\left((1+N)^{M}R\right)\cdot \left((1+N)^{M'}R'\right)=(1+N)^{M+M'}R''{\bmod {N}}^{2}\,}
となり、M + M′ の暗号文と一致する。 ここで R′′ = RR′。
すなわち、M の暗号文と M′ の暗号文から M + M′ の暗号文が求まった事になるので、加法準同型性が成り立つ。
しかし上の「暗号」は復号できないので、方式を改良する必要がある。ここで次の事実を使う(証明は後述)。
N の素因数 p, q から求まる λ が存在し、任意の r に対し、(r) = 1 mod N .
Paillier暗号とは Pascal Paillier が1999年に提案した公開鍵暗号方式で、m1 の暗号文と m2 の暗号文から m1 + m2 の暗号文を計算出来る(加法準同型性)という性質を満たす。
RSA暗号やElGamal暗号など、m1 の暗号文と m2 の暗号文から積 m1m2 の暗号文を計算できる(乗法準同型性)方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。
N 次の冪乗剰余性を計算することは困難である(合成数剰余仮定)と信じられており、Paillier暗号の安全性はこの仮定に基づいている。