什么是量子计算？

之前，在关于量子密码的系列文章中，已经描述了量子比特是什么，以及可以对这些数据执行什么操作。本文作者Nigel Smart，由格密链社区的徐昊翻译。

自量子密码成立以来，已经在量子计算机算法方面开展了大量工作。最重要的，与密码学最相关的是Grover搜索算法（Grover's algorithm）和Shor因式分解算法（Shor's algorithm）。

首先，我们来讨论Grover搜索算法。计算中的经典问题是给出N个项目的列表X以在列表中搜索具有属性的项目，我们将称之为P。在数学上我们正在寻找X中的x使得P(x) = 1，比如说。现在，如果X是非结构化集合，那么通常我们能做的最好就是获取X中的每个元素并测试P(x) = 1。如果我们怀疑只存在一个这样的x，那么这将需要N步。密码学上认为X是AES的密钥集合，P(x)是测试密钥是否将一个明文映射到给定密文的函数。传统的做法是，我们尝试定义密码，让它努力寻找x，使得该P(x) = 1完全由N给出。

然而，量子可以让我们做的更好。Grovers搜索算法可以在sqrt(N)步骤中解决上述问题。这意味着具有128位密钥的AES密码在量度上仅提供64位安全性，而不是128位安全性。对于分组密码，这意味着如果我们希望防止量子攻击，我们需要将密钥大小加倍。

Grovers搜索算法的另一个应用是在哈希函数中查找冲突。散列函数H中的冲突是一对值x和y，如H(x) = H(y)。哈希函数旨在使查找冲突变得困难。在签名之前对消息进行数字签名方案中需要这样做。因为如果你可以找到碰撞(x，y)，那么你可以将消息x上的签名作为签名传递给消息y。

传统上，如果哈希函数的输出是来自大小为N的集合X的元素，并且输出基本上是随机的，那么找到碰撞的最佳算法将采用sqrt(N)步骤。但是，Grovers的搜索算法可以适应这种情况，它允许我们在N ^ {1/3}步骤中量子地找到碰撞。因此，如果我们的哈希函数是量子安全的，我们需要使用具有更大输出长度的散列函数。

然而，Shor的因式分解算法最有趣的量子算法。该算法实际上做的是找到有限abelian群中的循环长度。Shor的算法可以在很短的时间内解决这个问题，这是我们不知道如何在经典计算机上做的事情。各种有趣的加密问题可以降低到在有限的阿贝尔群中找到循环长度的问题。最重要的是分解数字并找到离散对数。问题是，因式分解和离散对数是当今使用的所有公钥密码体制的基础。因此，量子计算机的发展将使所有部署的公钥算法立即变得不安全。

总而言之，如果构建量子计算机，我们必须增加对称密码的密钥长度，例如AES（比如使用AES-256而不是AES-128），我们需要找到新的公钥算法。