パイリエ暗号システム

1999年にパスカル・パリエによって発明され、その名にちなんで名付けられたパリエ暗号は、公開鍵暗号のための確率的非対称アルゴリズムです。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安全であることが示される。

アプリケーション

電子投票

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

電子現金

論文で言及されているもう一つの特徴は、自己ブラインド化の概念です。これは、復号化の内容を変えることなく、ある暗号文を別の暗号文に変換する能力です。これは、 David Chaum氏が主導したecashの開発に応用されています。オンラインで商品を購入する際に、販売者があなたのクレジットカード番号、ひいてはあなたの個人情報を知る必要がないことを想像してみてください。電子現金と電子投票の両方において目指されているのは、電子コイン（同様に電子投票）の有効性を確保しつつ、同時にそれが現在関連付けられている人物の個人情報を漏洩しないことです。

電子オークション

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

閾値暗号システム

Paillier暗号の準同型性は、閾値ECDSA署名の構築に使われることがある。^{[ 4 ]}

参照

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

参考文献

• Paillier, Pascal (1999). 「複合次数残余クラスに基づく公開鍵暗号システム」(PDF) .暗号学の進歩 – EUROCRYPT '99. EUROCRYPT . Springer. doi : 10.1007/3-540-48910-X_16 .
• Paillier, Pascal; Pointcheval, David (1999). 「効率的な公開鍵暗号システムは能動的な敵対者に対して証明可能な安全性を持つ」. ASIACRYPT . Springer. pp.  165– 179. doi : 10.1007/978-3-540-48000-6_14 .
• パイリエ、パスカル (1999)。複合残留性に基づく暗号システム(博士論文)。エコール国立高等通信局。
• Paillier, Pascal (2002). 「複合残差に基づく暗号：概要」(PDF) . CryptoBytes . 5 (1). 2006年10月20日時点のオリジナル(PDF)からのアーカイブ。

注記

1. ジョナサン・カッツ、イェフダ・リンデル、「現代暗号入門：原理とプロトコル」、チャップマン＆ホール/CRC、2007年
2. Paillier, Pascal (1999). 「複合次数残余クラスに基づく公開鍵暗号システム」.暗号学の進歩 — EUROCRYPT '99 . コンピュータサイエンス講義ノート. 第1592巻. Springer. pp.  223– 238. doi : 10.1007/3-540-48910-X_16 . ISBN 978-3-540-65889-4。
3. Pan, M., Sun, J., & Fang, Y. (2011). 裏取引の排除：Paillier暗号システムを活用したセキュアスペクトラムオークション. IEEE Journal on Selected Areas in Communications, 29(4), 866–876. https://doi.org/10.1109/JSAC.2011.110417
4. Canetti, Ran; Gennaro, Rosario; Goldfeder, Steven; Makriyannis, Nikolaos; Peled, Udi (2020年10月30日). 「UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts」 . Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security . Association for Computing Machinery. pp.  1769– 1787. doi : 10.1145/3372297.3423367 . ISBN 9781450370899. S2CID  226228099 .

外部リンク

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