暗号文の判別不能性

暗号文の区別不能性は、多くの暗号化方式の特性です。直感的には、暗号システムが区別不能性の特性を備えている場合、攻撃者は暗号化したメッセージに基づいて暗号文のペアを区別することはできません。選択平文攻撃下での区別不能性の特性は、証明可能に安全な 公開鍵暗号システムのほとんどにとって基本的な要件であると考えられていますが、一部の方式では、選択暗号文攻撃下および適応型選択暗号文攻撃下での区別不能性も提供されています。選択平文攻撃下での区別不能性は、意味的安全性の特性と同等であり、多くの暗号証明ではこれらの定義を互換的に使用します。

暗号システムは、敵対者が決定した 2 要素のメッセージ空間からランダムに選択されたメッセージの暗号化を与えられた場合、ランダムに推測するよりも大幅に高い確率 ( 1 ⁄ 2 )でメッセージの選択を識別できない敵対者がいない場合に、区別不能性に関して安全であると見なされます。敵対者が1 ⁄ 2よりも大幅に高い確率で選択された暗号文を区別できる場合、この敵対者は暗号文を区別する上で「有利」であると見なされ、その方式は区別不能性に関して安全であるとは見なされません。この定義には、安全な方式では、敵対者は暗号文を見ても情報を得ないという考えが含まれています。したがって、敵対者はランダムに推測した場合よりも優れた結果を得ることはできません。

識別不能性に関するセキュリティには、攻撃者の能力に関する仮定に応じて多くの定義があります。これは通常、ゲームとして表現され、ランダムに推測しなければならない攻撃者よりも大幅に高い確率でゲームに勝つことができる攻撃者がいない場合、暗号システムは安全であると見なされます。暗号化で使用される最も一般的な定義は、選択平文攻撃下での識別不能性(IND-CPA と略記)、(非適応型)選択暗号文攻撃下での識別不能性(IND-CCA1)、および適応型選択暗号文攻撃下での識別不能性(IND-CCA2) です。後者のいずれかの定義によるセキュリティは、前の定義によるセキュリティを意味します。つまり、IND-CCA1 で安全な方式は IND-CPA でも安全であり、IND-CCA2 で安全な方式は IND-CCA1 と IND-CPA の両方で安全です。したがって、IND-CCA2 は 3 つのセキュリティの定義の中で最も強力です。

確率的非対称鍵暗号化アルゴリズムの場合、選択平文攻撃下における区別不可能性(IND-CPA) は、攻撃者と挑戦者の間の次のゲームによって定義されます。計算セキュリティに基づくスキームの場合、攻撃者は確率的多項式時間 チューリングマシンによってモデル化されます。つまり、攻撃者は多項式数の時間ステップ内でゲームを完了し、推測を出力する必要があります。この定義では、 E ( PK、M )は、キーPKによるメッセージMの暗号化を表します。

1. 挑戦者は、何らかのセキュリティパラメータk (例: ビット単位のキーサイズ) に基づいてキーペアPK、SK を生成し、PK を攻撃者に公開します。挑戦者はSKを保持します。
2. 攻撃者は、多項式的に制限された数の暗号化またはその他の操作を実行する可能性があります。
3. 最終的に、攻撃者は2つの異なる選択された平文M ₀、M _{1 を}挑戦者に提出します。
4. 挑戦者はビットb∈ {0,1}を_一様にランダムに選択し、チャレンジ暗号文C = E ( PK , Mb )を攻撃者に送り返します。
5. 攻撃者は追加の計算や暗号化を自由に実行できます。
6. 最後に、敵対者はbの値の推測値を出力します。

暗号システムは、確率的多項式時間の攻撃者がランダムな推測に対して無視できるほどの「優位性」しか持たない場合、選択平文攻撃に対して区別がつきません。攻撃者が無視できるほどの「優位性」を持つと言われるのは、確率 で上記のゲームに勝つ場合です。ここで、 はセキュリティ パラメータ 内の無視できる関数であり、つまり、すべての (非ゼロの) 多項式関数poly()に対して、すべての に対してとなる が存在します。 ${\displaystyle \left({\tfrac {1}{2}}\right)\,+\,\epsilon (k)}$${\displaystyle \epsilon (k)}$${\displaystyle k}$${\displaystyle k_{0}}$${\displaystyle |\epsilon (k)|\;<\;\left|{\tfrac {1}{\mathrm {poly(k)} }}\right|}$${\displaystyle k\;>\;k_{0}}$

攻撃者はM ₀、M ₁、PKを知っていますが、 Eの確率的な性質により、 M _bの暗号化は多くの有効な暗号文のうちの 1 つに過ぎず、したがってM ₀、M ₁を暗号化し、結果の暗号文をチャレンジ暗号文と比較しても、攻撃者に無視できない利点はもたらされません。

上記の定義は非対称鍵暗号システムに特有のものですが、公開鍵暗号化機能を、秘密の暗号化鍵を保持し、敵対者の要求に応じて任意の平文を暗号化する暗号化オラクルに置き換えることで、対称鍵暗号システムにも適応できます。

選択平文攻撃を実行する敵対的プロセスは、通常、暗号ゲームの形式で概説されます。対称 IND-CPA をテストするために、上記のゲームが定義されます。^[1]をキー生成関数、を暗号化関数、を復号化関数とします。を対称暗号化方式とします。ゲームGuess は次のように定義されます。 ${\displaystyle {\mathcal {K}}}$${\displaystyle {\mathcal {E}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}$

攻撃者は好きなだけ、自分で選んだ平文メッセージを 2 つ選択し、LR オラクルに渡す。LRオラクルは、メッセージの 1 つを暗号化した暗号文を返す。攻撃者の優位性は、ゲーム開始時にランダムに選択された値bの値を推測する確率によって決まり、この値によってLRオラクルで暗号化されるメッセージが決まる。したがって、攻撃者の優位性は次のように定義される: ^[1]$${\displaystyle \operatorname {Adv} _{\mathcal {SE}}^{\mathrm {ind-cpa} }(A)=2\cdot \Pr \left[\mathrm {推測} _{\mathcal {SE} }^{A}\Rightarrow \mathrm {true} \right]-1}$$

非適応型および適応型選択暗号文攻撃における区別不能性 (IND-CCA1、IND-CCA2) は、IND-CPA と類似の定義を使用します。ただし、公開鍵 (対称型の場合は暗号化オラクル) に加えて、攻撃者は、攻撃者の要求に応じて任意の暗号文を復号し、平文を返す復号オラクルにアクセスできます。非適応型定義では、攻撃者はチャレンジ暗号文を受信するまでしかこのオラクルに問い合わせることができません。適応型定義では、攻撃者はチャレンジ暗号文を受信したあとでも復号オラクルに問い合わせ続けることができますが、チャレンジ暗号文を復号に渡すことはできないという条件があります (そうでなければ、定義は自明になります)。

1. 挑戦者は、何らかのセキュリティパラメータk (例: ビット単位のキーサイズ) に基づいてキーペアPK、SK を生成し、PK を攻撃者に公開します。挑戦者はSKを保持します。
2. 攻撃者は、任意の暗号文やその他の操作に基づいて、暗号化および復号化オラクルへの任意の数の呼び出しを実行する可能性があります。
3. 最終的に、攻撃者は2つの異なる選択された平文M ₀、M _{1 を}挑戦者に提出します。
4. 挑戦者はビットb ∈ {0, 1} を一様にランダムに選択し、「チャレンジ」暗号文C = E ( PK , M _b ) を敵対者に送り返します。
5. 攻撃者は追加の計算や暗号化を自由に実行できます。
   1. 非適応型の場合(IND-CCA1)、攻撃者は復号化オラクルにそれ以上の呼び出しを行うことはできません。
   2. 適応型の場合（IND-CCA2）、攻撃者は復号化オラクルへのさらなる呼び出しを行う可能性がありますが、チャレンジ暗号文C を送信することはできません。
6. 最後に、敵対者はbの値の推測値を出力します。

上記のゲームに勝つ上で、どの敵も無視できない優位性を持たない場合、そのスキームは IND-CCA1/IND-CCA2 安全です。

時には、暗号文の文字列が敵対者によってランダムな文字列と区別できない暗号化方式が必要になることがあります。^[2]

相手がメッセージが存在するかどうかさえ判断できない場合、メッセージを書いた人物は否認の余地が生まれます。

暗号化された通信リンクを構築する人の中には、トラフィック分析を困難にするために、暗号化された各データグラムの内容をランダムデータと区別できないようにすることを好む人もいます。^[3]

暗号化されたデータを保存するシステムを構築する人の中には、データの隠蔽を容易にするために、データをランダム データと区別できないようにすることを好む人もいます。たとえば、 TrueCryptなどのディスク暗号化には、何らかのデータ消去で残った無害なランダム データの中にデータを隠そうとするものがあります。別の例として、ステガノグラフィーには、デジタル写真の無害な「ランダム」画像ノイズの統計的特性と一致させることでデータを隠そうとするものがあります。

このような否認可能な暗号化システムをサポートするために、いくつかの暗号化アルゴリズムは、暗号文メッセージをランダムなビット文字列と区別できないように特別に設計されています。^{[4] [5] [6]}

ほとんどのアプリケーションでは、ランダムビットと区別がつかない暗号化メッセージを生成するための暗号化アルゴリズムは必要ありません。しかし、一部の著者は、そのような暗号化アルゴリズムは概念的に単純で扱いやすく、実用的にも汎用性が高いと考えています。実際、ほとんどのIND-CPA暗号化アルゴリズムは、ランダムビットと区別がつかない暗号化メッセージを生成するようです。^[7]

識別不能性は、暗号化された通信の機密性を維持する上で重要な特性です。しかし、識別不能性という特性は、場合によっては、他の、一見無関係なセキュリティ特性を意味することがわかっています。これらの意味合いは双方向に作用し、2 つの定義が同等になることもあります。たとえば、適応型選択暗号文攻撃 (IND-CCA2) における識別不能性という特性は、同じ攻撃シナリオ (NM-CCA2) における非展性という特性と同等であることがわかっています。この同等性はすぐには明らかではありません。なぜなら、非展性は機密性ではなく、メッセージの整合性を扱う特性だからです。他のケースでは、識別不能性を特定の定義と組み合わせることで、さらに別の有用な定義を意味することや、その逆があることが実証されています。次のリストは、いくつかの既知の意味合いをまとめたものです。ただし、完全なものではありません。

表記は、プロパティ A がプロパティ B を意味することを意味します。 は、プロパティ A と B が同等であることを意味します。は、プロパティ A が必ずしもプロパティ B を意味するわけではないことを意味します 。${\displaystyle A\Rightarrow B}$${\displaystyle A\Leftrightarrow B}$${\displaystyle A\not \Rightarrow B}$

• CPA に基づくIND-CPAセマンティック セキュリティ。${\displaystyle \Leftrightarrow}$
• NM-CPA（選択平文攻撃に対する非展性） IND-CPA。^[8]${\displaystyle \Rightarrow}$
• NM-CPA（選択平文攻撃に対する非展性） IND-CCA2。^[8]${\displaystyle \not \Rightarrow}$
• NM-CCA2（適応型選択暗号文攻撃における非展性） IND-CCA2。^[8]${\displaystyle \Leftrightarrow}$

• 攻撃の識別
• 計算上の区別不能性
• 選択暗号文攻撃
• 適応型選択暗号文攻撃

• Katz, Jonathan; Lindell, Yehuda (2007)。現代暗号入門: 原理とプロトコル。Chapman & Hall / CRC Press。ISBN 978-1584885511。