Paillier暗号

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

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

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

概要

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

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

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

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

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

$C=(1+N)^MR \bmod N^2\,$

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

$CC'=\left((1+N)^MR\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)^\lambda =1 \bmod N^2\,$ …(2)

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

$C=(1+N)^Mr^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 \bmod N^2\,$は$\mathbb{Z}_{N^2}$上の一様乱数と区別がつかない。

実際$r^N \bmod N^2\,$が一様乱数と区別がつかないのであれば、$r^N \bmod N^2\,$によってマスクされている暗号文$C=(1+N)^Mr^N \bmod N^2\,$も一様乱数と区別がつかず、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^n \mod n^2$を満たしているときyをzのn乗根という。またある$y\in\mathbb{Z}^{*}_{n^{2}}$が存在して$z=y^n \mod n^2$となっているとき、$z\in\mathbb{Z}^{*}_{n^{2}}$はn乗剰余であるという。

次の定理が成立する：

定理１ 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λ=1mod 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^n=(ab)^n=b^n\in H$。よってn乗剰余は必ずHに属する。

次にbをHの任意の元とする。λとnは互いに素なので、m=n^-1 mod λが存在する。bの位数はλの約数なので、(b^m)ⁿ=b^λの倍数=1 mod n²。よって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(\frac{k(k-1)}{2}+\cdots) = 1+kn \mod n^2$

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

$(1+ln)^k = 1+kln \mod n^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\in{0,\ldots,n-1}$を用いてg=1+kn mod n²と書ける。 そこで関数L:G→$\mathbb{Z}_{n}$を

$L : u \mapsto (u-1)/n$

により定義すると、L(g)=kであり、Lが乗法群Gから加法群$\mathbb{Z}_{n}$への同系写像である事が分かる。

Paillier暗号

アイデア

Gの任意の元g=1+kn mod n²をひとつ固定し、$m\in\mathbb{Z}_{n}$の暗号文を

$c=g^mr^n \mod\, n^2$

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

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

$c^{\lambda}=(g^mr^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を計算できる。　

方式

鍵生成

1. 二つの大きな素数 p,qをランダムに選び、n=pqとする。
2. $k\in\mathbb{Z}_{n}$を任意に選び、$g=1+kn \, mod \, n^2$とする。
3. 公開鍵$pk=(n,g)$と秘密鍵$sk=(p,q)$を出力する。

暗号化

$\mathbb{Z}_{n}$の元mを暗号化するには以下のようにする。

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

復号

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

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

を出力する。

備考

λ=lcm(p-1,q-1)および$L(g^{\lambda} \mod n^{2})$は事前計算しておく事ができるので、元論文に書かれているとおり, 復号は法$n^2$の元で1回のべき乗演算である.

準同型性

Paillier暗号の特筆すべき点はその準同型性である. 暗号化関数は加法的準同型性を持つ. 公開鍵pkと乱数ｒを使って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_1r_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 \cdot r^n \mod n^2$中にでてくるn乗剰余$r^n \mod n^2$は乱数と区別がつかない。よって$c=g^m \cdot r^n \mod n^2$からmに関する情報を得る事はできず、Paillier暗号がIND-CPA安全である事が分かる。

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

応用

電子投票

可展性が必要とされる状況もある。上記の準同型性は安全な電子投票に役立つ。

単純な賛成・反対の投票を考えよう。mを投票者の数とし、1で賛成の票を、0で反対の票を表すものとする。各投票者は各々の票を暗号化する。集票者は、投票者から集めた暗号化されたm個の票をすべて掛けあわせた後、復号する。その結果の値をnとすると、これは票に対応する数の和になっている。よって、集票者はn人が賛成票を入れ、m-n人が反対票を入れたことが分かる。

電子現金

自己ブラインド性 (論文で名付けられた) を持つ。これは、平文を変えることなくある暗号文を別の暗号文に作り替えることができることを指す。:これはDavid Chaumによって提唱された電子現金方式を構成する際に用いられる。

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

参考

• 岡本-内山暗号はPaillier暗号に先立って加法的準同型性を達成している.
• Damgaard-Jurik暗号はPaillier暗号の一般化である.
• Paillier cryptosystem interactive simulatorでは電子投票のデモを行っている.

参考文献

• Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999, pp223-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

関連項目

• 暗号理論
• 公開鍵暗号