這是一個安全的 PRG 嗎？
我見過這個問題！從 2 年前開始：
給定 $ F $ 是一個 $ PRF $ ，我們定義 $ G $ 對於輸入 $ x\in{0,1}^n $ 如下：
$$ G(x) = F_k(x) \oplus F_k(x \oplus 1^s) $$
問題是如果 $ G $ 是一個 $ PRG $ . 我稍微編輯了這個問題以適應當時給出的答案。答案表明這不是 $ PRG $ 因為
$$ G(x\oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x\oplus 1^n \oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x)=G(x) $$現在因為 $ x $ ，種子，必須是隨機的，因為對手不能以任何方式影響種子。為什麼這不是一個 $ PRG $ ? 對於隨機均勻選擇 $ x $ 不應該的輸出 $ F_k $ 在輸入 $ x $ 和 $ x\oplus 1^n $ 是偽隨機的，因此 $ F_k(x) \oplus F_k(x \oplus 1^s) $ 也是偽隨機嗎？
我相信您誤解了相關的問題，並且可能誤解了 PRG 的定義。
PRG 映射一個鍵 $ K $ （也稱為種子）位長 $ l $ 成一個位序列 $ x\in{0,1}^n $ 位長 $ n $ . 如果生成的位序列 PRG 是安全的 $ x $ 在計算上與真正的隨機無法區分。
連結問題的答案表明，給定 PRG 的輸出很容易與隨機區分開來，因為 PRG 輸出的固定位置的兩個位對於任何密鑰都是相等的 $ K $ .
PS：可能像連結的問題這樣的問題隱含地假設了以下從 PRF 創建 PRG 的結構：
假設我們有一個 PRF $ F:K\times D \to R $ 哪個映射鍵 $ K={0,1}^l $ 和域 $ D={0,1}^n $ 進入範圍 $ R={0,1}^m $ . 現在，我們可以建構一個 PRG $ G: K\to {0,1}^{n+m} $ :
$$ G(k)[x]=F(k,x) $$ 注意 $ x $ 是一個論點 $ F $ 但不是 $ G $ ; 在 LHS 上 $ x\in{0,1}^n $ 表示長度為的位序列的位置 $ m $ 在 PRG 輸出中。
在最簡單的情況下 $ m=1 $ , 即 PRF $ F $ 只輸出一位： $ R={0,1} $ ， 和 $ x\in{0,1}^n $ 表示位位置 $ G $ 輸出。