Katz/Lindell 問題 7.6

讓 $ f $ 是一個保持長度的單向函式，並且讓 $ \text{hc} $ 成為一個核心謂詞 $ f $ . 定義 $ G $ 作為 $ G(x)=f(x)|\text{hc}(x) $ . 是 $ G $ 一定是偽隨機生成器？

答案是肯定的，如果 $ f $ 是根據書中定理 7.6的偽隨機排列。我相當肯定答案是否定的 $ f $ 不再是雙射的。直覺地說，字元串的第一部分 $ G(x) $ 如果我們選擇一個均勻隨機的，則不再是均勻分佈的 $ x $ ， 所以 $ G $ 一般不應該是偽隨機的。但是，我認為這可能取決於多遠 $ f $ 偏離雙射性，如以下兩個極端情況所示：

1. 如果 $ f $ 是恆定的（取一個值 $ y_0 $ )，那麼一個明顯的區別就是輸出的完成 $ 1 $ 如果字元串的第一部分 $ G(x) $ 是 $ y_0 $ . 這有優勢 $ 1-2^{-n+1} $ ，這是不可忽略的。當然，問題在於 $ f $ 顯然不是單向函式。
2. 如果 $ f $ 恰好錯過了它的共域的一點，然後有一些 $ y_0 $ 恰好被擊中兩次。那麼上例的區分器有優勢 $ 2\cdot 2^{-n+1}-2^{-n+1} = 2^{-n+1} $ ，可以忽略不計。我也想不出更好的區分器。

讓 $ g(x) $ 是一個保持長度的單向函式。然後 $ f(b||x)=1||g(x) $ （在哪裡 $ b $ 是一位輸入）是一個保持長度的單向函式，並且 $ \text{hc}(b||x)=b $ 是一個核心謂詞 $ f $ . 但 $ G(b||x)=f(b||x)|\text{hc}(b||x) $ 不是偽隨機生成器。

所以這個問題的答案是否定的。

編輯：我原來的回答並沒有證明反例 $ f $ 實際上有一個核心謂詞。

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