密碼學偽隨機發生器範例問題 - 證明
對於 ii) G2 被證明是 PRG，似乎 G5 的解決方案使用 G2。
有人可以嘗試向我解釋我得到的解決方案嗎？我特別不明白如何計算給定的機率：
另外，我知道要證明錯誤，您可以舉一個反例。但是有沒有更正式的證明方式呢？
我將閱讀問題陳述為
$ G $ 是一個PRG。決定每個 $ i $ 無論 $ G_i $ 始終是 PRG 並證明答案：
（ii） $ G_2(s):=G(s_1\ldots s_{|s|-1})\mathbin|s_{|s|} $
（在） $ G_5(s):=G(s)\mathbin|G(s+1) $ 在哪裡 $ + $ 表示二進制數的加法。
$ G_2 $ 是一個PRG。直覺的論點：如果輸入 $ G_2 $ 是均勻隨機位，那麼它的整個輸出與隨機沒有區別，因為最右邊的位直接作為隨機輸入的最右邊的位，而所有其他位都是因為它們是一個以其他輸入位為種子的 PRG 的輸出（至關重要的是，它們是獨立的）。這可以通過將假設的區分符轉換為 $ G_2 $ 成為區分器 $ G $ （並顯示輸出 $ G_2 $ 比它的輸入更廣泛，以及 PRG 的定義所要求的任何其他技術性）。
引用的解決方案以
對於每一個 $ s $ 最後一位為零，我們有 $ G_2(s)\mathbin|G_2(s+1)= $ $ G(s_1\ldots s_{|s-1|})\mathbin|0\mathbin|G(s_1\ldots s_{|s-1|})\mathbin|1 $
但這沒有關於符號或意圖的解釋，並且有錯別字。
關於符號：位串 $ s $ 的 $ |s| $ 位被同化為一個元素 $ \Bbb Z_{2^{|s|}} $ 根據大端約定，第一個/左/最高有效位從 1 開始編號： $$ s=\displaystyle\sum_{i=1}^{|s|},s_i,2^{|s|-i} $$
意圖：計算什麼 $ G_5 $ 在兩個假設下
- 它僅限於輸入 $ s $ 的 $ G_5 $ 它的最後一位為零，這意味著 $ s_{|s|}=0 $ 或等效地 $ s $ 被同化為偶數，因此 $ s $ 和 $ s+1 $ 是相同的位串，除了位 $ s_{|s|} $
- 和 $ G_5 $ 是從形式的 PRG 建構的 $ G_2 $ , 本身由 PRG 建構而成 $ G $ 即使它的輸出比 $ G $ (v) 中的問題陳述
更換 $ G_5 $ 然後 $ G_2 $ 根據他們的定義，它來了
$$ \begin{align}G_5(s)&=G_2(s)\mathbin|G_2(s+1)\ &=G(s_1\ldots s_{|s|-1})\mathbin|0\mathbin|G(s_1\ldots s_{|s|-1})\mathbin|1 \end{align} $$
關於錯別字：在那個公式中，我們有兩次 $ |s|-1 $ 問題的解決方案在哪裡 $ |s-1| $ .
現在應該直覺地清楚 $ G_5 $ 不一定是PRG。該公式表明，如果 $ G_5 $ 由特殊形式的 PRG 建構而成 $ G_2 $ ，並且其輸入的最後一位為零，則輸出 $ G_5 $ 有兩個相同的一半，除了最後一位（ $ 0 $ 對於左半邊和 $ 1 $ 右半邊）。這個特性允許建立一個好的區分器（假設 $ |s|\ge2 $ 在輸入 $ G_5 $ ）。我們將詳細證明這一點。
區分器是一種確定性算法 $ D $ 它接受與待測 PRG 的輸出一樣寬的雙字元串作為輸入，並輸出 0 或 1。它的優點 $ \operatorname{Adv}(D) $ 根據定義，它在兩種情況下輸出 1 的機率在絕對值上相差多少：
- 區分器接收待測 PRG 的輸出作為輸入，它本身接收真正隨機的輸入位作為輸入；
- 區分器接收真正的隨機位作為輸入。
作為一個公式： $ \operatorname{Adv}(D)=\big|,\Pr[D(G(s))=1]-\Pr[D(r)=1],\big| $
左機率是在所有位串上計算的 $ s $ 與待測 PRG 的輸入一樣寬 $ G $ . 對所有位串計算正確的機率 $ r $ 與輸出一樣寬 $ G $ . 這 $ |\quad| $ 表示法代表實數的絕對值，而不是位串的長度 $ s $ 如在 $ |s| $ .
區分者 $ D $ 問題的解決方案提出的輸出 1 如果其輸入的兩半除了它們的正確位之外是相同的。測試發電機時 $ G_5 $ 考慮的特殊形式，當生成器輸入的最右邊位是 $ 0 $ ， 因此 $ \Pr[D(G_5(s))=1]\ge\frac12 $ ; 而如果輸入 $ D $ 是 $ 2n $ 位和 $ n\ge1 $ , $ \Pr[D(r)=1]=2^{-(n-1)} $ （因為在計算該機率的實驗中，比較了兩個隨機獨立的位串 $ n-1 $ 位）。所以 $ \operatorname{Adv}(D)\ge\big|,\frac12-2^{-(n-1)},\big|=\frac12\left(1-2^{-(n-2)}\right) $ ，這是一個相當大的優勢（至少 $ \frac14 $ 為了 $ n\ge3 $ ).
建議的解決方案至少說明 $ \frac12\left(1-2^{-(n-1)}\right) $ ，這是一個更好的優勢。這是可以實現的，但需要準確計算優勢，或/和更好的區分器，這留給讀者練習。
我知道要證明錯誤，您可以舉一個反例。但是有沒有更正式的證明方式呢？
反例是反駁某事的最簡單和最正式的方式。在密碼學中，它是最好的。其他領域也有例外。