如果 G 是安全 PRG 並且 G’ 是 G 的函式，那麼 G’ 是否安全？

例如：對於安全 PRG G，如果我有G'st G'(k) = G(k)||0，G'一定是安全的嗎？這個問題不僅適用於上述範例，還適用於任何其他可能性。我的想法是，既然G是安全的（ADV 可以忽略不計，PRG 是不可預測的），那麼無論我做什麼G，G'都是G'安全的。

提示：考慮函式 $ G’(k) = f(G(k)) $ ， 在哪裡 $ f(x) = 0 $ 對全部 $ x $ . 清楚地， $ G’ $ 是一個函式 $ G $ . 是 $ G’ $ 一個安全的 PRG？

當然不是。我們可以將一個簡單的統計檢驗 A 定義為：

A(x)：如果x的最後一位是0輸出1。否則輸出0。那麼

$$ Pr[A(G(k)) = 1]= 0 $$ 對於隨機 $ k \in K $ ， 在哪裡 $ K $ 是關鍵空間，並且 $$ Pr[A(r)=1 ]=1/2 $$ 對於隨機 $ r \in {0,1}^n $ . 所以 $$ ADV(A,G) = |0-1/2| = 1/2 $$ 這顯然是不可忽略的。

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