PRF的存在⟹⟹impliesPRG的存在
讓 $ F:{0,1}^n\times {0,1}^m \to {0,1}^l $ 成為PRF。我想證明 $ G(-)=F(-,x_0) $ 是每個人的 PRG $ x_0\in {0,1}^m $ .
證明嘗試：
讓 $ D $ 成為一個有效的區分者 $ G $ 在PRG 實驗中（見下文）。我們的目標是表明 $ D $ 具有微不足道的優勢。
考慮以下有效的區分器 $ D’ $ 在PRF 實驗中。授予對函式的訪問權限 $ \mathcal O $ 這是一個隨機函式 $ {0,1}^m\to {0,1}^l $ 或者 $ F_k $ ， 然後 $ D’ $ 精確輸出接受/拒絕選擇 $ D $ 在弦上 $ \mathcal O(x_0) $ .
按施工 $ D’ $ 當且僅當 $ D $ 接受。根據假設，由於 $ F $ 是 PRF，前一個事件的機率為 $ \frac{1}{2} + \text{negl}(n) $ 對於一些微不足道的 $ \text{negl} $ ，因此對於後一個事件也是如此。
我的問題：
- 證明正確嗎？
- 嚴謹程度夠不夠？
附加資訊： 這是我提到的兩個實驗（取自 Katz/Lindell）。
你的證明起初並沒有說服我。
授予對函式的訪問權限 $ \mathcal O $ 這是一個隨機函式 $ {0,1}^m\to {0,1}^l $ 或者 $ F_k $ ， 然後 $ D’ $ 精確輸出接受/拒絕選擇 $ D $ 在弦上 $ \mathcal O(x_0) $ .
“然後”這個詞把我嚇跑了。的輸出 $ D’ $ 不是第一個子句的結果。我會改寫它以明確聲明我們正在建構一個 $ D’ $ 使用 $ D $ 以特定的方式。這可能看起來很愚蠢，但這確實讓我做了雙重考慮。
按施工 $ D’ $ 當且僅當 $ D $ 接受。根據假設，由於 $ F $ 是 PRF，前一個事件的機率為 $ \frac{1}{2} + \text{negl}(n) $ 對於一些微不足道的 $ \text{negl} $ ，因此對於後一個事件也是如此。
第一句話不對。在 PRG 遊戲中，有時 $ D $ 實際上會得到一個隨機字元串而不是 $ G(s) $ ，在那些情況下， $ D $ 應該拒絕輸入，而不是接受它，才能獲勝。也許你的意思是 $ D’ $ 當且僅當 $ D $ 贏了？
此外，實際上並沒有給出任何理由（甚至是一個草圖）。讀者需要詳細了解 $ \mathcal{O}(x_0) $ 他自己甚至可以理解這個論點；那是它的失敗。證明的正確性只是成功的一半：它還必須讓讀者相信它的正確性，這可能要困難得多。
為什麼會這樣 $ D’ = D(\mathcal{O}(x_0)) $ 是一個區分符 $ F $ ，因此必須具有可以忽略不計的優勢？這就是證明的核心——你已經省略了。
我認為反證法更容易理解。讓我們也嘗試在我們的推理中明確。
我們獲得了 PRF $ F_k $ 我們想展示 $ G(s) = F_s(x_0) $ ， 在哪裡 $ x_0 $ 是一個固定常數 $ {0,1}^m $ , 是一個 PRG。
假設（朝向矛盾） $ G $ 不是 PRG，所以存在一個有效的區分器 $ D $ 在 PRG 不可區分性博弈中具有不可忽略的優勢 $ G $ .
我們將建立一個高效的區分器 $ D’ $ 在 PRF 實驗中使用 $ D $ . 在那次實驗中， $ D’ $ 將給出：
- 統一函式 $ \mathcal{O} \in \mathsf{Func}_m $ ， 或者
- 功能 $ \mathcal{O}(x) = F_k(x) $ 在哪裡 $ k $ 是一個統一的字元串 $ {0,1}^n $
方便的是，如果我們評估 $ \mathcal{O}(x_0) $ , 我們得到
- 一個統一的值 $ {0,1}^m $ ，根據定義 $ \mathcal{O} \in \mathsf{Func}_m $ ， 或者
- 價值 $ F_k(x_0) = G(k) $
請注意，可能的值 $ \mathcal{O}(x_0) $ 完全匹配 PRG 不可區分性博弈的參數 $ G $ . 因此， $ D $ 可以以不可忽略的優勢區分上述兩種情況，因為我們假設 $ G $ 不是PRG。
因此，如果我們讓輸出 $ D’ $ 成為的輸出 $ D $ ， 然後 $ D’ $ 在 PRF 博弈中具有不可忽略的優勢 $ F_k $ . 這違反了我們的假設，即 $ F_k $ 是一個PRF。因此，我們最初的假設是 $ G $ is not a PRG 必須為假，即 $ G $ 必須是 PRG。
上面的證明可能沒有一些人想要的那麼嚴格，但我認為它作為一個簡短的草圖已經足夠接受了（如果需要，可以用真實的數學細節來填充）。
請注意，我並沒有真正說出與您的文章不同的任何內容——我只是更明確了。我確實改用了反證法，但那是因為當我陳述結論時，它最終聽起來像是反證法。