P=NP世界中的对称加密

Question

我希望能找到关于攻击AES的量子计算洞察力的答案；然而，这个问题上的答案并不适用，因为“量子计算机在一般搜索问题上给出了二次加速比”。

让我们假设最坏的情况:构造性证明的P=NP。因此，3-SAT和直接多项式攻击AES和所有其他标准模型对称密码.

除了使用欧洲央行和每个密钥发送一个块之外，我们如何构建一个需要严重攻击才能打破的东西？除了一次性垫的特性外，量子验证的对称密码是否真的存在？

我认为我可以证明，如果您使用任何一种MAC，而不是多项式评估MAC (或其他具有其特征可否认性的东西)，则您的密码必然失败。

我可以证明加密的随机数据是可能的，因为你不能打破欧洲央行的随机数据，但这个证据是无用的。

我意识到在这个P=NP世界结束是不可能的。我还知道这个旧职位描述了为什么P=?NP是一个糟糕的易碎模型的很好的原因。我对这个问题很感兴趣，因为我相当肯定，任何解决方案都必须使用加密方法，这本身就是可以否认的。

一次性垫子具有这个属性；但是，如果可能的话，我宁愿得到一个不那么笨重的答案。

Answer 1

值得注意的是，\mathsf{P} = \mathsf{NP}不会从根本上威胁密码学--甚至是理论密码学。正如Meir Maor在他的回答中所提到的，这意味着没有单向函数，这意味着本质上没有“传统”密码学。

然而，单向函数和大多数密码学在理论上定义为在最佳攻击和诚实使用算法之间需要一个超多项式间隔。尽管如此，如果明天证明了\mathsf{P} = \mathsf{NP}，仍然可以存在一些函数，它们需要时间n来计算，而时间n^{10}则需要反转。这与\mathsf{P} = \mathsf{NP}一点也不矛盾。然而，对于所有实际目的来说，它都足够了:以N = 2^{10}为例，然后评估您的函数采取2^{10}步骤，而倒置它则采取2^{100}步骤。这种安全保证金对于大多数用途来说已经足够了。

这种单向函数，即求值与反演之间的间隙是一个固定多项式，而不是超多项式，称为细粒度单向函数。它们是密码学中一个新兴的研究课题(例如，这篇最近的论文)，主要是因为理论上它们可以建立在比已知的暗示标准OWF的较弱的假设之上(尽管从一般的、经过仔细研究的假设中显示出如此细粒度的OWF，而这种假设被认为并不意味着OWF至今仍是一个开放的问题)。它们可以用来构造细粒度伪随机发生器和流密码器.

如果我们证明了\mathsf{P} = \mathsf{NP}，我们对AES的最佳攻击仍然需要n^{10}步骤，这似乎并不荒谬。在这种情况下，经过一些适当的密钥大小调整后，每个人都会继续使用好的旧AES，就像什么都没有发生过一样，理论密码学家会将“假设此OWF采取\mathsf{superpoly}(n)步骤来破坏”替换为“假设此OWF采取n^{10}步骤来破坏”。

Answer 2

如果P=NP没有单向函数，就没有陷阱门单向函数，本质上也没有密码学。

如果是P=NP，它意味着验证密钥和找到密钥是同样困难的(直到多项式约简)。因此，有一次pads仍然有效，它们在理论上是安全的，不依赖于计算困难。但是，所有的加密，无论是否对称，哈希等都变得不安全。

实际上，量子密钥交换可以拯救我们，它将允许共享密钥材料的非加密安全通道，然后允许一个时间垫。

值得注意的是，即使P不等于NP，我们也有可能生活在密码远视中。我们不知道单向函数的存在，它们可能不存在，即使P!=NP。