如果 P=NP 猜想成立，後量子密碼也安全嗎？
首先，由於我不是電腦科學家，所以我只在相當淺的層次上理解P與**NP的辯論。**所以也許這個問題的答案很簡單，但如果不是，我很想知道更多。
我相信今天的電腦科學家、複雜性理論家和程序員之間的共識更傾向於P $ \neq $ NP比等式。儘管如此，我也發現網際網路上充斥著世界末日的圖片，如果
- P = NP猜想確實被證明是正確的，或/和
- 大型量子電腦（執行 Shor 算法）確實成為現實。
為了解決第二個問題，後量子密碼學領域一直在開發能夠抵抗 Shor 算法和變體的密碼分析的密碼。但是，我還沒有找到任何令人信服的答案來回答這個問題：後量子密碼是否也解決了第一個問題？
因此，我檢查了一些密碼的基本描述，例如，在後量子密碼學的旗幟下探索的 McEliece 密碼系統。其中一些顯然是基於NP難題（例如最短向量問題），這意味著即使P = NP猜想成立，這些密碼也不會變得脆弱（即使在理論上）。但是，所有目前以及未來的後量子密碼機制也是如此嗎？
後量子密碼是否也自動/自動解決了第一個問題？
並非如此，但是要詳細探討這一點，我們需要探討第一個問題是什麼。
如果 $ P=NP $ 被證明是真的，這實際上意味著什麼？好吧，它可能絕對沒有實際影響，或者這可能意味著幾乎所有已知的密碼系統都可以被輕易破解。
為什麼是這樣？嗯，有兩個原因：一，如果我們知道 $ P=NP $ 是的，我們知道 NP 內的任何問題都可以在多項式時間內解決；它並沒有說我們知道它是如何做到的。如果證明 $ P=NP $ 沒有給出算法（例如，證明表明 $ P \ne NP $ 導致矛盾），存在多時間算法的知識並不能幫助我們解決任何特定問題。
其次，即使我們知道一種多時間算法來解決其中的任意問題 $ NP $ ，它並沒有說它在任何實際時間內執行。如果算法在 $ O(N^{1000}) $ 時間上，要解決任何現實問題是不可行的，因此實際上根本不會影響任何密碼系統的安全性。
另一方面，什麼 $ P=NP $ 可能意味著有一個實用的算法可以解決任何規模合理的問題；實際上，我的意思是針對合理規模的問題執行算法是可行的。如果是這樣的話，除了少數幾個加密算法之外，所有的加密算法都會被破解。
原因如下：已知的密碼系統基於三個安全假設之一：
- 資訊安全；攻擊者實際上沒有足夠的資訊來恢復明文；一個例子是一次性墊（OTP）
- 量子安全；物理定律禁止攻擊者在沒有被察覺干擾的情況下收聽消息；量子密碼學 (QC) 屬於此類
- 計算安全；攻擊者擁有他需要的所有資訊；然而，恢復明文需要比他更多的計算；幾乎所有的密碼系統都屬於這一類
解決任意問題的實用方法 $ NP $ 問題將使計算安全類別中的所有內容無效，因為該類別中的所有內容都可以簡化為一系列 $ NP $ 問題。因此，在絕對最壞的情況下，我們將只剩下 OTP、QC 等。
所以，總而言之，只是說 $ P=NP $ 沒有為我們提供有關實際方面的足夠資訊。然而，“後量子”算法，即實際上無法破解的算法，即使可以訪問可以在量子電腦上執行的算法，也不會帶來任何特別的東西。
現在，您聲明：
其中一些顯然是基於 $ NP $ -hard 問題（例如最短向量問題），這意味著這些密碼不會變得脆弱（即使在理論上），即使 $ P=NP $ 猜想成立。
其實你誤會了什麼 $ NP $ - 硬手段；這並不意味著問題比 $ NP $ 問題; 這意味著如果你能解決那個問題，你就能解決任何問題 $ NP $ （所以它至少和任何一個一樣難 $ NP $ 問題）。但是，它沒有說明它是否會走另一條路。如果你能解決一個 $ NP $ - 完整的問題，您可能無法解決您的問題 $ NP $ -困難的問題。在實踐中，我們經常將問題稱為 $ NP $ - 硬（而不是 $ NP $ -complete）如果問題不是決策問題（也就是說，問題的答案不限於“是”或“否”），因此在迂腐的範圍內 $ NP $ （因此不在集合內 $ NP $ - 完整的問題）。