利用者:Roget/試訳/Paillier暗号

04:38, 21 November 2008版より訳す.

Paillier暗号とはPascal Paillierが1999年に提案した公開鍵暗号方式である. (訳者:確率的は別に必要なさそう.) n次のべき乗剰余性を計算することは困難であると信じられている. これは合成数剰余仮定 (訳者:?) と呼ばれ, 暗号方式はこの仮定に基づいている.

The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. This is known as the Composite Residuosity (CR) assumption upon which this cryptosystem is based.

加法的準同型性を持つ. すなわち, 公開鍵と $m_{1}$ および $m_{2}$ の暗号文から, $m_{1}+m_{2}$ の暗号文を計算出来るということである.

The scheme is an additive homomorphic cryptosystem; this means that, given only the public-key and the encryption of $m_{1}$ and $m_{2}$ , one can compute the encryption of $m_{1}+m_{2}$ .

アルゴリズム

以下で定義される.

The scheme works as follows:

鍵生成

二つの大きな素数 p と q をランダムに選ぶ.
$n=pq$ および $\lambda =lcm(p-1,q-1)$ を計算する.
$\mathbb {Z} _{n^{2}}^{*}$ からランダムな数 g を選ぶ.
N が g の位数を割り切るかどうかをチェックする. 以下で逆元の存在を確かめればよい.
$\mu =(L(g^{\lambda }\mod n^{2}))^{-1}\mod n$

ここで関数 L は

L(u)={\frac {u-1}{n}}

と定義される.

公開鍵は $(n,g)$ である.
秘密鍵は $(\lambda ,\mu )$ である.

Choose two large prime numbers p and q randomly and independently of each other.
Compute $n=pq$ and $\lambda =lcm(p-1,q-1)$
Select random integer $g$ where $g\in \mathbb {Z} _{n^{2}}^{*}$
Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $\mu =(L(g^{\lambda }\mod n^{2}))^{-1}\mod n$

where function

L

is defined as

L(u)={\frac {u-1}{n}}

The public (encryption) key is $(n,g)$ .
The private (decryption) key is $(\lambda ,\mu ).$

暗号化

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

Let $m$ be a message to be encrypted where $m\in \mathbb {Z} _{n}$
Select random $r$ where $r\in \mathbb {Z} _{n}^{*}$
Compute ciphertext as: $c=g^{m}\cdot r^{n}\mod n^{2}$

復号

暗号文を $c\in \mathbb {Z} _{n^{2}}^{*}$ とする.
平文を以下で計算する. $m=L(c^{\lambda }\mod n^{2})\cdot \mu \mod n$

Ciphertext $c\in \mathbb {Z} _{n^{2}}^{*}$
Compute message: $m=L(c^{\lambda }\mod n^{2})\cdot \mu \mod n$

元論文に書かれているとおり, 復号は"法 $n^{2}$ の元で1回のべき乗演算"ですむ.

As the original paper points out, decryption is "essentially one exponentiation modulo $n^{2}$ ."

準同型性

Paillier暗号の特筆すべき点はその準同型性である. 暗号化関数は加法的準同型性を持つ.

A notable feature of the Paillier cryptosystem is its homomorphic properties. As the encryption function is additively homomorphic, the following identities can be described:

平文の加法的準同型性

二つの暗号文の積は, 対応する平文の和に復号される.

D(E(m_{1},r_{1})*E(m_{2},r_{2})\mod n^{2})=m_{1}+m_{2}\mod n.\,

m_{1}

の暗号文と,

g^{m_{2}}

の積は, 平文の和に復号される.

D(E(m_{1},r_{1})*g^{m_{2}}\mod n^{2})=m_{1}+m_{2}\mod n.\,

Homomorphic addition of plaintexts

The product of two ciphertexts will decrypt to the sum of their corresponding plaintexts,

D(E(m_{1},r_{1})*E(m_{2},r_{2})\mod n^{2})=m_{1}+m_{2}\mod n.\,

The product of a ciphertext with a plaintext raising g will decrypt to the sum of the corresponding plaintexts,

D(E(m_{1},r_{1})*g^{m_{2}}\mod n^{2})=m_{1}+m_{2}\mod n.\,

平文の乗法的準同型性

暗号文を別の平文乗したものは, 2つの平文の積に復号される.

D(E(m_{1},r_{1})^{m_{2}}\mod n^{2})=m_{1}m_{2}\mod n,\,

D(E(m_{2},r_{2})^{m_{1}}\mod n^{2})=m_{1}m_{2}\mod n.\,

一般に, 暗号文を定数k乗したものは, 平文と定数の積に復号される.

D(E(m_{1},r_{1})^{k}\mod n^{2})=km_{1}\mod n.\,

Homomorphic multiplication of plaintexts

An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts,

D(E(m_{1},r_{1})^{m_{2}}\mod n^{2})=m_{1}m_{2}\mod n,\,

D(E(m_{2},r_{2})^{m_{1}}\mod n^{2})=m_{1}m_{2}\mod n.\,

More generally, an encrypted plaintext raised to a constant k will decrypt to the product of the plaintext and the constant,

D(E(m_{1},r_{1})^{k}\mod n^{2})=km_{1}\mod n.\,

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

However, given the Paillier encryptions of two messages there is no known way to compute an encryption of the product of these messages without knowing the private key.

安全性

以上の暗号方式は適切な仮定のもとで選択平文攻撃に対して強秘匿性を持つ (IND-CPA安全). 暗号文を識別出来れば, n次べき乗剰余性を決定出来る. この決定性合成数剰余仮定 (?) (DCRA) は困難であると信じられている.

The original cryptosystem as shown above does provide semantic security against chosen-plaintext attacks (IND-CPA). The ability to successfully distinguish the challenge ciphertext essentially amounts to the ability to decide composite residuosity. The so-called decisional composite residuosity assumption (DCRA) is believed to be intractable.

その準同型性から, 頑強性を持たない. 従って, IND-CCA2安全ではない. 通常, 暗号の分野では頑強性を持たないことは「利点」とは呼べない. しかし, 安全な電子投票や閾値暗号系といった応用分野では, このような性質が実際用いられている.

Because of the aforementioned homomorphic properties however, the system is malleable, and therefore does not enjoy the highest echelon of semantic security that protects against adaptive chosen-ciphertext attacks (IND-CCA2). Usually in cryptography the notion of malleability is not seen as an "advantage," but under certain applications such as secure electronic voting and threshold cryptosystems, this property may indeed be necessary.

PaillierとPointchevalは平文mと乱数rを組み合わせたハッシュ値を用いてより安全性の高い暗号方式を提案している. (訳:パディングじゃいけないのだろうか?) Cramer-Shoup暗号と同様に, ハッシュ関数を通すことで, c だけを与えられた攻撃者は mを意味あるように変更することが出来ない (一般に分かりづらいので消すかも.). ランダムオラクルモデルで, この暗号方式はIND-CCA2安全である.

Paillier and Pointcheval however went on to propose an improved cryptosystem that incorporates the combined hashing of message m with random r. Similar in intent to the Cramer-Shoup cryptosystem, the hashing prevents an attacker, given only c, from being able to change m in a meaningful way. Through this adaptation the improved scheme can be shown to be IND-CCA2 secure in the random oracle model.

応用

電子投票

(...) 可展性が必要とされる状況もある。上記の準同型性は安全な電子投票に役立つ。単純な賛成・反対の投票を考えよう。mを投票者の数とし、1で賛成の票を、0で反対の票を表すものとする。各投票者は各々の票を暗号化する。集票者は、投票者から集めた暗号化されたm個の票をすべて掛けあわせた後、復号する。その結果の値をnとすると、これは票に対応する数の和になっている。よって、集票者はn人が賛成票を入れ、m-n人が反対票を入れたことが分かる。乱数rによって、2つの票が同じ値に暗号化されることは無視できる確率でしか起きないことを保証される。これにより、投票者のプライバシーは守られる。（訳者:？？？）

Semantic security is not the only consideration. There are situations under which malleability may be desirable. The above homomorphic properties can be utilized by secure electronic voting systems. Consider a simple binary ("for" or "against") vote. Let m voters cast a vote of either 1 (for) or 0 (against). Each voter encrypts their choice before casting their vote. The election official takes the product of the m encrypted votes and then decrypts the result and obtains the value n, which is the sum of all the votes. The election official then knows that n people voted for and m-n people voted against. The role of the random r ensures with negligible likelihood that two equivalent votes will ever encrypt to the same value, hence ensuring voter privacy.

電子現金

論文中に自己ブラインド性である(訳語をどうするか?)。これは、平文を変えることなくある暗号文を別の暗号文に作り替えることができることを指す。これは電子現金方式を構成する際に用いられる。David Chaumによって...

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

Another feature named in paper is the notion of self-blinding. This is the ability to change one ciphertext into another without changing the content of its decryption. This has application to the development of electronic cash, an effort originally spear-headed by David Chaum. Imagine paying for an item online without the vendor needing to know your credit card number, and hence your identity. The goal in both electronic cash and electronic voting, is to ensure the e-coin (likewise e-vote) is valid, while at the same time not disclosing the identity of the person with whom it's currently associated.

参考文献

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

アルゴリズム

鍵生成

暗号化

復号

準同型性

安全性

応用

See also

参考文献