安全PRG的以下構造也是安全PRG嗎？
給定一個安全的 PRG $ G :\text{{0,1}}^n \rightarrow \text{{0,1}}^{2n} $ ，我建構了以下 PRG：
$$ G’(x) = \begin{cases} 0^{2n} & \text{if x is palindrome;}\ G(x) & \text{otherwise;}\ \end{cases} $$ 我的直覺是 $ G’ $ 是安全的，因為它僅對可忽略不計的輸入部分是“可預測的”，因此我嘗試編寫正式的歸約。
我試著展示給定一個有效的區分器 $ D’ $ 為了 $ G’ $ ，我可以構造一個有效的區分器 $ D $ 為了 $ G $ . 我面臨的直接問題是 $ D $ 接收隨機字元串作為輸入 $ r $ 長度 $ 2n $ ， 或者 $ G(s) $ 對於隨機 $ s $ 長度 $ n $ ，在後一種情況下，我在重新排列時遇到了麻煩 $ G(s) $ “適合” $ D’ $ . （我用作黑匣子）
是我的直覺 $ G’ $ 安全正確嗎？如果是這樣，證明其安全性的方法是什麼？
確實，您的直覺是完全正確的 $ D $ 你試圖建立的基本上是 $ D’ $ 本身。要看到這種情況，只需將實驗劃分為 $ G’ $ 分為兩種情況：選擇的輸入要麼是回文，要麼不是。第一種情況發生的機率可以忽略不計，所以我們可以專注於第二種情況，但現在很容易，因為這種情況對應於原始實驗 $ G $ .
如果你想正式一點，請記住
$$ \begin{multline*} \mathbb{P}\left[D’(G’(x)) = 1\right] = \mathbb{P}\left[D’(G’(x)) = 1|x\text{ is palindrome}\right]\cdot\overbrace{\mathbb{P}\left[x\text{ is palindrome}\right]}^{\delta} \ + \mathbb{P}\left[D’(G’(x)) = 1|x\text{ is not palindrome}\right]\cdot\underbrace{\mathbb{P}\left[x\text{ is not palindrome}\right]}_{1-\delta} \end{multline*} $$ 和 $$ \mathbb{P}\left[D’(r) = 1\right] = \delta\cdot\mathbb{P}\left[D’(r) = 1\right] + (1-\delta)\cdot\mathbb{P}\left[D’(r) = 1\right]. $$ 現在，當你拿差價 $$ \begin{align*} \left|\mathbb{P}\left[D’(G’(x)) = 1\right] - \mathbb{P}\left[D’(r) = 1\right]\right| \end{align*} $$ 嘗試適當地關聯術語並應用一些直接的不等式來表明這是可以忽略不計的。