理论计算机科学电子笔记270（2）（2011）231-249www.elsevier.com/locate/entcs量子密钥分配的图形演算（延伸摘要）鲍勃·科克1牛津大学计算实验室王泉龙2北京航空航天大学数学与系统科学学院，北京，中国中国信息安全国家重点实验室（中国科学院研究生院王宝山2王永军2张启业2北京航空航天大学数学与系统科学学院中国摘要受控的互补测量是量子密钥分发协议的关键。我们axiomatize控制互补测量对称monoidal范畴内，这为他们提供了相应的图形演算。我们研究了BB84和Ekert91协议在这个演算，包括有拦截重发攻击的情况下。关键词：范畴语义，量子密钥分配，互补观测量，图演算。1引言保证通信协议的安全属性是非常重要的，正如发现广泛使用的Needham-1Email：co ec k e @ c oml a b. 牛。AC. uk2电子邮件：[qlwang，bwang，wangyj，zhangqiye]@buaa. edu。Cn3这项工作得到了中国国家科学基金（NSFC）60773141和10701006号基金、EPSRC高级研究奖学金EP/D 072786/1和美国海军研究办公室（ONR）N 00014 -09-1-0248号基金的部分支持。我们感谢Samson Abramsky，Ross Duncan和Chris Heunen的建设性反馈。1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.01.034232B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231Schroeder协议实际上是不安全的[19]。因此，该领域的现代研究涉及高级方法。虽然传统公钥密码术的安全性依赖于某些数学函数的计算难度，并且不提供窃听的指示，相反，量子公钥密码术的安全性依赖于量子力学的基础，并且可以通过逐位比较通信方的数据的子集来检测窃听。本文主要研究量子公钥密码的高级方法。在过去的几年里，一些研究人员已经开发了一个高级的量子力学的猫-egorical形式化的对称monoidal dagger范畴，它带有相应的图形演算，例如。[1、22、8、4、6]。这一传统的哲学思想在20世纪70年代由Penros [ 2 1 ]提出，并成为Joyal和Street [ 16，23 ]工作的正式纪律。特别是对于用于量化的量化技术的量化技术相关的是Kelly和Laplaza的复杂性（clos ed）量化技术[17]、C a rbone i and W a lte r s ' Frb e nu s a l g e b r a s [ 3 ]和Laplaza的复杂性（clos ed）量化技术[18]。所有这些都是比较复杂的匕首版本[1，22，8]，它们解释了希尔伯特空间内积（以及因此的正交性）。在图形演算中，量子测量[8，10]、经典受控量子测量[6]和互补可观测量[4]可以被给出直观的公理化，这又提供了对典型量子协议的直观描述，例如量子隐形传态[1，8，6]、超密集编码[4]和几种基于测量的量子计算方案，例如Gottesman和Chung的logic-gatetele por t a t at量子密码协议，如BB84和Ekert 91 [2，12]涉及受控互补可观测量。虽然我们有图形的理解互补的两个可观的，以及控制可观的，在后者的控制空间是一个抽象的。因此，将这两个概念合二为一并非易事。这是本文的主要贡献：公理化控制互补测量的语言对称monoidal类别，因此在图形演算。这在第3节中完成。这使我们能够给出BB84和Ekert91协议的简明介绍我们证明了这些的正确性，并分析了情况下，有一个拦截重发攻击。这在第4节和第5节中完成。首先，在第2节中，我们调查以前的工作基础上，互补性，测量，控制和经典的量子区别在图形演算。2基础、互补性、测量、控制我们假设读者熟悉量子力学范畴形式化的相关范畴理论背景，这在[9]中进行了我们从[8，6，4]中回顾一些基本概念本文中的所有范畴都将是一个简单的概念，我们将与它一起工作，B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231233相应的图形演算[23]。设（X，δ，λ）是对称么半群上的一个特殊的交换<$-Frobenius代数†-C类，或者简单地说，一个经典结构。我们用图形化的方式来描述幺半群的余乘δ和它的单位：作为蜘蛛定理[18]的结果，这些经典结构使直观的图形推理成为可能。这个定理意味着任何态射得到利用经典结构（X，δ，δ）的幺半群乘法，讨论了它的单位、合成、张量、匕首和对称幺半群†-categories仅取决于其类型：X. . . X → X. . 第十章``n m我们将这种类型的唯一态射表示为：特殊情况包括：• spider（n=1，m= 2）=δ• spider（n= 1，m = 0）=0• 蜘蛛（n= 1，m = 1）= 1X我发现下面有几个这样的情节因此，我们不能认为这种类似的系统可以被忽略。这方面的一个具体例子是：234B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231也就是说，经典结构总是带有（自对偶）<$-紧结构[1，22，6]。因此，对于（支持的对象）两个经典结构（X，δX，X）和（Y，δY，Y）之间的每个态射f：X → Y，总是允许一个转置和一个共轭，也就是说，当描绘作为然后和设FdHilb是有限维Hilbert空间的对称monoidal <$-范畴，线性映射是张量积，线性代数伴随。在这一类中，经典结构是精确的标准正交基：命题2.1 [10]对于任何标准正交基{|Hilbert空间H的{i∈ {i ∈ {i ∈ {i ∈ {i}δ：：|我的博客→|二、� 和�：：|1个是FdHilb中经典结构的乘法和单位。相反，FdHilb中的每一个经典结构都是以这种方式产生的。命题2.2[4]根据命题2.1，两个经典结构对应于互补正交基当且仅当：（1）在哪里。在量子理论中，基础代表一些可观察的经典数据，因此B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231235经典结构的名称 A态射f：A→B是酉的当且仅当f <$f<$=1 B，ff = 1 A。 给定一个经典结构和一个酉态射U，（二）是一个经典结构，其中，根据命题2.1，U在给定结构的基础上映射所构造的经典结构的基础。根据[6]，m：X<$A→B表示控制酉当且仅当(3).这里，X输入采用经典数据，即基向量|根据这些数据，可以确定一个单位矩阵（|i 1 A）：执行A→B。4但是我们如何在图形语言中区分经典线和量子线呢？由于测量产生概率输出，我们需要考虑概率经典数据。给定希尔伯特空间中的基，这可以用对角的密度矩阵表示。塞林格提供了一个图解说明，[22]中关于混合态的一个完全正映射，作为范畴FdHilb上的范畴他提出了一个新的范畴CPFdHilb，它有相同的对象，但有态射其中f：A→B<$C是FdHilb中的任意态射，帽形线来自FdHilb的紧致结构，即： |ij→δij。所以任何量子系统实际上都是用两根线来表示的 在[6]中，通过经典结构实现了将分类数据从双线表示转换为单线，例如一个受控的酉运算，而不是（3）中的态射m，实际上是一个4 符号m的原因将在下面变得清楚。236B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231态射：其中m如（3）中所示，而非破坏性测量将采取以下形式：其中M服从[8]中所阐述的某些条件。考虑到满足（3）的态射的重要性，我 们 将 继 续 把 它 们 称 为 受 控 酉 单 位 （ asopposedtooc o n trontrolledunitary“op e r a t i o n s”）。定义2.3 [6]考虑对称monoidal <$-范畴C中的经典结构（X，δX，<$X）和（Y，δY，<$Y）。在C中具有控制（X，δX，X）和结果（Y，δY，Y）的受控非破坏性测量是一个态射：其中M是这样的：（四）B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231237我CP类似地，受控的破坏性测量是态射（五）如此以使得服从（4），因此引起受控的非破坏性测量。命题2.4[8，6]对于每个穷举投影谱族、、、K即对于所有的i，j，kPk Pk=δ Pk{Pi：H →H}i， Pkt= Pk、KΣ Pk= 1、线性映射i jij i i i i i i iH我ΣM：=i，k（|伊什托克|）P k满足（4），因此定义了CPFdHilb中的受控无损测量作为结果，对应于标准正交基的经典结构{|i} i并以标准正交基对应的经典结构作为控制。|k}k. 相反，FdHilb中的每个受控非破坏性测量都以这种方式产生。命题2.5与CP FdHilb中受控破坏性测量的命题2.4类似的陈述也成立。命题2.6如果在（5）中，我们取m为受控么正，则我们总是得到受控破坏性测量。我们称这些受控测量为非简并测量，因为在CPFdHilb中，这些精确地对应于非简并非破坏性测量。在这里，我们考虑任意的测量集合。这些对于实际目的来说并不那么有用。我们现在陈述一个相似的结果，用于成对互补的破坏性测量的受控238B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）2313受控互补碱基为了清楚起见，我们在这里仅限于非破坏性测量，对于非破坏性测量，存在与受控幺正的直接对应（参见图1）。命题2.6），因此也有基族。我曾在《易经》中有过一段回忆，那就是《易经》中的“六经”。 一个经典结构的经典点是一个态射<$：I →A，使得：经典结构的置换是态射π：A→B，使得：（六）这特别意味着π是自共轭的。定义3.1置换是不动点自由的当且仅当对于对应经典结构的任何经典点π π命题3.2在 FdHilb中，不动点自由置换是线性映射|π（i） |π (i)⟩其中π：{1，. . . ，n} → {1，. . . ，n}是一个普通的不动点自由置换。定义3.3受控互补测量是态射（5），m是受控酉式，使得：（七）对于所有不动点自由置换π.在这种情况下，我们称之为m个受控的互补幺正，以及相应的受控经典结构（参见。（2）互补的经典结构，或更短的互补碱基。下面的定理证明我们的术语是正确的。B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231239K√、、、定理3.4对于互补基{|ik，即k=l时的平均值δijKL吉吉|j =1000暗（H）对于 k l线性映射：m：=Σ（|伊什托克|）|Ki，k对于所有固定点自由排列π，满足（7）（并且因此定义CP FdHilb中的受控互补测量）。相反，CP FdHilb中的所有受控互补酉都以这种方式出现。证据证明的关键在于以下几点。给定受控幺正m，相应的基（cf.（2）是：对于给定的控制变量值，即基的选择，我们得到相同值的另一个基如下：通过在所有不动点自由排列和控制变量的所有值上的范围，我们得到所有可能的基对。为了断言所有对的互补性，240B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231在（1）中替换所有这些，结果是：哪里利用（3）并消去两幅图中的外部受控幺正，我们确实得到（7）。Q注意，证明的关键不依赖于具体的Hilbert空间结构，而是依赖于[4]中对互补性的抽象分析因此，我们对受控互补幺正的抽象定义自然地扩展到广泛的一类潜在模型。4BB84和Ekert 91的图形演算BB84的程序如下[2]：(i) Alice选择两个随机比特串α = α1。. . α4 n和a = a1。. . a4 n.(ii) Alice以依赖于ai的方式将每个比特ai编码为量子比特。 比特αi= 0被编码为qi= |0 if ai= 0 and as qi=|如果ai= 1，则将比特αi= 1编码为qi=|如果ai= 0且qi= 0，则为1|如果ai= 1，则为− 1。B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231241(iii) Alice通过量子信道将量子比特传输给Bob。(iv) Bob选择随机位串b = b1。. . b4 n，并测量如果bi= 0，则在Z -基上，如果bi= 1，则在X -基上，得到β = β1。. . β4 n.(v) Bob通过常规信道将b(vi) 爱丽丝发送一个b = a1b1。. . 通过传统渠道向鲍勃发送4n个电子邮件。(vii) 爱丽丝（Alice）Bob）仅保留α（resp.βiinβ），其中ai≠bi= 0，并丢弃其他。在没有攻击的情况下，两个结果串，平均长度为2n，重合。 记为ω =ω1。. . ωη。接下来，爱丽丝和鲍勃想确认夏娃是否没有攻击。(viii) Alice和Bob同意他们各自的字符串ωA_ lice的n位的子集，并且ωBeta并比较它们的值。(ix) 为了常规密码学的目的，将具有平均长度n的序列长度ω k的ωA和ωB的所有比特作为私钥。Ekert 91的过程是类似的; Alice和Bob共享Bell状态，然后botperform（iv），并且next（v）-（ix）。我们现在可以使用上一节的结果将这些协议转换为图形语言。注意，（ii）可以通过a控制幺正来实现，该幺正应用于ai= 0的恒等式和ai= 1的Hadamard门根据命题2.6，这两个协议是高度相关的。我们得到的程序，直到（七）：Ekert 91：（八）[5]确定这确实是一个贝尔状态是协议的一部分242B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231BB84：（九）其中XAL ice=XBob=YAL ice=YBob=A=C2，m：X−A→Y−：：|00 ⟩›→ |0分，|01 ⟩›→ |1个月，|联系我们|0分，|1 −⟩›→ |1个月，也就是说，作为一个矩阵，10√1√1（I H）=0 122英里。1 −√1其中I是2× 2单位矩阵，H是Hadamard门。这些图片表明，这两个协议是相互转换的仅仅是转换。因此，无论我们证明了什么，都可以立即翻译成另一个。下面我们选择考虑Ekert91协议。我们现在希望用图形语言来证明这些协议的正确性，也就是说，当Alice和Bob的控制输入一致时，来自Alice的信息可以完全传递给Bob，但是当Alice和Bob的控制输入在图形化的存储方面，第一个存储空间具有“连接到A”和“连接到B”（通过数据库），而第二个存储空间具有“连接到A”和“连接到B”。我们可以断言控制输入一致为：√22B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231243它们并不一致：其中π是{0， 1}的唯一不动点自由置换，即没有设（X，δX，<$X）和（Y，δY，<$Y）是任意对称幺半群中的经典结构<$-范畴C，设m：X<$A→Y是任意的控制么正，设π：X→X可以是任何不动点自由置换。 然后又道：244B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231在这里我们使用（3）。 如果m是互补的，则：其中我们使用了（7）和（6）。Heunen在[15] §3.3中已经考虑过第一种选择重合的情况。我们在这里的贡献是所选的基是互补的。5对BB84为了说明BB84的安全性，让我们考虑一个简单的例子：窃听者Eve的拦截-重发攻击，他测量了Alice在随机选择的基础上发送的每个量子位（足够快，以便Bob无法检测到干扰），然后将结果状态重新发送给Bob。 由于两个基地是随机选择的每一方，这样的拦截重发攻击将给出一个比特错误率为0。5× 0。5= 0。25，在BB84协议的第（viii）部分中，这很容易被Alice和Bob检测到B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231245对BB84的拦截重发攻击：（十）现在再考虑一个一般的对称么半群<$-范畴，其中的任何一对经典结构，任何相应的受控互补么正，和任何不动点自由置换，则：246B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231以及：B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231247六、结论我们提供了一个图形公理化的主要量子密钥分配协议，使能够非常容易地证明他们的正确性，以及他们的性质，在攻击的情况下。事实上，由于我们的方法的抽象程度，我们还证明了这一点对于更一般的量子协议类别，以及更一般的数学模型类别。关键是控制互补酉的公理化。这些显然有许多重要的应用，也是基础的重要性。因此，我们期待更多的结果从我们的出现。一个值得注意的问题是，在同一个文件中，（=Fr o b eni u s tru c t re e的特殊性）和对数据库的兼容性，在量子密钥分发中，针对Alice和Bob的密钥分配和分配（比较）选择，提出了一种新的算法公理BB84埃克特91相同：组件：这意味着新的网络已经覆盖了整个社区。 这是一个非常好的选择。quantum'. 可使用Def in it i ning（7）3. 3.在Alice和Bob选择不同测量值的情况下，证明了Quankeydistrionprotocols的正确性。你看，这是新的。等式（7）中的两个等式是具有互补性的“HOPF-LA”（1）的一个独立等式。这指出了经典-量子区别（即退相干）和互补性之间的一种新的结构联系。一个技术问题是，我们对不动点自由的抽象定义虽然完全适合我们在这里的目的，但可能无法提升到经典结构可能具有太少经典点的其他模型，例如。有限集和关系范畴FRel。由于FRel中的经典结构同时被很好地理解[5，20，13]，并且已经证明比预期的要丰富得多，因此值得248B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231也研究这一领域的密码学现象一个可能的替代解释是要求置换具有零迹，这涉及假设存在零标量。Heunen在[14]中已经考虑的另一个问题是对无界位串的显式说明，可以在这里混合。引用[1] S.Abramsky和B.科克量子协议的分类语义。在 ：Proceedingsof19thIEEEconnferencénlogicinComputerrSciencence，第415- 425页。 我的论文，2004年。 arXiv：quant-ph/0402130。修订和扩展版本：arXiv：0808.1023[2] C. H. Bennett和G.巴拉德量子密码学：公钥分配和掷硬币。在IEEE计算机、系统和信号处理国际会议论文集，第175 - 179页，Ban g alor e，I nd i a，1984中。我知道，我知道。[3] A. Carboni和R. F. C. WaltersCartesian bicategories I. Journal of Pure and Applied Algebra 49，11-32，1987.[4] B. Coecke 和 R. 邓 肯 相 互 作 用 的 量 子 观 测 。 In ： Proceedings of the 35th InternationalColloquiumonAutomata，LanguagesanddProgramming（ICALP），pp. 298- 310 ，计算机科学中的计算机科学5126，Springer-Verlag，2008。修订和扩展版本：arXiv：0906.4725[5] B. Coecke和B.爱德华兹玩具量子分类。电子笔记在理论计算机科学，出现。arXiv：0808.1037[6] B. Coecke，E. O. Paquette和D.帕夫洛维奇经典和量子结构主义。在《QuantumComptati on的语义T e c h n i q u e s》中，I. 我和S都是。GAY（EDS），第29- 69页arXiv：0904.1997[7] B. Coecke，E.O. Paquette和S.珀德里克斯图解量子协议的基础。 Electronic NotesinTheHeoreticalComputerSci ence218，131- 152，2008. arXiv：0808. 1037[8] B. Coecke和D.帕夫洛维奇量子测量不需要求和。在：量子计算机数学与技术，G. 奇恩湖KAUFMANNDS. 《法律 汇编 》， 第 567- 604页 。 Tayl or和Francis，2007年。arXiv：quant-ph/0608035[9] B. Coecke和E.O. 帕盖特物理学家的分类。在：物理学的新结构B. Coecke（ed），第167- 271页。 LectureNotesinPhysics，Springer-Verlag，2010. arXiv：0905. 3010[10] B. Coecke，D. Pavlovic和J. 牧师正交基的一种新描述。arXiv：0810.0812[11] R. Duncan和S.珀德里克斯图的状态和欧拉分解的必要性。在：Proceedings of ComputabilitryinEurope：Mathemati calTh eoryanddComputati onalPracti c e（CiE' 09），第167 - 177页中。计算机科学讲义5635，Springer-Verlag，2009。arXiv：0902.0500[12] A.Ekert.Quntumc ry ptographyasedo n Bell s t e o r m. Physi calRevi e wLetters67 ， pp.661-663，1991.[13] J. 埃文斯河，巴西-地Duncan，A.Lang和P.帕南加。在Rel对所有相互无偏的基进行分类。arXiv：0909.4453[14] C. Heunen（2008）Companies accessible categories and quantum key distribution.计算机科学中的逻辑方法4，第4期，论文9。arXiv：0811.2113[15] C. Heunen（2009）Categorical Quantum Models and Logics.博士论文，奈梅亨大学。[16] A. 我是约翰·阿兰德·R。 STRET。 传统的存储器或计算器I。 A DVANCESinMathemati cs88，55- 112，1991.[17] G. M. Kelly和M.L. 拉普拉扎紧闭范畴的相干性。 Journal of Pure and AppliedAlgebra19，193- 213，1980.[18] S. LACK。 我是一个很好的朋友。 TheheoryandAppli cati onsofCategori es13，147- 163，2004.[19] G.洛对Needham-Schroeder公钥认证协议的攻击。InformationProcessingLetters56，131- 136，1995.[20] D. 帕夫洛维奇非确定性计算中的量子与经典结构。 讲座笔记，《计算机科学》第5494期，第143-157页，《科学》，2009年。 arXiv：0812. 2266B. Coecke等人/Electronic Notes in Theoretical Computer Science 270（2）（2011）231249[21] R. 彭罗斯负维张量的应用。在《组合数学及其应用》中，D. Welsh（E d），第221- 244页。1971年的《ACADEMICPRESS》。[22] P. Selinger（2007）Dagger compact closed categories and completely positive maps.《电子注释》，《计算机科学》170，139- 163。[23] P.塞林格。monoidal范畴的图形语言综述。在：物理学的新结构，B. Coecke（ed），第275- 337页。 LectureNotesinPhysics，Springer-Verlag，2010. arXiv：0908. 3347
我的内容管理
展开
