偽隨機函式與否？
我已經閱讀了現代密碼學 PRF 部分介紹（和範例 3.26）和 stackexchange( 1 , 2 )，但我仍然不完全知道如何證明它（有機率）
為了證明它是 PRF，我知道你必須證明沒有對手可以區分 $ F’_k(x) $ 從隨機函式或我顯示可能的攻擊。所以問題是（類似於書中的 3.10）：
令 F 為保長偽隨機函式。證明 $ F’_k(x): {0, 1}^{n} → {0,1}^{2n} $ 這樣 $ F’_k(x) = F_k(0^{n})||F_k(x) $ 是一個 $ F’_k(x) $ 鍵控偽隨機函式與否。在哪裡 || 表示連接。
到目前為止我所做的：不。考慮一個對手 A 輸入 $ r \in {0, 1}^{n} $ ，如果它的前 n 位為 0…0，則返回 1。在一個真正隨機的字元串上，它返回 1 和機率 $ 2^{-n} $ . 在偽隨機字元串上，它以機率 1 返回 1。然後對手有優勢 $ 1 - 2^{-n} $ 這違反了偽隨機性的定義（因為它不再可忽略不計？）。
我認為這是正確的，或者我沒有正確理解什麼？
如果是這種情況，我無法將其應用於 $ F’_k(x) = F_k(x)||F_k(\bar x) $ 在我在這裡找到的一篇論文上，例如 3.7.2。它說不，但我無法將它與我在課堂上學到的方法聯繫起來，但在我看來它是隨機的。我會說如果它的最後一位返回 1？我不完全確定。
實際上有兩種不同的方法可以做到這一點，我將為這兩種方法提供提示，並在劇透中提供額外提示：
第一種方法：再次考慮安全遊戲的定義，區分器可以對預言機進行多少次查詢？
您可以在兩個值上查詢該函式。如果你比較這兩個結果，是否有相似之處？一個真正的隨機函式會如何表現？
第二種方法：正如其他人在評論中所說，如果您查詢會發生什麼 $ F_k’(0^n) $ ?
自從 $ F_k(0^n) $ 是一個 PRF，你可以假設這實際上是一個真正的隨機函式。如果你兩次查詢一個真正隨機的函式會發生什麼？是否以某種方式可見 $ F_k’(0^n) $ ?
從您的上一條評論來看，我想這還不清楚：區分器可以查詢函式以獲取任何類型的 $ x $ ，隨心所欲 - 具有多項式時間算法的限制。他必須找出他得到的結果是來自真正的隨機函式還是來自 $ F_k’(.) $ ，只有 $ k $ 被隨機抽取。所以區分器只能做一件事：選擇 $ x $ 以一種巧妙的方式，使某些結構出現在一個結果中或多個結果中，如果它是 $ F_k’ $ - 隨機函式沒有。