如何構造具有特定屬性的偽隨機數
如何構造一個偽隨機函式 $ PRF $ 具有以下屬性：
機率 $ PRF(k_1,i)=PRF(k_2,i) $ 可以忽略不計，對於所有鍵 $ k_1,k_2 $ 這樣 $ k_1\neq k_2 $
具有上述性質的 PRF 是否必須是這裡提到的偽隨機函式部落集合，或者它可以是任何具有足夠大輸出範圍的 PRF。
雙重 PRF是其中 PRF的任何一個參數都可以解釋為密鑰的 PRF。換句話說，對於隨機 $ k $ ， 功能 $ F(k,\cdot) $ 與隨機函式無法區分。而對於隨機 $ x $ ， 功能 $ F(\cdot,x) $ 與隨機函式無法區分。
如果 $ F : {0,1}^\kappa \times {0,1}^\kappa \to {0,1}^\ell $ 是對偶 PRF，則以下情況成立：
對所有人 $ k_1 \ne k_2 $ ,[Pri←{0,1}κ[F(k1,i)=F(k2,i)]Math Processing Error]幾乎可以忽略不計[1/2ℓMath Processing Error]. $ \displaystyle\Pr_{i \gets {0,1}^\kappa}\Big[ F(k_1,i) = F(k_2,i) \Big] $ $ 1/2^\ell $
根據我上面的評論，如果您想要一個確定性函式來滿足某些安全屬性（沒有隨機預言機假設），則必須隨機選擇*一些東西。*即使[iMath Processing Error]公開，但確實需要統一選擇。 $ i $
要看到這一點，只需應用 PRF 屬性 $ F(\cdot,i) $ （這裡用隨機密鑰實例化[iMath Processing Error]) 並觀察到[Pr[R(k1)=R(k2)]=1/2ℓMath Processing Error]對於隨機函式[RMath Processing Error]什麼時候 $ i $ $ \Pr[ R(k_1) = R(k_2) ] = 1/2^\ell $ $ R $ $ k_1 \ne k_2 $ .
當然，雙 PRF 並不是一個完全標準的假設。但它是 HMAC 的基礎，因此如果您對 HMAC 感到滿意，那麼您必須對假設某些雜湊函式是雙 PRF 感到滿意。
另外，如果 $ k_1, k_2 $ 被獨立/統一選擇，並且 $ i $ 以對抗方式選擇，您僅從正常 PRF 屬性中獲得的碰撞機率很低。