如何證明函式 F 不是偽隨機函式？

讓 $ F $ 是一個保長偽隨機函式。對於鍵控函式的以下結構 $ F’ : {0, 1}^n \times {0, 1}^{n−1} \to {0, 1}^{2n} $ , 說明是否 $ F’ $ 是一個偽隨機函式。如果是，證明它；如果沒有，顯示攻擊。

$$ F’_k(x) = F_k(0 ∥ x) ∥ F_k(1 ∥ x) \tag{a} $$

和

$$ F’_k(x) = F_k(0 ∥ x) ∥ F_k(x ∥ 1) \tag{b} $$

我不想要解決方案：我想了解如何解決這種類型的練習。

您的標題詢問“如何證明函式 F 不是偽隨機函式”，在您的問題中，情況 (b) 不是易於證明的 PRF。功能 $ F’ $ 如果對於所有PPT 區分者，則為 PRF $ D $ ，成功機率為 $ D $ 區分 $ F’ $ 從隨機函式可以忽略不計。所以為了證明這個函式 $ F’ $ 不是 PRF，它足以建構一個成功機率不可忽略的區分器（它查詢它的預言並尋找非隨機模式）。

相比之下，情況 (a) 是 PRF，它更難證明。用於證明函式 $ F’ $ 是@fkraiem提到的PRF假設 $ F’ $ 不是 PRF 並且 $ D’ $ 是區別於 $ F’ $ 然後構造一個算法 $ A $ 這打破了一些假設（區分 $ F $ 從這裡的隨機函式打破了假設 $ F $ 是PRF）。

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