計算不可區分性問題

我的定義是：

兩個機率集合 $ X = {X_n}{n \in \mathbf{N}} $ 和 $ X = {Y_n}{n \in \mathbf{N}} $ 如果對於每個機率多項式時間算法，則在計算上無法區分 $ D $ , 每個正多項式 $ p(\cdot) $ , 並且都足夠大 $ n $ 我們有

$$ |P(D(X_n, 1^n) = 1) - P(D(Y_n, 1^n) = 1) | < \frac{1}{p(n)}. $$ 我無法消化這裡的一些想法和符號。

做 $ X = {X_n}_{n \in \mathbf{N}} $ 意思是 $ X = X_1, X_2, \ldots $ 其中每個 $ X_i $ 來自同一個分佈？所以如果我們的 $ X $ 分佈是 $ 0-1 $ 硬幣翻轉，然後 $ X $ 是一個無限的序列 $ 0 $ 沙 $ 1 $ 年代？

註釋說“通常，每個 $ X_n $ 範圍超過長度的字元串 $ poly(n) $ ”。這是什麼意思？分配將採取 $ n $ 作為某種輸入？在我的擲硬幣範例中，每個 $ X_i $ 只給我們一點點……

我也想問為什麼 $ 1^n $ 作為區分器的輸入是必要的 $ D $ ，但我可能應該先了解上述問題的答案。

不， $ X = {X_n}_{n \in \mathbf{N}} $ 方法 $ X = X_1, X_2, \ldots $ 其中每個 $ X_i $ 是一個分佈。

所以可以讓每個 $ X_i $ 是長度字元串的均勻分佈 $ i $ .

這意味著有一個多項式 $ q $ 這樣對於所有人 $ n $ 和 $ x $ ， 如果 $ X_n $

將非零機率分配給 $ x $ 然後的長度 $ x $ 最多是 $ q(i\hspace{.02 in}) $ .

分佈確實“採取 $ n $ 作為某種輸入”。

看到這兩個問題_ $ 1^n $ .

$ P(D(X_n, 1^n) = 1) $ 表示以下算法返回的機率 $ 1 $ :

1. 樣本 $ x $ 根據 $ X_n $ .
2. 跑 $ D(x, 1^n) $ .
3. 隨便輸出 $ D $ 輸出。

例如說 $ X_n $ 是均勻分佈 $ {1,2,3,4} $ ， 和 $ D(x,1^n) $ 如下：

1. 如果 $ x $ 是奇數，輸出 $ x $ 或者 $ x+1 $ , 每個都有機率 $ 1/2 $ .
2. 如果 $ x $ 是偶數，輸出 $ x $ .

然後 $ P(D(X_n, 1^n)=1) $ 是 $ 1/8 $ （我們需要選擇 $ x=1 $ , 這發生在機率上 $ 1/4 $ ，然後輸出 $ x $ 有機率 $ 1/2 $ ).

我不認為你的例子是每個 $ X_i $ 定義在 $ {0,1} $ 會很有啟發性。一般來說， $ X_n $ 是某種算法在輸入上的輸出 $ n $ ，例如密碼系統的密鑰生成算法，其中 $ n $ 是所需的密鑰長度。然後是字元串的長度 $ X_i $ 被定義為真的是 $ \mathsf{poly}(i) $ .

在這種情況下 $ X_i $ 和 $ Y_i $ 是算法的輸出，定義的思想是 $ D $ 無法可靠地判斷它獲得的字元串是否已由 $ X $ 或通過 $ Y $ .

引用自：https://crypto.stackexchange.com/questions/20464