偽隨機函式與隨機選擇函式之間的區別
我目前正在學習密碼學課程。在此，我偶然發現了偽隨機函式。我對將輸入字元串（鍵）映射到擴展字元串的偽隨機生成器有了一點了解。但是，我不理解函式的偽隨機性。
在Katz 和 Lindell的《現代密碼學導論》一書中，我發現了這一點：
由於隨機選擇函式的概念不如隨機選擇字元串的概念那麼熟悉，因此值得花更多時間在這個想法上。從數學的角度來看，我們可以考慮集合 $ \operatorname{Func}n $ 所有功能映射 $ n $ -位字元串 $ n $ -位字元串；這個集合是有限的（我們稍後會看到），所以隨機選擇一個函式映射 $ n $ -位字元串 $ n $ 位字元串完全對應於從該集合中均勻地隨機選擇一個元素。
套裝有多大 $ \operatorname{Func}n $ ? 一個函式 $ f $ 由其在其域中每個點上的值精確指定；事實上，我們可以將任何函式（在有限域上）視為一個大型查找表，其中儲存 $ f(x) $ 在標記為的表的行中 $ x $ . 為了 $ f_n\in\operatorname{Func}n $ ，查找表為 $ f_n $ 有 $ 2^n $ 行（域的每個點一個 $ {0,1}^n $ ) 並且每一行包含一個 $ n $ -位字元串（因為範圍 $ f_n $ 是 $ {0,1}^n $ ）。因此，任何這樣的表都可以精確地表示 $ n\cdot2^n $ 位。
此外，函式在 $ \operatorname{Func}n $ 與這種形式的查找表一一對應；意味著它們與所有長度的字元串一一對應 $ n\cdot2^n $ .
我們得出的結論是 $ \operatorname{Func}n $ 是 $ 2^{n\cdot2^n} $ . 將函式視為查找表提供了另一種考慮選擇函式的有用方法 $ f_n\in\operatorname{Func}n $ 均勻隨機。確實，這完全等同於選擇查找表的每一行 $ f_n $ 均勻隨機。也就是說，價值觀 $ f_n(x) $ 和 $ f_n(y) $ （為了 $ x\neq y $ ) 完全獨立且均勻分佈。
回到我們對偽隨機函式的討論，回想一下我們希望構造一個鍵控函式 $ F $ 這樣 $ F_k $ （為了 $ k\gets{0, 1}^n $ 隨機均勻選擇）與 $ f_n $ （為了 $ f_n\gets\operatorname{Func}n $ 均勻隨機選擇）。請注意，前者是從（最多）的分佈中選擇的 $ 2^n $ 不同的功能，而後者是從所有的分佈中選擇的 $ 2^{n\cdot2^n} $ 中的功能 $ \operatorname{Func}n $ . 儘管如此，這些函式的“行為”對於任何多項式時間區分器來說必須看起來相同。
誰能用更簡單的方式向我解釋這個概念？
隨機函式——函式 $ F $ ，即從集合中隨機選擇 $ Func $ 所有可能的功能（具有給定的域和範圍）。
偽隨機函式—family $ {F_k} $ 由參數索引的函式 $ k $ （用作數字）。這是偽隨機的，因為如果有人選擇 $ k $ 偷偷地讓你與 $ F_k $ ，看起來你正在使用一個隨機函式，而實際上它是從一個小得多的集合中選擇的，而不是從所有可能函式的集合中選擇的。
主要概念點是：理想情況下，在密碼學中，人們通常希望使用隨機函式作為建構塊。但是，這些非常不方便（正如您複製的文本所闡述的那樣），因為通常儲存任意函式的唯一方法是作為查找表，它很快就會變得很大。因此，人們試圖找到一種更實用的方法來獲得一些隨機函式，這些函式實際上同樣好，並且生成和傳輸所需的工作量要少得多。這是在偽隨機（族）函式s 的概念中形式化的，它要求攻擊者不能有效地觀察從該族或** 所有函式集中隨機抽取的函式之間的任何顯著差異。此類系列的設計方式允許任何特定成員的輕鬆生成、傳輸和使用，例如作為單鍵功能。