Paillier暗号
任意の多項式時間機械Aに対し
| P r [ y ← Z n 2 ∗ , z ← y n , b ← A ( z , n ) : b = 1 ] − P r [ z ← Z n 2 ∗ , b ← A ( z , n ) : b = 1 ] | {\displaystyle |Pr[y\gets \mathbb {Z} _{n^{2}}^{*},z\gets y^{n},b\gets A(z,n):b=1]-Pr[z\gets \mathbb {Z} _{n^{2}}^{*},b\gets A(z,n):b=1]|}
は negligible である。
合成数剰余判定仮定 (DCRA) のもとでは、暗号文 c = g ⋅ r mod n 中にでてくる n 乗剰余 r mod n は乱数と区別がつかない。よって c = g ⋅ r mod n から m に関する情報を得る事はできず、Paillier暗号がIND-CPA安全である事が分かる。
Paillier暗号は加法準同型性を満たすので頑強性を持たず、従ってIND-CCA2安全ではないという欠点を持つ。しかし加法準同型性は電子投票や閾値暗号系のような暗号プロトコルを構築するのに有益である。ランダムオラクルモデルではPaillier暗号に藤崎岡本パディングを用いる事でIND-CCA2安全性を達成できるが、パディングを適用した方式は加法準同型性を満たさない。
自己ブラインド性(論文で名付けられた)を持つ。これは、平文を変えることなくある暗号文を別の暗号文に作り替えることができることを指す。これは David Chaum によって提唱された電子マネー方式を構成する際に用いられる。
電子マネーおよび電子投票の目標は、誰のものであるかを明かすことなく紙幣や票が正規のものであることを保障することにある。