パイリエ暗号システム

Paillier暗号システムは、1999 年に Pascal Paillier によって発明され、その名が付けられた、公開鍵暗号用の確率的非対称アルゴリズムです。n番目の剰余類を計算する問題は、計算上困難であると考えられています。決定的複合剰余仮定は、この暗号システムが基づいている 難解性仮説です。

この方式は加法準同型暗号システムです。つまり、公開鍵とおよびの暗号化のみが与えられれば、 の暗号化を計算できます。 ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle m_{1}+m_{2}}$

このスキームは次のように機能します。

1. 2つの大きな素数とをランダムに、かつ互いに独立に選び、 を満たす。この性質は、両方の素数の長さが等しい場合に保証される。^[1]${\displaystyle p}$${\displaystyle q}$${\displaystyle \gcd(pq,(p-1)(q-1))=1}$
2. 計算します。lcmは最小公倍数を意味します。${\displaystyle n=pq}$${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$
3. ランダムな整数を選択${\displaystyle g}$${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. の位数が次のモジュラ乗法逆数の存在によって割り切れることを確認します。${\displaystyle n}$${\displaystyle g}$${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

ここで関数はとして定義されます。 ${\displaystyle L}$${\displaystyle L(x)={\frac {x-1}{n}}}$

この表記は、のモジュラー乗算と のモジュラー逆数を掛けたものを表すのではなく、をで割った商、つまり、関係 を満たす最大の整数値を表すことに注意してください。${\displaystyle {\frac {a}{b}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle v\geq 0}$${\displaystyle a\geq vb}$

• 公開（暗号化）鍵は です。${\displaystyle (n,g)}$
• 秘密鍵（復号鍵）は${\displaystyle (\lambda ,\mu ).}$

同等の長さのp、qを使用する場合、上記のキー生成手順のより単純な変形は、およびを設定することです。ここで、。^[1]実装の目的では、 より単純な変形が推奨されます。これは、一般的な形式では、十分に大きな素数p、qの場合、の計算時間が非常に長くなる可能性があるためです。 ${\displaystyle g=n+1,\lambda =\varphi (n),}$${\displaystyle \mu =\varphi (n)^{-1}{\bmod {n}}}$${\displaystyle \varphi (n)=(p-1)(q-1)}$${\displaystyle \mu}$

1. 暗号化されるメッセージがあるとする。${\displaystyle m}$${\displaystyle 0\leq m<n}$
2. およびとなる ランダムな値を選択します。(注: となる値が見つかった場合は、これを使用して秘密鍵を計算できます。これは無視できるほどありそうにありません。)${\displaystyle r}$${\displaystyle 0<r<n}$${\displaystyle \gcd(r,n)=1}$
   ${\displaystyle \gcd(r,n)\neq 1}$
3. 暗号文を次のように計算します。${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

1. を復号する暗号文とします。ここで${\displaystyle c}$${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. プレーンテキストメッセージを次のように計算します。${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

元の論文^[2]が指摘しているように、復号化は「本質的には を法とする1つの累乗法」です。 ${\displaystyle n^{2}}$

Paillier 暗号システムの注目すべき特徴は、非決定論的暗号化とともに準同型特性を備えていることです (使用方法については、アプリケーションの電子投票を参照してください)。暗号化関数は加法準同型であるため、次のアイデンティティを記述できます。

• 平文の準同型加算

2つの暗号文の積は、対応する平文の合計に復号化される。

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

暗号文と平文の積は、対応する平文の合計に復号化される。${\displaystyle g}$

${\displaystyle D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

• 平文の準同型乗算

暗号文を平文で累乗すると、2つの平文の積に復号化されます。

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},\,}$

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

より一般的には、定数kの乗じられた暗号文は、平文と定数の積に復号化される。

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

しかし、2 つのメッセージの Paillier 暗号化を考えると、秘密鍵を知らずにこれらのメッセージの積の暗号化を計算する方法は知られていません。

Paillier 暗号システムは、特定の離散対数が簡単に計算できるという 事実を利用します。

例えば二項定理により、

${\displaystyle (1+n)^{x}=\sum _{k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{higher powers of }}n}$

これは次のことを示しています:

${\displaystyle (1+n)^{x}\equiv 1+nx{\pmod {n^{2}}}}$

したがって、次の場合:

${\displaystyle y=(1+n)^{x}{\bmod {n}}^{2}}$

それから

${\displaystyle x\equiv {\frac {y-1}{n}}{\pmod {n}}}$。

したがって：

${\displaystyle L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}}$、

ここで関数は(整数除算の商) およびとして定義されます。${\displaystyle L}$${\displaystyle L(u)={\frac {u-1}{n}}}$${\displaystyle x\in \mathbb {Z} _{n}}$

上記に示した元の暗号システムは、選択平文攻撃 ( IND-CPA ) に対する意味的セキュリティを提供します。チャレンジ暗号文を正常に区別する能力は、本質的には複合残余を決定する能力に相当します。いわゆる決定的複合残余仮定(DCRA) は、扱いにくいと考えられています。

しかし、前述の準同型特性のため、システムは柔軟であり、したがって、最高レベルの意味的セキュリティ、適応型選択暗号文攻撃 ( IND-CCA2 ) に対する保護を享受できません。通常、暗号化では、柔軟という概念は「利点」とは見なされませんが、安全な電子投票やしきい値暗号システムなどの特定のアプリケーションでは、この特性が実際に必要になる場合があります。

しかし、Paillier と Pointcheval は、メッセージmとランダムr を組み合わせたハッシュを組み込んだ改良された暗号システムを提案しました。Cramer -Shoup 暗号システムと意図が似ていますが、ハッシュにより、cのみを与えられた攻撃者がm を意味のある方法で変更するのを防止します。この適応により、改良された方式は、ランダム オラクル モデルでIND-CCA2安全であることが示されます。

意味的セキュリティだけが考慮すべき事項ではありません。 柔軟性が望ましい状況もあります。 安全な電子投票システムでは、上記の準同型特性を利用できます。 単純な 2 値 (「賛成」または「反対」) 投票を考えてみましょう。m人の投票者が1 (賛成) または0 (反対)のいずれかに投票します。 各投票者は投票する前に選択を暗号化します。 選挙管理官は、暗号化されたm票の積を取り、その結果を復号化して値nを取得します。これはすべての投票の合計です。 選挙管理官は、n人が賛成に投票し、mn人が反対に投票したことがわかります。 ランダムrの役割により、2 つの同等の投票が同じ値に暗号化される可能性はごくわずかであるため、投票者のプライバシーが確保されます。

論文で言及されているもう 1 つの機能は、自己ブラインドの概念です。これは、暗号文を別の暗号文に変更しても、その復号化の内容は変更されないというものです。これは、もともとDavid Chaumが先頭に立っていた取り組みであるecashの開発に応用されています。オンラインで商品の支払いをするときに、販売者がクレジットカード番号、つまりあなたの身元を知る必要がないことを想像してみてください。電子マネーと電子投票の両方の目標は、電子コイン (電子投票も同様) が有効であることを保証すると同時に、現在関連付けられている人物の身元を明らかにしないことです。

Pailler暗号システムは、電子オークションのセキュリティを強化する上で重要な役割を果たしています。不正な競売人や、入札者と競売人の共謀による入札操作などの不正行為を防止します。オークション結果を公開しながら実際の入札値の機密性を確保することで、Pailler暗号システムは公正な慣行を促進することに成功しています。^[3]

Paillier暗号の準同型性は、しきい値ECDSA署名の構築に使用されることがあります。^[4]

• ナカシェ・シュテルン暗号システムと岡本・内山暗号システムは、パイリエ暗号システムの歴史的な先例です。
• Damgård –Jurik 暗号システムはPaillier 暗号の一般化です。

• 準同型暗号プロジェクトは、Paillier 暗号システムとその準同型演算を実装します。
• Encounter: Paillier 暗号システムの実装と、それに基づく暗号化カウンターの構築を提供するオープンソース ライブラリ。
• python-paillier は、浮動小数点数を完全にサポートする、Python の部分準同型暗号化ライブラリです。
• Paillier 暗号システム対話型シミュレーター (2012-02-18 にWayback Machineでアーカイブ) は、投票アプリケーションをデモンストレーションします。
• Paillier 暗号システムのインタラクティブなデモ。
• インタラクティブなデモを備えた Paillier 暗号システムの概念実証 Javascript 実装。
• 暗号化方式を使用した投票に関する GoogleTechTalk ビデオ。
• Paillier 準同型加算とゼロ知識証明プロトコルの Ruby 実装 (ドキュメント)