P=NP 認證的後果
讓我們假設P=NP。也就是說，每個可以快速驗證解決方案的問題也可以快速解決，無論這在形式層面意味著什麼。因此，不僅P=NP，而且還有實用的多項式時間算法來解決NP 完全問題。此外，證明是建設性的或非建設性的。也就是說，可以找到一種算法，即使我們無法證明它最終也會足夠快地開始使用。然後，保守秘密變得更加困難——這是一個大問題。讓我害怕的不是我們無法隱藏資訊，而是我們無法透露資訊。
在復雜的社會中，我們需要信任他人，而我們能夠獨立驗證的東西是不夠的。在實踐中，當機構反復向我們提供準確資訊時，我們會與他們建立信任。我沒有看到其他方法，所以如果我們無法驗證我們是否從特定機構接收資訊，那麼冒名頂替者可能會利用我們的信任，這是不允許的。因此，我們無法充分了解複雜的社會。如果沒有找到其他解決方案， P=NP會破壞目前的身份驗證，因此會帶來根本風險。
能否找到其他解決方案？如果P=NP，我們將擁有一個沒有隱私的世界，但是，為了減少我們在這方面的損失，我們可以嘗試圍繞這一事實建立身份驗證。與其實體向我們提供辨識它們所需的資訊，我們可以將其從它們中擠出來。一個想法是，在收到消息後，我們會發送包含一些資訊的消息，這些資訊將與原始消息一起發送回我們，因此我們會知道我們的消息已被接收，並且收件人至少想發送原始消息資訊。我們的消息是間諜軟體，由我們針對NP 完全問題的有效算法增強，我們用它來驗證原始消息的來源。
我將嘗試回答我認為您要問的問題，即：
如果 $ P = NP $ ，可以通過用互動式協議替換結構來“修復”密碼學嗎？
這是一個很自然的問題，但有一個眾所周知的（否定）答案。具體來說，任何需要固定（有限）輪次互動的互動協議都被稱為存在於稱為多項式層次結構的複雜性類中 $ PH $ . 先驗的可能是 $ P = NP $ ， 但 $ P \subsetneq PH $ . 在這種情況下，上述問題的答案是“原則上是的”（儘管我不知道任何結構）。
不幸的是，關於的基本結果之一 $ PH $ 是不是這是假的，意思是 $ P = NP\implies P= PH $ ，所以基於密碼學（在一個世界 $ P = NP $ ) 僅在有限的幾輪互動中是不可能的。這裡有一些關於協議的警告 $ \omega(1) $ 回合（這些屬於稱為IP的複雜類），但它們會非常慢（由於每一回合都會因光速而產生不可避免的延遲），因此它們並不是特別有趣。
還有一些其他潛在的方法可以在一個世界中獲得（類似於）密碼學 $ P = NP $ 但是，即：
- 使用“嘈雜通道”假設，例如竊聽通道，以及
- 使用量子通道
與復雜性理論密碼學（我不會在此總結）相比，兩者都有明顯的缺點，但它們的有效性不會受到威脅 $ P = NP $ ，如果您對在一個世界中的安全通信的可能性感興趣，可能是好東西 $ P = NP $ .
話雖如此，總體而言，對電腦進行身份驗證要困難得多。另一個“解決方案”是依靠面對面的身份驗證。當然，這裡可能會出現欺詐行為，但要大規模進行則要困難一些。