你能證明PRG的存在嗎GGG每個偶數的 stķķk:G(k)=G(k+1)G(ķ)=G(ķ+1)G(k)=G(k+1)?
在其中的一個練習中$$ KL $$本書我需要說明加密方案在只有一條消息的竊聽者下是否安全。
給定一個 PRG $ G: {0,1}^n \rightarrow {0,1}^{n+1} $ . 加密方案加密 $ m \in {0,1}^{2n+2} $ 經過 $ c= <G(k) \oplus m_1, G(k+1) \oplus m_2> $
在哪裡 $ m_1 $ 和 $ m_2 $ 是前半部分和後半部分 $ m $ .
顯然，這不是 CPA 安全的。但是，如果我可以說存在PRG，那麼對於每個 $ k $ : $ G(k)=G(k+1) $ 我會說它甚至不能防止只有一條消息的竊聽者，因為對手可以檢查是否 $ m_1 \oplus m_2= c_1 \oplus c_2 $ 這將是真的 $ k $ 甚至發生的機率為 $ 1/2 $ .
那麼：我怎樣才能證明這樣的 PRG 存在呢？
練習的一個要點是表明，如果使用相關密鑰，您可能會遇到麻煩，因為在這種情況下，普通的安全概念不提供任何保證。
回想一下偽隨機生成器的安全定義：從 $ {0,1}^n $ , 計算 $ y_0 = G(x) $ ， 樣本 $ y_1 $ 均勻隨機地從 $ {0,1}^{n+1} $ ， 拋硬幣 $ b $ , 給對手 $ y_b $ . 對手現在必須確定擲硬幣 $ b $ .
首先考慮“明顯”的構造。讓 $ F: {0,1}^n \rightarrow {0,1}^{n+1} $ 是一個偽隨機生成器。定義 $ G $ 成為
$$ G(x_1x_2\dots x_n) = F(x_1x_2\dots x_{n-1}0), $$也就是說，在評估之前清除最後一位 $ F $ . 直覺上，這應該有效。如果我能分辨 $ G $ 的輸出，我可以區分“一半”的 $ F $ 的輸出，應該足夠了。
不幸的是，有反例。給定任何偽隨機生成器 $ H: {0,1}^{n-1} \rightarrow {0,1}^n $ ，我們可以構造一個偽隨機生成器 $ F: {0,1}^n \rightarrow {0,1}^{n+1} $ 使用
$$ F(x_1x_2\dots x_{n-1}x_n) = H(x_1x_2\dots x_{n-1}) || x_n . $$如果 $ H $ 是安全的，那麼 $ F $ 也是安全的。但是如果你把這個生成器插入到上面的結構中，你會得到一個 $ G $ 這很容易區分（最後一位總是 $ 0 $ ）。哪個不好。 相反，您應該從生成器開始 $ F: {0,1}^{n-1} \rightarrow {0,1}^{n+1} $ 並使用
$$ G(x_1x_2\dots x_{n-1}x_n) = F(x_1x_2\dots x_{n-1}). $$如果 $ F $ 是安全的，那麼 $ G $ 是安全的，並且 $ G $ 具有所需的屬性。 （請注意，您可以使用一位擴展器 $ H: {0,1}^{n-1} \rightarrow {0,1}^n $ 到一個兩位擴展器 $ F: {0,1}^{n-1} \rightarrow {0,1}^{n+1} $ 使用標準結構。）
（註二：對於任何給定的偽隨機生成器 $ {0,1}^n \rightarrow {0,1}^{n+1} $ ，我希望能夠構造一個好的偽隨機生成器 $ {0,1}^{n-1} \rightarrow {0,1}^n $ . 但是，我懷疑沒有通用結構。）