確率的暗号化

確率的暗号化は、暗号化アルゴリズムでランダム性を利用するもので、同じメッセージを複数回暗号化すると、通常は異なる暗号文が生成されます。「確率的暗号化」という用語は、通常、公開鍵暗号化アルゴリズムに関して使用されますが、さまざまな対称鍵暗号化アルゴリズムでも同様の特性が実現されています (例: CBCなどの連鎖モードで使用されるブロック暗号)。また、Freestyle ^[1]などのストリーム暗号は本質的にランダムです。意味的に安全であるためには、つまり平文に関する部分的な情報さえも隠すためには、暗号化アルゴリズムは確率的である必要があります。

最初の証明可能安全性の確率的公開鍵暗号化方式は、Shafi GoldwasserとSilvio Micaliによって提案されました。これは、 2 次残差問題の困難性に基づいており、メッセージ拡張係数は公開鍵のサイズに等しかったです。より効率的な確率的暗号化アルゴリズムには、Elgamal、Paillier 、および OAEP を含むランダム オラクル モデルに基づくさまざまな構成があります。

確率的暗号化は、公開鍵暗号化を使用する場合に特に重要です。攻撃者が暗号文を観察し、平文が「はい」または「いいえ」のいずれかであると疑ったり、平文が「カレーでの攻撃」であるかもしれないという予感を抱いたりするとします。決定論的暗号化アルゴリズムを使用すると、攻撃者は受信者の公開鍵で推測した各文を暗号化し、その結果をターゲットの暗号文と比較するだけで済みます。この攻撃に対抗するには、公開鍵暗号化方式にランダム性の要素を組み込んで、各平文が多数の可能性のある暗号文の 1 つにマッピングされるようにする必要があります。

決定論的暗号化方式を確率論的暗号化方式に変換する直感的なアプローチは、決定論的アルゴリズムで暗号化する前に、プレーンテキストにランダムな文字列を埋め込むという単純な方法です。逆に、復号化では決定論的アルゴリズムを適用し、ランダムな埋め込みを無視します。しかし、この単純なアプローチを適用した初期の方式は、一部の決定論的暗号化方式の制限により破られました。最適非対称暗号化パディング(OAEP) などの技術は、任意のトラップドア順列を使用して安全にランダムな埋め込みを統合します。

任意のトラップドア順列を使用した確率的暗号化の例:

• x - 1ビットの平文
• f -トラップドア順列（決定論的暗号化アルゴリズム）
• b - fのハードコア述語
• r - ランダムな文字列

${\displaystyle {\rm {Enc}}(x)=(f(r),x\oplus b(r))}$

${\displaystyle {\rm {Dec}}(y,z)=b(f^{-1}(y))\oplus z}$

これは、1 ビットのみが暗号化されるため非効率的です。つまり、メッセージ拡張係数は公開鍵のサイズに等しくなります。

ランダムオラクルモデルにおける確率的暗号化の例:

• x - プレーンテキスト
• f -トラップドア順列（決定論的暗号化アルゴリズム）
• h -ランダムオラクル（通常は公開されたハッシュ関数を使用して実装されます）
• r - ランダムな文字列

${\displaystyle {\rm {Enc}}(x)=(f(r),x\oplus h(r))}$

${\displaystyle {\rm {Dec}}(y,z)=h(f^{-1}(y))\oplus z}$

• 決定論的暗号化
• 効率的な確率的公開鍵暗号化方式
• 強力な秘密保持

• Shafi Goldwasser と Silvio Micali、「確率的暗号化」、Journal of Computer and Systems Sciences の特別号、第 28 巻、第 2 号、270 ～ 299 ページ、1984 年 4 月
• Freestyleは、オフラインでの総当たり攻撃や辞書攻撃に抵抗するためのChaChaのランダム化バージョンです[1]。