Block-Cipher
為什麼在固定長度的加密方案中使用真正的隨機函式效率不高？
我正在研究 Katz 和 Lindell，書中的定理 3.26 證明了基於 PRF 的構造是 CPA 安全的。該計劃的主旨是，如果 $ F_k $ 是一個 PRF，有 $ k, m, r \in {0, 1}^n $ （密鑰，消息，隨機字元串），然後 $ c = (r, F_k(r) \oplus m) $ .
證明背後的想法是首先使用真正的隨機函式證明方案的安全性 $ f_n $ 代替 PRF $ F_k $ ，然後表明如果該方案使用 PRF 不安全 $ F_k $ ， 然後 $ F_k $ 可以與真正的隨機函式區分開來。
在證明中，作者指出使用真正隨機函式的加密方案 $ f_n $ 代替 PRF $ F_k $ 不是合法的加密方案，“因為它沒有效率”。我想知道是否有人可以向我解釋為什麼會這樣？我認為該方案仍然有效，因為即使對真正隨機函式的描述 $ f_n $ 很長，用它來確定哪些點映射到什麼應該快？
考慮一個真正的隨機函式 $ F:{0,1}^n\to{0,1}^n $ . 通過組合學中的一個基本論證，寫下一個描述 $ F $ 需要 $ n2^n $ 位。具體來說，我們經常想要 $ n\approx 128 $ （雖然在資訊論環境中這可能會更小，比如低端的 80）。這已經比任何實際情況下可用的儲存空間多得多。
這就是說，即使儲存相關功能的描述也是不可行的。如果我們將函式儲存為 $ 2^n $ 條目，然後對其進行索引（在恆定時間內）需要指數級的時間，即該函式的計算速度也很慢。