計算不可區分性：函式參數是否已知？
我想澄清一下關於計算不可區分性和偽隨機數生成器的定義。假設我們想證明形式的線性同餘生成器 $ x_t = ax_{t-1} + b \pmod m $ 不是偽隨機數生成器**。**然後我們希望證明給定一個數字序列 $ x_0, x_1, \ldots $ ，我們可以區分這些數字是來自上面的 lcg 過程，還是來自均勻分佈（在多項式時間內，具有高機率等……）。
在這樣做時，我們是否假設給定了參數 $ a,b $ 和 $ m $ ? 一方面，如果給我們這些參數，那麼這不是微不足道的嗎？只需檢查給定的序列是否滿足給定的 lcg…另一方面，即使我們不知道 $ a,b,m $ ，顯然仍然存在一個多項式時間算法，它恰好有 $ a,b,m $ 硬編碼到其中，可用於將這些序列與真正隨機的序列區分開來。
這裡的正確解釋是什麼？從計算不可區分的意義上來說，問 LCG 是否是偽隨機生成器是否有意義？
簡短的回答
區分器僅在一個均勻選擇的適當長度的種子上給出生成器的輸出，以及與生成器的輸出具有相同長度的真正隨機字元串。所以，不，沒有給出區分符 $ a $ , $ b $ 和 $ m $ . 但是，正如您所注意到的，我們仍然可以考慮使用硬編碼這些值的算法，這個問題可以通過在生成器的每次執行時隨機選擇新參數來解決（另請參見下面的最後一段）。
長答案（我的定義來自 Goldreich 的書）
首先，計算不可區分性。請記住，機率集合是一系列隨機變數 $ X_0,X_1,X_2,\dots $ , 我們注意到 $ {X_n}_{n\in \mathbf{N}} $ . 一般來說， $ X_n $ 表示某個機率算法在某個長度的輸入上的輸出 $ n $ （通常要麼等於 $ 1^n $ 或統一選擇）。
兩個機率集合 $ X = {X_n}{n\in \mathbf{N}} $ 和 $ Y = {Y_n}{n\in \mathbf{N}} $ 如果對於每個機率多項式時間算法，則在計算上無法區分（在多項式時間內**）** $ D $ , 每個多項式 $ p $ 並且都足夠大 $ n $ ， 我們有
$$ \left|\mathrm{Pr}[D(X_n,1^n) = 1] - \mathrm{Pr}[D(Y_n,1^n) = 1]\right| < \frac{1}{p(n)}. $$
我們還沒有給隨機變數賦予“意義” $ X_n $ 和 $ Y_n $ , 但是我們可以說這個定義非正式地意味著以下。在一個整數上 $ n $ ，區分器被給出“算法”的輸出 $ X $ 或者 $ Y $ 在長度的輸入上 $ n $ （也 $ n $ 本身是一元形式的），並嘗試猜測字元串是否是 $ X $ 或輸出 $ Y $ . 我們可以不失一般性地說算法輸出 $ 1 $ 如果它猜測字元串是 $ X $ ， 和 $ 0 $ 否則。然後顯然是一種算法，可以可靠地區分輸出 $ X $ 和輸出 $ Y $ 會違反定義。
在下面的， $ U_n $ 表示在所有長度字元串上均勻分佈的隨機變數 $ n $ .
機率集合 $ X = {X_n}{n\in\mathbf{N}} $ 如果有函式是偽隨機的 $ \ell : \mathbf{N}\to\mathbf{N} $ 這樣 $ X $ 和 $ {U{\ell(n)}}_{n\in\mathbf{N}} $ 在計算上是無法區分的。
請注意，在這裡，在區分實驗中 $ n $ , $ D $ 給出 $ (X_n,1^n) $ 在一側和 $ (U_{\ell(n)},1^n) $ 在另一。向前跳躍， $ \ell(n) $ 將是長度為種子的偽隨機生成器的輸出長度 $ n $ ， 和 $ X_n $ 將是輸出本身。然後 $ D $ 必須區分 $ X_n $ ，生成器的輸出，和 $ U_{\ell(n)} $ ，長度等於輸出長度的統一字元串（與 $ U_n $ ，它是長度等於種子的長度的統一字元串）。
偽隨機生成器是一種確定性多項式時間算法 $ G $ 滿足以下兩個條件。
- **擴大輸入。**有一個功能 $ \ell:\mathbf{N}\to\mathbf{N} $ 這樣 $ \ell(n) > n $ 對於所有整數 $ n $ 和 $ |G(s)| = \ell(|s|) $ 對於所有字元串 $ s $ .
- **輸出的偽隨機性。**機率集合 $ {G(U_n)}{n\in\mathbf{N}} $ 和 $ {U{\ell(n)}}_{n\in\mathbf{N}} $ 在計算上是無法區分的。
的輸入 $ G $ 是種子，所以是長度的種子 $ n $ $ G $ 產生一個長度的“偽隨機字元串” $ \ell(n) $ . 只要 $ s $ 被統一選擇， $ G(s) $ 在計算上與長度一致的字元串無法區分 $ \ell(|s|) $ . 並且只給出了區分符 $ G(U_n) $ （即， $ G(s) $ 對於一個統一選擇的 $ s $ 長度 $ n $ ） 和 $ 1^n $ ， 沒有其他的。
還要注意，在這個定義中，輸入的大小沒有限制 $ G $ ，但如果你使用固定模數 $ m $ , 你不能有意義地處理大於 $ m $ . 這裡的解決方案也是在生成器的每次執行時生成適當長度的參數。
你是對的：如果你知道設置，計算任何給定的下一個輸出 $ x $ 是完全確定的，你已經知道了一切。
即使你不知道 $ a $ 和 $ b $ ，這些很容易從三個連續的 $ x_i $ . 如果 $ n $ 不知道，它的計算還是很容易的，給定幾個連續的 $ x_i $ .
無論如何，LCG 非常不適合加密任務。這就是為什麼在幾乎每個標準庫中，您都會發現不要將標準 Random 類用於加密協議的警告（至少對於 Java 和 Python，我知道這些警告存在）。
通常不會使用整個輸出，而只使用其中的一部分，因為否則兩個連續的數字不能相等（並且之後會再次更改）。這樣的 RNG 對於幾乎所有需要隨機性的非安全相關上下文來說已經足夠好了（它對於一點隨機性來說已經足夠了。但是例如在需要大量隨機數的模擬中，你想要“更好”的隨機性，例如來自Mersenne Twister）。無論如何，基於任何此類構造的可預測 PRNG（沒有CS ）都不適合密碼學。對於 CSPRNG，您可以在wikipedia上找到一些設計。