為什麼後量子算法的問題必須是 NP-Hard？
我遇到的用於後量子密碼學問題的數學問題是 NP 完全的，例如
- 求解有限域上的二次方程
- 短格向量和閉格向量
- 有限域上的有界距離解碼
至少這些的一般版本是NP完全的
我在問自己為什麼這些數學問題需要是 NP 完全的（在一般版本中），以及當使用非 NP 完全的實例時這如何有用
我不知道密碼學很難僅僅假設 $ P\neq NP $ ，所以我相信你誤解了一些東西。我最了解格子的故事，所以我將討論為什麼格子僅與 $ NP $ -困難的問題。
故事很簡單，但也很技術。讓 $ \mathsf{LWE}[n, \sigma, q] $ 是維度上的平均 LWE 問題 $ n $ , 標準差 $ \sigma $ , 和模 $ q $ . Regev 對 LWE 的從最壞情況到平均情況的量子縮減表明：
$$ \mathsf{SIVP}_{\tilde{O}(nq/\sigma)} \leq \mathsf{LWE}[n, \sigma, q] $$
在哪裡 $ \mathsf{SIVP}_\gamma $ 是短獨立向量問題（把它想像成最短向量問題的推廣到找到 $ n > 1 $ 短的線性獨立向量，其中 $ n $ 是晶格的尺寸）。請注意， $ \gamma $ 這是問題中允許的近似因子。
的精確複雜度是多少 $ \mathsf{SIVP}\gamma $ ? 這高度取決於參數 $ \gamma $ ，但對於這篇文章來說，以下內容就足夠了。眾所周知 $ \mathsf{SIVP}{\tilde{\Omega}(\sqrt{n})} $ 在 $ \mathsf{AM}\cap co\mathsf{AM} $ . 這意味著它不是 $ \mathsf{NP} $ -hard 除非多項式層次結構崩潰到某個有限的（看起來像第二個？）級別，複雜性理論家認為這不太可能。
這實質上意味著，雖然 $ \mathsf{SIVP}\gamma $ 已知對某些人來說是 NP 難的 $ \gamma $ ， 這 $ \gamma $ 在格密碼學中使用的是這樣的，我們認為極不可能 $ \mathsf{SIVP}\gamma $ 將是 NP 難的。儘管如此，對於基本協議，人們通常可以採取 $ \gamma $ 是一些小的多項式，所以 $ \mathsf{SIVP}_\gamma $ 是“接近”一個 NP-hard 問題，特別是因為我們擁有多項式時間算法的最小近似因子是次指數 iirc。
更一般地說，NP 硬度在密碼學中是錯誤的。人們真正想要的是一些平均情況硬度的概念。在格密碼學中，人們可以正式將其與最壞情況的硬度聯繫起來，但並非密碼學中的每個領域都有這樣的減少。在不這樣做的領域，問題的特定最壞情況難度不是很重要——一個問題可能有一些非常困難的實例，但對密碼學仍然不利，因為可能很難生成一個困難實例. 更重要的是指定一些合理的平均情況下的硬分佈並檢查其特定的硬度。