如果是P=NP，什么仍然是加密安全的？

Question

我知道，我知道-“如果P=NP”是一个非常大，高影响的假设。

但这是一种假设。

我的意思是，显然RSA (以及类似的混淆方法)很可能变得完全不相关--或者他们会吗？相对于指数时间而言，在多组分中可解是一个重大的打击，但它们是否能利用如此大的公钥/私钥(如果P=NP，那么更有效的素数定位器似乎很有可能)，以致于破解它们仍然“困难”吗？

这些大多只是讨论的要点。就原始问题而言:什么密码学方法最终不依赖于P!=NP？

Answer 1

任何经典密码体制在本质上都是算法性的，即任何经典密码体制都可以被打破(原则上)。我认为即将到来的量子信息领域有一天能够使通信变得安全。如果您想阅读有关量子密钥分发协议的更多信息，请尝试搜索: BB84协议、B92协议和eckert协议。

Answer 2

那得看情况。如果P= NP，但求解一般NP-完备的SAT的最佳算法是具有适当大常数的O(N^10)，那么尽管是多项式，我们今天使用的N值的传统密码仍然有效。如果P= NP对一般NP-完全问题，即具有适当小常数的O(N^3)有解，那么许多密码学就会变得很弱。

检查素数已经相当有效(不是指数型时间)，因此将SAT减少到P并不一定会以任何显著的方式加速对素数的搜索。