獨立的偽隨機發生器
用兩個不同的值播種偽隨機數生成器 (PRNG) 是否足以聲稱我們現在有兩個獨立的 PRNG？還是我們必須為此使用兩個功能不同的生成器？
偽隨機生成器 (PRG) 的標準加密工程近似 $ f\colon {0,1}^k \to {0,1}^n $ 為了 $ k \lll n $ 是如果你選擇兩個獨立的統一隨機鍵 $ K_0 $ 和 $ K_1 $ ，然後輸出 $ f(K_0) $ 和 $ f(K_1) $ 也是獨立的均勻隨機位串。
這適用於例如AES-CTR 偽隨機生成器
$$ f(K) = \operatorname{AES256}_K(0) \mathbin\Vert \operatorname{AES256}_K(1) \mathbin\Vert \cdots, $$假如 $ n \lll 2^{72} $ 避免生日區分。 但是，並非簡單地選擇兩個不同的鍵 $ K_0 $ 和 $ K_1 $ 給出兩個獨立均勻隨機數的近似值 $ n $ -位字元串 $ f(K_0) $ 和 $ f(K_1) $ 在預期的安全級別，首先是因為如果對手知道密鑰 $ K_0 $ 和 $ K_1 $ 那麼攻擊者就沒有什麼隨機的了，而且因為即使這兩個密鑰僅僅具有攻擊者已知的關係，那麼Biryukov 和 Khovratovich 的標準 AES-256 相關密鑰攻擊可能適用於使攻擊者能夠區分 $ f(K_0) $ 和 $ f(K_1) $ 從兩個獨立的均勻隨機 $ n $ -bit 字元串比一般攻擊更快。 另一方面，您通常可以使用偽隨機函式族(PRF) 而不是偽隨機生成器從單個鍵中獲取多個獨立字元串。 例如，您可以將上述構造中對 AES256 的輸入拆分為 64 位字元串索引 $ i $ 和一個 64 位塊計數器，並定義
$$ F(K, i) = \operatorname{AES256}_K(i \mathbin\Vert 0) \mathbin\Vert \operatorname{AES256}_K(i \mathbin\Vert 1) \mathbin\Vert \cdots. $$ 然後，只要您從中生成的數據總量 $ F $ 單鍵遠小於 $ 2^{72} $ 位， $ F(K, 0) $ 和 $ F(K, 1) $ 是近似獨立的均勻隨機位串，只要 $ K $ 是均勻隨機的 $ k $ -位字元串不用於任何東西，除了 $ F $ 鑰匙。 這一切都取決於 $ f $ 或者 $ F $ 當然，實際上是加密安全的。如果你使用線性同餘發生器或梅森撚線器，你就死定了。但是像 ChaCha 或 KMAC 這樣的標準 PRF，或者像 AES 這樣的 PRP（偽隨機排列族），被推測對於上述“CTR 模式”構造是安全的 $ f $ 和 $ F $ .
顯然，在嚴格的機率解釋中，不可能得到兩個獨立的均勻隨機串 $ n > k $ 比特作為一個均勻隨機字元串的確定性函式 $ k $ 位。為了形式化這一點（在具體設置中），我們量化了隨機算法的對抗優勢 $ A\colon {0,1}^n \to {0,1} $ 試圖判斷其輸入是否來自於 $ f $ 與否，定義為
$$ \operatorname{Adv}^{\operatorname{PRG}}_f(A) = |\Pr[A(f(K)) = 1] - \Pr[A(U) = 1]|, $$在哪裡 $ K $ 是均勻隨機的 $ k $ -位串和 $ U $ 是均勻隨機的 $ n $ 位字元串。然後我們嘗試設置一個非常小的上限 $ \operatorname{Adv}^{\operatorname{PRG}}f(A) $ 對所有人 $ A $ ，或者通過推測它 $ f $ 作為一個原始的並吸引許多密碼分析家花精力在它上面，或者通過建構 $ f $ 出自密碼分析家已經花費精力研究的一個原語，並展示了一個區分器如何 $ f $ 作為一個 PRG 可以用來構造一個有效的算法來打破原語。 （為了將其擴展到復雜性理論家喜歡閒逛的漸近設置，我們考慮一系列函式 $ f_k\colon {0,1}^k \to {0,1}^{p(k)} $ 對於一些多項式 $ p $ ，並嘗試證明 $ \operatorname{Adv}^{\operatorname{PRG}}{f_k}(A) < \epsilon(k) $ 對於一些可以忽略的功能 $ \epsilon $ .)