Paillier暗号

Paillier暗号とは Pascal Paillier が1999年に提案した公開鍵暗号方式で、m₁ の暗号文と m₂ の暗号文から m₁ + m₂ の暗号文を計算出来る（加法準同型性）という性質を満たす。

RSA暗号やElGamal暗号など、m₁ の暗号文と m₂ の暗号文から積 m₁m₂ の暗号文を計算できる（乗法準同型性）方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。

N 次の冪乗剰余性を計算することは困難である（合成数剰余仮定）と信じられており、Paillier暗号の安全性はこの仮定に基づいている。

概要

p, q を素数とし、N = pq とする。

Paillier暗号は、次の性質が成り立つ事を利用している（証明は後述）。

$(1+N)^{M}=1+MN{\bmod {N}}^{2}\,$ 　…(1)

上の式で、右辺から 1 を引いて N で割れば M が求まる^[1]｡

そこで (1 + N)^M を乱数 R でマスクしたデータ

$C=(1+N)^{M}R{\bmod {N}}^{2}\,$

を M の暗号文とみなせば、2つの暗号文 C = (1 + N)^MR, C′ = (1 + N)^M′R′ の積は、

$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^N)^λ = 1 mod N² …(2)

そこで前述の「暗号」の R を r^N に置き換えてできる暗号

$C=(1+N)^{M}r^{N}{\bmod {N}}^{2}\,$

を考え、これをPaillier暗号と呼ぶ。この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。また N の素因数 p, qを知っていれば、p, q から λ を計算し、

$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^N mod N² は Z_N² 上の一様乱数と区別がつかない。

実際 r^N mod N² が一様乱数と区別がつかないのであれば、r^N mod N² によってマスクされている暗号文 C = (1 + N)^Mr^N mod N² も一様乱数と区別がつかず、M に関するいかなる情報も知る事はできない。

上では 1 + N をベースにして方式を作ったが、1 + N の代わりに 1 + kN を使っても同様の方式を実現できる（k は N と互いに素な任意の定数）。この方式もPaillier暗号と呼ぶ。

$\mathbb {Z} _{n^{2}}^{*}$ の構造

Paillier暗号は群 $\mathbb {Z} _{n^{2}}^{*}$ を利用するので、群 $\mathbb {Z} _{n^{2}}^{*}$ の構造を調べる。 $\mathbb {Z} _{n^{2}}^{*}$ の位数 φ(n²) は、

φ(n²) = n²(1 − 1/p)(1 − 1/q) = n(p − 1)(q − 1)

である。（オイラーのφ関数参照。）n と (p − 1)(q − 1) は互いに素なので、 $\mathbb {Z} _{n^{2}}^{*}$ には位数 n の部分群 G と位数 (p − 1)(q − 1) の部分群 H が存在し、 $\mathbb {Z} _{n^{2}}^{*}=G\times H$ である（アーベル群の基本定理より）。

λ = lcm(p − 1, q − 1) とすると、n と互いに素な任意の a に対し、

a^λ = 1 mod n,

a^nλ = 1 mod n²

が成立する（カーマイケルの定理）。すなわち、群 $\mathbb {Z} _{n}^{*},\,\mathbb {Z} _{n^{2}}^{*}$ の各元の位数はそれぞれ λ, nλ である。

$y,z\in \mathbb {Z} _{n^{2}}^{*}$ が z = yⁿ mod n² を満たしているとき、y を z の n 乗根という。またある $y\in \mathbb {Z} _{n^{2}}^{*}$ が存在して z = yⁿ mod n² となっているとき、 $z\in \mathbb {Z} _{n^{2}}^{*}$ は n 乗剰余であるという。

次の定理が成立する:

定理1 G は 1 の n 乗根全体の集合である。一方 H は n 乗剰余全体の集合と一致し、H の各元の位数は λ の約数である。

証明 G の位数は n なので、G の元を n 乗すると 1 になる。したがって G の元はいずれも 1 の n 乗根である。また $\mathbb {Z} _{n^{2}}^{*}=G\times H$ で H の位数は n と互いに素なので、G 以外の元を n 乗しても 1 にならない。したがって G は 1 の n 乗根全体の集合と一致する。

b を H の任意の元とする。カーマイケルの定理より b^nλ = 1 mod n² なので、b の位数は nλ の約数である。また 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 を $\mathbb {Z} _{n^{2}}^{*}$ の任意の元とするとき、 $\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^m)ⁿ = b^kλ = 1 mod n² (k ∈ R)。よって H の任意の元 b は n 乗根 b^m を持つ。すなわち H の各元は n 乗剰余である。以上の議論より H は n 乗剰余全体の集合と一致する。

G の構造

k を任意の整数とするとき、

(1+n)^{k}=1+kn+{\frac {k(k-1)}{2}}n^{2}+\cdots =1+kn+n^{2}\left({\frac {k(k-1)}{2}}+\cdots \right)=1+kn\mod n^{2}

が成立する。同様の議論で、

(1+ln)^{k}=1+kln\mod n^{2}

が成立する事もわかる。

この事実から、次の定理が分かる。

定理2 G は 1 + n を生成元とする位数 n の巡回群である。

証明 G の位数が n であるのはすでに証明済みである。各 k = 0, ..., n − 1 に対し、(1 + kn)ⁿ = 1 + kn² = 1 mod n² なので、1 + kn は 1 の n 乗根である。しかも n 個の元 1 + 0n, ..., 1 + (n − 1)n はいずれも相異なる。G の元の個数は n だったので、以上の議論より、G = {1 + kn | k = 0, ..., n − 1} である。しかも (1 + n)^k = (1 + kn) mod n² なので、1 + n は G の生成元である。

各 k = 0, ..., n − 1 に対し、(1 + kn)ⁿ = 1 + kn² = 1 mod n² なので、1 + kn は 1 の n 乗根である。しかも n 個の元 1 + 0n, ..., 1 + (n − 1)n はいずれも相異なる。したがって G = {1 + kn | k = 0, ..., n − 1} である。しかも (1 + n)^k = (1 + kn) mod n² なので、1 + n は G の生成元である。

G の任意の元 g はある k ∈ {0, ..., n − 1} を用いて g = 1 + kn mod n² と表現できる。そこで関数 L: G → Z_n を

L\colon u\mapsto (u-1)/n

により定義すると、L(g) = k であり、L が乗法群 G から加法群 Z_n への同型写像である事が分かる。

Paillier暗号

アイディア

G の任意の元 g = 1 + kn mod n² をひとつ固定し、m ∈ Z_n の暗号文を

c=g^{m}r^{n}{\bmod {n}}^{2}

で定義する。ここで r は $\mathbb {Z} _{n^{2}}^{*}$ から選ばれた乱数である。

rⁿ は n 乗剰余であるので、H の元である。したがって rⁿ の位数は λ の約数である。そこで復号の際には秘密の情報 λ を用い、c^λ を計算すると、

c^{\lambda }=(g^{m}r^{n})^{\lambda }=g^{\lambda m}=(1+kn)^{\lambda m}=1+k\lambda mn\mod n^{2}\,

となる。よって L(c^λ) = λkm である。同様の議論により L(g^λ) = λk も示せるので、L(c^λ)/L(m^λ) により、平文 m を計算できる。

方式

鍵生成

二つの大きな素数 p, q をランダムに選び、n = pq とする。
k ∈ Z_n を任意に選び、g = 1 + kn mod n² とする。
公開鍵 pk = (n, g) と秘密鍵 sk = (p, q) を出力する。

暗号化

Z_n の元 m を暗号化するには以下のようにする。

$\mathbb {Z} _{n^{2}}^{*}$ からランダムに r を選ぶ。
$c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ が暗号文である。

復号

暗号文 $c\in \mathbb {Z} _{n^{2}}^{*}$ を復号するには λ = lcm(p − 1, q − 1) とし、

$m=L(c^{\lambda }\mod n^{2})/L(g^{\lambda }\mod n^{2}){\bmod {n}}$

を出力する。

備考

λ = lcm(p − 1, q − 1) および L(g^λ mod n²) は事前計算可能であるので、元論文 (PDF) に書かれているとおり、復号は法 n² の元で1回の冪乗演算である。

準同型性

Paillier暗号の特筆すべき点はその準同型性である。暗号化関数は加法的準同型性を持つ。公開鍵 pk と乱数 r を使って m を暗号化した暗号文を E_pk(m; r) と表記する。

平文の加法準同型性

二つの暗号文の積は、それらの平文の和の暗号文になる

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_{pk}(m_{1};r)\cdot g^{m_{2}}\mod n^{2}=E_{pk}(m_{1}+m_{2};r)\mod n^{2},\,

E_{pk}(m,r)^{k}\mod n^{2}=E_{pk}(km;r^{k})\mod n^{2}.\,

しかし、2つの暗号文だけを与えられた場合に、秘密鍵無しで平文の積の暗号文を計算する方法は知られていない。

安全性

ランダムに選んだ n 乗剰余の分布が $\mathbb {Z} _{n^{2}}^{*}$ 上の一様分布と計算量的識別不能である、という仮定を合成数剰余判定仮定 (DCRA) という。厳密には以下のとおり。

合成数剰余判定仮定 (DCRA): 任意の多項式時間機械Aに対し; $|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^m ⋅ rⁿ mod n² 中にでてくる n 乗剰余 rⁿ mod n² は乱数と区別がつかない。よって c = g^m ⋅ rⁿ mod n² から m に関する情報を得る事はできず、Paillier暗号がIND-CPA安全である事が分かる。

Paillier暗号は加法準同型性を満たすので頑強性を持たず、従ってIND-CCA2安全ではないという欠点を持つ。しかし加法準同型性は電子投票や閾値暗号系のような暗号プロトコルを構築するのに有益である。ランダムオラクルモデルではPaillier暗号に藤崎岡本パディングを用いる事でIND-CCA2安全性を達成できるが、パディングを適用した方式は加法準同型性を満たさない。

応用

電子投票: 可展性が必要とされる状況もある。上記の準同型性は安全な電子投票に役立つ。; 単純な賛成・反対の投票を考えよう。m を投票者の数とし、1 で賛成の票を、0 で反対の票を表すものとする。各投票者は各々の票を暗号化する。集票者は、投票者から集めた暗号化された m 個の票をすべて掛けあわせた後、復号する。その結果の値を n とすると、これは票に対応する数の和になっている。よって、集票者は n 人が賛成票を入れ、m − n 人が反対票を入れたことが分かる。
電子マネー: 自己ブラインド性（論文で名付けられた）を持つ。これは、平文を変えることなくある暗号文を別の暗号文に作り替えることができることを指す。これは David Chaum によって提唱された電子マネー方式を構成する際に用いられる。

電子マネーおよび電子投票の目標は、誰のものであるかを明かすことなく紙幣や票が正規のものであることを保障することにある。

脚注

^ 通常離散対数問題は困難であるが、以上の事実は、底が 1 + N である場合には離散対数問題のインスタンス (1 + N)^M が容易に解ける事を意味している

参考文献

岡本–内山暗号はPaillier暗号に先立って加法的準同型性を達成している。
Damgaard-Jurik暗号はPaillier暗号の一般化である。
Paillier cryptosystem interactive simulatorでは電子投票のデモを行っている。
Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999, pp. 223–238.
Pascal Paillier, David Pointcheval, Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries, ASIACRYPT 1999.
Pascal Paillier, PhD Thesis, 1999.
Pascal Paillier, Composite-Residuosity Based Cryptography: An Overview, CryptoBytes Vol. 5 No. 1, 2002.

Paillier暗号