DAOrayaki ｜量子密码学 vs 后量子密码学

Quantum Computing

a year ago • 15 min read

DAOrayaki ｜量子密码学 vs 后量子密码学

Quantum Computing

a year ago • 15 min read • Loading Views

DAOrayaki DAO研究奖金池：

资助地址: DAOrayaki.eth

投票进展：DAO Reviewer 1/0 通过

赏金总量：40 USD

研究种类：Quantum Computing,Post-Quantum Cryptography,Lattice-Based Cryptography

原文作者: Anastasia Marchenkova

创作者：xinyang@DAOrayaki.org

审核者：Yofu@DAOrayaki.org

原文: Quantum Cryptography vs Post-Quantum Cryptography

DAOrayaki 是一个去中心化的研究者组织和去中心化媒体，通过 DAO的形式去中心化地资助世界各地的研究者进行研究、翻译、分析等工作。DAOrayaki 由早期的 DAO 组织 DAOONE 核心成员发起，得到了Dora Factory基础设施的支持。欢迎通过文末方式提交星际移民、量子计算、DAO等相关研究，瓜分10000USDC赏金池！了解去中心化自治组织（DAO），探讨最新治理话题，关注DAO的发展趋势，欢迎加入DAOrayaki社区！

Originally published at https://www.amarchenkova.com on July 5, 2020.

通用量子计算机开发热潮渐起，未来很可能出现大规模容错量子计算机，为了保护我们的数据安全，研究能够取代现代密码体系的后量子算法和量子密码学就显得至关重要。

肖尔算法是密码学的杀手级算法。运行这种算法需要足够大规模的量子计算机，短期内无法实现。由于需要的量子比特是数百万级别，一些科学家认为可以运行肖尔算法的量子计算机永远不可能建成，但其他人认为这只是时间问题，现在就要未雨绸缪。

保护数据安全的途径有两种。一种是后量子密码学，这是一套新的经典密码算法标准，另一种是量子密码学，它利用量子力学的特性来确保数据安全。两者的工作原理有本质不同，在未来的通信安全领域都可能占有一席之地。

后量子密码学

后量子密码学依靠经典加密手段来抵御大型量子计算机的攻击。它不使用任何量子特性，也没有任何专门的硬件。它是纯粹的数学，使用难以破解的数学难题，就像我们现有的密码学一样。后量子密码学避免使用整数因式分解和离散对数难题来加密数据。因为量子计算机上运行的算法可以很轻松破解这两种问题。

后量子密码学算法将不需要任何量子硬件来加密数据。因为这些算法的加密建立在新的数学难题上，不容易受到已知的量子计算攻击。值得注意的是，在确保能抵御（已知）量子计算攻击的同时，也要能抵御超级计算机的攻击。

政府和国家标准及技术研究院NIST很早就意识到问题存在。早在2013年，相关的讨论就建议从Suite B密码机切换到可以实现量子安全的加密手段。2016年底，为寻找合适的能够抵抗量子计算攻击的公钥加密算法，NIST曾举办了一个后量子密码学标准竞赛。

获胜的算法必须具备哪些特性？

它必须能抵御量子计算的攻击，以及传统攻击。
它必须足够快。加密也需要在网络、智能手机、传感器和其他计算能力有限的设备上运行，过于慢的算法不利于通信。

关于这26种候选算法的进一步细节发表在NIST内部报告（NISTIR）8240，即NIST后量子密码学标准化进程第一轮的情况报告。

这26种算法各不相同，但可以大致分为3类：基于格子、基于纠错码和基于多变量的密码系统。这当中，基于格子的密码学研究早在1996年就开始了，已有大量的研究成果，被认为是后量子密码学标准的最有力的候选者之一。

格密码学

格密码学系统是如何工作的？我们可以把格子看成很多点组成的网格——二维（x，y）或三维网格的坐标（x，y，z）我们都比较熟悉，但网格的维数可以多得多。随着维数的增加，很多适合密码学的数学难题产生了，包括最近向量问题、有界距离问题和覆盖半径问题。基于格子的问题使用的网格通常有数百或数千个维度，目标是找到两个相邻的格子点。目前的算法，无论是经典算法还是量子算法，想解决这些问题需要花费时间是指数级的。

在2020年和2021年，NIST将继续评估和测试这些后量子加密标准，预计在2022-2024年的颁布标准草案。

再之后，我们就可以开始在全世界范围内升级计算系统以使用这些算法。我们需要升级几乎所有在线发送的东西，以对抗大型量子计算机。这种切换的代价高昂，而且相当耗时。在这之前，经典加密算法从理论到全面实施花了20年时间。当中包括软件开发，硬件层改造（如果需要的话），以及掌握破解的精确难度。而现在，我们还必须研究如何对尚未建成的量子计算机带来的风险进行评估。如果等到量子计算机达到破解现代加密的规模时，再去寻找量子安全的密码学系统就太晚了。

量子密码学

量子密码学使用量子力学原理来实现安全保证。因为利用物理定律而不是数学证明，量子密码学在理论上是 "不可破解的"。当然，这里所说“不可破解”不包括旁路攻击。

量子密钥分发利用量子力学特性来生成共享密钥并分发，同时可以确保没有第三方窃听。量子态的几个自然属性，使量子信息多了一层安全保护。量子态在被测量时就会塌缩。如果攻击者试图在基于纠缠的协议中读出信息，量子态将不再处于叠加态。此外，量子力学的无克隆定理指出，量子状态是不可复制的。攻击者不能复制正在传输的量子信息并对其副本进行操作。如果有窃听者，Alice和Bob会知道（Alice和Bob常用于密码学中描述通信的两端）。

因为量子密码学是基于物理学定律，而不是我们对数学和难题的理解，所以无论经典计算机和量子计算机多么强大，它都将是安全的。

说到长距离量子通信对量子特性的利用，最著名的量子密钥交换的通信协议是BB84和E91（基于纠缠的协议），他们会产生一个共享安全密钥。

BB84量子密钥交换协议

如何在量子系统上使用BB84协议？

1. Alice准备好她要发送的bit串，并随机选择一个偏振基。她可以选择水平/垂直偏振基，其中水平偏振是0状态，垂直偏振是1状态。她也可以选择对角线偏振基，向下倾斜的偏振基是1状态，向上倾斜的为0状态。

2. Alice制备一个光子序列，发送偏振。

例如，Alice选择了一个bit串01，并选择了一个水平/垂直偏振基。然后，她发送的第一个光子将是水平偏振，第二个将是垂直偏振。

3. Bob可以选择对角线或水平/垂直为基础进行测量。但如果他随机选择了错误的基础时，他就会失去信息。如果他选择用水平和垂直探测器来测量一个对角线偏振的光子，他就会得到一个随机的答案，并破坏了原来的偏振情况。如果他选择了正确的基础，那读出的结果就是正确的。这里我们检测并记录整个bit串的结果。

(实际上，可以想象一个偏振过滤器，比如一个酷炫的太阳镜。它只让正确偏振的光子通过，如果没有光子，意味着偏振过滤器阻止了它的传输）。

4. Alice和Bob公开比较他们的编码基础。对照上面的图表，Alice说，对于光子1，我使用的是水平基础。如果Bob用对角线的基础来读取，他只会得到随机结果。于是这个bit被丢弃。他们只保留制备光子的基础和测量基础匹配时的bit，来拼出bit串，这个序列的最后部分是共享的密钥。

如果邪恶的伊芙（密码学中常用伊芙Eve指代窃听者）想窃听的话，她可以进来窃听光子。她和Bob一样可以选择一个随机的基础。然而，一旦伊芙干扰了光子，就会在测量中引入错误。Alice和Bob可以通过选择密钥的一个子集并公开比较来检查错误。如果错误太多（多于信道或测量带来的预期损失），他们就会丢弃钥匙。

为什么不干脆全换成量子密码

如果量子密码学这么安全，我们为什么不到处都用呢？原因是量子密码学需要有专门的设备。例如，你需要有光子探测器、分束器和其他设备来使其工作。而像手机这样小的设备，显然不太现实。

此外，尽管加密本身享有物理学定律的安全保证，但攻击不能被避免。即使没有量子计算机，目前称得上安全的经典加密算法也会被入侵。被入侵的原因不是某些计算机可以破解加密算法，而是存在旁路攻击。这是我们在实现密码系统中产生的弱点，而不是算法本身的弱点。我们可以确信在量子密钥分配协议中，没有人可以在创建密钥的过程中直接截获光子，但在量子密码学中也会存在旁路攻击。

硬件要求使得量子密码学很难适用一切场合。所以，大多数设备的安全，仍然需要后量子密码协议来保证。后量子密码学和量子密码学在本质上有区别，但在拥有大型量子计算机的未来，为加强安全，两者不可或缺。

译注：旁路攻击Side Channel Attacks，指绕过加密算法，利用加密算法的硬件实现的运算中泄露的信息，如执行时间、功耗、电磁辐射等，结合统计理论实现对密码系统的破解。

参考资料

肖尔算法：https://www.amarchenkova.com/posts/break-rsa-encryption-with-this-one-weird-trick
NIST内部报告：https://csrc.nist.gov/publications/detail/nistir/8240/final

通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！

官方网站：daorayaki.org

Discord server: https://discord.gg/2UjpmPH9

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

微信助手：DAOrayaki-Media