イスラエルの科学者、シモン・イーブン（シモン・イーブン）とイーシャイ・マンスール（イーシャイ・マンスール）は1997年に疑問に思った。最小限では、暗号方式の構造要素の数を意味し、耐久性では、この暗号に対する攻撃の複雑さの（正式に）低い推定値を意味しました。彼らが言うように、カットの下で-証明可能な強度を持つ最小の（今日まで）ブロック暗号の説明。

叙情的な余談

現在使用されている~~ほとんど~~すべての暗号化標準は、正式には強力ではありません 。しおり、脆弱性、または弱点がないことを保証する人はいません。ただ、これらの暗号を解読する方法、つまり徹底的な検索の指数関数的な複雑さを大幅に減らす方法を誰もまだ発明していない（または少なくとも公開していない）だけです。対称暗号化、非対称暗号化、ハッシュ化など、セキュリティとプライバシーを支えるほぼすべての暗号化アルゴリズムを開くと、 比較的複雑な問題（離散対数問題など）を解決することになります。誰もまだ比較的単純な解決策を提案していないため、複雑です。有限体で対数を計算する方法、または多項式時間で数値を因数分解する方法を学ぶまで（または、より大きな量子コンピューターを構築するまで）、DHとRSAは安定していると見なされ、キーのビット数のみがパーソナルコンピューターのパワーに比例して増加します。

すべては、下から評価を取得する方法がまだわからないためです。友だち、数学（特に暗号）では、美しいアイデアや洗練された解決策はそれほど多くなく、下から証明された推定はさらに少ない。私の考えでは、ここで考慮された暗号は交差点に該当します。それは可能な限り単純であると同時に、形式的に耐性があります。

ベイズの条件付き確率式と分数の初等算術よりも複雑なものは含まれていませんが、この出版物は準備のできていない読者向けの芸術作品ではないことをすぐに警告します。 経験の浅い読者は、暗号の設計の説明に満足したままであり、その耐久性の厳密な証拠は、数学の専門家と真の愛好家のためにここに与えられます。

[EM97]のイスラエルの学者であるShimon EvenとYishay Mansourは、ランダムに選択された単一の置換に基づいて、証明可能な耐久性を持つブロック暗号を構築する方法を提案しました $S_ {2n}$ 。

このブロック暗号を直接紹介する前に、紹介したシンボルと基本的な定義のリストを示すことができます。ただし、いつでもそこに戻ることができます。したがって、「今ここ」のすべてを見るために私があなたに深刻な関心を抱かせた場合は、暗号の説明に直接進んでください。

定義と規則

セット、セット

$\左\ lbrace A、B、C、\ドット\右\ rbrace$ -順序付けられていない要素のセット $A、B、C、\ドット$
$\左\角A、B、C、\ドット\右\角$ -要素の順序付きセット $A、B、C、\ドット$

碑文

$\ mathcal {P}、\ mathcal {C}、\ mathcal {K}$ -暗号システムが使用するスペース
$\ mathrm {A}、\ mathrm {B}$ -アルゴリズム、計算モデル
$\ mathrm {E}、\ mathrm {P}、\ mathrm {D}$ -オラクル
$\ mathsf {E}、\ mathsf {P}$ -アルゴリズムによって開発されたセット
$\ pi、\ sigma、\ delta$ -置換
$\ mathsf {CP}、\ mathsf {EFP}$ -タスク

指定

$\ mathcal {P}$ -多くの平文（メッセージ）
$\左\ lbrace P_1、P_2、\ドット\右\ rbrace \ subseteq \ mathcal {P}$ -オープンテキスト $P_1、P_2、\ドット$
$\ mathcal {C}$ -多くの暗号文（暗号）
$\左\ lbrace C_1、C_2、\ドット\右\ rbrace \ subseteq \ mathcal {C}$ -暗号文 $C_1、C_2、\ドット$
$\ mathcal {K}$ -多くのキー
$\左\ lbrace K_1、K_2、\ドット\右\ rbrace \ subseteq \ mathcal {K}$ -キー $K_1、K_2、\ドット$
$\下線{K} \ in \ mathcal {K}$ 真の鍵
$E \コロン\ mathcal {P} \回\ mathcal {K} \ mapsto \ mathcal {C}$ -暗号化機能
$D \コロン\ mathcal {C} \回\ mathcal {K} \ mapsto \ mathcal {P}$ -復号化機能
$\ mathrm {P} _ {\ sigma}、\ mathrm {P} _ {\ sigma} ^ {-1}$ -置換を実装するオラクル $\シグマ、\シグマ^ {-1}$
$\ mathrm {E} _ {K、\ sigma}、\ mathrm {D} _ {K、\ sigma}$ -機能を実装するオラクル $E D$ キーに $K$
$p _ {\ mathrm {A}}$ -アルゴリズムが成功する確率 $\ mathrm {A}$
$T _ {\ mathrm {A}}$ -アルゴリズム実行時間 $\ mathrm {A}$

定義

暗号システム $S$ 順序付けられた5つのセットと呼ばれる $S = \左\ラングル\ mathcal {P}、\ mathcal {C}、\ mathcal {K}、E、D \ right \ rangle$ どこで

$\ mathcal {P}$ -多くの平文
$\ mathcal {C}$ -多くの暗号文
$\ mathcal {K}$ -多くのキー
$E$ -（単射）暗号化関数（ 暗号化 ）：

$E \コロン\ mathcal {P} \回\ mathcal {K} \ mapsto \ mathcal {C}; \ quad \ forall K \ in \ mathcal {K} \はE_K \コロン\ mathcal {P} \ mapsto \ mathcal {C}を意味します。$

$D$ -復号化機能（解読）：

$D \コロン\ mathcal {C} \回\ mathcal {K} \ mapsto \ mathcal {P}; \ quad \ forall K \ in \ mathcal {K} \はD_K \ colon \ mathcal {C} \ mapsto \ mathcal {P}を意味します。$

クラシックイーブン–マンスールスキーム

イスラエルの科学者Shimon EvenとYishay Mansourは、彼らの研究で、証明可能な暗号強度を持つブロック暗号を提案しました。 $\ pi$ すべての順列のセットからランダムに（または擬似ランダムに）選択されます $S_ {2 ^ n}$ プレーンテキスト上。

選択された置換はキーの一部ではなく、何らかの種類の「ブラックボックス」の形式ですべての攻撃者が利用できると想定されています。

攻撃者の観点から、提案された暗号は理想的なランダム暗号と実際に区別がつかず、システムが正常に開く確率（秘密鍵の回復） $\下線{K}$ ）は多項式的に小さい（主な結果は定理2 、それからの結果2.1 、および定理3 ）。

また、真にランダムな置換の代わりに疑似ランダム置換を使用しても、示されている暗号の強度は変わらないと主張されています。

説明

させる $\ mathcal {P} \ equiv \ mathcal {C}$ 、そして $\ pi \ in S _ {\ left \ vert \、{\ mathcal {P} \、\ right \ vert}$ -セットから選択された置換 $S _ {\左\ vert \、{\ mathcal {P} \、\右\ vert}$ 平文のセットに対するすべての順列、および $\ pi ^ {-1}$ -彼女に逆。

すべての要素に対して $P \ in \ mathcal {P}$ そして $C \ in \ mathcal {C}$ オープンおよび暗号文の値のセット $\ pi（P）$ そして $\ pi ^ {-1}（C）$ 順列の値を直接計算することで簡単に取得できます $\ pi$ そして $\ pi ^ {-1}$ 、またはパブリックオラクルを参照することにより $\ mathrm {P} _ {\ pi}$ そして $\ mathrm {P} ^ {-1} _ {\ pi}$ 。

オープンスペースと暗号文スペースはバイナリスペースです $n$ –次元ベクトル： $\ mathcal {P} \ equiv \ mathcal {C} = \左\ lbrace 0、1 \右\ rbrace ^ n = \ mathbb {Z} _ {2} ^ {n}$ 、およびシステムのキースペースは次元のバイナリベクトルのスペースです $2n$ ： $\ mathcal {K} = \左\ lbrace 0,1 \右\ rbrace ^ {2n} = \ mathbb {Z} _ {2} ^ {2n}$ 。

秘密鍵 $\下線{K} \ in \ mathcal {K}$ 2つの順序付きペアです $n$ –次元サブキー（半分） $\下線{K} _1$ そして $\下線{K} _2$ ; 各サブキーはスペースからランダムに選択されます $n$ –等確率の次元バイナリベクトル $2 ^ {-n}$ 。

また、選択された秘密鍵は $\下線{K}$ 正当なユーザーのみが知っており、平文（メッセージ）の暗号化と暗号文（暗号）の解読に使用されます。

平文暗号化 $P$ 秘密鍵を使用する $\下線{K} = \左\角度\下線{K} _1、\下線{K} _2 \右\角$ および選択された置換 $\ pi$ 次のように生成されます。

$E _ {\下線{K}}（P）= E（P、\左\角\下線{K} _1、\下線{K} _2 \右\角）= \ pi（P \ oplus \下線{K} _1）\ oplus \下線{K} _2、$

暗号文の解読 $C$ キーを使用して $K$ および選択された置換 $\ pi$ -次のように：

$D _ {\下線{K}}（C）= D（C、\左\角\下線{K} _1、\下線{K} _2 \右\角）= \ pi ^ {-1}（C \ oplus \下線{K} _2）\ oplus \下線{K} _1。$

本当に簡単？ 鍵の前半でポクソリューというメッセージを受け取り、すべてがアクセス可能な開いたプレートに置き換えられ、鍵の後半でポクソリを受け取り、暗号文を取得しました。いいですねなぜ誰も実際にこのスキームを使用しないのですか？結局のところ、AESやDESよりもずっと簡単です。最も単純なブロック暗号。ここでキャッチはどこですか？

キャッチ

問題は、置換がバイナリに設定されていることです $n$ -ビットベクトル。ランダムに選択された置換の置換テーブルを保存することは完全に受け入れられません。これには、 $\ mathcal {O} \！\左（n 2 ^ n \右）$ メモリ。この問題の唯一の可能な解決策は、任意のポイントで比較的簡単に値を計算できる、 優れた擬似ランダム置換（ランダム置換とは多項式的に区別できない）を構築することです。方法がわかりません

回路の最小性について

古典的なスキームは、このスキームの要素のいずれかを削除すると、その抵抗が大幅に弱くなるという意味で最小であることに注意してください。サブキーへの追加の削除、または置換を示すことは簡単です $\ pi$ スキームが脆弱になり、その結果、完全に不安定になります。

最初のサブキーには追加はありません。

暗号化関数の形式は次のとおりです。

$E（P、\下線{K}）= C = \ pi（P）\ oplus \下線{K}、\ text {where} \下線{K} \ in \ mathcal {K} \ equiv \ mathcal {P} = \ mathbb {Z} _ {2} ^ {n}。$

攻撃者は秘密鍵を簡単に計算できます。 $\下線{K}$ 置換を知る $\ pi$ ：

$\下線{K} = C \ oplus \ pi（P）。$
2番目のサブキーへの追加はありません。

暗号化関数の形式は次のとおりです。

$E（P、\下線{K}）= C = \ pi（P \ oplus \下線{K}）、\ text {where} \下線{K} \ in \ mathcal {K} \ equiv \ mathcal {P} = \ mathbb {Z} _ {2} ^ {n}。$

攻撃者は秘密鍵を簡単に計算できます。 $\下線{K}$ 置換を知る $\ pi ^ {-1}$ ：

$\下線{K} = \ pi ^ {-1}（C）\ oplus P$
行方不明です $S$ –ブロック（置換 $\ pi$ ）

暗号化関数の形式は次のとおりです。

$E（P、\下線{K} _1 \ oplus \下線{K} _2）= C = P \ oplus \下線{K} _1 \ oplus \下線{K} _2。$

攻撃者は秘密鍵を簡単に計算できます。 $\下線{K}$ ：

$\下線{K} = \下線{K} _1 \ oplus \下線{K} _2 = P \ oplus C$

回路耐久性について

永続性の前提、定義

提案されたスキームの安定性は、次の仮定によるものです。

本当の鍵は攻撃者に知られていません $\下線{K} \ in \ mathcal {K}$ ;
攻撃者は、秘密鍵で平文（メッセージ）を暗号化し、暗号文（暗号）を解読することができます $\下線{K}$ ;
攻撃者は順列値を計算することができます $\ pi$ そしてそれへの逆順列 $\ pi ^ {-1}$ 。

システムを明らかにするアルゴリズムは、次の4つのオラクルを参照できます。 $\ mathrm {P}、\ mathrm {P} ^ {-1}、\ mathrm {E}、\ mathrm {D}$ ：

オラクル $\ mathrm {P} _ {\ pi}$ 順列値を計算します $\ pi \ in S _ {\ left \ vert \、\ mathcal {P} \ right \ vert \、}$ に $n$ –次元バイナリ入力セット $M$ ：

$\ mathrm {P} _ {\ pi} \コロン\ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathbb {Z} _ {2} ^ {n}、\ quad \ operatorname {\ mathrm {P } _ {\ pi}} \左[M \右]} = \ pi（M）;$

オラクル $\ mathrm {P} ^ {-1} _ {\ pi}$ 順列値を計算します $\ pi ^ {-1} \ in S _ {\ left \ vert \、\ mathcal {P} \、\ right \ vert}$ に $n$ –次元バイナリ入力セット $M '$ ：

$\ mathrm {P} ^ {-1} _ {\ pi} \コロン\ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathbb {Z} _ {2} ^ {n}、\ quad \ operatorname {\ mathrm {P} ^ {-1} _ {\ pi}} \左[M '\右]} = \ pi ^ {-1}（M'）;$

オラクル $\ mathrm {E} _ {\下線{K}、\ pi}$ 暗号化する $n$ –次元バイナリタイピング（プレーンテキスト） $P$ に $2n$ –次元キー $\下線{K}$ ：

$\ mathrm {E} _ {\下線{K}、\ pi} \コロン\ mathcal {P} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {C} \ equiv \ mathbb { Z} _ {2} ^ {n}、\ quad \ operatorname {\ mathrm {E} _ {\ underline {K}、\ pi}} \ left [P \ right]} = \ underline {K} _2 \ oplus \ pi（P \ oplus \下線{K} _1）;$

オラクル $\ mathrm {D} _ {\下線{K}、\ pi}$ 解読する $n$ –次元バイナリセット（暗号文） $C$ に $2n$ –次元キー $\下線{K}$ ：

$\ mathrm {D} _ {\下線{K}、\ pi} \コロン\ mathcal {C} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {P} \ equiv \ mathbb { Z} _ {2} ^ {n}、\ quad \ operatorname {\ mathrm {D} _ {\ underline {K}、\ pi}} \ left [C \ right]} = \ underline {K} _1 \ oplus \ pi ^ {-1}（C \ oplus \下線{K} _2）。$

さらに、Oracleが値を計算する置換 $\ mathrm {P} _ {\ pi}$ （ $\ mathrm {P} ^ {-1} _ {\ pi}$ ）、選択され、暗号化と復号化が固定キーで実行されます $\下線{K}$ 、Oracle表記法のインデックスを省略します： $\ mathrm {P}、\ mathrm {P} ^ {-1}、\ mathrm {E}、\ mathrm {D}$ 。

オラクルに目を向ける $\ mathrm {P}$ そして $\ mathrm {P} ^ {-1}$ 置換の値を計算するクエリを使用して $\ pi$ そして $\ pi ^ {-1}$ ポイントで $M$ そして $M '= \ pi（M）$ 、アルゴリズムは答えを取得します $M '$ そして $M$ それに応じて。

したがって、任意のアルゴリズムとオラクルとの通信 $\ mathrm {P}$ そして $\ mathrm {P} ^ {-1}$ 「ポイント」、「置換値」という形式のペアの形成に縮小 $\ pi$ この時点で：

$\ left \ langle M、M '\ right \ rangle = \ left \ langle M、\ pi（M）\ right \ rangle$

このようなペアを呼び出します $P$ –Pairs 、およびすべてのセット $P$ –アルゴリズムによって生成されたペア $\ mathrm {A}$ 実行の結果として、 $\ mathsf {P} _ {\ mathrm {A}}$ または単に $\ mathsf {P}$ 。

オラクルに目を向ける $\ mathrm {E}$ そして $\ mathrm {D}$ 平文暗号化リクエスト $P$ 暗号文の解読 $C = E（P、\下線{K}）$ 、アルゴリズムは答えを取得します $C$ そして $P$ それに応じて。

したがって、任意のアルゴリズムとオラクルの通信 $\ mathrm {E}$ そして $\ mathrm {D}$ 「プレーンテキスト」、「暗号文」という形式のペアの形成に縮小されます。

$\左\ Langle P、C \右\ rangle = \左\ langle M、E（P、\下線{K \右\ rangle）}。$

このようなペアを呼び出します $E$ –Pairs 、およびすべてのセット $E$ –アルゴリズムによって生成されたペア $\ mathrm {A}$ 実行の結果として、 $\ mathsf {E} _ {\ mathrm {A}}$ または単に $\ mathsf {E}$ 。

定義

$E$ –ペア $\左\ラングP_1、C_1 \右\ラング$ そして $\左\ラングP_2、C_2 \右\ラング$ 交差すると呼ばれます $P_1 = P_2$ どちらか $C_1 = C_2$ 。

同様の定義は $P$ –ペア

定義

$P$ –ペア $\左\ラングルM_1、M_1 '\右\ラングル$ そして $\左\ラングルM_2、M_2 '\右\ラングル$ 交差すると呼ばれます $M_1 = M_1 '$ どちらか $M_2 = M_2 '$ 。

ステートメント1 （重複するペアは同一です）

すべてのオラクルが $\ mathrm {P} _ {\ sigma}、\ mathrm {P} ^ {-1} _ {\ sigma}、\ mathrm {E} _ {K、\ sigma}、\ mathrm {D} _ {K、\シグマ}$ 固定されたものに正直 $\シグマ$ そして $K$ 次の文が真です。

交差する $E$ –ペアの一致。
交差する $P$ –ペアが一致します。

モジュロアサーション1、セットのすべてのペアを仮定できます。 $\ mathsf {E}$ そして $\ mathsf {P}$ 互いに交差しないでください。

成功の確率 $p _ {\ mathrm {A}}$ アルゴリズム $\ mathrm {A}$ このアルゴリズムを計算する確率を呼び出します $\ mathrm {A}$ 任意の（ただし正しい）入力での正しい出口。したがって、たとえば、確率によって $p _ {\ mathrm {A}}$ アルゴリズムの成功 $\ mathrm {A}$ 暗号化キーを計算する $E$ –ペア $\左\ラングP、C \右\ラング$ 確率があります

$\ forall P、C \＆gt; \ Longrightarrow \＆gt; p _ {\ mathrm {A}} = \ Pr {\ operatorname {A} \ left [\ left \ langle P、C \ right \ rangle \ right]} = \下線{K}}。$

実行時 $T _ {\ mathrm {A}}$ アルゴリズム $\ mathrm {A}$ このアルゴリズムによって実行されるクエリの数を理解します $\ mathrm {P}、\ mathrm {P} ^ {-1}、\ mathrm {E}、\ mathrm {D}$ 。

定義

機能 $f（n）\コロン\ mathbb {N} _0 \ mapsto \ left [0、1 \ right]$ 多項式の場合、 多項式無視可能と呼ばれます $p（n）$ あります $n_0$ そのような $n＆gt; n_0$ 行った $f（n）＆lt; 1 / p（n）$ ：

$f（n）\ text {多項式的に無視できる} \ n \ n \ n \ n \ n \ n \ n \ n \ n_0 \＆gt; \ Longrightarrow \＆gt; f（n）＆lt; \ frac {1} {p（n）}。$

定義

タスク $\ mathsf {T}$ 時間的に多項式で区切られた、それを解くアルゴリズムの成功確率が多項式的に小さい場合、それを困難と呼びます。

正式なモデルの説明

[EM97]で提案されたモデルでは、攻撃者は暗号デバイスと選択された置換についての知識を完全に所有しています。 $\ pi$ 。システムを破壊するために、攻撃者は何らかのアルゴリズムを使用します $\ mathrm {A}$ 、次の2つの問題のいずれかを解決できます： 復号化問題 $\ mathsf {CP}$ 、または新しい平文/暗号文のペアを構築するタスク $\ mathsf {EFP}$ 。

復号化問題（ $\ mathsf {CP}$ ）

復号化問題（

$\ mathsf {CP}$ 、 クラッキングの問題 ）は、一部の閉じたテキストの攻撃者による復号化の問題として理解されています $C_0$ 。さらに、任意のアルゴリズム $\ mathrm {A}$ 問題を解決するために攻撃者によって使用されるオラクルにアクセスできます $\ mathrm {P}$ 、 $\ mathrm {P} ^ {-1}$ 、 $\ mathrm {E}$ 、 $\ mathrm {D} '$ ここで：

（限定 $C_0$ ）オラクル $\ mathrm {D} '$ 解読する $n$ –次元バイナリセット（暗号文） $C$ を除く $C_0$ キーに $\下線{K}$ ：

$\ mathrm {D} _ {\下線{K}、\ pi} '\コロン\ mathcal {C} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {P} \ equiv \ mathbb {Z} _ {2} ^ {n}、\ quad \ mathrm {D} _ {\下線{K}、\ pi} '\左[C \右] = \下線{K} _1 \ oplus \ pi ^ {-1}（C \ oplus \下線{K} _2）\ text {with} C \ neq C_0。$

アルゴリズム $\ mathrm {A}$ システムを正常に開きます $\演算子名{A} \左[C_0 \右]} = D（C_0、\下線{K}）$ 。

新しい平文/暗号文のペアを構築するタスク（ $\ mathsf {EFP}$ ）

新しいテキストのペアを作成するタスクの下（ $\ mathsf {EFP}$ 、 実存の偽造問題 ）このようなペアを構築する問題が理解されています $\左\ラングP、C \右\ラング$ 関係を満たすだろう $C = E（P、\下線{K}）$ 、同時にオラクルの1つへの要求と応答で構成されていませんでした $\ mathrm {E}、\ mathrm {D}$ 。さらに、任意のアルゴリズム $\ mathrm {B}$ 攻撃者が問題を解決するために使用すると、4つのオラクルすべてにアクセスできます。 $\ mathrm {P}、\ mathrm {P} ^ {-1}、\ mathrm {E}、\ mathrm {D}$ 。

アルゴリズムの成功 $\ mathrm {B}$ 平文と暗号文の新しい正しいペアの受信が考慮されます $\左\ラングP、C \右\ラング$ 。

テキスト/暗号文のペアを作成するタスクを剖検タスクに削減（ $\ mathsf {EFP} \ varpropto \ mathsf {CP}$ ）

定理1 （EFPからCPへの削減）

させる $n \ in \ mathbb {N}$ 、そしてアルゴリズムがあります $\ mathrm {A}$ 剖検問題の解決 $\ mathrm {CP}$ 時間内に $T（n）$ 成功の確率で $\ xi（n）$ その後、アルゴリズムがあります $\ mathrm {B}$ いくつかのテキストを作成する $\左\ラングP、C \右\ラング$ 同時に $T（n）$ 成功の確率で $\ xi（n）/ T（n）$ ：

$\存在する\ mathrm {A} \ text {解の場合} \ mathsf {CP} \ mid T _ {\ mathrm {A}} = T（n）、\ p _ {\ mathrm {A}} = \ xi（n）\ ＆gt; \ Longrightarrow \＆gt; \存在する\ mathrm {B} \ text {for solution} \ mathsf {EFP} \ mid T _ {\ mathrm {B}} \ leq T（n）、\ p _ {\ mathrm {B}} = \ frac {\ xi （n）} {T（n）}。$

証明

プレーンテキストを修正 $P_0$ 鍵 $\下線{K}$ および暗号文 $C_0 = E（P_0、\下線{K}）$ 、およびアルゴリズムの進行を検討する $\演算子名{A} \左[C_0 \右]}$ 。

一般性を失うことなく、アルゴリズムが $\ mathrm {A}$ 正常に復号化する $C_0$ その後、ある重要な時点で $T＆lt; T（n）$ このアルゴリズムの実行、攻撃者は見つかった平文、-、候補をチェックします $P_0$ （初めて）暗号化のリクエストをOracleに送信する $\ mathrm {E}$ 解読可能な暗号文の比較 $C_0$ オラクルの答え：

$\ operatorname {E_K} \ left [P_0 \ right]} \ stackrel {？} {=} C_0。$

アルゴリズムに基づいて $\ mathrm {A}$ アルゴリズムを構築する $\ mathrm {B}$ 問題を解決する $\ mathsf {EFP}$ ：

暗号文を修正 $C_0 \ in \ mathcal {C}$ ;
アルゴリズムの実行を始めましょう $\演算子名{A} \左[C_0 \右]}$ ;
ランダムに選択 $\タウ$ セグメント全体に均一に分布 $\左[1、t（n）\右]$ ;
アルゴリズムの実行を停止します $\演算子名{A} \左[C_0 \右]}$ 後 $\タウ-1$ オラクルへのクエリ。
リクエストに応じて $\タウ$ アルゴリズム $\演算子名{A} \左[C_0 \右]}$ 暗号化を要求する $P '$ 、 その後、アルゴリズムの実行が停止し、元のペア- $\左\ラングP '、C_0 \右\ラング$ 。

アルゴリズムがわかりやすい $\ mathrm {B}$ もうしません $T（n）$ Oracleクエリ $\ mathrm {E}、\ mathrm {D}$ 望ましいペア $\左\ラングP '、C_0 \右\ラング$ 復号化アルゴリズムが $\ mathrm {A}$ テキストを正常に解読します $C_0$ （確率付き $p _ {\ mathrm {A}} = \ xi（n）$ ）および $\ mathrm {A}$ 重要なタイミングで停止します $T '$ （確率付き $1 / T（n）$ ）：

$p _ {\ mathrm {B}} = p _ {\ mathrm {A}} \ cdot \ frac {1} {T（n）} = \ frac {\ xi（n）} {T（n）}$

証明する必要がある場合。

帰結1.1

任せて $\ mathsf {EFP}$ 難しい（多項式決定アルゴリズムの場合） $\ mathrm {B}$ 彼の成功の可能性 $p _ {\ mathrm {B}}$ 多項式が小さい）、次に問題 $\ mathsf {CP}$ 難しい（多項式決定アルゴリズムの場合） $\ mathrm {A}$ 彼の成功の可能性 $p _ {\ mathrm {A}}$ 多項式が小さい）。

逆の声明（還元性 $\ mathsf {CP} \ varpropto \ mathsf {EFP}$ ）は一般的な場合には当てはまりません：暗号システムの一部のクラスでは、対応する暗号文が事前に知られており、キーに依存しない平文があります（たとえば、 $P = 1$ RSA回路で）。

ランダム置換を使用したシステムの安定性 $\ pi$

レジリエンスの証明の主なアイデアは次のとおりです。

多項式的に制限された攻撃の任意の段階で、「良好な」キー（攻撃者が利用できるデータに基づいて攻撃者が真実を確認も拒否もできないキー）のセットが指数関数的に大きいことを示します（ 補題1 ）。
攻撃者が真の鍵を「推測」できることを示す $\下線{K}$ 多項式の確率が小さい場合のみ（ 定理2 ）。
攻撃者が真のキーを識別するのに十分なデータを収集することを示す $\下線{K}$ オラクルに対するクエリの多項式数（ 定理2 ）。

定義

最初のサブキー $K_1$ キー $K = \左\角K_1、K_2 \右\角$ アルゴリズムに関して悪いと呼ばれる $\ mathrm {A}$ そして彼が開発したセット $\ mathsf {E}$ そして $\ mathsf {P}$ 存在する場合 $E$ –ペア $\左\ Langle P_i、C_i \右\ rangle \ in \ mathsf {E}$ そして $P$ –ペア $\左\ langle M_j、\ pi（M_j）\右\ rangle \ in \ mathsf {P}$ そのような $P_i \ oplus K_1 = M_j$ ; そして別の場合には良い：

$K_1 \ text {悪いキーです} \ iff \存在する\ left \ langle P_i、C_i \ right \ rangle \ in \ mathsf {E}、\ left \ langle M_j、\ pi（M_j）\ right \ rangle \ in \ mathsf {P} \＆gt; \ Longrightarrow \＆gt; P_i \ oplus K_L = M_j。$

つまり、サブキー $K_1$ アルゴリズムの結果として得られた素材に基づいて、 $\ mathrm {A}$ かどうかを把握することは不可能 $K_1$ 本当の鍵で $\下線{K}$ 。次の例を使用して、この非公式の定義について説明しましょう。 $K_1$ 悪いです、そして、悪いサブキーの定義によると、 $E$ –ペア $\左\ラングP_i、C_i \右\ラング、$ どこで $C_i = E（P_i、\左\ langle \下線{K} _1、\下線{K} _2 \右\ rangle）$ 、そして $P$ –ペア $\左\ langle P_i \ oplus K_1、\ pi（P_i \ oplus K_1）\ right \ rangle$ 。次にキー $K = \左\角K_1、K_2 \右\角$ 真のキーの役割の候補 $\下線{K}$ どこで

$K_2 = C_i \ oplus \左（\ pi（P_i \ oplus K_1）\右）。$

明らかにそのようなキー $K = \左\角K_1、K_2 \右\角$ これを満たす $E$ –ペア、なぜなら

$E（P_i、K）= K_2 \ oplus \ pi（K_1 \ oplus P_i）= \ big（C_i \ oplus（\ pi（P_i \ oplus K_1））\ big）\ oplus \ pi（K_1 \ oplus P_i）= C_i 。$

収集された他の使用 $E$ –ペアと $P$ –カップル攻撃者は、この方法で構築されたキーが $K$ 真の鍵 $\下線{K}$ オープンシステム。受け入れます（サブキーとして $\下線{K} _1$ ）、またはサブキーを破棄 $K_1$ 。

同様の定義を2番目のサブキーに定式化できます $K_2$ 。

定義

2番目のサブキー $K_2$ キー $K = \左\角K_1、K_2 \右\角$ アルゴリズムに関して悪いと呼ばれる $\ mathrm {A}$ そして彼が開発したセット $\ mathsf {E}$ そして $\ mathsf {P}$ 存在する場合 $E$ –ペア $\左\ Langle P_i、C_i \右\ rangle \ in \ mathsf {E}$ そして $P$ –ペア $\左\ langle M_j、\ pi（M_j）\右\ rangle \ in \ mathsf {P}$ そのような $C_i \ oplus K_2 = \ pi（M_j）$ ; そして別の場合には良い：

$K_2 \ text {-bad} \ iff \存在する\ left \ langle P_i、C_i \ right \ rangle \ in \ mathsf {E}、\ left \ langle M_j、\ pi（M_j）\ right \ rangle \ in \ mathsf { P} \＆gt; \ Longrightarrow \＆gt; C_i \ oplus K_2 = \ pi（M_j）。$

定義

キー $K = \左\角K_1、K_2 \右\角$ 両方のサブキーが良いと呼ばれる $K_1$ そして $K_2$ 良い場合と悪い場合があります。

ステートメント2 （真のサブキーは長所を共有します）

秘密鍵付き $\下線{K} = \左\角度\下線{K} _1、\下線{K} _2 \右\角$ および再配置 $\ pi$ 差し込む $\下線{K} _1$ そして $\下線{K} _2$ 両方とも良いか悪いか：

$\下線{K} _1 \テキスト{良いキー} \ iff \下線{K} _2 \テキスト{良いキー} \クワッド（\テキスト{when} \下線{K}、\ pi \テキスト{修正済み}）。$

補題1 （不良キーの割合）

アルゴリズムをしましょう $\ mathrm {A}$ たくさん働いた $\ mathsf {E}、\ left \ vert \、{\ mathsf {E} \、\ right \ vert = l$ そして $\ mathsf {P}、\左\ vert \、{\ mathsf {P} \、\右\ vert = m$ ばらばら $E$ –ペアと $P$ –それぞれペアリングしてから共有 $Q$ キースペースの不良キー $\ mathcal {K}$ 超えない $2lm / 2 ^ n$ 。

証明

不良サブキーの定義によると、サブキー $K_1$ 見つかったら悪い $E$ –ペア $\左\ langle P_ {i}、C_ {i} \ right \ rangle \ in \ mathsf {E}$ そして $P$ –ペア $\左\ langle M_ {j}、\ pi（M_ {j}）\右\ rangle \ in \ mathsf {P}$ そのような

$P_ {i} \ oplus K_1 = M_ {j}、\ text {または} K_1 = P_ {i} \ oplus M_ {j}。$

最後の手段として、すべてのセットで最後の平等を実現できます $私、j$ 、その後、様々な $P_ {i} \ mid 1 \ leq i \ leq l$ そして $M_ {j} \ mid 1 \ leq j \ leq m$ すべて $\左\ vert \、\ mathsf {E} \、\右\ vert \ cdot \左\ vert \、\ mathsf {P} \、\右\ vert = l \ cdot m$ 差し込む $K_1$ 悪いです。

同様の推論は、不良サブキーの最大数という事実につながります $K_2$ また超えない $lm$ 。

両方のサブキーがから選択されます $\ mathbb {Z} _ {2} ^ {n}$ 、これにより、不良キーの数の上限を取得できます。

$\＃\ left \ lbrace K \ text {悪いキーです} \ right \ rbrace \ leq lm \ cdot 2 ^ n + lm \ cdot 2 ^ n = 2 lm 2 ^ n、$

そして、キースペース内の不良キーのシェア $\ mathcal {K} = \ mathbb {Z} _2 ^ {2n}$ ：

$Q \ leq \ frac {2 lm 2 ^ n} {2 ^ {2n}} = \ frac {2lm} {2 ^ n}。$

証明する必要がある場合。

定義

させる $\シグマ$ -からの置換 $S _ {\左\ vert \、\ mathcal {P} \、\右\ vert}$ 、そして $K = \左\角K_1、K_2 \右\角$ いくつかのキーです。

私たちはカップルと言うでしょう $\左\ラングル\シグマ、K \右\ラングル$ セットを満たす $E$ –ペア $\ mathsf {E}$ そして $P$ –ペア $\ mathsf {P}$ 次の条件に該当する場合：

代用 $\シグマ$ 真の置換と区別できない $\ pi$ 結果セットで $P$ –ペア：

$\ forall \ left \ langle M、\ pi（M）\ right \ rangle \ in \ mathsf {P} \＆gt; \ Longrightarrow \＆gt; \シグマ（M）= \ pi（m）、$

代用 $\シグマ$ 真の置換と区別できない $\ pi$ 結果セットで $E$ –ペア：

$\ forall \ left \ langle P、C \ right \ rangle \ in \ mathsf {E} \＆gt; \ Longrightarrow \＆gt; \シグマ（P \ oplus K_1）= C \ oplus K_2。$

次の補題は、すべての適切なキーが、ある意味で、真の暗号化キーの役割の同等の候補であることを示しています $\下線{K}$ 。

補題2 （真のキー候補の配布）

させる $\ mathsf {E}、\左\ vert \、\ mathsf {E} \、\右\ vert = l$ そして $\ mathsf {P}、\左\ vert \、\ mathsf {P} \、\右\ vert = m$ -セット $E$ –ペアと $P$ –それぞれ、および $\下線{K}$ 真のキーである場合、あるキーが $K_ {i} \ in \ mathcal {K}$ 秘密鍵です $\下線{K}$ 誰もが同じです $私は$ ：

$\ forall i \ mid 1 \ leq {i} \ leq \ left \ vert \、{\ mathcal {K} \、\ right \ vert \＆gt; \ Longrightarrow \＆gt; \ Pr {\左[\下線{K} = K_ {i} \右]} = \ alpha = \ operatorname {const}。$

証明

キーが均等に配布される場合：

$\ forall K_ {i} \ in \ mathcal {K} \＆gt; \ Longrightarrow \＆gt; \ Pr {\左[K_ {i} = \下線{K} \右]} = \ frac {1} {2 ^ {2n}}、$

および置換 $\ pi$ ランダムに選択：

$\ forall \ sigma_ {i} \ in S _ {\ left \ vert \、\ mathcal {P} \、\ right \ vert} \＆gt; \ Longrightarrow \＆gt; \ Pr {\左[\ sigma_ {i} = \ pi \右]} = \ frac {1} {2 ^ n！}、$

所望の確率は条件付き確率であることがわかります

$\ alpha = \ Pr {\ left [K_ {i} = \ underline {K} \ mid \ left \ langle \ pi、K_ {i} \ right \ rangle \ text {satisfies} \ mathsf {E}、\ mathsf { P} \右]}。$

ベイズ式を使用します。

$\ Pr {\ left [K_ {i} = \下線{K} \ mid \ left \ langle \ pi、K_ {i \ right \ rangle} \ text {satisfies} \ mathsf {E}、\ mathsf {P} \ right]} = \ frac {\ overbrace {\ Pr {\ left [K_ {i} = \ underline {K} \ right]}} ^ {\ operatorname {const}} \ cdot \ overbrace {\ Pr {\ left [ \左\ langle \ pi、K_ {i \ right \ rangle} \ text {satisfies} \ mathsf {E}、\ mathsf {P} \ mid K_ {i} = \下線{K} \ right]}} { \ beta}} {\下括弧{\ Pr {\ left [\ left \ langle \ pi、K_ {i} \ right \ rangle \ text {satisfies} \ mathsf {E}、\ mathsf {P} \ right]}} _ {\ operatorname {const}}}。$

補題の証明が陳述の証明に還元されることは容易にわかります $\ beta = \ operatorname {const}$ 。

どのキーでもそれを示します $K_ {i} = \左\ラングルK_ {i、1 \右\ラングル、K_ {i、2}}$ 多くの $E$ –ペア $\ mathsf {E}$ 同等のセットに変換できます $P$ –ペア $\ mathsf {P} '$ ルックアップの制限 $\ pi$ 次のルールに従って：

$\ forall \ underbrace {\ left \ langle P_ {i}、C_ {i} \ right \ rangle} _ {E \ text {pair}} \ in \ mathsf {E} \ leadto \ underbrace {\ left \ langle P_ { i} \ oplus K_ {i、1}、C_ {i} \ oplus K_ {i、2} \ right \ rangle} _ {P \ text {pair}} \ in \ mathsf {P} '。$

明らかに、置換が固定されています $\ pi$ キーの場合 $K_ {i}$ 満足する $P$ –ペア $\左\ラングルP_ {i} \ oplus K_ {i、1}、C_ {i} \ oplus K_ {i、2} \右\ rangle$ それは満足し、 $E$ –ペア $\左\ラングP_ {i}、C_ {i} \右\ラング$ 。また、 $\左\ vert \、\ mathsf {E} \、\右\ vert = \左\ vert \、{\ mathsf {P} '\、\右\ vert$ 、示されたマッピングは全単射を定義するため $\ mathsf {E} \ mapsto \ mathsf {P} '$ 。

したがって、確率の式 $\ベータ$ 次の形式を取ります。

$\ beta \ equiv \ Pr {\ left [\ left \ langle \ pi、K_ {i} \ right \ rangle \ text {satisfies} \ mathsf {E}、\ mathsf {P} \ mid K_ {i} = \下線{K} \ right]} = \ Pr {\ left [\ left \ langle \ pi、K_ {i} \ right \ rangle \ text {satisfies} \ emptyset、\ mathsf {P} \ cup \ mathsf {P} ' \ mid K_ {i} = \下線{K} \右]}$

キーが $K_ {i}$ 良いですし、設定します $P$ –ペア $\ mathsf {P}$ そして $\ mathsf {P} '$ 適切なキーの定義によって交差しないでください：

$K_i \ text {良いキーです} \＆gt; \ Longrightarrow \＆gt; \ mathsf {P} \ cap \ mathsf {P} '= \ emptyset。$

この場合、望ましい確率 $\ベータ$ （ランダムに選択された）順列の確率 $\ pi$ 満足する $\左\ vert \、{\ mathsf {E} \、\右\ vert + \左\ vert \、{\ mathsf {P} \、\右\ vert = l + m$ 制限。この確率はキーに依存しません。 $K_ {i}$ と等しい

$\ beta = \ Pr {\ left [\ pi（M）= M '\ mid \ left \ langle M、M' \ right \ rangle \ in \ mathsf {P} \ cup \ mathsf {P} '\ right]} = \ frac {\ left（2 ^ n-（l + m）\ right）！} {2 ^ n！} = \ prod_ {j = 0} ^ {l + m-1} \ frac {1} {2 ^ n-i}。$

したがって、確率の式のすべての確率は一定であり、キーに依存しません $K_ {i}$ 、必要に応じて。

定理2 （任意の成功確率の境界 $\ mathrm {A}$ 解く $\ mathsf {EFP}$ ）置換させます $\ pi$ からランダムに選択 $S _ {\左\ vert \、\ mathcal {P} \、\右\ vert}$ キー $\下線{K}$ からランダムに選択 $\ mathbb {Z} _ {2} ^ {2n}$ 次に、アルゴリズムが成功する確率について $\ mathrm {A}$ 問題を解決する $\ mathsf {EFP}$ 次の上限があります。

$p _ {\ mathrm {A}} = \ mathcal {O} \！\左（\ frac {lm} {2 ^ n} \右）、$

どこで $l$ -オラクルへのクエリの数 $\ mathrm {E}$ そして $\ mathrm {D}$ 、そして $m$ -オラクルへのクエリの数 $\ mathrm {P}$ そして $\ mathrm {P} ^ {-1}$ 。

証明

あるアルゴリズムがあるとしましょう $\ mathrm {A}$ それは問題を解決します $\ mathsf {EFP}$ 同時にセットを生成します $\ mathsf {E}、\ left \ vert \、{\ mathsf {E} \、\ right \ vert = l$ そして $\ mathsf {P}、\左\ vert \、{\ mathsf {P} \、\右\ vert$ $E$ –ペアと $P$ –それぞれペア。このアルゴリズムは、次の2つの場合のいずれかでのみ成功します。 $\下線{K}$ アルゴリズムのステップの1つで 、またはその後で不良になる $l + m$ ステップアルゴリズム $\ mathrm {A}$ 正しいペアを「推測」するだけです $\左\ラングP、C \右\ラング$ 提供された $\下線{K} \ in \ mathcal {K} ^ {（l + m）}$ 。

で示す $\ mathsf {E} ^ {（r）}$ そして $\ mathsf {P} ^ {（r）}$ 多くの $E$ –ペアと $P$ –アルゴリズムによって生成されたペア $\ mathrm {A}$ 最初は $r-1$ クエリ：

$\ mathsf {E} ^ {（r）} \ subseteq \ mathsf {E}、\ \ big \ lvert \ mathsf {E} ^ {（r）} \ big \ rvert = l ^ {（r）} \ leq l = \左\ vert \、{\ mathsf {E} \、\ right \ vert、\ quad \ mathsf {P} ^ {（r）} \サブセットeq \ mathsf {P}、\ \ big \ lvert \ mathsf {P } ^ {（r）} \ big \ rvert = m ^ {（r）} \ leq m = \ left \ vert \、{\ mathsf {P} \、\ right \ vert。$

で示す $\ mathcal {K} ^ {（r）}$ 多くのキー、セットに関して良好 $\ mathsf {E} ^ {（r）}$ そして $\ mathsf {P} ^ {（r）}$ 。次に、先に証明した補題により、このようなキーの数は次のように推定できます。

$\ big \ lvert \ mathcal {K} ^ {（r）} \ big \ rvert \ geq 2 ^ {2n}-2 l ^ {（r）} m ^ {（r）} 2 ^ n \ geq 2 ^ { 2n}-2lm 2 ^ n。$

一般性を失うことなく、真の鍵は $\下線{K}$ このセットに属します（良い）。アルゴリズムは $\ mathrm {A}$ 以下の結果として、成功した場合 $r$ -リクエストキー $\下線{K}$ 悪いことが判明します。この成功の定義は、前に示した定義に対応していないが、後者の必要条件であることに注意してください。

アルゴリズムによって送信される可能性のあるすべての種類の要求を検討してください。 $\ mathrm {A}$ 次のオラクルに、 $r$ –ステップ、およびそれらのどれが、そしてどの確率で、キーを除外するかを見つけます $\下線{K}$ 良いキーの中から（ $\下線{K} \ notin \ mathcal {K} _ {i + 1}$ ）：

オラクルへのリクエスト $\ mathrm {E}$ ：

させる $\左\ラングP、C \右\ラング$ -そのようなリクエストの結果として形成された $E$ カップル。次の2つのオプションが可能です。

- カップル $\左\ Langle P、C \右\ rangle \ in \ mathsf {E} ^ {（r）}$ 、この場合、アルゴリズムによって解決されたセットは変更されず、キー $\下線{K}$ 良いままです。
- カップル $\左\ Langle P、C \右\ rangle \ notin \ mathsf {E} ^ {（r）}$ 、この場合、次の等式が成り立ちます。

$\ mathsf {E} ^ {（r + 1）} = \ mathsf {E} ^ {（r）} \ cup \ left \ langle P、C \ right \ rangle; \ quad \ mathsf {P} ^ {（r + 1）} = \ mathsf {P} ^ {（r）}。$

キーの数を数える $\ Delta_ {r、r + 1} Q _ {\ mathrm {E}、K}$ そのようなペアの形成の結果として悪化した $\左\ラングP、C \右\ラング$ 。キー $K = \左\角K_1、K_2 \右\角$ サブキーの少なくとも1つが悪い場合は悪い $K_1、K_2$ ：

$\ big \ lvert \ mathcal {K} ^ {（r）} \ setminus \ mathcal {K} ^ {（r + 1）} \ big \ rvert \ leq \＃{K_1}$

数 $Q_ {K_1} ^ {（r + 1）}$ 悪いサブキー $K_1$ （ステップで $r$ ）不良サブキーの定義により、異なる量の数に等しい $P_i \ oplus M_j$ インデックスはどこですか $私は$ すべてを駆け抜ける $E$ –セットのパラメーター $\ mathsf {E} ^ {（r + 1）}$ 、およびインデックス $j$ -すべてのために $P$ –セットのパラメーター $\ mathsf {P} ^ {（r + 1）}$ ：

$Q_ {K_1} ^ {（r + 1）} = \＃\ left \ lbrace K_1 \ text {悪いキー} \ right \ rbrace = \＃\ left \ lbrace P_i \ oplus M_j \ mid \ left \ langle P_i 、C_i \ right \ rangle \ in \ mathsf {E} ^ {（r + 1）}、\ left \ langle M_j、M_j '\ right \ rangle \ in \ mathsf {P} ^ {（r + 1）} \右\ rbrace}。$

上記の等式が与えられると $\ mathsf {E} ^ {（r + 1）}$ そして $\ mathsf {P} ^ {（r + 1）}$ 私達は得る：

$Q_ {K_1} ^ {（r + 1）} = Q_ {K_1} ^ {（r）} + \＃\左\ lbrace P \ oplus M_j \提供される\左\ langle M_j、M_j '\右\ rbrace \ in \ mathsf {P} ^ {（r）\ right \ rangle} \ leq Q_ {K_1} ^ {（r）} + m。$

同様の理由で、不良サブキーの数 $K_2$ また、もう $Q_ {K_2} ^ {（r）} + m$ ：

$Q_ {K_2} ^ {（r + 1）} = Q_ {K_2} ^ {（r）} + \＃\ left \ lbrace C \ oplus M_j '\提供\ left \ langle M_j、M_j' \ right \ rbrace \ \ mathsf {P} ^ {（r）\ right \ rangle} \ leq Q_ {K_2} ^ {（r）} + m。$

それから数 $Q_K ^ {（r + 1）}$ 悪い鍵 $K$ ステップで $r$ 次のように評価されます。

$Q_K ^ {（r + 1）} \ leq Q_ {K_1} ^ {（r + 1）} \ cdot 2 ^ n + 2 ^ n \ cdot Q_ {K_2} ^ {（r + 1）} = Q_K ^ { （r）} + 2 m 2 ^ n、$

目的の差は次と等しくなります。

$\ Delta_ {r、r + 1} Q _ {\ mathrm {E}、K} = Q_K ^ {（r + 1）}-Q_K ^ {（r）} \ leq 2 m 2 ^ n$

（ランダムに選択された）キー $\下線{K}$ の中になります $\ Delta_ {r、r + 1} Q _ {\ mathrm {E}、K}$ 不正になったキー（オラクルへのリクエストの結果として） $\ mathrm {E}$ ）と等しい

$\ Pr {\左[\下線{K} \ in \ mathcal {K} ^ {（r）} \ setminus \ mathcal {K} ^ {（r + 1）} \ mid \ left \ langle P、C \ right \ rangle \ right]} = \ frac {\ Delta_ {r、r + 1} Q _ {\ mathrm {E}、K}} {Q_K ^ {（r）}} \ leq \ frac {2m} {2 ^ n -2lm}。$

オラクルへのリクエスト $\ mathrm {D$

Oracleリクエストに似ています $\ mathrm {E}$ キーの確率 $\下線{K}$ （オラクルへのリクエストの結果として）悪いことが判明します $\ mathrm {D}$ ）超えない

$\ Pr {\左[\下線{K} \ in \ mathcal {K} ^ {（r）} \ setminus \ mathcal {K} ^ {（r + 1）} \ mid \ left \ langle P、C \ right \ rangle \ right]} = \ frac {\ Delta_ {r、r + 1} Q _ {\ mathrm {D}、K}} {Q_K ^ {（r）}} \ leq \ frac {2m} {2 ^ n -2lm}。$

オラクルへのリクエスト $\ mathrm {P}$

させる $\左\ Langle M、M '\右\ rangle$ -そのようなリクエストの結果として形成された $P$ カップル。次の2つのオプションが可能です。

- カップル $\左\ langle M、M '\右\ rangle \ in \ mathsf {P} ^ {（r）}$ 、この場合、アルゴリズムによって解決されたセットは変更されず、キー $\下線{K}$ 良いままになります;
- カップル $\左\ langle M、M '\右\ rangle \ notin \ mathsf {P} ^ {（r）}$ この場合、次の等式が成り立ちます。

$\ mathsf {E} ^ {（r + 1）} = \ mathsf {E} ^ {（r）}; \ quad \ mathsf {P} ^ {（r + 1）} = \ mathsf {P} ^ {（r）} \ cup \ left \ langle M、M '\ right \ rangle$

キーの数を数える $\ Delta_ {r、r + 1} Q _ {\ mathrm {P}、K}$ そのようなペアの形成の結果として悪化した $\左\ Langle M、M '\右\ rangle$ 。

数 $Q_ {K_1} ^ {（r + 1）}$ 悪いサブキー $K_1$ （ステップで $r$ ）不良サブキーの定義により、異なる量の数に等しい $P_i \ oplus M_j$ インデックスはどこですか $私は$ すべてを駆け抜ける $E$ –セットのパラメーター $\ mathsf {E} ^ {（r + 1）}$ 、およびインデックス $j$ -すべてのために $P$ –セットのパラメーター $\ mathsf {P} ^ {（r + 1）}$ ：

の等式を考えると $\ mathsf {E} ^ {（r + 1）}$ そして $\ mathsf {P} ^ {（r + 1）}$ 私達は得る：

$Q_ {K_1} ^ {（r + 1）} = Q_ {K_1} ^ {（r）} + \＃\ left \ lbrace P_i \ oplus M \ mid \ left \ langle P_i、C_i \ right \ rangle \ in \ mathsf {E} ^ {（r）} \ right \ rbrace \ leq Q_ {K_1} ^ {（r）} + l。$

同様の理由で、不良サブキーの数 $K_2$ また、もう $Q_ {K_2} ^ {（r）} + l$ ：

$Q_ {K_2} ^ {（r + 1）} = Q_ {K_2} ^ {（r）} + \＃\ left \ lbrace C \ oplus M_j '\ mid \ left \ langle M_j、M_j' \ right \ rangle \ \ mathsf {P} ^ {（r）} \ right \ rbrace \ leq Q_ {K_2} ^ {（r）} + m。$

それから数 $Q_K ^ {（r + 1）}$ 悪い鍵 $K$ ステップで $r$ 次のように評価されます。

$Q_K ^ {（r + 1）} \ leq Q_ {K_1} ^ {（r + 1）} \ cdot 2 ^ n + 2 ^ n \ cdot Q_ {K_2} ^ {（r + 1）} = Q_K ^ { （r）} + 2 l 2 ^ n、$

そして、望ましい差：

$\ Delta_ {r、r + 1} Q _ {\ mathrm {P}、K} = Q_K ^ {（r + 1）}-Q_K ^ {（r）} \ leq 2 l 2 ^ n。$

（ランダムに選択された）キー $\下線{K}$ の中になります $\ Delta_ {r、r + 1} Q _ {\ mathrm {P}、K}$ 不正になったキー（オラクルへのリクエストの結果として） $\ mathrm {P}$ ）と等しい

$\ Pr {\左[\下線{K} \ in \ mathcal {K} ^ {（r）} \ setminus \ mathcal {K} ^ {（r + 1）} \ mid \ left \ langle M、M '\ right \ rangle \ right]} = \ frac {\ Delta_ {r、r + 1} Q _ {\ mathrm {P}、K}} {Q_K ^ {（r）}} \ leq \ frac {2l} {2 ^ n-2lm}。$

オラクルへのリクエスト $\ mathrm {P ^ {-1}}$ 。

Oracleリクエストに似ています $\ mathrm {P}$ キーの確率 $\下線{K}$ （オラクルへのリクエストの結果として）悪いことが判明します $\ mathrm {P} ^ {-1}$ ）超えない

$\ Pr {\下線{K} \ in \ mathcal {K} ^ {（r）} \ setminus \ mathcal {K} ^ {（r + 1）} \提供\ left \ langle M、M '\ right \ rangle } = \ frac {\ Delta_ {r、r + 1} Q _ {\ mathrm {P} ^ {-1}、K}} {Q_K ^ {（r）}} \ leq \ frac {2l} {2 ^ n -2lm}。$

結論を導きます：

$E$ –ペア $\左\ラングP、C \右\ラング$ ステップで生成 $r$ キーが発生します $\下線{K}$ 悪くないことが判明し、確率は大きくない $2m /（2 ^ n-2lm）$ その後、キー $\下線{K}$ 少なくとも1つの結果として悪化します $l$ そのようなリクエスト（ $l = \左\ vert \、\ mathsf {E} \、\右\ vert$ ）、これ以上 $2lm /（2 ^ n-2lm）$ 。

同様に、キー $\下線{K}$ 少なくとも1つの結果として悪化します $m$ Oracleクエリ $\ mathrm {P}、$ $\ mathrm {P} ^ {-1}$ また、もう $2lm /（2 ^ n-2lm）$ 。次に、真のキーが生成される確率の上限を取得します $\下線{K}$ 一般的に、アルゴリズムの実行中に悪化します $\ mathrm {A}$ ：

$\ Pr {\下線{K} \ in \ mathcal {K} \ setminus \ mathcal {K} ^ {（l + m）}} \ leq \ frac {4 ^}-2lm}。$

別のケースでは、アルゴリズム $\ mathrm {A}$ 「推測」正しい $E$ –カップル $\左\ラングP、C \右\ラング$ ：

$\ pi（P \ oplus \下線{K} _1）\ oplus \下線{K} _2 = C$

後 $l + m$ キーを使用したクエリ $\下線{K}$ -セットに関して良い $\ mathsf {E} \ cup \ left \ langle P、C \ right \ rangle$ そして $\ mathsf {P}$ 。定義上、すべての間に適切なキーは存在しません $P$ –ペアセット $\ mathsf {P}$ そのようなペアではない $\左\ Langle M、M '\右\ rangle$ あれ $P \ oplus \下線{K} _1 = M$ どちらか $C \ oplus \下線{K} _2 = M '$ 。

置換値 $\ pi$ その時点で $P \ oplus \下線{K} _1$ に限定されない $P$ –多くのペア $\ mathsf {P}$ キーという事実のために $\下線{K}$ 良いと単一ではありません $E$ –「推測された」ペアという事実によるペア $\左\ラングP、C \右\ラング$ -新しい。だから $\ pi（P \ oplus \下線{K} _1）$ のいずれかを取ることができます $2 ^ n-（m + l）$ 「値」、および望ましい確率

$\ Pr {\左[\ pi（P \ oplus \下線{K} _1）= C \ oplus \下線{K} _2 \右]} = \ frac {1} {2 ^ n-（m + l）} = \ mathcal {O} \！\左（\ frac {lm} {2 ^ n} \右）。$

その後、成功の確率 $p _ {\ mathrm {A}}$ アルゴリズム $\ mathrm {A}$ ：

$p _ {\ mathrm {A}} \ leq \ frac {4lm} {2 ^ n-2lm} + \ frac {1} {2 ^ n-（m + l）} = \ bigo {\ frac {lm} {2 ^ n}}、$

証明する必要がある場合。

帰結2.1

代入してみましょう $\ pi$ からランダムに選択 $S _ {\左\ vert \、\ mathcal {P} \、\右\ vert}$ その後、任意のアルゴリズムの成功の確率 $\ mathrm {A}$ 問題を解決する $\ mathsf {EFP}$ そして、オラクルへのクエリの数によって多項式的に制限されます $\ mathrm {P}、$ $\ mathrm {P} ^ {-1}、$ $\ mathrm {E}、$ $\ mathrm {D}、$ 多項式が小さい。

擬似ランダム置換を使用したシステムの安定性 $\ pi$

[EM97]で提案されている暗号は、置換が行われても $\ pi$ 擬似ランダムに選択されます。

このステートメントを証明するには、擬似ランダム置換の概念を明確にすれば十分です。

定義

させる $\シグマ$ -ランダム置換、および $\デルタ$ -いくつかの代替から選択 $S _ {\左\ vert \、\ mathcal {P} \、\右\ vert}$ いくつかの不均一な分布法に従って、 $\ mathrm {P} _ {\ sigma}$ そして $\ mathrm {P} _ {\ delta}$ -それらを実現する神託。私たちは置換と言います $\デルタ$ オラクルを区別する多項式クエリ制限アルゴリズムがない場合は擬似ランダム $\ mathrm {P} _ {\ sigma}$ そして $\ mathrm {P} _ {\ delta}$ 。

言い換えれば、提示されたオラクルを使用した計算モデルでは、擬似ランダム置換はランダムと区別できません。したがって、次の定理が成り立ちます。

定理3

代入してみましょう $\ pi$ から擬似ランダムに選択 $S _ {\左\ vert \、{\ mathcal {P} \、\右\ vert}$ その場合、 $\mathrm{A}$ 問題を解決し、 $\mathsf{EFP}$ オラクルへのクエリの数によって多項式的に制限されているアルゴリズムの成功確率は、 $\mathrm{P},$ $\mathrm{P}^{-1},$ $\mathrm{E},$ $\mathrm{D},$ 多項式の小さいです。

続けて

はい、フラスコにはまだ火薬があります。Habréに興味のある人がいる場合、次のパートでは、この古典的なスキームの変更と、さまざまな暗号攻撃を検討することができます（ちなみに、以下で得られた推定値は正確であり、改善できないことを示しています）。

参照資料

非常に興味がある人のために：

Eli Biham、Yaniv Carmeli、Itai Dinur、Orr Dunkelman、Nathan Keller、およびAdi Shamir。2つのキーを使用した反復Even-Mansourスキームの暗号解析。IACR暗号化ePrintアーカイブ、2013：674、2013。
Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Francois-Xavier Standaert, John Steinberger, and Elmar Tischhauser. Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations. In Advances in Cryptology–EUROCRYPT 2012, pages 45–62. Springer, 2012.
Alex Biryukov and David Wagner. Advanced slide attacks. In Advances in Cryptology—EUROCRYPT 2000, pages 589–606. Springer, 2000.
Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, and John Steinberger. Minimizing the two-round Even-Mansour cipher. In Advances in Cryptology–CRYPTO 2014, pages 39–56. Springer, 2014.
Joan Daemen. Limitations of the Even-Mansour construction. In Advances in Cryptology—ASIACRYPT'91, pages 495–498. Springer, 1993.
Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2. In Advances in Cryptology-ASIACRYPT 2013, pages 337–356. Springer, 2013.
Orr Dunkelman, Nathan Keller, and Adi Shamir. Minimalism in cryptography: The Even-Mansour scheme revisited. In Advances in Cryptology–EUROCRYPT 2012, pages 336–354. Springer, 2012.
[EM97] Shimon Even and Yishay Mansour. A construction of a cipher from a single pseudorandom permutation. Journal of Cryptology, 10(3):151– 161, 1997.
Shoni Gilboa and Shay Gueron. Balanced permutations even-mansour ciphers. arXiv preprint arXiv:1409.0421, 2014.
Philip Hawkes and Luke O'Connor. Xor and non-xor differential probabilities. In Advances in Cryptology—EUROCRYPT'99, pages 272–285. Springer, 1999.
Nicky Mouha and Atul Luykx. Multi-key security: The Even-Mansour construction revisited. Technical report, Cryptology ePrint Archive, Report 2015/101, 2015.
Ivica Nikolic, Lei Wang, and Shuang Wu. Cryptanalysis of round-reduced LED. In Shiho Moriai, editor, Fast Software Encryption, volume 8424 of Lecture Notes in Computer Science, pages 112–129. Springer Berlin Heidelberg, 2014.

PSこの出版物の一部は、TeXで構成されており、Habrirジャムに課されています。あなたが気づいた場合-連絡先、私は修正します。

編集1.科学者の名前を修正しました、ありがとうalexyr。

暗号のミニマリズム、または偶数–マンスール方式

叙情的な余談

セット、セット

碑文

指定

定義

クラシックイーブン–マンスールスキーム

説明

回路の最小性について

回路耐久性について

永続性の前提、定義

正式なモデルの説明

復号化問題（ $\ mathsf {CP}$ ）

新しい平文/暗号文のペアを構築するタスク（ $\ mathsf {EFP}$ ）

テキスト/暗号文のペアを作成するタスクを剖検タスクに削減（ $\ mathsf {EFP} \ varpropto \ mathsf {CP}$ ）

ランダム置換を使用したシステムの安定性 $\ pi$

擬似ランダム置換を使用したシステムの安定性 $\ pi$

続けて

参照資料

More articles:

暗号のミニマリズム、または偶数–マンスール方式

叙情的な余談

セット、セット

碑文

指定

定義

クラシックイーブン–マンスールスキーム

説明

回路の最小性について

回路耐久性について

永続性の前提、定義

正式なモデルの説明

復号化問題（ ）

新しい平文/暗号文のペアを構築するタスク（ ）

テキスト/暗号文のペアを作成するタスクを剖検タスクに削減（ ）

ランダム置換を使用したシステムの安定性

擬似ランダム置換を使用したシステムの安定性

続けて

参照資料

More articles:

復号化問題（ $\ mathsf {CP}$ ）

新しい平文/暗号文のペアを構築するタスク（ $\ mathsf {EFP}$ ）

テキスト/暗号文のペアを作成するタスクを剖検タスクに削減（ $\ mathsf {EFP} \ varpropto \ mathsf {CP}$ ）

ランダム置換を使用したシステムの安定性 $\ pi$

擬似ランダム置換を使用したシステムの安定性 $\ pi$