之前,在关于量子密码的系列文章中,已经描述了量子比特是什么,以及可以对这些数据执行什么操作。本文作者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),我们需要找到新的公钥算法。
以上所述就是小编给大家介绍的《什么是量子计算?》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 十八岁华裔天才携手「量子计算先驱」再次颠覆量子计算
- 从基础量子位到当下火热的量子计算机,一文助你入门量子计算
- [量子计算]量子搜索Grover算法
- 为什么抵抗量子计算需要量子密钥分发
- 学术向丨量子计算与区块链抗量子算法
- Google “量子优越性” 论文正式发表,量子计算到底是什么?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。