Block-Cipher
輸出欄位元素的偽隨機函式 VS 輸出字元串的偽隨機函式
假設我們有兩個偽隨機函式 $ PRF $ 和 $ PRF’ $ 定義如下：
$ PRF: {0,1}^{n}\times {0,1}^{m}\rightarrow {0,1}^{n} $
$ PRF’: {0,1}^{n}\times {0,1}^{m}\rightarrow \mathtt{F}_p $
在哪裡 $ p $ 是一個大素數， $ |p|=l $ ， 和 $ l $ , $ n $ 是安全參數。
問題1：是 $ PRF’ $ 安全且符合偽隨機函式的標准定義嗎？
如果是，那麼
問題2：這兩個偽隨機函式在安全級別和發生碰撞的機率方面是否不同？
$ F_p $ 具有與整數集的一對一映射 $ [0, p) $ . $ {0, 1}^n $ 具有與整數集的一對一映射 $ [0, 2^n) $ . 它們的尺寸分別為 $ p $ 和 $ 2^n $ .
兩個都 $ F_p $ 和 $ {0, 1}^n $ 是常見的（共）域，因為在更大的事物方案中具有效率、易於分析或易用性的良好特性。但是要分析 PRF，這些基本相同。
您正在將一組映射到另一組。在安全範圍內，此映射必須與隨機預言機無法區分。對於分析，唯一的基本屬性是您正在映射的集合的大小和分佈，而不是這些集合實際包含的內容。
對安全 PRF 的生日攻擊大致表明你會在之後發現衝突 $ \sqrt{s} $ 隨機輸出，其中 $ s $ 是共域的大小。所以對於你的問題分別 $ \sqrt{p} $ 和 $ 2^{n/2} $ .