麻省理工学院的科学家揭开破解不可破解密码的量子飞跃

麻省理工学院的科学家发明了一种新的量子算法，可以让我们更接近破解复杂的密码系统。这一进步结合了近期突破的速度和更高的内存效率，可能为密码学中更实用的量子计算应用铺平道路。

量子密码破译之旅

我们大多数的数字通信都依赖于传统计算机无法在合理的时间内破解的加密方法。例如，广泛使用的RSA加密系统依赖于对极大数进行因式分解的难度。2,048位RSA密钥(617位数字)被认为可以抵御传统计算攻击。

然而，量子计算机有望彻底改变这一局面。1994年，现任麻省理工学院教授的PeterShor提出了一种量子算法，理论上可以比任何传统计算机更快地破解RSA加密。

麻省理工学院福特基金会工程学教授VinodVaikuntanathan解释了这一潜在影响：“如果大规模量子计算机真的建成，那么因式分解就无用武之地了，我们必须找到其他方法用于加密。但这种威胁有多大?我们能让量子因式分解变得实用吗?我们的工作可能会让我们更接近实际实施。”

尽管过去三十年来量子计算取得了重大进展，但我们距离建造一台足够强大的量子计算机来有效运行Shor算法还很远。目前的估计表明，大约需要2000万个量子比特，而当今最大的量子计算机只有大约1,100个量子比特。

量子因式分解的新方法

麻省理工学院的研究团队由Vaikuntanathan和研究生SeyoonRagavan领导，以纽约大学计算机科学家OdedRegev提出的最新理论改进为基础。他们的新算法将Regev方法的速度与更高的内存效率相结合。

量子计算机使用由量子门组成的量子电路来操纵量子比特进行计算。然而，这些门会引入噪声，从而导致错误。麻省理工学院的研究人员通过开发一种技术来过滤掉错误的结果并只处理正确的结果，从而解决了这一难题。

Vaikuntanathan解释了他们处理大数的新方法：“这有点像乒乓球游戏，我们从一个数字开始，然后来回反弹，在两个量子存储寄存器之间相乘。”这种方法使他们能够仅使用两个量子存储单元来计算任何指数，从而大大减少了所需的资源。

最终，该算法不仅速度更快，而且对量子噪声的适应性更强，所需量子比特数也更少。这些特性的组合将使其在未来更易于在真实的量子硬件上实现。

奥德·雷格夫(OdedRegev)在评论麻省理工学院团队的工作时表示：“作者解决了早期量子因式分解算法中最重要的两个瓶颈。尽管目前还不能立即投入使用，但他们的工作使量子因式分解算法更接近现实。”

重要性：这项研究代表着朝着使量子因式分解更加实用迈出了重要一步。随着量子计算机的不断发展，像这样的算法的改进可能会加速量子机器破解当前加密方法的时间表。这凸显了开发新的抗量子加密系统以保护未来敏感数据的紧迫性。

然而，值得注意的是，我们距离看到这些算法在真正的量子硬件上实现还很遥远。Ragavan提出了一个关键问题：“它真的能让我们更接近破解RSA密码吗?目前还不清楚;这些改进目前只有在整数远大于2,048位时才会发挥作用。我们能否推动这种算法，使其比Shor的算法更可行，即使对于2,048位整数也是如此?”

这项研究将在2024年国际密码学大会上发表，得到了美国国防高级研究计划局和美国国家科学基金会等多个组织的支持。随着该领域工作的继续，我们可以期待看到进一步的改进和潜在的新突破，这些可能会重塑数字安全的格局。