Paillier暗号

Paillier暗号とは Pascal Paillier が1999年に提案した公開鍵暗号方式で、 の暗号文と の暗号文から の暗号文を計算出来る（加法準同型性）という性質を満たす。
RSA暗号やElGamal暗号など、 の暗号文と の暗号文から積 の暗号文を計算できる（乗法準同型性）方式は数多いが、加法準同型性を満たす方式はPaillier暗号などごく少数しか知られていない。
 次の冪乗剰余性を計算することは困難である（合成数剰余仮定）と信じられており、Paillier暗号の安全性はこの仮定に基づいている。
概要.
 を素数とし、 とする。
Paillier暗号は、次の性質が成り立つ事を利用している（証明は後述）。
上の式で、右辺から を引いて で割れば が求まる｡
そこで を乱数 でマスクしたデータ
を の暗号文とみなせば、2つの暗号文 の積は、
となり、 の暗号文と一致する。 ここで 。
すなわち、 の暗号文と の暗号文から の暗号文が求まった事になるので、加法準同型性が成り立つ。
しかし上の「暗号」は復号できないので、方式を改良する必要がある。ここで次の事実を使う（証明は後述）。
そこで前述の「暗号」の を に置き換えてできる暗号
を考え、これをPaillier暗号と呼ぶ。この暗号が加法準同型性を満たす事は前述と同様の方法で示せる。また の素因数 を知っていれば、 から を計算し、
を求める事ができる。右辺に式 (1) を適用する事で が求まるので、 を で割る事で平文 が復号できる。
Paillier暗号の安全性は以下の仮定（DCR仮定）のもと成り立つ。
実際 が一様乱数と区別がつかないのであれば、 によってマスクされている暗号文 も一様乱数と区別がつかず、 に関するいかなる情報も知る事はできない。
上では をベースにして方式を作ったが、 の代わりに を使っても同様の方式を実現できる（ は と互いに素な任意の定数）。この方式もPaillier暗号と呼ぶ。
formula_1の構造.
Paillier暗号は群 formula_1 を利用するので、群 formula_1 の構造を調べる。formula_1 の位数 は、
である。（オイラーのφ関数参照。） と は互いに素なので、formula_1 には位数 の部分群 と位数 の部分群 が存在し、formula_6 である（アーベル群の基本定理より）。
 とすると、 と互いに素な任意の に対し、
が成立する（カーマイケルの定理）。すなわち、群 formula_7 の各元の位数はそれぞれ である。
formula_8 が を満たしているとき、 を の 乗根という。またある formula_9 が存在して となっているとき、formula_10 は 乗剰余であるという。
次の定理が成立する:
定理1
 は の 乗根全体の集合である。一方 は 乗剰余全体の集合と一致し、 の各元の位数は の約数である。
証明
 の位数は なので、 の元を 乗すると になる。したがって の元はいずれも の 乗根である。また formula_6 で の位数は と互いに素なので、 以外の元を 乗しても にならない。したがって は の 乗根全体の集合と一致する。
 を の任意の元とする。カーマイケルの定理より なので、 の位数は の約数である。また は の元であり、しかも の位数は なので、 の位数は の約数でもある。よって の位数は と の公約数である。 と は互いに素であり、しかも は の約数なので、 と の最大公約数は である。以上の議論より の任意の元の位数は の約数である。
 を formula_1 の任意の元とするとき、formula_6 なので、ある の元 とある の元 が存在し、 となる。 の位数は なので、 となる。よって 乗剰余は必ず に属する。
次に を の任意の元とする。 と は互いに素なので、 が存在する。 の位数は の約数なので、。よって の任意の元 は 乗根 を持つ。すなわち の各元は 乗剰余である。以上の議論より は 乗剰余全体の集合と一致する。
の構造.
 を任意の整数とするとき、
が成立する。同様の議論で、
が成立する事もわかる。
この事実から、次の定理が分かる。
定理2
 は を生成元とする位数 の巡回群である。
証明
 の位数が であるのはすでに証明済みである。各 に対し、 なので、 は の 乗根である。しかも 個の元 はいずれも相異なる。 の元の個数は だったので、以上の議論より、} である。しかも なので、 は の生成元である。
各 に対し、 なので、 は の 乗根である。しかも 個の元 はいずれも相異なる。したがって である。しかも なので、 は の生成元である。
 の任意の元 はある を用いて と表現できる。そこで関数 を
により定義すると、 であり、 が乗法群 から加法群 への同型写像である事が分かる。
Paillier暗号.
アイディア.
 の任意の元 をひとつ固定し、 の暗号文を
で定義する。ここで は formula_1 から選ばれた乱数である。
 は 乗剰余であるので、 の元である。したがって の位数は の約数である。そこで復号の際には秘密の情報 を用い、 を計算すると、
となる。よって である。同様の議論により も示せるので、 により、平文 を計算できる。
方式.
暗号化.
 の元 を暗号化するには以下のようにする。
復号.
暗号文 formula_22 を復号するには とし、
を出力する。
備考.
 および は事前計算可能であるので、元論文 (PDF) に書かれているとおり、復号は法 の元で1回の冪乗演算である。
準同型性.
Paillier暗号の特筆すべき点はその準同型性である。暗号化関数は加法的準同型性を持つ。公開鍵 と乱数 を使って を暗号化した暗号文を と表記する。
また以下の性質を満たす：
しかし、2つの暗号文だけを与えられた場合に、秘密鍵無しで平文の積の暗号文を計算する方法は知られていない。
安全性.
ランダムに選んだ 乗剰余の分布が formula_1 上の一様分布と計算量的識別不能である、という仮定を合成数剰余判定仮定 (DCRA) という。厳密には以下のとおり。
合成数剰余判定仮定 (DCRA) のもとでは、暗号文 中にでてくる 乗剰余 は乱数と区別がつかない。よって から に関する情報を得る事はできず、Paillier暗号がIND-CPA安全である事が分かる。
Paillier暗号は加法準同型性を満たすので頑強性を持たず、従ってIND-CCA2安全ではないという欠点を持つ。しかし加法準同型性は電子投票や閾値暗号系のような暗号プロトコルを構築するのに有益である。ランダムオラクルモデルではPaillier暗号に藤崎岡本パディングを用いる事でIND-CCA2安全性を達成できるが、パディングを適用した方式は加法準同型性を満たさない。
応用.
電子マネーおよび電子投票の目標は、誰のものであるかを明かすことなく紙幣や票が正規のものであることを保障することにある。