抗碰撞偽隨機函式
假設我們有一個偽隨機函式：PRF(.)
我們希望以下屬性具有很高的機率：
$ \forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i) $
在哪裡 $ k_1 $ 和 $ k_2 $ 是兩個獨立挑選的隨機密鑰。
**問題1：**文獻中稱具有上述性質的偽隨機函式是什麼？
**問題2：**有沒有使用上述偽隨機函式的論文？
這個問題似乎暗示您實際上打算詢問任何給定索引不碰撞的機率，而不是每個索引同時不碰撞的機率。如果是這種情況，那麼答案是微不足道的：任何 PRF 的兩個輸出，即使在相同的索引處，根據定義都是獨立的隨機變數，因此與機率相衝突 $ \frac{1}{n} $ .
但是，如果您確實指的是通用概念，則情況會稍微複雜一些：任何具有輸出大小的 PRF $ a $ （以位為單位）和輸入大小 $ b $ 大約有這個性質 $ 1-2^{a-b} $ .
要看到這一點，讓 $ \rho $ 表示所需屬性成立的機率，並取 codomain 的大小 $ \alpha n $ 在哪裡 $ \alpha $ 是一個常數。
$$ \rho = \Pr(\forall i \in [0, n]: PRF(k_1, i)\neq PRF(k_2,i)) $$ 假設值是 iid： $$ \rho = \Pr(PRF(k_1,i) \neq PRF(k_2,i))^{n+1} $$ 假設值是統一的： $$ \rho = \left(1-\frac{1}{\alpha n}\right)^{n+1} $$ 取極限為 $ n\to\infty $ : $$ \rho \approx e^{-1/\alpha} $$ 在真值的 5% 以內時 $ n \geq 32 $ 和 $ \alpha \geq 1 $ . 我們猜測 $ \rho = 1-\frac{1}{z} $ 並解決 $ \log_2\alpha $ ，根據定義，輸出位數減去輸入位數： $$ e^{-1/\alpha} = 1-\frac{1}{z} $$ $$ \alpha = \left(\log\frac{z}{z-1}\right)^{-1} $$ $$ \log_2\alpha = -\log_2\log\frac{z}{z-1} $$ 始終在真實值的一半以內，只要 $ z \leq e^n $ . 我們用另一個方便的近似值再次簡化： $$ \log_2\alpha \approx \log_2 z $$ 最壞的情況是比真實值低半位。由於您的條件保持的機率由 $ z $ ， 和 $ \alpha $ 是輸出域和輸入域的基數之間的比率，條件成立的機率大約與輸出域的大小除以輸入域的大小成正比。 $ \square $