計算上の区別不能性

コンピュータサイエンスにおいて、2つの分布族の関係

計算の複雑さと暗号化においては、効率的なアルゴリズムで、無視できる確率以外では 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}$

参考文献

1. 講義 4 - 計算上の区別不能性、疑似乱数生成器
2. Goldreich, O. (2003). 暗号の基礎. ケンブリッジ大学出版局. ケンブリッジ, イギリス.

外部リンク

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

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

「https://en.wikipedia.org/w/index.php?title=Computational_indistinguishability&oldid=1118763271」より取得