計算上の区別不能性

計算複雑性と暗号化においては、無視できる確率を除いて 2 つの分布ファミリを区別できる効率的なアルゴリズムがない場合、それらの分布ファミリは計算上区別できません。

と を、セキュリティパラメータn (通常は入力の長さを参照)でインデックス付けされた2 つの分布アンサンブルとします。任意の非均一確率多項式時間アルゴリズムAに対して、次の量がnに関して無視できる関数である場合、これらは計算上区別できないと言えます。 ${\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N}}}$${\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N}}}$

${\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.}$

と表記される。^[1]言い換えれば、あらゆる効率的なアルゴリズムA の挙動は、の極限でD _nまたはE _nに従ってサンプルが与えられた場合、大幅に変化しない。計算上の区別不能性の別の解釈は、2 つの集団を積極的に区別しようとする多項式時間アルゴリズムが区別できないということである。つまり、そのようなアルゴリズムは、推測だけを行う場合よりもわずかに優れたパフォーマンスしか発揮しないということである。 ${\displaystyle D_{n}\approx E_{n}}$${\displaystyle n\to \infty }$

定義には、アルゴリズムが分布の 1 つから 1 つのサンプルに基づいて決定しなければならないという条件が暗黙的に含まれています。2 つの分布を区別しようとするアルゴリズムが、必要な数のサンプルにアクセスできる状況を想像してみてください。したがって、複数のサンプルを調べる多項式時間アルゴリズムでは区別できない 2 つのアンサンブルは、多項式時間サンプリングでは区別できないとみなされます。^{[2] :} 107多項式時間アルゴリズムが多項式時間でサンプルを生成できるか、またはサンプルを生成するランダムオラクルを利用できる場合、多項式時間サンプリングによる区別不能性は計算上の区別不能性と同等です。^{[2] : 108}${\displaystyle A}$

• イェフダ・リンデル. 暗号入門
• ドナルド・ビーバー、シルビオ・ミカリ、フィリップ・ロガウェイ、「セキュアプロトコルのラウンド複雑性（拡張要約）」、1990 年、503 ～ 513 ページ
• シャフィ・ゴールドワッサーとシルビオ・ミカリ「確率的暗号化」JCSS、28(2):270–299、1984
• Oded Goldreich . 暗号の基礎: 第 2 巻 - 基本的なアプリケーション。ケンブリッジ大学出版局、2004 年。
• ジョナサン・カッツ、イェフダ・リンデル、「現代暗号入門：原理とプロトコル」、チャップマン＆ホール/CRC、2007年

この記事には、Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMathの computeally indistinguishable からの資料が組み込まれています。