Paillier暗号
..(2)
そこで前述の「暗号」の R を r に置き換えてできる暗号
C = ( 1 + N ) M r N mod N 2 {\displaystyle C=(1+N)^{M}r^{N}{\bmod {N}}^{2}\,}
を考え、これをPaillier暗号と呼ぶ。この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。また N の素因数 p, qを知っていれば、p, q から λ を計算し、
C λ = ( 1 + N ) M λ ( r N ) λ = ( 1 + N ) M λ mod N 2 {\displaystyle C^{\lambda }=(1+N)^{M\lambda }(r^{N})^{\lambda }=(1+N)^{M\lambda }{\bmod {N}}^{2}\,}
を求める事ができる。右辺に式 (1) を適用する事で Mλ が求まるので、Mλ を λ で割る事で平文 M が復号できる。
Paillier暗号の安全性は以下の仮定(DCR仮定)のもと成り立つ。
p, q を知らない場合、r mod N は ZN 上の一様乱数と区別がつかない。
実際 r mod N が一様乱数と区別がつかないのであれば、r mod N によってマスクされている暗号文 C = (1 + N)r mod N も一様乱数と区別がつかず、M に関するいかなる情報も知る事はできない。
上では 1 + N をベースにして方式を作ったが、1 + N の代わりに 1 + kN を使っても同様の方式を実現できる(k は N と互いに素な任意の定数)。この方式もPaillier暗号と呼ぶ。