計算的に制限された敵対者

情報理論において、計算量的に制限された敵対者問題とは、ノイズの多いチャネルを介してデータを送信する問題に対する別の見方です。以前のモデルでは、最大d /2 個のエラー (d はコードのハミング距離)まで正しくデコードすることを保証するのが最善でした。この方法の問題は、敵対者が利用できる実際の計算能力が考慮されていないことです。むしろ、メッセージを正しくデコードしながら、特定のコード ワードのビットをいくつ変更できるかということだけが問題になります。計算量的に制限された敵対者モデルでは、チャネル (敵対者) は、コード ワードのどのビットを変更する必要があるかを決定するために、妥当な量の計算のみを実行できることに制限されます。言い換えると、このモデルでは、処理可能なエラーの数を考慮する必要はなく、敵対者の計算能力が妥当な量である場合に、どれだけのエラーが導入される可能性があるかだけを考慮する必要があります。チャネルにこの制限が与えられると、以前の方法と比較してエンコードとデコードが高速で、多数のエラーも処理できるコードを構築できるようになります。

一見すると、最悪のケースのモデルは直感的に理想的に思えます。アルゴリズムが何があっても成功するという保証は、もちろん非常に魅力的です。しかし、それはあまりにも多くのことを要求します。現実の敵は、アルゴリズムが対処に苦労する 1 つのエラー パターンを見つけるために、メッセージを調査するのに無限の時間を費やすことはできません。

比較のために、クイックソートアルゴリズムについて考えてみましょう。最悪のシナリオでは、クイックソートは O( n ² ) 回の比較を行いますが、そのようなことが起こるのはまれです。クイックソートは、ほぼ常に O( n  log  n ) 回の比較を行い、O( n  log  n ) の動作を保証できる他のアルゴリズムよりも優れています。攻撃者がクイックソート アルゴリズムに O( n ^{2 ) 回の比較を行わせたいとします。その場合、入力文字列の}n ! 通りの順列をすべて検索し、アルゴリズムの実行速度が大幅に低下する順列が見つかるまで、各順列でアルゴリズムをテストする必要があります。しかし、これには O( n !) 時間がかかるため、攻撃者がこれを行うのは明らかに不可能です。同様に、エンコードおよびデコード システムの攻撃者が、最も効果的なエラー パターンを見つけるために、すべてのエラー パターンをテストできると想定するのは不合理です。

確率的ノイズ モデルは、一種の「愚かな」ノイズ モデルと言えます。つまり、「インテリジェントな」脅威に対処する適応性がありません。攻撃者が制限されている場合でも、少しの巧妙さで確率的モデルを克服できる可能性があります。確率的モデルには、この種の攻撃に対抗する実際の方法がないため、防御策を講じることが望ましい「インテリジェントな」脅威に対処するのには適していません。

そのため、両者の妥協案として、計算的に制限された敵対的モデルが提案されている。^[1]これにより、メッセージが意識的に、さらには悪意を持って改ざんされる可能性があることを考慮する必要はありますが、アルゴリズム設計者が決して発生しない可能性のあるまれなケースについて心配する必要はありません。

計算量に制限のある攻撃者は、各ビットに対して O( n ) 時間でコインを投げることができるため、この攻撃者に対抗できるエンコードおよびデコード システムは、確率的ノイズ モデルでも機能するはずであることは直感的に明らかです。逆はそれほど単純ではありませんが、確率的ノイズ モデルで機能するシステムは、計算量に制限のある攻撃者に対しても効率的にエンコードおよびデコードできることが示されており、その場合の追加コストはnの多項式です。^[1]これを実現する次の方法は、Dick Lipton によって設計され、^{[1]から引用されています。}

を確率的ノイズ モデルのエンコーダーとし、を同じエンコーダーの単純なデコーダーとします。これらはそれぞれ多項式時間で実行されます。さらに、送信者と受信者の両方がランダムな順列関数とランダムなパターンを共有するものとします。 ${\displaystyle E()}$${\displaystyle D()}$${\displaystyle \pi}$${\displaystyle R}$

エンコードの場合: 1. とします。 ${\displaystyle X=E(M)}$

2. とします。 ${\displaystyle Y=\pi (X)\oplus R}$

3. 送信する${\displaystyle Y}$

次にデコードするには: 1. 受信します。計算します。 ${\displaystyle Y'}$${\displaystyle Z=\pi ^{-1}(Y'\oplus R)}$

2. 計算します。 ${\displaystyle M=D(Z)}$

上記のクイックソートの比較と同様に、チャネルが何か賢いことをしたい場合、最初にすべての順列をテストする必要があります。ただし、これは計算量に制限のある攻撃者にとっては実行不可能であるため、せいぜいランダムなエラー パターンを作成することしかできません。しかし、次のようになります。 ${\displaystyle N}$

${\displaystyle Z=\pi ^{-1}(Y'\oplus R)=\pi ^{-1}(Y\oplus N\oplus R),}$

定義によります。 ${\displaystyle Y'=Y\oplus N}$

${\displaystyle =\pi ^{-1}(Y\oplus R)\oplus N'}$、 どこ${\displaystyle N'=\pi ^{-1}(N),}$

任意の順列はXORに関して線形であるため、

${\displaystyle =X\oplus N',}$

上記の定義に従って。 ${\displaystyle Y}$

はランダムなので、は単なるランダムノイズであり、単純なデコーダーを使用して受信したメッセージをデコードし、 を返すことができます。 ${\displaystyle \pi}$${\displaystyle N'}$${\displaystyle M}$

計算上制限のある敵対者を想定することで、エラー確率が無視できるほどの、効率的かつ最適に近いローカルにデコード可能なコードを設計することが可能です。これらのコードは、自己修正計算、確率的にチェック可能な証明システム、疑似乱数生成器の構築における最悪ケースから平均ケースへの困難性の削減など、複雑性理論で使用されます。これらは、プライベート情報検索プロトコルとの関連により、暗号化にも役立ちます。また、フォールトトレラントデータストレージなどの多くのデータベースアプリケーションにも使用されています。^[2]

さらに、最悪の場合のコードの既知の限界を超えるコード、具体的には、エラー率のある一意のデコードを構築することも可能です。^[3] これは、タイムスタンプ付きのデジタル署名をメッセージに連結することで実現できます。計算的に制限されたチャネルは署名を偽造できません。また、有効な過去の署名を持っている場合でも、受信者はリストデコードを使用して、署名に正しいタイムスタンプがある場合にのみメッセージを選択できます。 ${\displaystyle 1-R}$

• コンクリートセキュリティ