Pseudo-Random-Function
密鑰 PRF 中包含的功能數量
我正在閱讀 Katz 和 Lindell 的《現代密碼學導論》,我發現了這一點:
回到我們對偽隨機函式的討論,回想一下偽隨機函式是一個鍵控函式 F,使得 $ F_k $ (為了 $ k\in2 {0, 1}^n $ 隨機均勻選擇)與 $ f $ (為了 $ f\in $ $ Func_n $ 均勻隨機選擇)。前者是從(最多)的分佈中選擇的 $ 2^n $ 不同的功能,而後者是從所有 $ 2^{n*2n} $ Funcn中的功能。儘管如此,這些函式的“行為”對於任何多項式時間區分器來說必須看起來相同。
他是如何得出選擇鍵控函式 F 的結論的 $ 2^n $ 不同的功能?
他是否假設有一個固定函式可以通過鍵 k 來區分,所以總共 $ 2^n $ “功能”?
有 $ 2^n $ 可能的值 $ k $ , 每一個都有一個函式 $ F_k $ ,因此, 最多有 $ 2^n $ 可能的功能 $ F_k $ . (“最多”是因為可能有兩個不同的值 $ k $ 產生相同的功能 $ F_k $ .)