交換XXx和ķķk在 GGM 建設中
我正在研究從偽隨機生成器到偽隨機函式的 Goldreich-Goldwasser-Micali 構造。在這個特定的結構中，假設 $ G:{0,1}^n\rightarrow {0,1}^{2n} $ 是一個 PRG，映射 $ x $ 到 $ G(x)=(G_0(x),G_1(x)) $ . 那麼這個結構中的 PRF 由下式給出
$$ F_k(x)=G_{x_n}\circ\cdots\circ G_{x_1}(k), $$ 使用隨機密鑰 $ k $ 在相同的長度 $ x $ . 證明是一個混合論證，通過替換 $ G_{x_j}\circ\cdots\circ G_{x_1}(k) $ 具有真正的隨機函式 $ {0,1}^j\rightarrow{0,1}^n $ . 現在我想知道如果我們交換 $ x $ 和 $ k $ 在這個結構中，即定義
$$ F’k(x)=G{k_n}\circ\cdots\circ G_{k_1}(x). $$ 直覺地說，不能使用類似上述的混合技術來證明其偽隨機性。但是我沒有想出一個反例，因為我想保留一些資訊 $ x $ 之內 $ G(x) $ ，但此資訊保留後的可能性 $ n $ -round 迭代總是可以忽略不計。例如，如果我們保留第一個位 $ G(x) $ 存在 $ x_1 $ , 只有 $ 2^{-n} $ 機率我們仍然可以看到該位 $ x_1 $ 在 $ F_k’(x) $ ， 什麼時候 $ k $ 是隨機的。 是否有任何方法可以證明或反駁該構造 $ F’_k(x) $ 是偽隨機的？提前致謝。
$ F’_k(x) $ 不一定是偽隨機的。
證明：
改變一個輸出不會影響 PRGness，所以如果有一個 PRG
延伸了 2 倍，那麼就有一個 PRG 延伸
了 2 倍並將全零字元串發送到全零字元串。
對全部 $ n $ 和 $ k $ 和 $ x $ ， 如果 $ G $ 那麼是這樣的PRG嗎 $ F’_k(x) $ 是字元串 $ n $ 零。
對全部 $ n $ ， 如果 $ : n\neq 0 : $ 然後還有其他具有該長度的字元串。
所以 $ F’_k(x) $ 不一定是偽隨機的。
（當然，這並不能證明你的構造不能是偽隨機的。）