利点（暗号化）

暗号学において、敵対者の優位性は、暗号アルゴリズムをそのタイプのアルゴリズムの理想化されたバージョンと区別することによって、そのアルゴリズムを攻撃する成功度を測る尺度です。この文脈では、「敵対者」はアルゴリズム自体であり、人ではないことに注意してください。暗号アルゴリズムは、敵対者の計算リソースの指定された制限に従って、敵対者が無視できない優位性を持たない場合、安全であるとみなされます (具体的なセキュリティを参照)。「無視できる」とは通常、「 O (2 ^−p )以内」を意味します。ここで、p はアルゴリズムに関連付けられたセキュリティ パラメータです。たとえば、p はブロック暗号のキーのビット数です。

F を研究対象の関数のオラクルとし、G をそのタイプの理想化された関数のオラクルとします。敵対者 A は確率アルゴリズムであり、F または G を入力として与えられ、1 または 0 を出力します。A の仕事は、与えられたオラクルにクエリを実行して、F と G を区別することです。次のように言います。 ${\displaystyle Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|}$

F をDES ブロック暗号のランダムなインスタンスとします。この暗号には 64 ビットのブロックと 56 ビットのキーがあります。したがって、キーは2 ^{64 個の可能な 64 ビット ブロック上の 2 56 個の} 順列のファミリから 1 つを選択します。「ランダム DES インスタンス」とは、オラクル F が何らかのキー K (敵対者には不明) を使用して DES を計算することを意味します。ここで、K は 2 ^{56 個の}可能なキーから等確率で選択されます。

DES インスタンスを、64 ビット ブロック上の (2 ⁶⁴ ) !個の可能な順列からランダムに選択された順列を意味する、理想的な64 ビット ブロック暗号と比較します。このランダムに選択された順列を G と呼びます。スターリングの近似から、 (2 ⁶⁴ ) ! は 付近であることに注意してください。そのため、どの順列が選択されるかを指定する場合も、実際のコンピュータで正確に表すには大きすぎる数値を書き留める必要があります。別の見方をすると、G は「鍵の長さ」が約 10 ²¹ビットである「暗号」のインスタンスであり、これもコンピュータに収まるには大きすぎます (ただし、ランダム オラクルを使用して、クエリの数に比例するストレージ スペースで G を実装できます)。 ${\displaystyle 10^{3.47\times 10^{20}}}$

与えられたオラクルは任意の平文を暗号化するため、選択平文攻撃( CPA)をモデル化しており、計算している利点は特定の敵対者の CPA 利点と呼ぶことができることに注意してください。復号化オラクルも利用できる場合は、選択暗号文攻撃( CCA)を実行し、敵対者の CCA 利点を見つけます。

この敵を A _{0 と}呼びます。この敵は、コインを投げて、オラクルコールを行わずに、同じ確率で 1 または 0 を返します。したがって、Pr[A ₀ (F)=1] と Pr[A ₀ (G)=1] は両方とも 0.5 です。これらの確率の差はゼロなので、Adv(A ₀ ) はゼロです。常に 0 を返す場合も、常に 1 を返す場合も同じことが当てはまります。つまり、F と G の確率は同じなので、利点はゼロです。この敵は、F と G を区別できません。暗号設計者であれば、(おそらく実現不可能ですが)、どの敵にとってもこれよりはるかに優れた結果を出すことが計算上不可能になるようにすることが望みです 。ブルートフォース検索よりも高速な区別器がない暗号を作成できれば、成功したことになります。

_{この敵対者 (A 1}と呼ぶ) は、入力をブルート フォースで解読しようとします。敵対者には独自の DES 実装があります。敵対者は、オラクルに 1 つのクエリを与え、すべてゼロの 64 ビット文字列を暗号化するように要求します。結果として得られる暗号文を E ₀と呼びます。次に、徹底的なキー検索を実行します。アルゴリズムは次のようになります。

E 0 = オラクルクエリ(0)
 kが0,1,...,2 56 -1の範囲にある場合:
   DES k (0) == E 0の場合:
      戻り値 1
 0を返す

これは 56 ビットの DES キースペース全体を検索し、一致するキーが見つかる可能性がある場合は「1」を返します。実際には、2 つの異なるキーによって 1 つ以上の一致するプレーンテキストと暗号テキストのペアが生成される可能性があるため、キーを確認するには複数のプレーンテキストが必要です。キーが見つからない場合は、0 を返します。

入力オラクルがDESの場合、この徹底的な検索でキーが確実に見つかるので、Pr[A ₁ (F)=1] = 1です。入力オラクルがランダム順列の場合、 E ₀の可能な値は2 ^{64 個}あり、そのうち最大で2 ^{56個がDESキー検索で調べられます。したがって、A} ₁が1を返す確率は最大で2 ⁻⁸です。つまり、

${\displaystyle Pr[A_{1}(G)=1]\leq 2^{-8}}$、 それで

${\displaystyle Adv(A_{1})=|Pr[A_{1}(F)=1]-Pr[A_{1}(G)=1]|\geq 1-2^{-8}}$

したがって、優位性は少なくとも約 0.996 です。これはほぼ確実な区別ですが、ブルート フォース検索よりも高速ではないため、セキュリティ上の欠陥ではありません。結局のところ、これはブルート フォース検索 です。

• 擬似ランダム関数の利点
• キーリカバリの利点
• PR-CPAの利点

• フィリップ・ロガウェイとミヒル・ベラーレ著『現代暗号入門』
• オデッド・ゴールドライヒ、暗号の基礎