Paillier暗号

テンプレート:参照方法 Paillier暗号とは Pascal Paillier が1999年に提案した公開鍵暗号方式で、テンプレート:Math の暗号文と テンプレート:Math の暗号文から テンプレート:Math の暗号文を計算出来る（加法準同型性）という性質を満たす。

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

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

概要

テンプレート:Math を素数とし、テンプレート:Math とする。

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

上の式で、右辺から テンプレート:Math を引いて テンプレート:Mvar で割れば テンプレート:Mvar が求まる｡

そこで テンプレート:Math を乱数 テンプレート:Mvar でマスクしたデータ

を テンプレート:Mvar の暗号文とみなせば、2つの暗号文 テンプレート:Math の積は、

となり、テンプレート:Math の暗号文と一致する。 ここで テンプレート:Math。

すなわち、テンプレート:Mvar の暗号文と テンプレート:Math の暗号文から テンプレート:Math の暗号文が求まった事になるので、加法準同型性が成り立つ。

しかし上の「暗号」は復号できないので、方式を改良する必要がある。ここで次の事実を使う（証明は後述）。

そこで前述の「暗号」の テンプレート:Mvar を テンプレート:Mvar に置き換えてできる暗号

を考え、これをPaillier暗号と呼ぶ。この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。また テンプレート:Mvar の素因数 テンプレート:Mathを知っていれば、テンプレート:Math から テンプレート:Mvar を計算し、

を求める事ができる。右辺に式 (1) を適用する事で テンプレート:Mvar が求まるので、テンプレート:Mvar を テンプレート:Mvar で割る事で平文 テンプレート:Mvar が復号できる。

Paillier暗号の安全性は以下の仮定（DCR仮定）のもと成り立つ。

実際 テンプレート:Math が一様乱数と区別がつかないのであれば、テンプレート:Math によってマスクされている暗号文 テンプレート:Math も一様乱数と区別がつかず、テンプレート:Mvar に関するいかなる情報も知る事はできない。

上では テンプレート:Math をベースにして方式を作ったが、テンプレート:Math の代わりに テンプレート:Math を使っても同様の方式を実現できる（テンプレート:Mvar は テンプレート:Mvar と互いに素な任意の定数）。この方式もPaillier暗号と呼ぶ。

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

Paillier暗号は群 ${\mathbb{Z}}_{n^2}^{*}$ を利用するので、群 ${\mathbb{Z}}_{n^2}^{*}$ の構造を調べる。${\mathbb{Z}}_{n^2}^{*}$ の位数 テンプレート:Math は、

テンプレート:Math

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

テンプレート:Math とすると、テンプレート:Mvar と互いに素な任意の テンプレート:Mvar に対し、

テンプレート:Math

テンプレート:Math

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

$y,z\in {\mathbb{Z}}_{n^2}^{*}$ が テンプレート:Math を満たしているとき、テンプレート:Mvar を テンプレート:Mvar の テンプレート:Mvar 乗根という。またある $y\in {\mathbb{Z}}_{n^2}^{*}$ が存在して テンプレート:Math となっているとき、$z\in {\mathbb{Z}}_{n^2}^{*}$ は テンプレート:Mvar 乗剰余であるという。

次の定理が成立する:

定理1 テンプレート:Mvar は テンプレート:Math の テンプレート:Mvar 乗根全体の集合である。一方 テンプレート:Mvar は テンプレート:Mvar 乗剰余全体の集合と一致し、テンプレート:Mvar の各元の位数は テンプレート:Mvar の約数である。

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

テンプレート:Mvar を テンプレート:Mvar の任意の元とする。カーマイケルの定理より テンプレート:Math なので、テンプレート:Mvar の位数は テンプレート:Mvar の約数である。また テンプレート:Mvar は テンプレート:Mvar の元であり、しかも テンプレート:Mvar の位数は テンプレート:Math なので、テンプレート:Mvar の位数は テンプレート:Math の約数でもある。よって テンプレート:Mvar の位数は テンプレート:Mvar と テンプレート:Math の公約数である。テンプレート:Mvar と テンプレート:Math は互いに素であり、しかも テンプレート:Mvar は テンプレート:Math の約数なので、テンプレート:Mvar と テンプレート:Math の最大公約数は テンプレート:Mvar である。以上の議論より テンプレート:Mvar の任意の元の位数は テンプレート:Mvar の約数である。

テンプレート:Mvar を ${\mathbb{Z}}_{n^2}^{*}$ の任意の元とするとき、${\mathbb{Z}}_{n^2}^{*}=G\times H$ なので、ある テンプレート:Mvar の元 テンプレート:Mvar とある テンプレート:Mvar の元 テンプレート:Mvar が存在し、テンプレート:Math となる。テンプレート:Mvar の位数は テンプレート:Mvar なので、テンプレート:Math となる。よって テンプレート:Mvar 乗剰余は必ず テンプレート:Mvar に属する。

次に テンプレート:Mvar を テンプレート:Mvar の任意の元とする。テンプレート:Mvar と テンプレート:Mvar は互いに素なので、テンプレート:Math が存在する。テンプレート:Mvar の位数は テンプレート:Mvar の約数なので、テンプレート:Math。よって テンプレート:Mvar の任意の元 テンプレート:Mvar は テンプレート:Mvar 乗根 テンプレート:Mvar を持つ。すなわち テンプレート:Mvar の各元は テンプレート:Mvar 乗剰余である。以上の議論より テンプレート:Mvar は テンプレート:Mvar 乗剰余全体の集合と一致する。

テンプレート:Mvar の構造

テンプレート:Mvar を任意の整数とするとき、

$(1+n{)}^k=1+kn+\frac{k(k-1)}{2}{n}^2+\cdots =1+kn+n^2(\frac{k(k-1)}{2}+\cdots )=1+knmod{n}^2$

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

$(1+ln{)}^k=1+klnmod{n}^2$

が成立する事もわかる。

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

定理2 テンプレート:Mvar は テンプレート:Math を生成元とする位数 テンプレート:Mvar の巡回群である。

証明 テンプレート:Mvar の位数が テンプレート:Mvar であるのはすでに証明済みである。各 テンプレート:Math に対し、テンプレート:Math なので、テンプレート:Math は テンプレート:Math の テンプレート:Mvar 乗根である。しかも テンプレート:Mvar 個の元 テンプレート:Math はいずれも相異なる。テンプレート:Mvar の元の個数は テンプレート:Mvar だったので、以上の議論より、テンプレート:Math} である。しかも テンプレート:Math なので、テンプレート:Math は テンプレート:Mvar の生成元である。

各 テンプレート:Math に対し、テンプレート:Math なので、テンプレート:Math は テンプレート:Math の テンプレート:Mvar 乗根である。しかも テンプレート:Mvar 個の元 テンプレート:Math はいずれも相異なる。したがって テンプレート:Math である。しかも テンプレート:Math なので、テンプレート:Math は テンプレート:Mvar の生成元である。

テンプレート:Mvar の任意の元 テンプレート:Mvar はある テンプレート:Math を用いて テンプレート:Math と表現できる。そこで関数 テンプレート:Math を

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

により定義すると、テンプレート:Math であり、テンプレート:Mvar が乗法群 テンプレート:Mvar から加法群 テンプレート:Math への同型写像である事が分かる。

Paillier暗号

アイディア

テンプレート:Mvar の任意の元 テンプレート:Math をひとつ固定し、テンプレート:Math の暗号文を

$c=g^m{r}^n{modn}^2$

で定義する。ここで テンプレート:Mvar は ${\mathbb{Z}}_{n^2}^{*}$ から選ばれた乱数である。

テンプレート:Mvar は テンプレート:Mvar 乗剰余であるので、テンプレート:Mvar の元である。したがって テンプレート:Mvar の位数は テンプレート:Mvar の約数である。そこで復号の際には秘密の情報 テンプレート:Mvar を用い、テンプレート:Mvar を計算すると、

$c^{\lambda }=(g^m{r}^n{)}^{\lambda }=g^{\lambda m}=(1+kn{)}^{\lambda m}=1+k\lambda mnmod{n}^2$

となる。よって テンプレート:Math である。同様の議論により テンプレート:Math も示せるので、テンプレート:Math により、平文 テンプレート:Mvar を計算できる。

方式

鍵生成

1. 二つの大きな素数 テンプレート:Math をランダムに選び、テンプレート:Math とする。
2. テンプレート:Math を任意に選び、テンプレート:Math とする。
3. 公開鍵 テンプレート:Math と秘密鍵 テンプレート:Math を出力する。

暗号化

テンプレート:Math の元 テンプレート:Mvar を暗号化するには以下のようにする。

1. ${\mathbb{Z}}_{n^2}^{*}$ からランダムに テンプレート:Mvar を選ぶ。
2. $c=g^m\cdot r^n{modn}^2$ が暗号文である。

復号

暗号文 $c\in {\mathbb{Z}}_{n^2}^{*}$ を復号するには テンプレート:Math とし、

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

を出力する。

備考

テンプレート:Math および テンプレート:Math は事前計算可能であるので、元論文 (PDF) に書かれているとおり、復号は法 テンプレート:Math の元で1回の冪乗演算である。

準同型性

Paillier暗号の特筆すべき点はその準同型性である。暗号化関数は加法的準同型性を持つ。公開鍵 テンプレート:Mvar と乱数 テンプレート:Mvar を使って テンプレート:Mvar を暗号化した暗号文を テンプレート:Math と表記する。

• 平文の加法準同型性

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

$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つの暗号文だけを与えられた場合に、秘密鍵無しで平文の積の暗号文を計算する方法は知られていない。

安全性

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

合成数剰余判定仮定 (DCRA)

任意の多項式時間機械Aに対し

$|Pr[y\leftarrow {\mathbb{Z}}_{n^2}^{*},z\leftarrow y^n,b\leftarrow A(z,n):b=1]-Pr[z\leftarrow {\mathbb{Z}}_{n^2}^{*},b\leftarrow A(z,n):b=1]|$

は negligible である。

合成数剰余判定仮定 (DCRA) のもとでは、暗号文 テンプレート:Math 中にでてくる テンプレート:Mvar 乗剰余 テンプレート:Math は乱数と区別がつかない。よって テンプレート:Math から テンプレート:Mvar に関する情報を得る事はできず、Paillier暗号がIND-CPA安全である事が分かる。

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

応用

電子投票

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

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

電子マネー

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

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

参考文献

• 岡本–内山暗号は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.

関連項目

• 暗号理論
• 公開鍵暗号