NIST 後量子項目中的安全級別：例如 AES-128 與 SHA-256
在一篇關於 NIST 後量子標準化項目的文章中，我讀到了所提議方案的安全標準，並且有這張表（I 級最低安全，V 級最高）：
一級：至少和 AES-128 一樣難以破解（詳盡的密鑰搜尋）
二級：至少和 SHA-256 一樣難破解（碰撞搜尋）
級別 III：至少與 AES-192 一樣難以破解（詳盡的密鑰搜尋）
級別 IV：至少與 SHA-384 一樣難以破解（碰撞搜尋）
V 級：至少與 AES-256 一樣難以破解（詳盡的密鑰搜尋）
如果我理解正確，那麼（以經典方式，不使用量子電腦和 Grover 算法）在 AES-128 上進行詳盡的密鑰搜尋，我們需要通過 $ 2^{128} $ 可能性和在 SHA-256 的碰撞搜尋中，我們需要通過 $ 2^{128} $ 找到碰撞的可能性（感謝生日悖論）。
所以我的問題是 - 安全級別 I 和級別 II 有何不同？同樣 - 為什麼 AES-192 的安全性低於 SHA-384 的安全性。
這是由於Brassard 等人。的雜湊函式方法。具有 $ \mathcal{O}(\sqrt[3]{n}) $ n 位散列函式的攻擊時間，其中Grover的方法具有 $ \mathcal{O}(\sqrt{n}) $ -時間。
- 一級：至少和 AES-128 一樣難破解 $ \mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64}) $ ——格羅弗
- II 級：至少與 SHA-256 一樣難以破解 $ \mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85}) $ - 布拉薩德等人。
- III 級：至少與 AES-192 一樣難以破解 $ \mathcal{O}(\sqrt{2^{192}}) = \mathcal{O}(2^{96}) $ ——格羅弗
- IV 級：至少與 SHA-384 一樣難以破解 $ \mathcal{O}(\sqrt[3]{2^{384}}) = \mathcal{O}(2^{128}) $ - 布拉薩德等人。
- V 級：至少與 AES-256 一樣難以破解 $ \mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128}) $ 通過格羅弗
兩種量子雜湊碰撞方法的時空比較。
$$ \begin{array} {|c|c|}\hline & \text{time} & \text{space} \ \hline \text{Grover} & \mathcal{O}(\sqrt{n}) & \mathcal{O}(\log{n}) \ \hline \text{Brassard et al.} & \mathcal{O}(\sqrt[3]{n}) & \mathcal{O}(\sqrt[3]{n}) \ \hline \end{array} $$
Bernstein 有一篇很好的文章“雜湊衝突的成本分析：量子電腦是否會使 SHARCS 過時”關於與並行化 van Oorschot-Wiener 的比較。您還可以閱讀 Squeamish Ossifrage 的回答。