這些函式是偽隨機的嗎？為什麼或者為什麼不？
所以我被困在這個問題上，對正確答案是什麼或如何證明它完全沒有直覺。任何幫助，將不勝感激。
讓 $ F $ 是一個保長偽隨機函式。對於以下鍵控功能的構造 $ F’:{0,1}^n\times{0,1}^{n-1}\rightarrow{0,1}^{2n} $ , 說明是否 $ F’ $ 是一個偽隨機函式。
一個。 $ F_k’(x)=F_k(0||x)||F_k(1||x) $
灣。 $ F_k’(x)=F_k(0||x)||F_k(x||1) $
我的一點直覺讓我認為 a 不是偽隨機的，但 b 是因為在 a 中你知道 a 1 最初在中間所以也許這有幫助，但我不知道為什麼。它主要只是一個瘋狂的猜測。
（這裡 || 表示連接）
無論 $ F′ $ 偽隨機函式是圍繞著：能否有效地區分隨機函式？也就是說，你能不能設計一個實驗（鑑別器），它有比隨機更好的機會來辨識一個盒子計算 $ F_k′(x) $ 給定 $ x $ 對於一些隨機未知的固定 $ k $ ，從一個計算一些隨機函式（隨機預言）？
對於您的兩種情況之一，您可以，因此 $ F’ $ 不是偽隨機生成器。為了證明這一點，只需找到並揭示你的區分器是如何工作的，並證明它比隨機的更好。
提示 1：一種方法是找到一些不同的 $ x $ 這樣 $ F_k $ 將使用相同的輸入進行評估，並從 $ F_k’ $ .
提示 2：在目前情況下，所述數字至少為 2。
提示 3：區分器比隨機器效果更好的證明需要 $ n>2 $ ，可以假設。
對於另一種情況，您不能製作一個 distincter ，因此 $ F′ $ 是一個偽隨機生成器。通常的形式證明技術是對立：假設一個區分器 $ F′ $ ，並為 $ F $ ，假設不存在。
在這裡，有一種更直覺的方法： $ F_k’(x) $ 由輸出的串聯構成 $ F_k $ ; 並且這樣的輸出與隨機無法區分（對於一個不知道 $ k $ )，除了相同的輸入 $ F_k $ 產生相同的輸出。因此，如果輸出 $ F_k $ 每當我們評估時，都是針對不同的輸入 $ F_k’ $ 對於不同的輸入，則總輸出 $ F_k’ $ 對於不同的輸入與隨機輸入無法區分，並且 $ F’ $ 是偽隨機的。