你能幫我理解這個偽隨機生成器的例子嗎？
我是加密新手。我正在根據“現代密碼學簡介”一書學習。我在理解 PRG 以及如何證明某個函式是否是 PRG 方面遇到了麻煩。
我正在嘗試解決這個簡單的範例：
G(x1,x2…xn) = x1,x2,…xn, x1 xor x2 xor x3… xor xn
G是PRG嗎？
好吧，根據這本書我需要檢查是否
[數學處理錯誤]$$ |Pr[D(r)=1]-Pr[D(G(s))=1| <= negl(n) $$ 在哪裡 $ r $ 均勻地隨機選擇 $ {0,1}^|G(s)| $
種子 $ s $ 均勻地隨機選擇 $ {0, l}^n $ ，
並且機率被接管使用的隨機硬幣[DMath Processing Error]和選擇[rMath Processing Error]和[sMath Processing Error]. $ D $ $ r $ $ s $
但我不知道如何計算 $ D(r) $ 和 $ D(G(s)) $ ……我覺得我在這裡錯過了一些東西。你能幫我理解我錯過了什麼嗎？
假設你的問題是 $ G(x_1,x_2,…,x_n) = x_1,x_2,…,x_n, x_1 \oplus x_2 \oplus x_3 … \oplus x_n $
是一個PRG。[Math Processing Error] $ D $ 是一些固定的機率多項式時間區分器。
所以要證明 $ G(.) $ 是一個 PRG，你需要證明對於所有這樣的區分， $ D(G(.)) $ 無法區分 $ D(.) $ .
例如 [|Pr[D(G(s))=1]−Pr[D(s)=1]|⩽negl(n)Math Processing Error]在哪裡 $ \big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| \leqslant negl(n) $ $ s \leftarrow {0,1}^n $
反之顯示 $ G(.) $ 不是 PRG 你只需要辨識一個區分符 $ D(.) $ 使得上述等式不成立。
在這種情況下， $ G(.) $ 看起來它可以與隨機分佈區分開來，因為輸出只是輸入，然後是輸入的異或。
IE $ D(.) $ 是一些輸出的函式 $ 1 $ 如果輸出的最後一位是前面所有位的異或。這在應用於隨機分佈的時間中是正確的，但對於隨機分佈總是正確的 $ G(.) $ . 這將意味著[|Pr[D(G(s))=1]−Pr[D(s)=1]|=|1−0.5|=0.5Math Processing Error] $ \big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| = \big| 1 - 0.5 \big| = 0.5 $
由於一半不可忽略，我們可以說 $ G(.) $ 不是PRG。