Credit:CC0 Public Domain检查问题的解决方案是否正确是否比解决问题更容易？这个问题被称为“NP对P”问题，是计算机科学和密码学中最深层次的基本问题，是任何互联网数据是否能够真正保密的核心。
在P = NP的不太可能的情况下，所有加密方案和保持我们在互联网上的数据隐私的方法都是不安全的。但是即使P不等于NP，即使有人设法证明了这一点，我们仍然不知道如何获得一个真正安全的加密方案。
康奈尔科技大学和康奈尔大学安·鲍尔斯计算与信息科学学院的计算机科学教授拉斐尔·帕斯和合著者、计算机科学领域的博士生·刘提供了一个解决方案——算是吧。
他们的工作在“基于EXP ≠ BPP的密码学的可能性”中有详细描述，该论文在CRYPTO’21上获得了最佳论文奖，并将在8月17日的会议上发表。
论文标题中提出的问题涉及随机性的概念，这是一个棘手的计算机科学和数学问题。根据帕斯的说法，EXP对BPP的问题——虽然没有“NP对P”那么有名——是另一个长期悬而未决的问题，也是该领域更加尴尬的原因。
"本质上的问题是，随机性能成倍地加速计算吗？"帕斯说。“那显然被认为是不可能的。我们不会认为随便扔一些硬币就能让我们成倍地加快计算速度。这有点疯狂，但人们仍未能证明这一点。”
如果利用随机性可以成倍地加速计算，那么所有的加密方案都可能被破坏。所谓的“暴力”攻击，其中列举了所有可能的密钥，现在可以有效地实现。
Pass和刘解决了这样一个问题，即简单地假设EXP不等于(使用随机度时，计算不能以指数方式加速)是否足以得到牢不可破的加密方案。为此，帕斯和刘重新审视了他们去年建立的加密方案和有时间限制的Kolmogorov复杂性之间的联系。
字符串(x)的时间有界Kolmogorov复杂度是在设定的时间内可以输出x的最短程序的长度。但是这项新工作考虑了一个不同的Kolmogorov复杂性y的概念:计算一个字符串(x)的“莱文-Kolmogorov复杂性”。问题:给定x，找到打印x的“最高效”程序，其中“效率”是程序长度和程序运行时间的对数之和。
他们的论文表明，当且仅当不存在能够计算大多数字符串的Levin-Kolmo gorov复杂度而不会犯太多错误的有效算法时，不可破解的加密才是可能的。
“所以要获得牢不可破的加密，”Pass说，“我们只需要证明没有有效的算法可以解决这个特殊的问题。”
虽然他们不能证明不存在这样的算法，但他们表明，假设EXP不等于BPP，不存在有效的“无错误”算法(一种要么产生正确答案要么说“我不知道”的算法)来确定大部分随机字符串的莱文-科尔莫戈罗夫复杂度。
帕斯说:“它不必为所有的弦解决它——它有时会放弃。“但当它给出答案时，它总是需要是正确的。”
换句话说，可能出错的算法在根据答对的问题数量奖励你的测试中表现很好，而无错算法在根据答错的问题惩罚你的测试中也表现很好。
他们的结果得出结论，莱文-科尔莫戈罗夫复杂性问题对于理解EXP和BPP问题以及不可破解的加密方案是否存在的问题至关重要。
帕斯说:“这个问题掌握着计算机科学中一些最重要问题的关键。“这个具体问题是根本性的，我们真的需要理解无错算法和可能出错的算法之间的差距。”
作者表明，如果这个差距可以被弥合——这在计算机科学中是一个巨大的“如果”——那么你不仅证明了牢不可破的密码学存在，即使EXP不等于BPP，而且事实上你还证明了NP不等于p
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
