葱一根 - one sat on Nostr: 7 量子密码学 ...

7
量子密码学

第六章介绍了传统的二进制密码学，它可以抵抗已知的量子攻击。本章涵盖了基于量子的密码学，使用量子特性的量子设备上存在和操作的密码学。基于量子的密码学本身也能抵抗已知的量子攻击，以及来自传统二进制计算机的攻击。在后量子世界中，二进制密码技术是一种可以接受的防御，因为在这个世界里，还没有足够广泛、廉价的量子计算和网络设备。但量子密码理论上对所有已知的攻击都要安全得多，而且很可能成为长期安全的密码选择。在本章中，我们将介绍量子密码术的主要类型，包括随机数发生器（RNG）、散列、密钥分配和数字签名。第八章将探索量子网络。
在所有这些量子密码的实现所固有的是所有流行的量子力学性质。然而，四种特殊的量子特性一次又一次地被证明是量子密码学如何提供保护超能力的核心：叠加、纠缠、观察者效应和非克隆定理。叠加比二进制数字提供了更多可能的选择。纠缠通常为所涉及的密码秘密在授权方之间传递提供了途径。观测者效应和不可克隆定理使得实现不可检测的窃听变得更加困难。在我们讨论各种量子密码实现时，您将了解更多关于这些属性的信息。
值得注意的是，由于可工作的量子计算机和设备还比较年轻，这样的系统还没有几十万个。这并不是说没有任何类型或某些类型不存在不断增长的数量。事实上，有很多现有的量子设备（即，基于量子的RNG和密钥分配系统可能数以千计）已经存在了近二十年。但是，没有人期望在未来的很多很多年里，量子密码学能达到它的二进制表兄弟那样的规模。抗量子密码肯定会首先站稳脚跟，并且足够安全，可以把我们带到一个只能使用量子密码的时代。
话虽如此，本章研究了量子密码的现状。有些类型的量子密码技术和设备已经相当成熟，可以在今天得到广泛的应用，而另一些类型的量子密码和设备仍然非常年轻和复杂，因此今天需要一个罕见的、昂贵的用例来考虑它们。我们将首先讨论RNGS，它在大多数密码学中都使用，而不管类型如何。

量子RNG

在第5章“后量子世界是什么样子？”中首次提到，大多数密码函数都需要强随机数作为算法的关键初始部分。如果没有真正的随机数，任何依赖的算法或函数都不安全。在传统的二进制世界中，有一个大多数电脑用户不知道的不便的事实：传统的二进制电脑不能产生一个真正的随机数。我们只能得到看起来几乎是真正随机的东西。

随机并不总是随机的

二十多年前，我在一家大型联合企业担任IT主管时学到了这一课——随机并不总是随机的。这家企业有一个小业务，就是在比赛中对专业运动员进行药物测试。这些运动员包括职业网球运动员和赛车手。比赛的胜利者总是会受到测试，而其他人在这一年里也会被随机地测试。为了随机挑选尿样的运动员，体育协会或竞赛会每月向该公司发送一份文件，其中包含所有运动员的姓名和其他身份信息，比如会员号码。我会把文件上传到程序中，并运行随机抽样选择器特性。程序将输出从该月份的输入文件中随机选择的运动员，我们将把结果转发给运动员的代表组织。
有一天，我被带到一个紧急会议，因为一个顶级车手已经连续两个月被“随机”选中。我接到高级管理人员的电话，他们正在回应司机的投诉，他是不公平的目标。我查看了程序的编码（用 dBASE III +编写），没有发现编码错误，并报告了相同的错误。管理层举办了一场盛大的“狗和小马”表演，在那里，赛车组织的高级官员和车手代表听取了我——常驻计算机专家——的意见，驾驶员的重复选择仅仅是真正的随机化工作的一个因素。在真正的随机中，每个人在每一轮选择中被选中的可能性都是一样的，而司机的连续重复选择只是随机中的随机。每个人都喜欢了解真正的随机性是如何工作的，司机参加了他的第二次药检并通过了，每个人似乎都很高兴把这件事抛在脑后。然后，同一个司机在下一个月被选中。
赛车组织和车手从来没有听说过这个第三顺位。我们意识到我们有一个真正的问题。我重新检查了代码，没有发现错误。但是，为了弄清楚到底发生了什么，我创建了一个新的程序，它只包含相同的随机化编码例程（用 dBASE III +编写）。不多不少。我使用数字1到100，并告诉程序运行10,000次，并输出任何特定数字被选中的频率。在一个真正的随机选择过程中，所有的数字都应该得到大约1%的关注，在这里和那里有一些小的偏差。但当我运行完这个程序后，发现只有少数几个数字被选中的概率高达15%，一个数字的受欢迎程度超过20%，还有很多数字的受欢迎程度接近于0%。我惊呆了。软件程序的随机功能甚至不接近于真正的随机。
我决定编写一个不依赖dBASE的更好的程序III +的随机函数，显然有问题。这一次我使用了微软Windows的RNG功能。我重新运行了同样的测试，但这次有一千个数字和成千上万的测试轮。再一次，我被震撼了；虽然Windows的RNG更好，但过度选择和不足选择的模式仍然出现。于是，我用汇编语言编写了一个（我在20世纪80年代末学会了反汇编计算机病毒），它使用计算机内置的RNG功能。我重新做了测试。虽然它比Windows RNG更接近随机性，但它也不是完全随机的。我发现了偏爱和回避的明确模式，尽管它们比之前的测试要微妙得多。那时我才知道，在计算机世界里没有真正的随机性，而只有随机性的伪近似值。您将看到许多使用术语伪RNG（也称为PRNG）的密码学家和密码例程指出了这一事实。他们承认我们现在都知道的事实：在二进制计算机上没有真正的随机性。
在我自己发现后的三十年里，所有涉及的RNG--一台内置计算机的RNG--包括微软Windows(Microsoft Windows)和其他许多不同程序的定制RNG--都被编码成更接近真正的随机性。但如果你做一个类似我早期做的测试，仍然会有一些无限小的喜爱和回避。
这是因为传统的二进制计算机无法实现真正的随机性。所有的二进制计算机都依赖于一个或多个位于主板上的石英晶体和其他硬件来进行操作和计时。这些石英“时钟”每秒振动（称为振荡）一定和恒定的次数（每个单独的时间周期被称为时钟滴答或时钟周期）。计算机主板上的所有东西都是由主板的石英钟振荡周期发送的定时信号来运行的。今天的CPU有自己的内部时钟振荡，它控制CPU什么时候可以做某事（例如，将该位移到CPU寄存器中，将该数字和该数字相加，擦除该寄存器中该值）。CPU中的每个内核一次只能做一个动作（除非你在做并行操作），并且这个操作只能在CPU时钟的每个滴答上发生。CPU的时钟比主板的时钟快得多，但通常是主板时钟周期的精确数量级（例如，对于每个主板周期，CPU可以执行100倍的操作，每个操作在时间上均匀分布）。也可以有其他的定时时钟，但主板和CPU时钟是最重要的。
计算机所做的每一件事都源于一个均匀分散的时钟周期，它保证每秒平均分裂次数，这与随机相反。这种缺乏随机性的真理来源阻止了任何依赖它的东西成为真正的随机因素，不管上层依赖的硬件或软件有多大程度上可能试图近似真实的随机性。最好的硬件和软件例程看起来很好地近似于真正的随机性，但它们并不是真正的随机。我们所能做的最好是尽可能接近真正的随机性，这样任何由此产生的错误对于产生依赖的应用程序来说都是很小的。
这并不是说没有好的和坏的PRNG，或者有些PRNG不比其他PRNG好。NIST创建了一系列的测试，任何量子或其他RNG供应商或客户可以运行，看看他们的RNG与理论上完美的随机数生成器相比有多好或多坏。他们在NIST特别出版物800-22（https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf).
附注：RNG的官方定义是它的随机性近似必须是非确定性的(即不能提前确定)，而PRNG是确定性的。有趣的是，因为PRNG是确定性的，它们必须以RNG的种子值开始，我们知道在二进制计算机上不可能是真正随机的。具有讽刺意味的是，在二进制计算机上，一个好的PRNG可以返回一个比RNG给它的种子值更随机的数字。

为什么真正的随机性如此重要？

大多数加密算法都需要一个真正的随机数作为算法的开始（通常称为初始化向量、种子值或nonce），然后使用困难的数学来产生一个真正难以分解或猜测的结果。例如，RSA需要两个随机选择的大素数作为其算法的一部分（通常在数学上表示为p和q）。一旦随机素数被选中，它们就被卷入到数学中，产生一个难以分解的结果。
但是假设质数，不管有多大，都不是随机的。假设，由于某些错误，每次选择的质数每次都是相同的。这类似于像 X + 23 = Z 这样的代数公式但你知道X总是5有了这些知识，无论何时Z是28，X是5你有多少次运行“算法”在这种情况下，如果素数总是相同的话，RSA的结果也总是相同的。任何知道这个错误的攻击者，看到相同的预期结果，将立即知道所使用的素数是什么，他们将能够立即将结果分解回原来的X和Z分量。密码就没有保护了。
如果说这种零随机性的场景听起来有点牵强的话，在计算机世界里已经发生过很多次了。人们依赖于他们被告知是好的，经过测试的，可靠的密码来保护他们的机密数据，后来得知，实现密码的程序在其RNG中有一个错误，这完全使密码的保护无效。这已经发生在广泛使用的程序，保护数以百万计的网站和计算机，不止一次。

Debian OpenSSL RNG错误

最著名的不安全RNG bug的例子之一是2006年的Debian OpenSSL RNG崩溃。Debian Linux是一个非常流行的Linux版本，包括一个被称为Ubuntu的“发行版”，它经常被那些第一次尝试从微软Windows转换到Linux的人使用。OpenSSL是开放源代码操作系统计算机使用的最流行的开放源代码加密编程库和程序。当2006年OpenSSL的一个更新版本“分叉”到Debian时，Debian OS的一个开发者错误地解释了一个编译器代码警告信息，删除了几行相关代码，并意外地删除了几乎所有的随机性。
直到发出数百万个非随机密钥后才发现这个错误，并且在2008年发现了这个错误。去除随机性意味着可能的密钥从数万亿种可能的组合减少到最多只有32767种组合中的1种。并且在许多情况下，成千上万的实现共享完全相同的密钥对。年后，数以万计的网站仍然包含众所周知的和广泛记录的密钥对，今天仍然存在数千个（虽然大多数在互联网上使用的现在已经过期）。黑客们甚至创建了一些工具来检查和暴力破解依赖于该漏洞的数字证书和密钥对；见www.madirish.net/309。
您可以在以下网站阅读更多关于Debian RNG bug的信息:
www.schneier.com/blog/archives/2008/05/random_number_b.html, https://hdm.io/tools/debian-openssl/, https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166
www.schneier.com/blog/archives/2008/05/random_number_b.html、https://hdm.io/tools/debian-openssl/ https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166
https://security.stackexchange.com/questions/143133/all-weak-debian-openssl-dsa-key
我不希望你认为只有一个开发者曾经犯过这样的错误。在历史上有更多的bug rngs的例子在这里：https://en.wikipedia.org/wiki/Random_number_generator_attack.而这还不包括政府和公司可能有意制造出的问题，如第6章所述，“抗量子密码学。”确认随机性是一种需要。
但更大的问题来了。即使RNG不包含一个糟糕的编码错误，它们仍然不是真正的随机。它们看起来都像 dBASEIII + RNG 示例。它们可能看起来是随机的，但当由拥有深厚资源的合适的人进行分析和审查时，非随机性的口袋就会显露出来。这是因为在二进制计算机上，真理的来源是一个石英晶体时钟，而计算机中每个进程运行的时钟周期不是随机发生的。缺乏真正的随机性给密码攻击者提供了一个“婴儿床”，可以轻易地破坏密码学和其他需要真正随机数的保护机制。
更糟糕的是，大多数抗量子密码都依赖于二进制的RNG或PRNG。它们的保护的弹性仍然是令人难以置信的高，它们是依赖于一个固有的薄弱RNG。这种困境常常被各种量子抵抗密码的创造者作为他们无法完全控制的设计风险来解决。由于这些RNG问题，无意或其他原因，重要的是随机生成的数字是真正的随机和可证明的随机。如果没有量子设备的参与，这两件事在传统计算机上都是不可能的。

基于量子的RNG

输入基于量子的RNG（QRNG）。QR NG是基于量子的设备，可以产生真正可证明的随机数。至少自2001年以来，已经有了多个真实世界的QR NG，在此之前，还有关于如何创建它们的论文。大量生产的例子有几十个。它们是目前产量最高的量子器件。量子随机数产生的方式多种多样，使用不同的量子材料和机制来产生真正的随机数。
大多数QR NG的核心是叠加、纠缠和不确定性的量子特性。在测量之前，量子属性可以是所有可能的状态，你不能提前预测某个特定属性的值。一起，你就得到了产生真正的随机性所需的基本属性。大多数QRNG器件以这样或那样的方式使用光子的量子特性作为它们的主要来源。

贝尔不等式定理

自从量子物理学发现以来，物理学家和密码学家一直担心他们所观察到的量子性质是真的量子行为还是其他什么东西（有一个他们已经错过的经典解释）。在1930年代，爱因斯坦和其他物理学家提出理论，认为当时未知且无法解释（经典）的局部隐变量可能是所有科学家所看到的所谓量子行为的原因。从本质上讲，爱因斯坦并不相信科学家们所看到并解释为量子行为的东西真的是量子行为。他（和其他人）想知道它是否可能是符合标准的经典物理模型的其他东西。他们所猜想的就是所谓的局部隐变量理论。
局部中的局部隐藏变量指的是影响对象并决定其行为的变量或属性在对象上、在对象内、在对象附近或以其他方式直接附加到对象上。隐藏的部分意味着当前没有看到或解释局部变量。
局部隐藏变量的论点可以用这个愚蠢的寓言来解释。假设在一个非常寒冷的气候中，有一群人一直被观察到，他们的手总是莫名其妙地比他们周围的环境和身体的其他部分都要温暖。不管外面的温度是多少，他们的手正好温暖了两度。
进一步假设，一组科学家假设，人的手周围的天气一定总是比影响人们身体其他部分的天气更温暖。他们不能解释为什么只有人的手所在的区域天气比较暖和，只是说在所有的观察中都是这样，这是为什么人的手总是比较暖和的一个“合理”的解释。科学家们甚至给它起了个名字，叫“微天气”，经过几十年的观察，它被越来越多的科学家广泛接受了很多年。
后来，当想象中的科学家更仔细地观察时，他们看到这些人一直从口袋里掏出手套来保暖。这不是什么新奇和美妙的东西；它是一种少了很多刺激和基本的东西。这个例子说明了物理学家的恐惧，他们害怕不能正确地解释他们在现有的经典理论中看到的东西，并可能过早地把一些无法解释的行为称为量子行为。量子物理学似乎与每个科学家以前所观察到的东西背道而驰。
爱因斯坦还提出了一种结论性的方法来证明或否定局部隐变量的存在。如果局部隐变量可以被证伪，那将为量子力学的存在提供更多的证据。爱因斯坦在世时并没有得到证明（他于1955年去世），但他为物理学界提供了一种实验方法，可以排除最后一种相反的可能性，并弄清楚量子物理学是一种新的奇妙的东西，还是只是经典物理学中缺失的一个方面。
1964年，爱尔兰物理学家John Stewart Bell在他的开创性论文《论爱因斯坦-Podolsky-Rosen悖论》中，从数学上证明了局部隐变量不能解释观测到的量子行为，他建议可以进行实验来证明这一点。没有对贝尔的提议进行理论解释（它涉及角度、自旋以及量子粒子和它们的性质的测量差异），它显示了在一个物体的性质和如果只有经典行为（和局部隐变量）存在的情况下所观察到的预期测量之间的细微差异。从图形上看，在一个经典世界中，测量的差异将遵循直线，但在量子是真实的世界中，测量将更像一个钟形曲线（见图7.1作为一个例子）。事实证明，实验观测的形状总是更像一个钟形曲线，从而证明了量子特性的存在。预期的经典测量和现实生活中的量子测量之间的差异被称为贝尔不等式破坏。
[插图]
图7.1用图形表示的贝尔不等式
简单地说，贝尔创建了一个实验框架，如果我们只有经典物理学，答案只能是假的，但我们看到答案总是真的所以不能只涉及经典物理学。本质上，贝尔最终“证明”了量子物理学，证明了局部隐变量不可能被涉及。记住，物理学家不需要等待图片才能相信什么。实验和支持数学就足够了。
从20世纪70年代开始，一些物理学家进行了实验，给出了贝尔不等式定理所预期的结果，但一些观众认为实验设计得很差，可能有某种方式偷偷摸摸的局部变量仍然可以在工作（被称为贝尔的漏洞）。但经过数百次实验，贝尔定理从未失败，2015年，一个明确的，无漏洞的实验进行了(www.physicsforums.com/threads/another-loophole-free-test-of-bells-theorem.842620/),终于毫无疑问地证明了贝尔定理。贝尔定理的一个相当好的解释是在这里：https://en.wikipedia.org/wiki/Bell%27s_theorem.
注意：虽然这看起来违反直觉，但“违反”贝尔不等式定理是一个好的和预期的结果，意味着实验或设备正确地显示了量子特性。“违反”是测量的结果与你只从经典物理学得到的结果不同。
所有使用纠缠的量子设备，包括QR NG，都应该进行测试，以确保它们通过贝尔的测试。开发人员希望确保他们交付的结果是纯量子的，并且不允许在结果中出现一些经典的、非量子的错误。这可以在创建、测试和认证过程中完成。这是特别重要的QR NG的真正的随机性，必须得到保证，以保证最强的安全性，在其余的任何依赖的实现。
还有一种理论上的担忧是，使用纠缠的QRNG可能被证明通过了贝尔的测试，然后被恶意修改，输出非随机数。例如，也许一个敌对的民族国家制造了一个QRNG组件，一个受欢迎的QRNG品牌所依赖的组件看起来是安全的；但实际上，它输出的一长串"看起来随机的"数字是秘密记录的，这意味着民族国家知道它们是什么，也知道它们将是什么。QRNG应该可以被任何人测试，以确保它符合贝尔不等式定理，并且是真正随机的。最佳设计的QR NG的设计，使他们在操作过程中进行自我测试，以确保他们违反贝尔不等式。你会在这里找到一篇关于这个概念的好论文：文章/npjqi201621。
此外，希望证明自己是随机的QRNG将采取NIST 800-22测试创建来测量任何RNG（量子或非量子）的随机性，并张贴他们的结果。客户应该能够运行相同的测试，并得到类似的结果。您可以在这里找到一个QRNG供应商的测试结果示例:
http://marketing.idquantique.com/acton/attachment/11868/f-004c/1/-/-/-/-/Randomness%20Test%20Report.pdf
但要证明QRNG（使用纠缠）提供的数字是真正随机的，最好的测试方法是证明它们是在违反贝尔不等式的情况下产生的。证明是在量子层面上提供的。到目前为止，唯一能做到这一点的商业QR NG是剑桥量子计算的QRNG被称为铁桥（IronBridge）（IronBridge）。https://cambridgequantum.com/cqc-unveils-the-worlds-first-commercially-ready-certifiable-quantum-cryptographic-device/)以及NIST目前正在开发的私有版本（稍后将介绍）。

工作的QRNG

在早期，QR NG充满了长长的实验室，通过在两个设备之间发射激光来工作，两个设备之间被许多激光光缆隔开。但是QR NG越来越多地被创建在一个“比萨盒”计算机单元大小的设备中，或者甚至被创建为可以插入到大约独立网络接口卡大小的计算机中的小接口卡。
您可以从多个供应商购买各种形式的工作的QRNG，从小型原始设备制造商（OEM）芯片到价格低于1000美元的服务器。它们被认证可以与许多操作系统一起工作，包括Windows、Linux、BSD、Solaris和苹果。它们有代码库、API和几种编程语言的接口。需要QRNG服务的公司已经购买和使用它们很长一段时间了。QRNG被用于银行、科学、彩票、电信、金融和军事领域。
瑞士公司ID Quantique(www.idquantique.com/random-number-generation/overview/)早在2001年，QRNG就成为了第一家拥有真实世界的QRNG的公司。自那以后，他们发布了许多不断成熟的产品。图7.2显示了三种不同的ID Quantique QRNG产品，可以插入计算机的内部接口插槽。
其他出售QRNG的公司包括澳大利亚的Quint精华实验室(www.quintessencelpos.com/)、总部设在美国的ComScire公司(https://comscire.com)，和加拿大量子数字公司(www.quantumnumber斯科p.com))。你会发现一个很好的总结文章，这些公司和他们的产品在这里：www.nanalyze.com/2017/02/quantum-random-number-generator-qrng/. 您甚至可以在Internet上的几个免费站点生成和使用您自己的量子生成的随机数，包括https://qrng.anu.edu.au.

NIST QRNG公共信标

NIST在2018年创建了一个QRNG(www.nist.gov/news-events/news/2018/04/nists-new-quantum-method-generates-really-random-numbers)用高强度激光照射晶体以产生纠缠光子。随机性被证明是“在1%的万亿分之一以内”，这是它能得到的最好的结果。NIST项目的目标是创建一个公共随机性信标，任何人和任何程序都可以使用（https://csrc.nist.gov/projects/interoperable-randomness-beacons).最初NIST打算开发一个私人服务，但决定世界可以受益于一个值得信赖的公共QRNG真理源。
图7.2示例ID数量QRNG
Courtesy of ID Quantique
由ID数量友情提供

QRNG的缺点

QRNG的缺点包括成本和互操作性。你可以买到相对便宜的QRNG（几百美元起），但PRNG是免费的或几乎免费的。每台电脑都已经内置了一个或多个要使用QRNG，您必须购买、安装、接口和使用它。目前，很少有应用程序与QRNG一起工作，也没有超级流行的现成软件默认与QRNG一起工作。QRNG供应商已经创建了软件和驱动程序，以允许现有的应用程序与他们的产品接口，但大多数应用程序还没有必要的“胡克斯。”开发人员可以很容易地添加它们，但对于绝大多数依赖RNG的应用程序来说，它们并不存在。这与传统的RNG形成了鲜明的对比，后者目前已经被每个现有设备和依赖应用程序所使用。
QRNG是受欢迎的设备，甚至前量子世界，因为它们给我们可证明的随机数，改善所有相关的加密操作，经典和量子。

量子哈希和签名

本节讨论基于量子的散列和数字签名。

量子哈希

如前所述，散列是单向加密函数，其为所检查的唯一内容创建/输出唯一的代表性字符或位集合（称为散列、散列结果、数字签名或消息摘要）。散列是必需的，并在许多其他加密过程中使用，如加密和数字签名。传统的散列是量子敏感的前图像攻击（虽然不是每https://cr.yp.to/hash/collisioncost-20090517.pdf).因此，需要基于量子的散列。
基于量子的散列可以接受传统的二进制输入或量子输入，并返回基于量子状态的散列。采用二进制内容并返回量子散列的量子散列称为经典量子散列.像任何其他散列，传统或量子，它应该是抵抗前图像攻击，第二个前图像攻击和碰撞。量子散列自然会导致基于量子的数字签名。
一些基于量子的散列符合这些条件，尽管大多数还没有经过长时间的很好测试。虽然一些量子散列已经在实际工作设备中实现，但大多数都是简单的思想实验，以证明量子散列是可能的，并且可以在需要时大规模实施。许多关于量子散列的科学研究论文是可用的。
例如，2013年俄罗斯人Farid Ablayev和Alexander Vasiliev提出了一种理论上的经典量子散列（https://arxiv.org/pdf/1310.4922v1.pdf).他们的量子散列算法（见图7.3）在数学上很复杂，包含了足够多的高等数学，可能会让大多数非数学专业的学生倒胃口。简而言之，使用数学证明，他们提出并证明了所有必需的哈希属性，如量子属性所表示的。
[插图]
图7.3Ablayev和Vasiliev量子散列算法的数学表示
他们的关键论点是，他们的算法允许量子位精确且唯一地表示任何长度为n位且不超过O（log n）量子位的讯息。在不涉及细节的情况下，O（log n）本质上意味着散列消息的每一位所需的量子位少于n个，这在理论上意味着原始消息不可能从较小的结果散列中获得。
附注：如果您有兴趣进一步了解O（log n）在数学上表示什么，请参见www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm,和www.quora.com/How-would-you-explain-O-log-n-in-algorithms-to-1st-year-undergrad-student-Can-any-one-explain-it-with-mathematical-proof-for-log-n-complexity-by-taking-a-simple-example-like-Binary-search-and-simple-to-understand.

霍列沃边界

Ablayev和Vasiliev的算法依赖于另一个称为Holevo's Bound的量子定理（https://en.wikipedia.org/wiki/Holevo%27s_theorem).这个定理说，一个量子比特可以是两种状态之一，但是当它被测量（解码）时，它必须分解成两个状态中的一个来表示测量——在每个量子比特测量中丢失了一个状态的信息（即，只有两个状态的比特不能准确地测量具有三个可能状态的属性）。要准确地表示单个量子比特（可以是三种可能的状态）需要至少两个二进制比特（ 2 比特= 2的二次方= 4 ，这意味着它们可以代表 4 种可能状态）。
他们在论文的结尾创建了一个基于量子的数字指纹算法，基于他们的散列。这篇论文和他们的研究得到了俄罗斯基础研究基金会的资助。这两位哈希算法的创建者都继续定义了更多的量子哈希算法，甚至发现并证明了更复杂的数学，可以用来建立任何量子哈希算法。
有关量子散列的更多信息，请参见www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/4_4_17日-布拉耶夫

量子数字签名

散列和签名的区别在于身份认证。散列为唯一内容提供唯一指纹。数字签名将散列绑定到主体的身份。例如，假设您散列了一个文件，散列返回为1234。然后使用非对称密钥对的私钥对哈希进行数字签名。非对称密钥对与您的身份相关联。数字签名是在特定时间点锁定特定散列到特定身份的主体。
要获得数字签名，需要一个散列，后面跟着一个非对称密钥对和一个数字签名算法。为了验证任何所谓的数字签名，利益相关者将需要签名者经过验证的相应公钥，然后他们将使用该公钥“解锁”散列，这只有在签名由有效的相应私钥签名时才有可能。如果公钥没有正确地显示有效的、先前“加密”的哈希值，而该哈希值正确地表示了所称的哈希值内容，则将对文件的完整性或数字签名进行审查。无论哪种方式，没有任何利益相关者会信任该文件或数字签名。
传统的非对称密钥对和数字签名可以使用量子通信传输，但在本章中，我们谈论的是一个真正的量子数字签名，其中的量子数字签名是基于量子特性。基于量子的数字签名需要一个量子散列、一个基于量子的非对称密钥对和一个基于量子的数字签名算法，所有这些都由量子属性表示。目前量子特性在长时间内是不稳定的，因此它们不能制造出奇妙的非对称密钥对。还有许多其他的缩放问题（稍后讨论），使得基于量子的数字签名不能很好地用于正常的数字签名，特别是与现有的远没有那么严格（但仍然非常安全）的抗量子数字签名相比。但是对于有限使用的情况，基于量子的实现可以在短时间内实现超安全的数字签名。
基于量子的数字签名非常安全的原因之一是使用了基于量子的散列。如前所述，基于量子的散列很难被攻击。它们基于Holevo's Bound定理，即使使用量子计算机也不可能计算出原始信息。重要的复杂问题是，由于不可克隆定理，签名者不能简单地创建一堆相同的量子公钥并将它们发送给接收者。相反，它变得复杂得多。

第一个量子数字签名算法

第一个实用的量子数位签章算法出自Daniel Gottesman和Isaac Chuang（https://arxiv.org/pdf/quant-ph/0105032.pdf).它不漂亮也不高效，但它很有效。首先，发送方/签名者Alice必须分别对消息的每个qubit/位进行签名。她不能只是散列内容，并在单个操作中对散列进行签名，而传统的签名算法是可能的。散列（或消息）必须一次签署一个量子比特。Alice 必须创建一个或多个私钥，如果她正在签名的消息的位= 1 ，则必须创建单独的私钥组（如果她的消息位= 0 ）。然后，使用非对称密码算法，Alice为创建的每个私钥生成一个对应的公钥，并将所有公钥发送给所有收件人Bob和Charlie。收件人的数量不能超过少数，因为每增加一个复制的密钥对都会增加密钥泄露的风险。
现在，对于签名消息中的每个0比特，Alice将所有与0比特相关的私钥以及签名消息的0比特发送给Bob和Charlie。对于签名消息中的每一个1比特，Alice将所有与1比特相关的私钥连同签名消息的1比特一起发送给Bob和Charlie。Bob和Charlie然后使用先前发送的公钥来验证带符号位的私钥。如果Bob和Charlie的比较出错率较低，则验证有符号位。如果Bob和Charlie的比较出错率不低，那么可以假定系统中存在某种妥协。必须对签名消息/散列的每个比特重复该过程。
即使您需要超高的安全性，这也不是一种非常有效的数字签名方式，尽管已经提出了提高所有消息位效率的协议（https://www.researchgate.net/publication/312062995_The_postprocessing_of_quantum_digital_signatures).尽管如此，它仍然是第一个基于量子的数字签名，表明它可以做到，无论多么低效。

相位编码数字签名

随后，2012年，《自然》杂志发表了另一种效率略高但非常相似的量子数字签名算法，该算法使用了“相位编码相干光态”（www.nature.com/articles/ncomms 2172）。通过这种方法，Alice选择了一组随机的量子态（等同于私钥），这些量子态可以用不同的光的相位来表示。每个消息位仍然由Alice单独签名。对于每一个0比特或1比特的消息，爱丽丝产生一对相位编码的状态，并发送一个副本对鲍勃和一个副本对查理。Bob和Charlie然后解码相位并验证符号位。
在2013年，基于量子的数字签名再次略有改进（https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.112.040502),随后进行了许多成功的数字签名实验包括www.nature.com/articles/s41598-017-03401-9和http://cnqo.phys.strath.ac.uk/research/quantum-theory-of-light/quantum-digital-signatures/.这些后面的实验使用了改进的，相位编码的签名变化。
基于量子的数字签名已经取得了足够的进展，密码学家们现在正在研究可以成功攻击它们的方法，包括以下两篇论文：https://link.springer.com/article/10.1007/s11128-019-2365-8和www.sciencedirect.com/science/article/pii/S0030402617308069. 每当一个加密算法或产品进行攻击审查，这是一个很好的迹象和成熟的协议。尽管如此，对基于量子的数字签名的需求，特别是随着复杂性的增加和良好的抗量子数字签名的数量的增加，在可预见的将来可能仍然很低。
有关量子数字签名的更多信息，请参见https://arxiv.org/pdf/quant-ph/0105032.pdf, https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.113.040502,和https://en.wikipedia.org/wiki/Quantum_digital_signature.

量子加密密码

量子加密是指使用量子设备、软件和属性在静止或传输期间保护数据。就像传统的二进制世界一样，量子加密密码可以是对称的，也可以是非对称的。很难查看、复制或操作受量子状态保护或处于量子状态的数据。如果有人未经授权试图直接查看数据或将自己插入量子编码数据流或存储区域，则量子状态将被更改。这是由观察者效应和非克隆定理所保证的.观察员可以操纵编码数据，但不能以不容易被有关授权方发现的方式操作。这对于密码学家和密码学用户来说是一个可取的特征。本节将介绍一般的非对称量子密码，但在第8章中将更详细地讨论量子网络。
附注：读者可能想知道为什么没有讨论基于量子的对称密码。这是因为该领域在很大程度上是未被研究的，文献和研究很少。传统的二进制对称加密目前被认为可以抵抗已知的量子攻击，因此，关于它们的讨论并不多。也许基于量子的对称密码领域在未来会得到更多的研究和资源投入，但目前这个领域基本上还没有研究过。
非对称密码学自20世纪70年代就已经出现。我们知道，这种类型的加密通常用于在源和目标之间安全地传输对称加密密钥，以及用于数字签名和身份验证。到目前为止，传统的非对称密码已经工作了半个多世纪。
作为本书的重点，量子计算机可能很快会打破传统的易受量子影响的公钥密码术的许多形式，包括RSA和Diffie-Hellman，最流行的实现。如第6章所述，有超过24种抗量子密码算法竞争成为新的NIST后量子标准。所有这些抗量子的算法，包括公钥加密和密钥交换，都是基于使用二进制设备使用二进制密钥进行二进制计算。
基于量子的非对称密码基于量子器件和量子特性。一种是目前最流行的，利用量子特性在授权源和目的地之间安全对称地传输传统秘密。这就是所谓的量子密钥分发（QKD）。另一种方法是利用量子特性来安全地传输密钥，而密钥本身就是由量子特性构成的。一些研究人员称之为量子公钥密码学（QC PK C）一班和二班，分别为（含本论文：https://arxiv.org/pdf/0810.2859.pdf).QPKC类1是QKD，其中的密钥仍然是由二进制位组成的。QPKC 2类是由量子比特组成的密钥的QKD。QPKC Class 2更难实现，因为缺乏量子网络设备，而且需要长期保持基于量子的密钥稳定。因此，大多数QC K算法和实现都是Class 1。即使是这些，现在在现实世界中实现也很有挑战性，但我们有很多成功的实现。

量子密钥分配

有许多QPKC Class 1密钥分配算法和系统，尽管它们并不普及，但自2000年代初以来，已经有许多私人和商业网络使用QKD。基于QKD的网络于2007年首次在欧洲使用，自2010年起在美国使用。今天，许多国家，特别是中国，都在使用和改进它们。在第八章中有更多关于这些量子网络的内容。

BB84

第一个量子密钥分配算法是由美国人Charles Bennett和加拿大人Gilles Brassard于1984年提出的，通常简称为BB84。贝内特和布拉萨德被认为是量子密码学之父。班尼特是IBM的研究员，70多岁时仍在从事研究工作，并在一个名为“量子教皇”的部落格发表文章，（https://dabacon.org/pontiff/author/chb/)直到2016年。布拉萨尔还帮助创建了Cascade纠错协议，该协议有助于检测和纠正由量子保护的加密通道上的窃听所引起的“噪音”（贝内特在这里也做了很多研究），并在量子隐形传态和一个新的博弈论量子伪心灵感应方面做了工作。
BB84不仅是第一个量子密钥分配方案，而且根据定义，它是第一个用数学方法证明使用量子态可以安全地防止窃听的算法。虽然我跳过了数学细节，但下面是BB 84所涉及的基本思想。Alice想通过不受信任的通道向Bob发送消息。爱丽丝需要给鲍勃一个共享的对称密钥这样他们就可以开始给对方加密密信了。以下是基本的BB84步骤:
Alice创建了两个随机的二进制字符串，比如a和b，然后使用量子位和BB84数学算法将它们编码成一个单一的结果，比如n。a和b在数学上相互联系，但没有人能知道b是什么，除非首先知道a是什么。
Alice将n作为量子比特通过量子信道发送给Bob，这是最后一次使用量子信道。其余的通信发生在公共古典频道上。
Bob测量接收到的n个量子位，它将量子位解码成比特。鲍勃用一种方法（如方法1）测量一半的量子比特，用另一种方法（如方法2）测量一半的量子比特。只有一个方法是爱丽丝发送的正确方法。方法1和方法2在测量过程中根据量子位代表0还是1给出不同的答案。与Alice发送的信息一致的正确方法将正确地测量其一半量子位的所有100%（即总数的50%），而错误的方法最终将只能正确测量其一半量子位的50%（即总数的另外25%）。如果鲍勃从爱丽丝那里正确地接收并测量了所有的量子比特，由于测量的方式，使用正确和错误的方法，只有75%的比特将准确地代表爱丽丝发送的量子比特。这是意料之中的。
鲍勃告诉爱丽丝他用来测量每一个量子比特的方法是1还是2。
爱丽丝现在知道了鲍勃对每个量子位使用的方法和结果，告诉鲍勃他测量的哪些量子位是正确的，哪些是错误的。
Alice和Bob都将丢弃错误转换的位，其余的75%将成为他们的共享密钥。
在为将来的可信通信使用新共享的密钥之前，作为一个测试，Alice和Bob将通过不可信的信道在彼此之间共享密钥位的一个短序列。如果测试比较100%匹配，他们将开始使用共享密钥的其余部分进行安全通信。如果没有，他们将承担噪音或窃听和不信任当前共享密钥。
BB84协议有更多的步骤，比这更复杂，但这一系列步骤包含了协议的总体要点。BB84的一个很好的视频表示在这里:几乎所有的 QKD 方案都是 BB84 的改进版本，或者至少提供比 BB84 更好的保护。
如果窃听者伊芙能够截获爱丽丝和鲍勃之间的原始量子比特，伊芙对量子比特的测量将解码成只有75%的正确比特（任何原始的、合法的测量者都会这样）。但是Alice不知道哪些位被正确测量，哪些位没有被正确测量，所以她必须将她测量的数据（包括25%的错误位）发送给Bob。将这些测量到的位元以量子位元的形式重新传送给鲍伯，结果鲍伯只能得到原本要传送给他的正确量子位元的75%。当他用两种方法对它们进行解码时，他得到的百分比不到75%，而不是75%。当Bob和Alice交流接收到的比特是什么以及Bob使用了什么方法来读取它们时，如果Bob得到的准确率低于75%，那么Alice和Bob就知道这个信道有噪声或者被窃听了。
QKD方法，如BB84，其中单光子的量子态在发送者和探测器之间发送，通常被称为离散变量QKD。基于BB84开发了许多其他改进的QKD系统，包括B92(www.semanticscholar.org/paper/Quantum-cryptography-using-any-two-nonorthogonal-Bennett/e99dc04d91409a4668ad0368ef7017e27a034008),由BB84的合著者贝内特创建；SARG04https://en.wikipedia.org/wiki/SARG04);和《六态协议》（https://en.wikipedia.org/wiki/Six-State_Protocol).

纠缠量子密钥分发

1991年，英裔波兰教授阿图尔·埃克尔在他的论文《基于贝尔定理的量子密码学》（http://cqi.inf.usi.ch/qic/91_Ekert.pdf).Eker的方法看起来有点像这样：
Alice creates a secret key using a split entangled qubit for each bit of the key.
Alice使用分裂的纠缠量子位为密钥的每一位创建一个秘密密钥。
Alice keeps one side of the entangled pair and sends the other side to Bob across a quantum channel.
爱丽丝保留纠缠对的一面，另一面通过量子通道发送给鲍勃。
Both Alice and Bob measure their qubits (decohering them into bits), using their own detectors with different orientation combinations for each qubit.
Alice和Bob都测量他们的量子位元（将它们解码成比特），使用他们自己的探测器对每个量子位元进行不同方向的组合。
After measuring all qubits, Alice and Bob announce the orientation of their individual detectors for each measured qubit.
在测量完所有的量子位后，Alice和Bob宣布他们各自的探测器对于每个测量的量子位的方向。
The qubits that were measured by the same detector orientation are discarded.
用相同的探测器方向测量的量子比特被丢弃。
Both Bob and Alice, now knowing what each other's detector orientations were, can convert the remaining bits into their resulting binary representations.
Bob和Alice现在都知道了对方的探测器方向，就可以将剩余的二进制位转换成相应的二进制表示。
最后，Bob和Alice都使用Bell不等式检验来进行纠缠检验。如果纠缠被打破，那么就可以假定有窃听者或坏的噪音参与其中。无论哪种方法，生成的密钥都是不可信的。
Eker的QKD方法（也称为E91）导致了一系列新的QKD算法和其他相关方案。

光子数分裂攻击

理论上，由于量子物理的观察者效应和不可克隆定理，QKD系统是抗窃听的。只要在传输过程中使用单个量子比特来表示单个比特，Eve就很难在不被发现的情况下进行窃听。但在实际应用中，大多数量子密钥分配系统不能只为每个传输比特发送一个光子。当光子沿着光纤电缆传输时，光子很快就会失去强度，而读出探测器很难准确地探测到单个光子。正因为如此，大多数QKD系统为每个传输的量子比特/比特发送多个光子。在多光子系统中，伊芙可以吸走一个或多个重复的光子，而让其余的光子在爱丽丝和鲍勃之间继续。QKD协议（如SARG04）已经被创建，大多数现实世界的QKD系统包括额外的保护和纠错机制，以减少光子数分裂攻击的风险。

连续变量QKD

第二种主要的，更新的QKD被称为连续变量QKD(CV-QKD).在CV-QKD中，量子特性被编码在激光束流的振幅和相位的调制中，然后可以被称为零差检测器的检测器解码。这些方法对光子数分裂攻击更有弹性。CV-QKD系统可以在每个时间段发送更多的密钥（与离散变量QKD系统相比），并且实现成本更低，但它们不能在离散变量系统可以的多公里距离上发挥作用。CV-QKD计划的例子可在此找到:https://arxiv.org/ftp/arxiv/papers/0705/0705.0515.pdf和https://arxiv.org/pdf/1703.09278.pdf.你会经常阅读支持离散变量或连续变量算法的量子网络设备。

中继器问题

QKD系统，由于不可克隆定理，是抵抗不可检测的窃听。密码学界来说，这是一件非常好的事情。在实践中，试图在大型网络中使用QKD是一个巨大的问题。QKD系统本质上是点对点的。你不能只是在两个QKD端点之间插入一个传统类型的中继器或路由器来重复沿途的消息。重复的装置会被当作窃听者对待。即使在长时间的点对点连接中，在量子光信号失去强度并不得不重复之前，你也只能发送这么多英里。
注意：正在进行研究，以增加量子信号在需要重复之前可以发送的距离，包括：www.nature.com/articles/s41586-018-0066-6.
因此，QKD网络必须是一个连续的点对点系统，或者必须测量量子比特，将其解相干为二进制，然后使用量子中继器重传。这些二进制位置中的每一个都是链中的薄弱环节，窃听者可以在其中插入自己并了解加密信息而不受惩罚。
想想有多少中继器点，你只是在你简单的家庭网络就有那么多。您的移动设备可能连接到Wi-Fi路由器，Wi-Fi路由器连接到您的电缆调制解调器，电缆调制解调器连接到您房子外面的设备，连接到社区聚合点，然后连接到数十到数百个其他中继器，在通往您的互联网服务提供商（ISP）的路上。然后，您的ISP连接到一到三十多个节点，以绕过互联网（每一个都可以有任意数量的中继器），并最终进入最终的目的地计算机或设备，并且对于每个需要发送回的网络包，该路径都是相反的。典型的因特网网络数据包可以轻松地通过几十个中继器。如果我们想有一天拥有一个基于量子的互联网，这将是一个巨大的挑战。这一挑战和解决方案将在第9章中详细介绍。