AES-128 是量子安全的
我最近一直在閱讀一些關於 AES128 的量子安全電阻的相互矛盾的消息。首先，愛立信人的部落格文章如下：
量子攻擊者能否破解 AES-128？
不會。NIST 估計，到 2030 年，可以在幾小時內以大約 10 億美元的價格建造一台突破 RSA-2048 的量子電腦。這意味著 NIST 估計早期的量子電腦的時鐘頻率為幾 MHz。這樣一台執行 Grover 算法的量子電腦（單個 20 MHz 量子核心）需要 10 11年（一千億年）才能破解 AES-128。即使是時鐘頻率為 2 THz 的 109 個量子核心（世界上最大的公共經典超級電腦有 10 個7核心）的集群，也需要 10 6年（一百萬年）才能打破 AES-128。
考慮到這一切，格羅弗的算法不會對對稱密碼學構成任何明顯的威脅。幾年前，有一個普遍的概念，即 Grover 的算法需要將對稱密鑰大小加倍——需要使用 AES-256 而不是 AES-128。這在今天被認為是一種誤解——例如，NIST 現在聲明 AES-128 可能會在未來幾十年保持安全，儘管有 Grover 的算法
$$ 5 $$. 事實上，NIST PQC 標準化中的安全級別之一等同於 AES-128。這意味著 NIST 認為標準化 PQC 的參數與 AES-128 在量子攻擊下的強度一樣大。當然，可能還有其他原因需要更長的密鑰，例如合規性，並且使用更長的密鑰對性能的影響很小。
總而言之，我們最重要的對稱加密工具（AES、SNOW 3G、SHA2、SHA3 等）對量子電腦仍然是安全的。這也適用於純粹依賴對稱加密的 3G、4G 和 5G 中的身份驗證、密鑰生成、加密和完整性。
此外，Cloudfare 中的一些人提到：
這一切都是一種冗長的說法，即在可預見的未來，安全級別 1 似乎是可靠的。
來源這裡
最後，NIST 還提到了關於 PQC 的評估標準：
NIST 的分類將基於現有 NIST 對稱密碼學標準提供的安全強度範圍，NIST 預計該標準將對量子密碼分析提供顯著的抵抗力。特別是，NIST 將為以下每個安全要求定義一個單獨的類別（按強度遞增的順序列出 2）：
- 任何破壞相關安全定義的攻擊都必須需要與使用 128 位密鑰（例如 AES128）的分組密碼進行密鑰搜尋所需的計算資源相當或更大的計算資源
**值得注意的是，基於這些參考原語的安全類別提供的量子安全性比簡單分析所暗示的要多得多。**例如，類別 1、3 和 5 是根據分組密碼定義的，可以使用 Grover 算法以二次量子加速來破解。但是格羅弗的算法需要長時間執行的串列計算，在實踐中很難實現。在實際攻擊中，必須並行執行許多較小的算法實例，這使得量子加速不那麼顯著。
來源：這裡
那麼，真相在哪裡？多年來我一直有這樣的印象，即我們肯定需要將對稱加密中的密鑰大小加倍以保持量子安全。這真的是一種誤解嗎？
以上所有來源都是正確的；Grover 算法對 AES 沒有實際威脅。
的標題聲明 $ 2^{64} $ 量子運算經常被誤解，因為人們認為 $ 2^{64} $ 計算上可行的操作。他們沒有意識到的是，而 $ 2^{64} $ 並行執行的操作對於現代經典電腦是可行的， $ 2^{64} $ 串列執行的操作是不可行的。另一件要知道的是，格羅弗的算法是高度不可並行的。如果我們部署 $ 2^c $ 使用 Grover 算法並行搜尋的計算單元，它將按比例完成時間 $ 2^{(128-c)/2} $ 所以使用 256 量子電腦只會減少 1/16 的執行時間，1024 量子電腦只會減少 1/32 的執行時間等等。
現在考慮量子電腦目前以 kHz 時鐘速率執行，而經典電腦可能以 GHz 時鐘速率執行，我們看到有一個巨大的鴻溝需要克服。有關範例，請參閱愛立信數字（請注意，愛立信網站有一個錯字：106 年應閱讀 $ 10^6 $ 年）。
有人可能會問，一種改進的算法是否可以勝過 Grover 的算法。然而，Christof Zalka 表明 Grover 的算法（尤其是其非並行性質）是非結構化搜尋的最佳可能複雜度。