ACM通信gydF4y2Ba

研究突出了gydF4y2Ba

完全独立于设备的量子密钥分发gydF4y2Ba

作者:Umesh Vazirani, Thomas VidickgydF4y2Ba
美国ACM通信，2019年4月，第62卷第4期，第133页gydF4y2Ba
10.1145 / 3310974gydF4y2Ba
评论gydF4y2Ba

量子密码学保证了在经典世界中无法达到的安全水平。量子协议的经典用户甚至可能不信任用于实现协议的量子设备，能否保证这种安全性呢?gydF4y2Ba

这个核心问题可以追溯到20世纪90年代初，当时实现设备独立量子密钥分发(DIQKD)的挑战首次提出。我们通过严格地证明基于纠缠的协议的设备独立安全性来应对这一挑战，该协议建立在Ekert最初的量子密钥分发提议的基础上。安全性的证明建立在经典伪随机性理论的技术上，以实现对量子相关的非局域性质的新的定量理解。gydF4y2Ba

回到顶部gydF4y2Ba

1.简介gydF4y2Ba

经典密码学的黄金标准是语义安全gydF4y2Ba^16gydF4y2Ba给定一个编码的消息(密文)，任何多项式时间的对手都应该有一个微不足道的机会获得任何关于明文(被编码的消息)的信息。经典密码学家已经开发出了能够提供这种保证的加密方案，依靠的是关于数论问题的计算难度的未经证实的假设，比如因式分解大数，gydF4y2Ba^28gydF4y2Ba或者其他更一般的复杂性理论假设。这样的密码假设比gydF4y2BaPgydF4y2BaNPgydF4y2Ba，并且被认为在可预见的未来不太可能被证明，因此人们可能会问，是否任何密码系统都可以有安全保证，而不依赖于未经证实的计算假设。gydF4y2Ba

贝内特和布拉萨德的开创性发现gydF4y2Ba^7gydF4y2Ba1984年，量子密钥分配协议(QKD)的提出，为另一种安全“无条件安全”或仅基于普遍接受的物理定律的有效性的安全打开了可能性。QKD是一种协议，允许两个遥远的当事方合作和私下生成一个完全随机的字符串，称为用户密钥。一旦用户生成了一个私有共享密钥，他们就可以使用它进行完全安全的通信，如下所示。为了安全地发送消息，发送方使用共享密钥作为一个时间垫:编码的消息只是密钥与消息按位的异或(奇偶校验)。这种方案的语义安全性很容易验证，只要一次性密钥是完全随机的，并且对任何对手来说都是不可预测的。gydF4y2Ba

QKD安全性的第一个严格证明，gydF4y2Ba^{21gydF4y2Ba，gydF4y2Ba31gydF4y2Ba}它在二十多年前成立，似乎保证了这一终极安全概念能够实现。然而，这种承诺是短暂的。QKD研究人员很快意识到，实际实现容易受到安全证明中没有考虑到的攻击类型的攻击，包括侧通道攻击gydF4y2Ba^8gydF4y2Ba以及光子受体致盲攻击。gydF4y2Ba^20.gydF4y2Ba更普遍地说，这些攻击指向一个基本问题:鉴于量子力学的显著特征，如叠加、纠缠和不确定性原理，其中一些使QKD成为可能，人们怎么能相信没有新的方法来攻击实现QKD协议的量子设备，而不知道诚实但经典的协议用户?用户完全控制并信任其量子设备的加密协议(所有安全证明都依赖于此)，这种基本假设现在看来完全不现实。gydF4y2Ba

在1998年FOCS会议上发表的一篇论文中，梅耶斯和姚明gydF4y2Ba^22gydF4y2Ba提出了以第一原则的方式来解决这个问题的一种新的安全范式的形式称为gydF4y2Ba设备独立性。gydF4y2Ba^{一个gydF4y2Ba}在这个公式中，协议中使用的所有量子设备都被建模为具有经典输入和输出的黑盒子。用户对量子设备的信心应该只基于观察到的设备的输入输出行为。具体地说，在QKD上下文中，安全协议应该包括一个实际测试，以确保用户的量子设备按照规范运行，即使在设备可能是由敌对方制造的场景中也是如此。更准确地说，协议的任何执行都应该要么中止，要么包含一个仅基于执行过程中观察到的经典统计数据的证明，即没有窃听者(我们将用这个术语与“对手”同义)可能获得关于最终密钥的任何部分信息(除非是指数级小概率)。gydF4y2Ba

设备独立性似乎设定了一个不可能的高标准。然而，早在这个概念提出的几年前，埃克特就提出了一种不同的QKD协议，gydF4y2Ba^14gydF4y2Ba再加上直觉暗示它应该有强大的安全保证，这让人联想到设备独立性。埃克特协议的起点是由一种非凡的量子现象的性质提供的，这种现象就是纠缠，正是这种著名的现象使“EPR悖论”的作者们感到困惑。gydF4y2Ba^13gydF4y2Ba纠缠的一个典型例子是两个量子比特上的贝尔态gydF4y2Ba量子比特gydF4y2Ba:gydF4y2Ba．在物理上，这样一对最大纠缠量子位元可以在一对光子的偏振中实现，也可以通过任何一对自旋-实现gydF4y2Ba粒子，如电子。gydF4y2Ba

在20世纪60年代的开创性工作中(参见贝尔gydF4y2Ba^6gydF4y2Ba)物理学家约翰·贝尔(John Bell)证明，对处于贝尔态的两个量子位元进行适当的测量会在它们的输出之间产生相关性，而非通信的经典设备无法再现这种相关性。这种非局域相关性提供了一种“量子性测试”，它将量子力学与爱因斯坦所倡导的各种隐变量理论区分开来。这种形式的非局部相关已在贝尔不等式违背形式中得到了精确的实验验证。gydF4y2Ba^{15gydF4y2Ba，gydF4y2Ba18gydF4y2Ba，gydF4y2Ba30.gydF4y2Ba}

Bell实验最简单的例子是由Clauser等人发现的。gydF4y2Ba^9gydF4y2Ba这个实验可以表述为一个游戏，CHSH游戏，以它的发明者Clauser、Horne、Shimony和Holt的名字命名，它在我们的协议中扮演着重要的角色。在这个游戏中，是设备gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba均为输入均匀随机位，gydF4y2BaxgydF4y2Ba而且gydF4y2BaygydF4y2Ba分别。他们的目标是返回比特，gydF4y2Ba一个gydF4y2Ba而且gydF4y2BabgydF4y2Ba分别,这样gydF4y2BaxygydF4y2Ba＝gydF4y2Ba一个gydF4y2Bab。gydF4y2Ba一个简单的论证表明如果gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba是经典的，即每个设备的输出仅作为设备输入的函数计算，即使允许设备访问公共共享随机字符串，它们也不能在大于3/4的概率下成功。相比之下,如果gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba都是量子，每个包含一个贝尔态的量子比特，那么通过对它们的量子比特进行适当的量子测量，它们可以获得cosgydF4y2Ba^2gydF4y2Ba/8 0.85 > 3/4。gydF4y2Ba

非局部相关对于设备独立性的重要性在于直觉，在某些条件下，这些相关可以通过Bell实验进行经典测试，可以确定两个设备共享的纠缠状态，即被称为刚性的现象，也可以排除与第三方的纠缠，如被称为一夫一妻制的窃听者现象。不幸的是，除了它的直观表述外，一夫一妻制是出了名的难以量化，这一直是在设备独立框架中正式证明安全性的主要障碍之一。gydF4y2Ba

巴雷特等人迈出了重要的一步，gydF4y2Ba^5gydF4y2Ba谁能够显示一个协议的安全性，生成单位密钥仅基于无信号假设，即用户的设备之间，或设备和窃听者之间没有交换信息。这是一个比量子形式主义更弱的假设，量子形式主义暗示没有信号，但通常更有限制。他们的工作启发了大量后续的论文gydF4y2Ba^{1gydF4y2Ba，gydF4y2Ba2gydF4y2Ba，gydF4y2Ba29gydF4y2Ba}它为生成多个比特的协议寻找安全性，并试图利用量子形式主义来获得更细粒度的安全性分析，从而导致密钥速率的潜在改进。不幸的是，所有这些尝试都遇到了一个基本的障碍，那就是人们不能在量子环境中使用贝叶斯的条件概率规则:偷听者猜测密钥的两个比特的最大概率gydF4y2BakgydF4y2Ba_1gydF4y2BakgydF4y2Ba_2gydF4y2Ba不能表示为她猜的最大概率的乘积gydF4y2BakgydF4y2Ba_1gydF4y2Ba乘以她猜的最大概率gydF4y2BakgydF4y2Ba_2gydF4y2Ba考虑到她的猜测gydF4y2BakgydF4y2Ba_1gydF4y2Ba．这与窃听器的量子性质有关，而且同一量子态的不同测量并不总是兼容的(它们可能不会交换)。gydF4y2Ba

在作者之前的工作中首次给出了Ekert协议变体的安全性的完整证明。gydF4y2Ba^35gydF4y2Ba本文的目标是强调该安全性证明的两个关键组成部分。第一种是使用随机提取器(基于计算复杂度的伪随机理论的极端对象)的深层属性和它们的量子证明扩展来绕过障碍，比如更具体地说，在分析生成多个比特的量子协议时，缺乏合适的贝叶斯规则。基于之前在可认证量子随机数生成方面的工作，gydF4y2Ba^34gydF4y2Ba安全性证明使用了一种基于提取的证明技术，称为“量子重建范式”，将窃听者的全局攻击减少到对单轮协议的攻击。这个证明的组成部分应该引起对随机提取器和多人游戏感兴趣的复杂性理论家的广泛兴趣，并且阐述试图使这些方面易于理解。gydF4y2Ba

证明的第二部分排除了窃听者的单轮攻击。这涉及到争论任何这样的攻击将意味着一个不可能好的策略，三个参与者参与一个简单的非本地“猜谜游戏”，这将违背非信号原则。该证明采用了猜谜游戏之间减少的形式，鉴于最近对委托计算环境中无信号分布的特性的兴趣，这可能与密码学家特别相关。gydF4y2Ba^19gydF4y2Ba

我们的安全性证明是在Bell实验框架的相当泛化下进行的，Bell实验包括三个量子设备(第三个设备用于对协议的窃听器建模)的输出之间的相关性研究，涉及复杂的交互，其中包括设备之间的一些有限的通信。这种概括抓住了新的物理现象，比如前面提到的纠缠的一夫一妻制。在我们的阐述中，我们的目标是通过采用协议中经典用户的观点来抽象尽可能多的量子形式主义，因此也强调了安全性证明中经典可理解的元素，同时尽可能推迟提供所使用的量子设备的底层建模所需的任何关于量子形式主义的知识。gydF4y2Ba

为了在实验中实现设备独立的安全性，实现能够以足够的保真度执行诚实方协议的设备，使其输入输出行为通过协议中指定的统计测试就足够了。这与传统的安全证明相反，传统的安全证明要求设备保证每次发射单个量子位，而这一标准无法基于统计数据进行验证。最近贝尔测试的实验演示即使在严格的对抗假设(所谓的“无漏洞”)下也能重现所需的相关性。gydF4y2Ba^{5gydF4y2Ba，gydF4y2Ba18gydF4y2Ba，gydF4y2Ba30.gydF4y2Ba}几乎可以肯定的是，QKD的设备独立协议很快就会实现。最近证明了将纠缠量子比特从卫星分布到遥远的地面站的可行性，为这类实验提供了更大的空间。gydF4y2Ba^36gydF4y2Ba这是量子密码学激动人心的时刻!gydF4y2Ba

回到顶部gydF4y2Ba

2.量子态，纠缠和Chsh博弈gydF4y2Ba

量子比特是量子信息的基本单位。就我们的目的而言，考虑以下简化的定义就足够了:一个量子比特是一种粒子，它可以处于两种状态的真实叠加状态，标记为|0和|1。叠加用二维实平面上的单位向量表示，可以用一个参数表示gydF4y2Ba:(因为gydF4y2Ba罪gydF4y2Ba）gydF4y2Ba^TgydF4y2Ba，或ket符号为|gydF4y2Ba=因为gydF4y2Ba| 0 +罪gydF4y2Ba| 1。这意味着一个单位向量指向gydF4y2BaxgydF4y2Ba方向指示状态|0，单位向量指向gydF4y2BaygydF4y2BaDirection表示状态|1gydF4y2Ba^bgydF4y2Ba．gydF4y2Ba

在量子位上进行的观察或测量由选择的基来指定。形成的区分基础gydF4y2BaxgydF4y2Ba而且gydF4y2BaygydF4y2Ba-axes被称为标准基。量子测量结果的玻恩法则规定了状态|的测量gydF4y2Ba在标准基下，结果为0，概率为cosgydF4y2Ba^2gydF4y2Ba1的概率是singydF4y2Ba^2gydF4y2Ba．一旦测量完成，量子位坍缩到与所获得的结果一致的测量后状态|gydF4y2Ba_0gydF4y2Ba= |0或|gydF4y2Ba_{/ 2gydF4y2Ba}= | 1。更一般地说，对任何角度都适用gydF4y2Ba量子位也可以在将标准基旋转一个角度得到的基中测量gydF4y2Ba．这样的测量产生的结果是0，概率为cosgydF4y2Ba^2gydF4y2Ba（gydF4y2Ba)， 1表示概率为singydF4y2Ba^2gydF4y2Ba（gydF4y2Ba)(见gydF4y2Ba图1gydF4y2Ba)．gydF4y2Ba^cgydF4y2Ba测量后状态为|gydF4y2Ba或|gydF4y2Ba_{/ 2 +gydF4y2Ba}分别。gydF4y2Ba

图1。测量gydF4y2Ba在标准基下产生结果0，概率为||gydF4y2Ba^2gydF4y2Ba．以(gydF4y2BaugydF4y2Ba，gydF4y2BaugydF4y2Ba产量结果gydF4y2BaugydF4y2Ba概率因为gydF4y2Ba^2gydF4y2Ba．gydF4y2Ba

现在我们来讨论一下纠缠。最基本的纠缠态是贝尔态，它是两个量子位的最大纠缠态。用ket符号表示贝尔状态gydF4y2Ba为了理解这种状态的显著特性，让我们从描述在同一基(|gydF4y2Ba、|gydF4y2Ba_{/ 2 +gydF4y2Ba}):首先注意，由于对称性，每个量子位上的测量结果是均匀随机的;也就是0或1，概率都是1/2。但贝尔态的对称性有更深层次的含义。注意，Bell状态是旋转不变的，可以写成gydF4y2Ba(这可以通过直接计算很容易验证)。这意味着对两个量子位的测量结果是两个结果都是0，或者两个结果都是1，每个结果的概率都是1/2。测量后状态为|gydF4y2Ba|gydF4y2Ba、|gydF4y2Ba_{/ 2 +gydF4y2Ba}|gydF4y2Ba_{/ 2 +gydF4y2Ba}分别。无论两个量子位之间的空间分隔如何，这个结论都是成立的，这个结论乍一看似乎非常违反直觉:第二个量子位是如何“知道”第一个量子位被测量的基础和得到的结果的?gydF4y2Ba

然而，这种自然的困惑是我们的演示的产物(爱因斯坦、波多尔斯基和罗森也给出了同样的答案!)事实上，一个简单的经典场景可以重现同样的现象。考虑两枚随机方向相同的硬币，使其表面法线形成相同的(随机)角度gydF4y2Ba在gydF4y2BaxgydF4y2BaygydF4y2Ba飞机。然后将两个硬币在空间上分开，同时保持它们的方向不变并进行测量。测量的意思是选择一个角度gydF4y2Ba，看硬币沿角度gydF4y2Ba(从无穷远处看硬币)，并报告看到的是正面还是反面(0或1)。显然，由于方向不同，结果是一致随机的gydF4y2Ba都是随机选择的。如果我们从同一个角度观察(测量)两枚硬币gydF4y2Ba，结果是相同的。gydF4y2Ba

当两个量子位在不同的基下测量时，量子和经典设置之间的基本区别就显现出来了。如果我们用标准基测量第一个量子位，用a测量第二个量子位gydF4y2Ba-旋转的基础，那么和前面一样，每个结果(0或1)单独是随机的，但测量规则表明两个结果将与概率cos匹配gydF4y2Ba^2gydF4y2Ba．这与上面描述的经典场景中获得的统计数据不同，在经典场景中，获得匹配结果的机会为|1gydF4y2Ba/gydF4y2Ba|对gydF4y2Ba[0,gydF4y2Ba)．这两个数的差，gydF4y2Ba^2gydF4y2Bavs。gydF4y2Ba/gydF4y2Ba对小gydF4y2Ba，是贝尔量子性检验的基础。gydF4y2Ba

我们现在可以在CHSH游戏中看到这种差异是如何以一种特别优雅的方式表现出来的。量子策略从爱丽丝和鲍勃共享一个贝尔态开始。它们中的每一个都在一个依赖于它们的输入位的基上对它们的量子位进行测量(gydF4y2BaxgydF4y2Ba或gydF4y2BaygydF4y2Ba)，并宣布结果:Alice在a中测量她的量子位gydF4y2Ba_{一个gydF4y2Ba}旋转的基础上,gydF4y2BaxgydF4y2Ba， Bob测量他的量子位gydF4y2Ba_BgydF4y2Ba旋转的基础上,gydF4y2BaygydF4y2Ba（gydF4y2Ba图2gydF4y2Ba)．在这三种情况下gydF4y2BaxygydF4y2Ba= 0时，玩家以相对于彼此/8旋转的基数进行测量，因此输出相同的位(即。gydF4y2Ba一个gydF4y2BabgydF4y2Ba= 0)，概率为cosgydF4y2Ba^2gydF4y2Ba/ 8。在这种情况下gydF4y2BaxygydF4y2Ba= 1时，它们以相对于彼此旋转3/8的基数进行测量，因此输出不同的位(即。gydF4y2Ba一个gydF4y2BabgydF4y2Ba= 1)概率为cosgydF4y2Ba^2gydF4y2Ba/ 8。因此，在四种情况下，每一种成功的概率都是cosgydF4y2Ba^2gydF4y2Ba/ 8。相比之下，基于前面描述的使用随机硬币的经典策略，使用与量子策略相同的角度(角度应该翻倍，以说明这些角度在量子或经典策略中使用的不同方式)，将在每种情况下产生有效的结果，概率为1 1/4 = 3/4。gydF4y2Ba

图2。我们的安全性证明依赖于最基本的贝尔不等式之一，CHSH不等式，gydF4y2Ba^9gydF4y2Ba这是一个小游戏。用图中右边所示的底座测量贝尔对的可靠设备将产生这样的输出:Pr(gydF4y2Ba一个gydF4y2BabgydF4y2Ba＝gydF4y2BaxygydF4y2Ba) = cosgydF4y2Ba^2gydF4y2Ba/ 8时gydF4y2BaxgydF4y2Ba，gydF4y2BaygydF4y2Ba{0,1}gydF4y2Ba一个gydF4y2Ba＝gydF4y2BabgydF4y2Ba每当gydF4y2BaxgydF4y2Ba= 2,gydF4y2BaygydF4y2Ba= 0。gydF4y2Ba

回到顶部gydF4y2Ba

3.埃克特协议和一个可证明的变体gydF4y2Ba

我们准备继续进行更复杂的密钥分发任务。此任务的目标是让两个受信任但距离较远的用户Alice和Bob就共享达成一致gydF4y2BangydF4y2Ba一些关键gydF4y2BaKgydF4y2Ba{0,1}gydF4y2Ba^ngydF4y2Ba．密钥分发协议必须保证，如果协议运行到完成，那么用户产生相同的密钥，对于任何窃听者来说，这些密钥都是统一的随机字符串。用户唯一可用的资源是可信的本地随机数生成器和一个公共的、经过身份验证的量子通信通道。gydF4y2Ba

3.1.Ekert的协议gydF4y2Ba

我们首先介绍Ekert协议的一个轻微变体，它具有相同的安全性直觉。用户Alice和Bob最初共享一个大数字，gydF4y2BaNgydF4y2Ba，贝尔州。这些状态可以由Alice生成，每个状态有一个量子位传送给Bob。由于所有的通信通道都是公开的，窃听者可能已经干扰了量子位。从对抗性的角度来看，考虑一个对称的公式是很方便的，Alice和Bob被提供了量子设备，gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba，由一些不可信的提供者。设备包含任意状态，当用户操作时，它们对该状态执行任意测量。gydF4y2Ba

在协议中，设备gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba使用gydF4y2BaNgydF4y2Ba在序列。每次使用，爱丽丝的设备gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}可以从三个可能的输入中选择一个吗gydF4y2BaxgydF4y2Ba_我gydF4y2Ba{0, 1, 2}和Bob的设备gydF4y2BaDgydF4y2Ba_BgydF4y2Ba有两个输入gydF4y2BaygydF4y2Ba_我gydF4y2Ba{0,1}。这些输入在每一轮中由用户统一随机选择。设备的理想方案是，在Alice的两个输入选择(和Bob的两个输入选择)中，设备应该执行CHSH博弈的最佳量子策略(gydF4y2Ba图2gydF4y2Ba)．这意味着Alice和Bob以2/3的概率使用他们的设备来玩CHSH游戏，在这种情况下，他们检查所需的相关性满足CHSH游戏条件，在这样的游戏回合数中有足够高的平均频率。Alice设备的第三个输入表示与Bob设备在输入0上的测量值相同的测量值。这意味着对于概率gydF4y2BaAlice和Bob选择这对匹配的输入，在这种情况下，他们期望获得相同的结果，从而生成密钥。gydF4y2Ba

埃克特对该协议安全性的直观论证依赖于一些观察结果。第一种是，当量子位从源传输时，窃听者无法获得任何有意义的信息，因为在Bell状态下没有编码信息:如Ref. Ekert所表述的，gydF4y2Ba^14gydF4y2Ba只有当量子位被Alice和Bob测量时，信息才会“产生”。因此，在这个阶段，窃听者唯一合理的攻击是保持一个可能与Alice和Bob的设备中存在的量子位部分或完全纠缠的量子态。第二个观察结果是，CHSH博弈测试可以用来建立量子比特确实处于贝尔状态的信心。直观地说，Bell状态是一种纯状态，根据定义，它不能与窃听者持有的任何量子位纠缠。因此，即使在用户与他们的设备交互之后，窃听者也不应该通过对其系统执行测量而获得额外的信息。埃克特没有为他的QKD协议提供安全性证明。在较弱的安全模型中，用户的量子设备是可信的，首先通过简化到BB'84协议实现了证明。gydF4y2Ba^31gydF4y2Ba这个证明绕过了埃克特最初的直觉，而是建立在量子纠错的新理论及其在纠缠蒸馏中的应用上，而且它关键地依赖于量子设备是完全可信的假设。gydF4y2Ba

3.2.E1协议gydF4y2Ba

我们将展示上一节中描述的协议变体的安全性gydF4y2Ba图3gydF4y2Ba．和前面一样，用户Alice和Bob可以使用任意的量子设备gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}，它将trit作为输入gydF4y2BaxgydF4y2Ba_我gydF4y2Ba{0, 1,2}和gydF4y2BaDgydF4y2Ba_BgydF4y2Ba，它以一个比特作为输入gydF4y2BaygydF4y2Ba_我gydF4y2Ba{0,1}。这些设备在gydF4y2BaNgydF4y2Ba轮，每次返回一个输出位，gydF4y2Ba一个gydF4y2Ba_我gydF4y2Ba，gydF4y2BabgydF4y2Ba_我gydF4y2Ba分别为{0,1}。设备的理想规格与前面的协议相同。gydF4y2Ba

图3。DIQKD协议，E1协议。gydF4y2Ba

我们将协议分为三个阶段。第一阶段是gydF4y2Ba生成阶段gydF4y2Ba，用户在其中执行各自的设备gydF4y2BaNgydF4y2Ba通过均匀随机选择输入和收集gydF4y2BaNgydF4y2Ba输出部分。然后开始gydF4y2Ba测试阶段gydF4y2Ba:用户公开地均匀随机地选择一个固定比例的回合，并在这些回合产生的输入-输出对的平均值上评估设备在CHSH博弈的变体中的成功概率。如果他们观察到成功概率偏离最优值超过允许的公差gydF4y2Ba时，用户终止协议。否则他们会继续gydF4y2Ba提取阶段。gydF4y2Ba为此，他们交换了所有回合的输入，丢弃了没有输入的回合(gydF4y2BaxgydF4y2Ba_我gydF4y2Ba，gydF4y2BaygydF4y2Ba_我gydF4y2Ba) =(2,0)。其余轮(称为校验轮C)的输出由每个用户保持私有，并指定为gydF4y2Ba生的关键gydF4y2Ba，gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaKgydF4y2Ba_BgydF4y2Ba分别。基于这些字符串，用户执行错误调和和隐私放大的后处理步骤，以获得最终的共享密钥gydF4y2BaK。gydF4y2Ba信息协调是一种以纠错码为基础的过程，其目的是确保gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}＝gydF4y2BaKgydF4y2Ba_BgydF4y2Ba在一次公开的小修正之后。我们在这里不讨论这个标准程序。隐私放大的目的是将原始密钥中存在的秘密从窃听者的部分未知放大到从窃听者的角度看不可区分的统一。我们将在后面详细描述这个过程。gydF4y2Ba

与埃克特的协议最重要的不同点在于，在测试CHSH博弈相关性的少数回合中。省略测试可能会削弱协议的安全性:为什么不使用所有可能的相关性进行测试呢?另一方面，测试涉及公开那些回合的输入/输出对，这有不诚实的设备将信息泄露给窃听者的风险。事实上，正如我们将看到的，协议的安全性证明将要求我们在选择用于测试的子弹的比例上设置一个小的、恒定的上限。gydF4y2Ba

我们用两个概念形式化了协议E1的直觉，这两个概念在Ekert发表论文时都没有明确表述。第一种被称为刚性。这是观察到有一个本质上唯一的方法来实现cos的最优成功概率gydF4y2Ba^2gydF4y2BaCHSH游戏中的/8:设备的任何最优策略gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba在局部上等同于基于前面描述的Bell状态的特定策略。第二个概念是相关性的一夫一妻制。这一思想建立在第一个理论的基础上，指出最大纠缠量子位必须是纯量子位，因此不能与任何其他量子位共享它们的“最大纠缠自由度”。这是Ekert直觉的形式化表现，通过见证证明他们的设备共享Bell状态的相关性，用户有效地排除了设备与任何恶意窃听者之间纠缠的可能性。gydF4y2Ba

正式证明协议安全性的一种可能方法是对这两个概念给出定量表述。虽然这可以在量子力学的数学形式主义中完成，但使用由此产生的理论来证明任何实际意义上的安全性都存在很强的障碍。首先，实现设备独立性使我们无法对所使用的量子系统做出任何先验假设，例如在基础希尔伯特空间的维度上有一个界限。如果没有这样的约束，到最优策略的距离如何作为观察到的统计数据的最优性偏差的函数，就不是一个先验的明显问题，这是Mayers和Yao已经面临的一个难题。gydF4y2Ba^22gydF4y2Ba更重要的是，发生在QKD协议中的交互场景是复杂的，涉及多个信息源泄露给窃听者。虽然参考文献Reichardt等人给出了沿着这些路线的安全性证明，gydF4y2Ba^27gydF4y2Ba获得的边界太弱，无法容忍协议执行中的任何错误(如不可避免的光子损失、错误检测事件等)。gydF4y2Ba

回到顶部gydF4y2Ba

4.安全证明概述gydF4y2Ba

安全性证明可以分解为两个部分。第一个分析单轮随机选择的协议。它表明，如果协议成功，那么窃听者很有可能在选定的回合中，设备的输出至少是部分未知的。为了做到这一点，窃听者所面临的挑战被表述为一个双人猜谜游戏，窃听者的信息被简化为一个简单的猜谜游戏。后一种博弈的最大成功概率受无信号原则的限制，即在双方没有沟通的情况下，一方的输出分布必须独立于另一方的输入。这部分证明完全不诉诸于量子形式主义(尽管这样做可以用来给出更强的定量界限)。gydF4y2Ba

第二部分的证明表明，超过大量gydF4y2BaNgydF4y2Ba对于轮，协议产生(gydF4y2BaNgydF4y2Ba)的共享随机密钥位，以防止窃听者。分析多轮协议会遇到与窃听者及其攻击的量子性质有关的基本障碍。理想情况下，我们希望将小于(的提取联系起来gydF4y2BaNgydF4y2Ba)位共享的随机密钥与失败的猜谜游戏争论在某些回合，导致矛盾。问题是，窃听者的攻击可能是基于协议中所有回合交换的经典信息对她的量子态部分进行的全局测量，导致对协议顺序性质的控制丧失。我们将利用随机提取器理论的强大结果来直接处理由Alice、Bob和窃听者生成的经典信息之间的相关性，从而绕过这些障碍。大致上，这个范例允许我们直接得出这样的结论:如果协议生成的密钥可以被窃听者从随机密钥中区分出来，那么就有一个(有效的)经典过程以不可忽略的概率重建Alice的原始密钥。这使得我们可以使用经典的信息理论工具来简化猜谜游戏。gydF4y2Ba

回到顶部gydF4y2Ba

5.猜谜游戏gydF4y2Ba

单轮E1协议提供的安全保证，其核心取决于以下猜谜游戏(gydF4y2Ba图4gydF4y2Ba)．我们从CHSH博弈的增强变体开始，除了CHSH博弈输入之外，Alice还可以得到第三个输入，标记为2(每个输入的选择概率为1/3)。如果玩家的输入是(gydF4y2Bax, ygydF4y2Ba) =(2,0)那么它们的输出应该匹配。假设无信号原理和量子力学的有效性gydF4y2Ba=因为gydF4y2Ba^2gydF4y2Ba/8是CHSH博弈的最优界)，很容易看出Alice和Bob可以以概率赢得增广CHSH博弈gydF4y2Ba这是最优的。gydF4y2Ba

图4。猜谜游戏。同时满足CHSH条件的任何设备gydF4y2Ba一个gydF4y2BabgydF4y2Ba＝gydF4y2BaxygydF4y2Ba而猜测条件gydF4y2BacgydF4y2Ba＝gydF4y2Ba一个gydF4y2Ba用足够高的概率必须允许信号之间gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba．gydF4y2Ba

图5。猜想引理的证明。使用CHSH游戏的获胜条件，无论gydF4y2BabgydF4y2Ba_1gydF4y2Ba是距离gydF4y2Ba一个gydF4y2Ba_0gydF4y2Ba而且gydF4y2Ba一个gydF4y2Ba_1gydF4y2Ba必须至少是2(1gydF4y2Ba)．这意味着半径为(1)的球gydF4y2Ba)为中心gydF4y2Ba一个gydF4y2Ba_0gydF4y2Ba而且gydF4y2Ba一个gydF4y2Ba_1gydF4y2Ba是不相交的。gydF4y2Ba

现在我们考虑在游戏中添加另一个规则，即“猜测规则”:Bob应该总是产生第二个输出，gydF4y2BacgydF4y2Ba{0,1}。猜谜规则要求这样做gydF4y2BacgydF4y2Ba应该匹配Alice的输出吗gydF4y2Ba一个gydF4y2Ba每当她的输入是gydF4y2BaxgydF4y2Ba= 2(如果gydF4y2BaxgydF4y2Ba{0,1}则无上的要求gydF4y2BacgydF4y2Ba)．我们将证明Alice和Bob不能达到接近的最优概率gydF4y2Ba在扩展的CHSH博弈中，同时满足Bob输出的猜测规则gydF4y2BacgydF4y2Ba当概率接近1时:无论Bob做什么，他都不能与Alice合作在CHSH游戏中成功，同时为Alice的输出产生有效的猜测。这是前面提到的量子相关的一夫一妻制现象的表现。要理解这个结果对E1协议安全性的重要性，请注意，它还意味着Alice的输出位对窃听者来说一定是随机的，即使提供Alice和Bob的输入也是如此。要了解这一点，观察任何这样的偷听者都可以与Bob放在一起，从而在上面描述的猜谜游戏中得出一个成功的策略。gydF4y2Ba

证明可以简化为下面这个简单的猜谜游戏。有两个合作的玩家，Alice和Bob。在游戏开始时，Bob收到了一个比特gydF4y2BaygydF4y2Ba{0,1}是均匀随机选择的。玩家可以进行任意计算，但不允许进行交流。在游戏结束时，Alice输出了一点gydF4y2Ba一个gydF4y2Ba，如果玩家赢了gydF4y2Ba一个gydF4y2Ba＝gydF4y2Bay。gydF4y2Ba显然，任何有成功概率的策略都偏离了gydF4y2Ba表示违背了Alice和Bob之间的无信号假设。使用猜谜游戏背后的想法是要表明，在加密协议中任何不受欢迎的结果(如窃听者的成功策略)都可以引导成Alice和Bob在简单猜谜游戏中的成功策略，从而与无信号假设相矛盾。gydF4y2Ba

猜测引理。gydF4y2Ba假设Alice和Bob在增广CHSH博弈中至少有概率成功gydF4y2Ba在哪里gydF4y2Ba那么Bob成功猜出Alice在输入x = 2时输出的最大概率是gydF4y2Ba1gydF4y2BaCgydF4y2Ba（gydF4y2Ba_0gydF4y2Ba)，gydF4y2Ba在C和gydF4y2Ba_0gydF4y2Ba是普遍的常数。gydF4y2Ba

尽管一般的量子策略优化是难以处理的，但是通过考虑玩家有效量子策略集的凸松弛，通常可以获得良好的上界(使用例如半定规划)。这里的游戏足够简单，可以给出一个直观的论点，它已经提供了一个有意义的边界。gydF4y2Ba

证明。为了简单起见，我们首先说明当gydF4y2Ba= 0，那么Bob不能以1的概率猜出Alice的输出。对参数进行更仔细的计算，然后提供所要求的边界。请注意,gydF4y2BaAlice和Bob在增强的CHSH博弈中成功的最大概率是什么?为了使这一切发生，他们必须以最优概率赢得CHSH博弈gydF4y2Ba，以及输入gydF4y2BaxgydF4y2Ba= 2,gydF4y2BaygydF4y2Ba= 0，输出gydF4y2Ba一个gydF4y2Ba而且gydF4y2BabgydF4y2Ba必须是相等的。我们假设Bob可以猜出Alice的输出(输入)gydF4y2BaxgydF4y2Ba= 2)，概率为1。gydF4y2Ba

我们设想用相同的固定输入重复顺序执行设备gydF4y2BaxgydF4y2Ba而且gydF4y2BaygydF4y2Ba，对于某个数gydF4y2BakgydF4y2Ba的执行。让gydF4y2Ba表示Bob的输出，和gydF4y2Ba表示Alice的输出，除以这些gydF4y2BakgydF4y2Ba执行。那么在增广的CHSH对策上的条件意味着当输入为时，参与人的输出应该匹配gydF4y2Ba同样假设成功猜测，输入(2，gydF4y2BaygydF4y2Ba)对于任何gydF4y2BaygydF4y2Ba玩家的输出满足gydF4y2Ba由此可见,gydF4y2BaAlice和Bob赢得CHSH游戏的概率gydF4y2Ba意味着对于任何gydF4y2BaxgydF4y2Ba{0,1}，相对汉明距离gydF4y2Ba(根据切尔诺夫的界限，这是非常集中的gydF4y2BakgydF4y2Ba增长)。由此可见,gydF4y2Ba

现在假设Alice知道Bob的输出gydF4y2Ba(我们将在后面证明这一假设)。我们声称这使Alice在猜测Bob的输入时具有优势gydF4y2BaygydF4y2Ba这就与本节开头描述的基本猜谜游戏产生了矛盾。Alice的策略如下:如果给出她的输入gydF4y2BaxgydF4y2Ba和输出gydF4y2Ba她猜测gydF4y2BaygydF4y2Ba= 0,如果gydF4y2Ba,gydF4y2BaygydF4y2Ba否则= 1，其中gydF4y2Ba是一个任意小的常数(取决于gydF4y2BakgydF4y2Ba)．gydF4y2Ba

首先要注意，如果gydF4y2BaygydF4y2Ba= 0，那么她成功的概率接近1。这是因为如上所示，因为gydF4y2Ba对于任何gydF4y2Ba另一方面，当gydF4y2BaygydF4y2Ba= 1，根据CHSH博弈条件应该是gydF4y2Ba而且gydF4y2Ba根据三角形不等式，gydF4y2Ba由此可见,gydF4y2Ba而且gydF4y2Ba不能两者都接近任何固定gydF4y2Ba:即两种情况gydF4y2Ba而且gydF4y2Ba不能同时得到满足。这意味着在这种情况下gydF4y2BaygydF4y2Ba= 1时，Alice必须以1/2的概率成功，因此Alice可以以接近3/4的概率猜出Bob的输出。矛盾。gydF4y2Ba

为了证明Alice知道Bob的输出gydF4y2Ba，我们考虑下面的实验:Alice和Bob执行gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba在大块的gydF4y2BakgydF4y2Ba执行,反复。在每个数据块中，Alice选择一个均匀随机的输入gydF4y2BaxgydF4y2Ba{0,1}。Bob总是选择相同的秘密输入gydF4y2Bay。gydF4y2BaBob选择一个值gydF4y2Ba在这些块上均匀随机后选择gydF4y2Ba他将这些块的索引传递给爱丽丝。泄露的信息gydF4y2BaygydF4y2Ba是非常小的，因为边际分布gydF4y2Ba必须匹配边际分布gydF4y2Ba获得当gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}提供输入gydF4y2BaxgydF4y2Ba= 2，它不依赖于gydF4y2BaygydF4y2Ba；因此，Bob发送给Alice的数据块的索引接近于均匀分布，无论gydF4y2Bay。gydF4y2Ba

的证明就完成了gydF4y2Ba= 0。在更一般的情况下，复制同样的证明使推理更定量并不难gydF4y2Ba> 0。我们将此作为练习留给读者。gydF4y2Ba

在继续进行多轮分析之前，我们注意到，根据巴雷特等人的论证，猜测引理已经给出了量子密钥分发安全性的“原则上”证明。gydF4y2Ba^4gydF4y2Ba(尽管他们使用了一个不同的、更复杂的贝尔不等式来实现一个安全参数，该参数的比例与子弹数成反比)。考虑下面协议E1的简化变体。用户指示他们的设备按顺序播放(gydF4y2BaNgydF4y2Ba)扩充了CHSH游戏的实例。Alice随机选择了一个停止游戏的时间，并(公开地)向Bob宣布。用户公开交换他们的输入。一旦完成了这一步，它们就会确定在停止时间之前的最后一轮，在那里它们使用输入对(2,0)，因此应该有匹配的输出;称之为钥匙轮。他们在关键回合之前交换所有回合的输出，并估计(增强的)CHSH博弈相关性。只要这些相关性足够接近CHSH游戏边界，他们就会使用他们在关键回合的输出作为最终的关键。基于一个简单的鞅论证，我们不难看出，如果设备在关键回合之前的所有回合中产生的输出都满足CHSH博弈相关性，那么关键回合中的设备也有很高的概率满足CHSH博弈条件(即使它没有被检查)。根据猜测引理，在这一轮中，窃听者猜测用户共享比特的概率是有限的。gydF4y2Ba

请注意，上面的论点提供了安全性的完整证明(对于单个密钥位)，而完全不需要诉诸量子形式主义:安全性所需的唯一假设是无信号原则。然而，要超越单轮，还需要我们假设设备的行为可以用量子力学建模。gydF4y2Ba

回到顶部gydF4y2Ba

6.提取安全密钥gydF4y2Ba

我们继续分析完整的协议gydF4y2Ba^dgydF4y2Ba．我们的目标是提供一种简化:我们的目的是表明，任何针对窃听者的全局策略，只要能产生关于用户最终共享密钥的部分信息，就意味着对前一节中所描述和排除的形式的单轮协议进行攻击。如前所述，分析多轮协议会遇到与窃听者及其攻击的量子性质有关的基本障碍。我们将利用随机提取器理论的强大结果来直接处理由Alice、Bob和窃听者生成的经典信息之间的相关性，从而绕过这些障碍。gydF4y2Ba

第一步是明确窃听者的策略是由什么组成的。回想一下，协议E1包含一个终极后处理步骤，称为gydF4y2Ba隐私放大。gydF4y2Ba此任务转换原始键gydF4y2BaKgydF4y2Ba由爱丽丝和鲍勃共享(他们从这个词衍生而来gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaKgydF4y2Ba_BgydF4y2Ba通过执行信息协调)转换为更短的字符串gydF4y2BaZ。gydF4y2Ba隐私放大保证只要gydF4y2BaKgydF4y2Ba从窃听者的角度来看包含了足够的熵gydF4y2BaZgydF4y2Ba从窃听者的角度来看，隐私放大是通过使用强(量子防)随机性提取器实现的:gydF4y2Ba^{12gydF4y2Ba，gydF4y2Ba32gydF4y2Ba}一种以两串位作为输入的过程Ext，即源gydF4y2BaXgydF4y2Ba(角色将由谁扮演gydF4y2BaKgydF4y2Ba)和一个短的均匀随机种子gydF4y2BaYgydF4y2Ba(将使用私有随机性生成，并公开共享)并将它们组合起来生成一个输出gydF4y2BaZgydF4y2Ba= Ext (gydF4y2BaX, YgydF4y2Ba)．可以将种子看作一个短标记，用于从公开指定的族中选择哈希函数;输出是通过对源上所选哈希函数的求值得到的。强提取程序的安全条件保证没有对手gydF4y2Ba即使能接触到种子gydF4y2Ba，能够将提取器的输出与相同长度的均匀随机字符串区分开来。只要从对手的角度看，源包含足够的熵，这个保证就会得到满足。gydF4y2Ba

因此，主要的挑战仍然是确定来源，gydF4y2BaKgydF4y2Ba，从窃听者的角度来看，包含了足够的熵。我们证明这一点的方法是基于一种证明技术(量子泛化)，这种证明技术来自于被称为“重构范式”的伪随机性理论，它最初是由特雷维桑提出的gydF4y2Ba^33gydF4y2Ba针对一类的分析gydF4y2Ba强烈的随机性提取器。gydF4y2Ba粗略地说，这个范例允许我们做出比上面概述的一般强提取器简化更强的声明:它允许我们直接表明，如果协议生成的密钥(在隐私放大之后)被窃听者从随机密钥中区分出来，那么就有一个(有效的)经典过程，以不可忽略的概率重建Alice的原始密钥。这使得我们可以使用经典的信息理论工具来完成对猜谜游戏的还原。gydF4y2Ba

6.1.全球恐怖袭击gydF4y2Ba

在深入研究重构范式的更多细节之前，我们首先回顾一下分析需要克服的一些困难。gydF4y2Ba

回想一下，与Ekert协议相比，E1协议引入的主要区别是只有一小部分测试轮。下面的简单攻击演示了这种限制对于安全性是必要的。注意爱丽丝的装置gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}能够区分关键弹和测试弹，因为它为前一种类型的弹提供了一个特殊的输入，2。假设窃听程序gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}在某种程度上，设备系统地输出其输入的任何位gydF4y2BaxgydF4y2Ba= 2两次:按要求在关键轮中，以及在紧接着的轮中。假设密钥回合相对较少，那么第二轮很可能是测试回合。设备可能会在那一轮的CHSH游戏条件中失败，但如果有足够多的测试回合，对其平均成功概率的影响将保持较小。但测试回合的输出由用户公开交换，完整的原始密钥泄漏给窃听者!这种攻击说明了在我们的场景中面临的主要困难:用户的设备可能有内存，并且在每一轮中行为自适应，利用用户的公共通信秘密地泄露有关最终密钥的信息。gydF4y2Ba

即使把自适应设备的问题放在一边，还有第二个重要的困难。假设用户有办法强制他们的设备在每一轮中执行独立和相同的操作。仍然有可能出现这样的情况:窃听者(偷听者不可能对其进行控制)从对其在整个协议中收集的所有侧信息的全局测量中获益，以实现对密钥的最终攻击。应该排除这样的攻击，即使它的成功概率很小，只要它高于协议的安全参数。假设窃听者成功实施了一次攻击。难点开始了:对一个不太可能的事件的成功进行条件反射，这涉及到对量子侧信息和整个协议中泄漏的公共信息的测量，引入了用户观察到的经典数据(包括设备在所有回合的输入和输出)之间的相关性，这些数据需要由安全证明来处理。gydF4y2Ba

这里的混淆因素是贝叶斯的条件概率规则在存在量子侧信息时不起作用。非正式地,如果gydF4y2BaPgydF4y2Ba_ggydF4y2Ba（gydF4y2BaKgydF4y2Ba|gydF4y2BaEgydF4y2Ba)是窃听者猜出字符串的最大概率gydF4y2BaKgydF4y2Ba考虑到她的量子侧信息gydF4y2BaEgydF4y2Ba，那么就不是这样了gydF4y2BaPgydF4y2Ba_ggydF4y2Ba（gydF4y2BaKgydF4y2Ba|gydF4y2BaEgydF4y2Ba) =gydF4y2BaPgydF4y2Ba_ggydF4y2Ba（gydF4y2BaKgydF4y2Ba_NgydF4y2Ba|gydF4y2BaKgydF4y2Ba_{NgydF4y2Ba1gydF4y2Ba}、……gydF4y2BaKgydF4y2Ba_1gydF4y2Ba，gydF4y2BaEgydF4y2Ba)…gydF4y2BaPgydF4y2Ba_ggydF4y2Ba（gydF4y2BaKgydF4y2Ba_1gydF4y2Ba|gydF4y2BaEgydF4y2Ba)．事实上，有可能在右边的量都非常接近1，而在左边的量非常小，原因是猜测测量gydF4y2BaKgydF4y2Ba_1gydF4y2Ba，gydF4y2BaKgydF4y2Ba_2gydF4y2Ba、……gydF4y2BaKgydF4y2Ba_NgydF4y2Ba，不一定要“拼接在一起”，成为整个弦的猜测测量。gydF4y2Ba

为了回避这个问题，我们将设备和窃听者的联合量子态的组合以及全局测量的可能影响视为一个黑箱，并关注由Alice和Bob处理的经典信息以及它与窃听者生成的经典信息之间的关联方式。分析中的主要工具是上面提到的“重构范式”，我们接下来将讨论它。gydF4y2Ba

6.2.安全和重建范式gydF4y2Ba

让我们首先回顾一下(经典的)重构范式背后的主要思想。gydF4y2Ba^{33gydF4y2Ba，gydF4y2BaegydF4y2Ba}考虑一个强提取器Ext，它接受两个比特字符串作为输入，即源gydF4y2BaXgydF4y2Ba和种子gydF4y2BaYgydF4y2Ba，并将它们组合起来生成输出gydF4y2BaZgydF4y2Ba= Ext (gydF4y2BaX, YgydF4y2Ba)．采用矛盾法，假设对手有能力将提取器的输出与均匀输出区分开来，具有不可忽略的优势。观察这个出发点的弱点:对手的优势可能来自任何类型的信息;例如，她能够以很小的优势，预测的一小部分位的奇偶校验gydF4y2BaZgydF4y2Ba，它本身的位置取决于其他的gydF4y2BaZgydF4y2Ba等。重构范式使用Ext的特定构造的属性来表明，可以从任何这样的对手构造(明确地，这对我们来说很重要)以下更强大的对手。较强的对手有能力，作为侧信息提供给原始对手可用的信息(关于gydF4y2BaXgydF4y2Ba和种子gydF4y2BaYgydF4y2Ba)，以及一些关于gydF4y2BaXgydF4y2Ba，以生成完整字符串的“重构”猜测gydF4y2BaXgydF4y2Ba这在(/)的概率顺序下是正确的gydF4y2Ba米gydF4y2Ba）gydF4y2Ba^2gydF4y2Ba,在那里gydF4y2Ba米gydF4y2Ba的长度gydF4y2BaZ。gydF4y2Ba

我们的安全证明依赖于重构范式对量子侧信息情况的适应性。这让我们认为，任何能够分辨出最终密钥的窃听者gydF4y2BaZgydF4y2Ba用户从一个统一的随机字符串中生成的信息可以被“引导”成一个更强大的窃听者，只要给他一些额外的建议，他就能够猜出输出的完整字符串gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}协议中Alice的设备生成的非平凡概率。注意，此概率与安全参数的顺序相同。要看出它是一个强界，请注意它比提取的密钥长度的反指数的容易界要大得多，它遵循(使用任何强提取器)量子条件最小熵和猜测概率之间的对应关系。正式引入量子重构范式需要的符号超出了本文的范围。对于专家，我们提到分析中使用的主要工具是豪斯拉登和Wooters的“相当好的测量”，gydF4y2Ba^17gydF4y2Ba这样我们就能掌握窃听者的全局测量数据。gydF4y2Ba

6.3.还原成猜谜游戏gydF4y2Ba

回想一下原始键gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}是由比特组成的吗gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}＝gydF4y2Ba一个gydF4y2Ba_1gydF4y2Ba、……gydF4y2Ba一个gydF4y2Ba_{c | |gydF4y2Ba}由爱丽丝的设备产生gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}C{1，…，gydF4y2BaNgydF4y2Ba}。假设存在矛盾，当一个提取器ExtgydF4y2Ba_CgydF4y2Ba根据规范构建的重构范式被应用到gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}，用均匀选择的种子，产量gydF4y2BaZgydF4y2Ba是gydF4y2Ba不gydF4y2Ba难以区分的统一:有一个攻击对手使用所有的量子侧信息gydF4y2BaEgydF4y2Ba可以让窃听者在协议E1的末端进行区分gydF4y2BaZgydF4y2Ba从制服中获得一些优势。我们的第一步是应用量子重建范式将自己置于一个更强的位置:正如在前一节中所讨论的，它遵循存在一个“靴带”对手，他使用侧信息的组合gydF4y2BaEgydF4y2Ba和少量额外的建议位，能够产生对字符串的猜测gydF4y2BaKgydF4y2Ba_{一个gydF4y2Ba}这是正确的概率顺序(/gydF4y2Ba米gydF4y2Ba）gydF4y2Ba^2gydF4y2Ba,在那里gydF4y2Ba米gydF4y2Ba的长度gydF4y2BaZ。gydF4y2Ba

分析的第二步是排除此类攻击。我们通过简化第5节中讨论的猜谜游戏来实现这一点。为了呈现约简，我们方便地将目前的情景抽象为下面的多轮猜谜游戏形式。爱丽丝得到一gydF4y2BaNgydF4y2Ba三进制数位输入gydF4y2BaxgydF4y2Ba和鲍勃gydF4y2BaNgydF4y2Ba位输入gydF4y2BaygydF4y2Ba，均匀随机选择。他们使用各自的设备，gydF4y2BaDgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_BgydF4y2Ba，依次生成gydF4y2BaNgydF4y2Ba位输出gydF4y2Ba一个gydF4y2Ba而且gydF4y2Bab。gydF4y2Ba第三个玩家伊芙出场了gydF4y2BaxgydF4y2Ba，gydF4y2BaygydF4y2Ba，以及少量关于Alice和Bob的输出的任意建议。(这包括测试回合的输出和重构过程所需的建议位。)假设Alice和Bob的设备平均上满足CHSH博弈相关性，在随机选择的轮数上进行测试时，协议执行的顺序概率不可忽略。目标是显示Eve无法对子字符串产生正确的猜测gydF4y2Ba一个gydF4y2Ba_CgydF4y2Ba，其中C包含(gydF4y2BaxgydF4y2Ba_我gydF4y2Ba，gydF4y2BaygydF4y2Ba_我gydF4y2Ba) =(2,0)，具有不可忽略的概率。gydF4y2Ba

为了证明这一点，我们对单轮猜谜游戏进行了简化。我们试图确定一个回合gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba{1,…,gydF4y2BaNgydF4y2Ba}，使下述情况成立。让gydF4y2BaDgydF4y2Ba_{一个jgydF4y2Ba0gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_{B jgydF4y2Ba0gydF4y2Ba}表示循环开始时Alice和Bob的设备的状态gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba，以所有过去的事件为条件。这包括固定所有先前输入和输出位的值，并使这些值对三个玩家可用。那么情况应该是(i)设备gydF4y2BaDgydF4y2Ba_{一个jgydF4y2Ba0gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_{B jgydF4y2Ba0gydF4y2Ba}当提供均匀随机输入时，在增强的CHSH博弈中有很大的成功概率(gydF4y2Bax, ygydF4y2Ba) {0,1,2} ×{0,1}，和(ii) Eve有一种策略，允许她对输出产生正确的猜测gydF4y2Ba一个gydF4y2Ba获得的gydF4y2BaDgydF4y2Ba_{一个jgydF4y2Ba0gydF4y2Ba}，当给定输入时gydF4y2BaxgydF4y2Ba= 2，概率大。如果这两个条件可以同时成立，单轮猜测引理，引理1，将给出收缩。gydF4y2Ba

正如前面所解释的，完成减少的主要困难是，在原始的多轮协议中，对手的攻击是基于对其侧信息的全局测量，其中包括整个协议中收集的经典信息，以及她的初始量子态。量子重构范式的应用免除了处理对手量子态的需要，代价是为对手提供少量的建议比特。我们将这些信息分为两部分:首先，用户的输入字符串(gydF4y2Bax, ygydF4y2Ba)．第二，用户的输出(gydF4y2Ba一个gydF4y2Ba_BgydF4y2Ba，gydF4y2BabgydF4y2Ba_BgydF4y2Ba)，以及建议部分gydF4y2BaggydF4y2Ba（gydF4y2Ba一个gydF4y2Ba_CgydF4y2Ba)．信息的第二部分可以使用一个标准的技巧来处理:我们不是等待可用的比特，而是将对手修改为为他们做出统一随机选择的对手。与|C|相比，用作检查的轮数较少，她的成功概率仍然不可忽略。gydF4y2Ba

侧信息的另一部分，输入(gydF4y2Bax, ygydF4y2Ba)，不能以同样的方式消除，因为它包含太多的位。我们可以把输入分成两部分:一轮前要选择的部分gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba以及之后被选中的人。前轮选择的输入gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba将作为设备规格的一部分公开提供吗gydF4y2BaDgydF4y2Ba_{一个jgydF4y2Ba0gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_{B jgydF4y2Ba0gydF4y2Ba}，所以没有必要担心他们。关于一轮后要选择的输入gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba在美国，这足以证明存在“好的”输入选择:事实上，设备的输出是圆形的gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba不能依赖轮询后提供给设备的输入gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba；在这里，协议的顺序性质被用于一种重要的方式。gydF4y2Ba

现在，我们对对手有了一个单一的、固定的度量，对(有硬连线值)gydF4y2Bax, ygydF4y2Ba)和建议部分，我们终于可以应用(经典!)用贝叶斯规则来识别回合gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba满足条件(i)和(ii)。这提供了以下直接的含义:gydF4y2Ba

对于某个小常数gydF4y2Ba> 0。gydF4y2Ba

然而，贝叶斯规则所隐含的条件反射提出了最后一个困难:它可能引入设备在初始状态之间的相关性gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba-th轮，以及设备在该轮“期望”的输入。事实上，条件作用是基于对手在回合之前的猜测gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba是正确的。猜测又取决于输入的选择(gydF4y2Bax, ygydF4y2Ba)，它们被“硬连接”到对手中，作为上述减少的一部分。因此，对手猜测的正确性可以使输入的分布呈圆形gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba，它不再是统一的，可能与设备的状态联合相关gydF4y2BaDgydF4y2Ba_{AjgydF4y2Ba0gydF4y2Ba}而且gydF4y2BaDgydF4y2Ba_{BjgydF4y2Ba0gydF4y2Ba}．例如，它可能是一个固定回合的输入gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba都被迫做出特定的选择，如(0,0)，使得保证(i)几乎无用(如果输入是固定的，很容易赢得CHSH游戏)。这种困难类似于分析多人游戏的平行重复。Raz的工作中介绍了解决这个问题的标准方法gydF4y2Ba^26gydF4y2Ba证明了经典二人对策值的平行重复定理。其主要思想在于论证对一个具有足够大概率的事件的条件作用不能在最初以乘积形式存在的分布的所有坐标，甚至大部分坐标中引入强相关性。在技术层面上，分析使用互信息的链式法则和平斯克不等式。gydF4y2Ba

在我们的场景中，我们可以使用非常类似的方法来显示对手成功的条件反射(前提是成功发生的概率足够大)，不能在大多数回合中对用户的输入分布产生太大的偏差。这使用了最初(在条件作用之前)的分布是一个乘积分布，在协议的大量轮的每一轮中独立抽样。gydF4y2Ba

不幸的是，这一陈述并不足以达到我们的目的。我们需要展示，不仅仅是设备的输入gydF4y2Ba我gydF4y2Ba_0gydF4y2Ba接近均匀随机，而且设备的测量后状态(以相同的成功事件为条件)与用户的输入选择无关。为了证明这是不可能发生的，我们通过引入一个编码参数来处理量子相关性来扩展Raz的技术。为了避免矛盾，假设设备的状态与它们的输入(在成功猜测窃听者之后)具有非微不足道的相关性，并且这在大多数情况下都成立。我们证明了这样的装置，包括窃听者的策略，可以用来将经典信息从鲍勃和窃听者以比量子信息理论的标准论点允许的更有效的速率传输给爱丽丝，从而达到一个矛盾。要进一步讨论这一步，我们参考作者以前的工作。gydF4y2Ba^35gydF4y2Ba

回到顶部gydF4y2Ba

7.前景gydF4y2Ba

从EPR思想实验的起源，到Bell的工作和CHSH测试中的表述，再到它们在设备独立密码学中的应用，量子力学的非局部相关性已经从不受欢迎的悖论发展到操作上令人满意的证明，不仅是量子性的，而且是随机性和私密性的。gydF4y2Ba^fgydF4y2Ba

我们对安全性的证明是在一长串的工作中发现的，证明了量子相关性越来越强的用途。尽管Ekert已经指出了非局部相关对密码学的相关性，但第一个具体结果考虑了与随机放大相关的任务，其中一个用户Alice希望证明她拥有的两个设备产生随机比特，同时使用尽可能少的随机种子比特来测试设备。gydF4y2Ba

一个随机认证的协议首先在科尔贝克提出，gydF4y2Ba^10gydF4y2Ba这项任务在2012年得到了实验证明。gydF4y2Ba^25gydF4y2Ba本文中提出的一些想法首先是在分析我们在作者以前的工作中介绍的指数随机展开协议时提出的;gydF4y2Ba^34gydF4y2Ba随后，它被证明，甚至无界膨胀是可能的。gydF4y2Ba^11gydF4y2Ba

继我们在量子密钥分配方面的工作之后，Miller和Shi提出了DIQKD安全性的第二个证明。gydF4y2Ba^23gydF4y2Ba这两个证明都没有达到实际的参数，最近第三个证明填补了这个空白gydF4y2Ba^3.gydF4y2Ba它建立了协议的安全性，具有最优的噪声容忍度和密钥率。虽然这三个证明不可避免地有一些相似之处，但它们似乎依赖于本质上不同的论点;找到一个统一的设备独立性框架，将它们各自的优势结合起来，仍然是一个挑战。gydF4y2Ba

实验的最新进展gydF4y2Ba^{15gydF4y2Ba，gydF4y2Ba18gydF4y2Ba，gydF4y2Ba30.gydF4y2Ba}基于纠缠的量子密钥分发协议的实现近在咫尺。人们甚至可能开始看到，不仅在单量子比特设备之间产生纠缠(QKD所需要的)，而且在小型多量子比特“云中的量子计算机”(如IBM最近演示的那种)之间产生纠缠的可能性正在出现。共享量子纠缠的计算设备可能能够实现量子密钥分发之外的任务，从简单的协议，例如，量子秘密共享或纠缠交换，到可验证的委托计算的复杂任务。虽然这仍然是一个遥远的前景，但我们希望在这项工作中开发的技术将在未来的量子密码学中找到更广泛的适用性!gydF4y2Ba

回到顶部gydF4y2Ba

致谢gydF4y2Ba

我们感谢gydF4y2Ba通信gydF4y2Ba编辑和Gilles Brassard对本文早期版本的有用反馈。gydF4y2Ba

Umesh Vazirani获得了NSF基金CCF-1410022、MURI基金FA9550-18-1-0161和Vannevar Bush学院奖学金的支持。Thomas Vidick获得AFOSR YIP奖编号FA9550-16-1-0495、MURI奖FA9550-18-1-0161和CIFAR Azrieli全球学者奖的支持。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2019 ACM, Inc.gydF4y2Ba

---

没有发现记录gydF4y2Ba