Pseudo-Random-Function
為什麼 G 不是安全的偽隨機函式？
讓 $ F(k,x) $ 是一個安全的偽隨機函式定義在 $ {0,1}^n $ ，這意味著：
$ F: {0,1}^n \times {0,1}^n \rightarrow {0,1}^n $
定義一個 $ G(k,x) = F(k,x) ; \Vert ; 0 $
如何證明 $ G $ 不安全？
在我看來，如 $ F $ 是安全的， $ G $ 總是會導致一些安全輸出後跟 0，換句話說，我的意思是：
如果你猜不出是什麼 $ X $ 是，你不會猜到是什麼 $ ;X ; \Vert ; 0; $ 是。
但正如我被要求證明的那樣 $ G $ 不安全，顯然我的想法有問題。
問題是 $ G $ 很容易與隨機函式區分開來。假設我們有一個預言機，它要麼應用隨機函式，要麼應用你的 PRF（在遊戲開始時選擇）。我們查詢預言機 $ n $ -時代與 $ n $ 不同的輸入，如果所有最後一位都是 $ 0 $ 然後我們說oracle使用PRF。為了證明你需要計算的不安全感
$ Adv_F(A):=Pr[\text{you guess it’s G | Oracle uses G}]-Pr[\text{you guess it’s G | Oracle uses random RF}] $ .
第一個機率等於 $ 1 $ （如果 $ A $ =攻擊者使用建議的方法）。第二個機率以指數方式變為零，因此 $ n $ 足夠高（在這種情況下甚至 $ n=4 $ 提供足夠的優勢）的優勢 $ \textit{significantly} $ 不同於RF的優勢。
“真實”世界範例：假設您在計數器模式下使用 F(k,x) 作為分組密碼。然後，您只需查看密文即可有效地了解明文的每一位。