偽隨機函式的後量子安全
我想知道 PRF 的確切後量子安全性是什麼。我知道對於大多數對稱機制，假設將密鑰大小加倍就足夠了，但我正在尋找在偽隨機函式的情況下更精確的分析（比如 $ 2^{(n/2)} $ 使用 Grover 算法對原像進行操作）。
澄清一下，我正在尋找 (1) 通用攻擊（不在任何特定的 PRF 上）(2) 只對 PRF 具有經典訪問權限的攻擊者。
對 PRF的最佳通用經典攻擊是對未知密鑰的通用原像搜尋。給定一個輸入 $ x $ 和一個輸出 $ f_k(x) $ 對於均勻隨機 $ k \in {0,1}^n $ ，最知名的算法成本約為 $ 2^n $ 的試驗評價 $ f $ 去尋找 $ k $ . 給定多個目標 $ (f_{k_1}(x), f_{k_2}(x), \dots, f_{k_t}(x)) $ , 大約花費 $ 2^n!/t $ 的試驗評價 $ f $ 找到至少一個 $ k_i $ ，如果在至少並行化的機器上完成，則使用彩虹表搜尋 $ t^2 $ 方式。
最佳通用量子原像搜尋成本約為 $ \sqrt{2^n} = 2^{n/2} $ 量子疊加的試驗評價 $ k \mapsto f_k(x) $ ，使用 Grover 算法。Grover 的算法不能很好地並行化：如果並行化 $ p $ 方式，它會及時返回答案 $ \sqrt{2^n!/p} = 2^{n/2} / \sqrt p $ 因此成本 $ 2^{n/2} \cdot \sqrt p $ 執行機器 $ p $ 倍大 $ 1/!\sqrt p $ 倍。在單目標設置中，格羅弗算法是漸近最優的。多目標搜尋的最著名的批量優勢（不知道是最優的，但似乎不太可能有顯著的改進）是適度的，僅將成本降低了 $ \sqrt[4]{t} $ 找到第一個 $ t $ 目標。
還有一個幻想威脅模型，對手不僅擁有一台量子電腦，而且你出於某種莫名其妙的原因計算量子疊加 $ x \mapsto f_k(x) $ 代表對手。
雖然我不知道任何通用攻擊，但在這個雙重不切實際的威脅模型中，使用西蒙算法（隨機範例）可以破解許多特定的密碼系統，其中對手有一台量子電腦，你有一台量子電腦，我有一台量子電腦，並且每個人和他們的狗都有一台量子電腦，你可以根據對手的要求，在輸入的量子疊加上愉快地計算秘密函式。
解決方案：當穿著深色外套的陌生人在街上問你秘密功能的量子疊加時，快跑！
更嚴重的是，如果你想自己評估量子電腦上的秘密功能，代表任何人，包括小狗和獨角獸，而不僅僅是穿著深色外套的陌生人，花點時間進行文獻搜尋，重新考慮你的生活選擇。