密碼散列後量子安全嗎？
目前的電腦無法破解相當強的散列密碼，例如 14 個 CSPRNG 生成的字母數字字元（ $ \approx $ 80 位熵）。
據我所知，Grover 的算法適用於雜湊函式（例如在這個答案中提到），這意味著給定任何 128 位的 MD5 輸出，它可以在 $ \sqrt{2^{128}}=2^{64} $ 對算法的評估，為電腦提供了足夠的量子比特。如果量子電腦能夠足夠快地評估 MD5（或者足夠便宜以建構足夠的副本），那麼無論使用者的密碼有多強，這都會徹底破壞 MD5。
然而，找到一個通過 256 位（或更強）散列函式執行的 256 位隨機密鑰仍然遙不可及。
如果散列函式本身是後量子安全的，例如 SHA-512，但輸入的是密碼怎麼辦？是否有任何已知的量子算法可以在比傳統的蠻力搜尋少得多的評估中找到輸入（ $ \frac{2^{80}}{2} $ 以上範例的平均值）？Grover 算法（或任何其他適用的量子算法）是否僅適用於弱化散列函式本身，或者它是否也可以僅搜尋合理的輸入（az、AZ、0-9 <=14 個字元）以減少搜尋空間？
需要明確的是，我知道任何裸散列函式（即使具有不必要的長輸出，如 SHA-512）都是儲存使用者密碼的糟糕方式，應該使用 Argon2 或類似方法，但我認為記憶體硬度和其他方面可能會使問題太寬泛或答案不那麼適用。
Grover 算法（或任何其他適用的量子算法）是否僅適用於弱化散列函式本身，或者它是否也可以僅搜尋合理的輸入（az、AZ、0-9 <=14 個字元）以減少搜尋空間？
Grover 是一種通用的搜尋方法——它不知道也不關心函式是如何解釋輸入的。如果您給它一個將輸入解釋為“（az，AZ，0-9 <= 14 個字元）”的函式，它將與它一起工作，並具有預期的複雜性。
另一方面，相關問題可能是“與 GPU 農場或某些 ASIC 相比，使用量子電腦是否具有經濟意義？” 我建議在接下來的幾十年裡（也就是說，直到量子電腦技術經歷了幾代人），經典方法在這種情況下會更快。
造成這種情況的一些原因：
- 預計量子計算操作的成本將遠大於相應經典操作的成本。比較兩者時，這是一個常數因子 - 但是，如果這個常數因子可能是十億或一萬億，它真的不應該被忽略。
- 並行化 - 經典的電腦搜尋（例如這個）是完全可並行化的（GPU 場或一組 ASIC 將充分利用）。相比之下，Grover 的算法（或任何類似的 Quantum Oracle 搜尋）不是 - 你確實知道 $ n^2 $ 如果您可以執行，請加快速度 $ O(n) $ 連續操作。但是，如果您不能等待那麼久並且需要實施多台量子電腦來進行搜尋，那麼您就不會明白 $ n^2 $ 在他們之間加速。例如，要將搜尋速度提高 100 倍，您需要 10,000 倍的量子電腦。
- 重用關鍵字搜尋。使用經典計算，我們可以生成一個 Rainbow 表——生成該表的時間大約與完整搜尋一樣長；但是，一旦完成，對各種散列密碼進行重複搜尋是很便宜的。相反，執行 Grover 算法將搜尋單個密碼——如果我們想檢查另一個雜湊，我們必須重新為完整搜尋付費。當然，您可以在量子電腦上建構彩虹表；但是我不相信你會得到任何 Quantum 加速，而且我還沒有聽說過你可以得到 Quantum 加速的替代方案。
現在，隨著時間的推移，我們可以合理地預期量子電腦的成本會下降（並且比傳統計算的相對成本下降得更快），並且我們可以預期量子電腦會隨著時間的推移變得更快（因此需要更少的並行化）；我只是不認為這兩種趨勢會在一夜之間發生……
需要明確的是，我知道任何裸散列函式（即使具有不必要的長輸出，如 SHA-512）都是儲存使用者密碼的糟糕方式，應該使用 Argon2 或類似方法，但我認為記憶體硬度和其他方面可能會使問題太寬泛或答案不那麼適用。
以我們目前對量子電腦內在權衡的理解（可能相當偏離基礎），記憶硬功能對於量子電腦來說將是非常痛苦的。評估這樣一個雜湊函式似乎需要一個大的 Quantum 記憶體，而且（據我們所知）看起來非常昂貴
$$ 1 $$. Grover 的算法將適用（同樣，它不關心散列函式是什麼）；但是，它似乎相當昂貴。
因此，假設我們的猜測是正確的，那麼記憶硬散列函式（Argon2）將比簡單的散列函式更能抵抗量子計算。
$$ 1 $$：我相信至少部分原因是如果你有一個大的量子儲存器，並訪問它以獲得一個糾纏的地址，你最終會在每個單個儲存單元上執行操作（或者至少，每個可能由糾纏地址）。相比之下，使用經典記憶體，您只需要訪問正在定址的單元格。如果我們談論的是具有 1,000,000 個可定址位置的儲存器，這意味著與經典情況相比，量子儲存器可能需要執行 1,000,000 倍的操作。