偽隨機字元串的一部分也是偽隨機字元串嗎？
我正在做一個只使用第一個加密消息的練習 $ n $ 偽隨機發生器輸出的位 $ G(k) $ ， IE $ F_k(m) := G(k)_{0…n−1} \oplus m $ .
$ k $ 是隨機均勻選擇的，並且 $ k, m \in {0, 1}^n $ . 我的任務是決定一個加密方案是否基於 $ F_k $ 可以安全地抵禦純密文攻擊、CPA 攻擊以及它是否無法區分。
我的想法是，如果 $ G(k)_{0…n−1} $ 仍然是一個偽隨機字元串，練習減少到使用整個輸出的情況 $ G(k) $ . 然後該方案將安全地抵抗純密文攻擊並且無法區分，但不安全地抵抗 CPA 攻擊，因為它是一個確定性方案。
我的問題是我找不到，是否 $ G(k)_{0…n−1} $ 可以完全像整個輸出一樣對待 $ G(k) $ . 此外，我不確定我對解決練習的直覺是否正確。我將不勝感激任何提示！
你問了很多問題，我不清楚你想回答什麼。特別是，您的意思是：
我的問題是我找不到，是否 $ G(k)_{0…n−1} $ 可以完全一樣地對待 $ G_k $ .
什麼是 $ G_k $ 應該是這裡的意思？的完整輸出 $ G(k) $ ? 你對“完全一樣對待”的定義是什麼？
在任何情況下， $ n $ 安全 PRG 的第一位當然也是偽隨機的，但是 $ F_k $ 正如您正確指出的那樣，它不是 IND-CPA 安全方案。它也不是 PRF（偽隨機函式）。你能看出為什麼嗎？提示：首先查詢 $ F_k(\cdot) $ 在消息上 $ 0^n $ ，接下來在其他消息上查詢它 $ m \neq 0^n $ . 你對兩者的關係有什麼想說的 $ F_k(0) $ 和 $ F_k(m) $ ? 您是否希望這適用於隨機繪製的函式 $ f \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^n $ ?
根據評論更新
所以基本上你想顯示以下語句：“ $ G(k) $ 是安全的 PRG $ \implies G(k){0\dotsc n-1} $ 是一個安全的 PRG”。在加密貨幣中，我們通常通過證明等效的相反陳述來證明這些陳述：“ $ G(k){0\dotsc n-1} $ 不是一個安全的PRG $ \implies G(k) $ 不是一個安全的PRG”。在這種情況下，這非常簡單。所以假設存在一些（假設的）區分符 $ D $ 反對 $ G(k){0\dotsc n-1} $ . 然後假設給你一個字元串 $ x $ 長度 $ |G(k)| $ 並挑戰說是否 $ x $ 是一個隨機字元串或由 $ G(k) $ . 你做什麼工作？好吧，簡單的剁碎 $ n $ 的第一位 $ x $ ， 說 $ x’ $ , 並將其提供給 $ D $ . 注意 $ D $ 試圖判斷它是否被賦予了一個隨機長度的字元串 $ n $ 或者 $ G(k){0\dotsc n-1} $ . 你現在所做的只是輸出任何猜測 $ D $ 使。如果 $ x $ 是一個隨機長度的字元串 $ |G(k)| $ ， 然後 $ x’ $ 是一個隨機長度的字元串 $ n $ . 而如果 $ x = G(k) $ ， 然後 $ x’ = G(k){0\dotsc n-1} $ . 因此，我們能夠區分的機率 $ G(k) $ 來自隨機字元串的機率恰好是 $ D $ 能夠區分 $ G(k){0 \dotsc n-1} $ 從一個隨機字元串。因此，如果 $ D $ 成功了，我們就成功了。