建立對手以顯示 PRF 是不安全的
讓 $ F(k,x) $ 成為一個安全的 PRF $ (\mathcal{K},\mathcal{X},\mathcal{Y}) $ 在哪裡 $ \mathcal{K} = \mathcal{X} = \mathcal{Y} = {0,1}^n $ .
讓 $ F’(k, x) = F(F(k, 0^n), x) ; \Vert ; F(k, x) $ .
$ a ; \Vert ; b $ 方法 $ a $ 連接到 $ b $ .
我怎麼能證明這一點 $ F’ $ 不是一個安全的 PRF？我一直在嘗試建立一個可以找到某種模式的對手，但我找不到。我最好的猜測是最初使用 $ x = 0^n $ ，所以輸出會是這樣的 $ F(k’, 0^n) ; \Vert ; k’ $ （在哪裡 $ k’ = F(k, 0^n) $ ，這是左側的鍵），我可以使用 $ k’ $ 對於接下來的計算，但似乎不足以在輸出序列中找到任何模式。
詢問 $ 0^n $ 給你的神諭，接受 $ a\Vert b $ 作為回應。如果 $ F(b,0^n) = a $ 輸出 $ 1 $ , 否則輸出 $ 0 $ .
如果預言機是 $ F’ $ ， 自從 $ F’(k,x) $ 定義為 $ F(F(k,0^n),x)\Vert F(k,x) $ 你的回應將是 $ a\Vert b = F(F(k,0^n),0^n)\Vert F(k,0^n) = F(k’,0^n)\Vert k’ $ , 這將永遠是真的 $ F(b,0^n) = a $ . 是的
$$ \Pr_k[\mathcal{A}^{F’(k,\cdot)}(1^n)=1] = 1. $$ 在預言機是真正隨機函式的情況下 $ g : {0,1}^n \times {0,1}^n \to {0,1}^n $ , $ a $ 均勻分佈且獨立於 $ b $ . 因此機率 $ F(b,0^n) = a $ 是 $ 2^{-n} $ . 因此，
$$ \Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}. $$ 因此
$$ \left|\Pr_k[\mathcal{A}^{F’(k,\cdot)}(1^n)=1]-\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|=1-2^{-n}, $$ 這顯然是不可忽略的。