基于正则图上量子游走的仲裁量子签名方案

奥鹏网院作业

基于正则图上量子游走的仲裁量子签名方案
施荣华 冯艳艳* 石金晶
(中南大学计算机学院 长沙 410083)
摘 要：量子游走已经被提出可以用于瞬时地传输量子比特或多维量子态。根据量子游走的隐形传输模型，该文提出一种无需提前准备纠缠源的基于正则图上量子游走的仲裁量子签名算法。在初始化阶段，密钥是由量子密钥分发系统制备；在签名阶段，基于正则图上的量子游走隐形传输模型被用于转移信息副本密文从发送者到接收者。具体地，发送者编码要签名信息的密文在硬币态上，通过两步正则图上的量子游走，可以自动地产生用于量子隐形传输必须的纠缠态。发送者和接收者对制备的纠缠态的测量为签名生成和签名验证的凭据。在验证阶段，在仲裁的辅助下，验证者依照发送者的经典结果核实签名的有效性。此外，随机数和认证的公共板被引进阻止接收方在接收真正信息序列之前的存在性伪造攻击和否认攻击。安全性分析表明设计的算法满足签名者和接收者的不可抵赖以及任何人的不可伪造。讨论表明方案不能抗击发送者的抵赖攻击，相应的建议被给出。由于实验上已经证明量子游走可以在多个不同的物理系统上实现，因此该签名方案未来是可实现的。
关键词：量子密码；仲裁量子签名；量子游走；量子隐形传输
1 引言
签名是一种允许签名后的信息从一方传送给另一方，同时信息及相应的签名被确保不可抵赖或篡改，且不可伪造的一种密码通信协议。量子签名是经典签名在量子领域的推广。目前，经典签名已经遍及多种不同的领域，比如，电子商务、电子医疗以及电子支付。然而，由于大多数经典签名方案的安全性依赖于难解的数学难题，比如，大整数因式分解和离散对数。随着未来量子计算机[1]的产生，以及运行在量子计算机上的量子算法[2,3]的提出，这些基于计算复杂度的经典签名方案将不再是安全的。而此时依赖于物理特性的量子密码签名算法依然是信息安全的，且量子保密通信技术[4,5]在理论和实验上也在不断发展，量子签名是量子保密通信协议中一个非常有意义的研究方向。与经典签名类似，量子签名同样区分为真实量子签名和仲裁量子签名(Arbitrated Quantum Signature, AQS)。从实用的角度，有可信任第三方的参与AQS方案更加实用[6,7]，且Barnum等人[8]指出不存在绝对安全的两方量子签名协议。因此本文研究AQS算法。
2002年，Zeng和Keitel[7]初次建议了基于GHZ(Greenberger–Horne–Zeilinger)态的AQS算法，他们给出了AQS方案设计的基本框架。随后，大量AQS方案被研究。2009年，Li等人[9]使用Bell态设计了AQS方案，且其方案传输效率更高且容易实现。2010年，Zou和Qiu[10]指出已存在的AQS方案无法抵抗来自验证者的抵赖，于是建议了可以抵抗来自接收者抵赖攻击的不需要纠缠态的AQS算法。此后，除了提出新颖的AQS方案，AQS方案的密码分析也引起了研究者们的关注。2011年，Gao等人[11]声称量子一次一密并不适用于AQS方案，其将导致Bob通过执行泡利操作的存在性伪造攻击行为。同时期Choi等人[12]以基于GHZ态的AQS方案作为例子提出了一类抵抗存在性伪造攻击的方法。2013年，张骏和吴吉义[13]也提议了一个可以抗击验证者已知明文攻击的AQS算法。2015年，Li和Shi[14]设计了应用受控非加密操作的AQS方案。2016年，Yang等人[15]建议了一种效率可以达到1的基于簇态的AQS算法。2017年，Zhang等人[16]设计了基于键控链式受控非加密操作的AQS方案，用于抵抗量子一次一密加密操作所遭受的潜在威胁。2018年，Zhang和Zeng[17]提议了一个改进的基于Bell态的AQS算法。上面提到的这些方案都是在离散场景下设计的AQS协议。在连续变量场景，文献[18]和文献[19]分别设计了基于相干态和压缩真空态的AQS方案。最近，基于双模压缩真空态的AQS算法[20]也被提出，其中连续变量的量子密集编码技术被应用。
从信息副本由发送者到接收者转移方式的角度，以上的方案共包含两种方式：(1)基于纠缠态的量子隐形传输方式，比如GHZ态[7,12]、Bell态[8,17]，连续Einstein-Podolsky-Rosen (EPR)对[18–20]；(2)量子加密方式，比如，量子一次一密[10]，受控非加密[14]，键控链式受控非加密[16]。相比于第2种量子加密的传输方式，基于纠缠的量子隐形传输[21,22]方式具有以下特点：(1)不需要传输粒子本身，传输的是粒子所处的状态；(2)一种瞬时传输，传输时间取决于经典通信的时间；(3)传输距离不受物理限制更容易实现远距离的量子通讯；(4)由于纠缠的存在，具有反窃听功能。本文将应用量子游走的隐形传输模型，呈现一种新颖的AQS算法。
量子游走是经典游走在量子领域的对应物。1993年，Aharonov等人[23]首次提议了量子游走的概念，他们指出由于量子干涉效应，量子游走中的可实现的平均路径长度比经典随机游走允许的最大路径长度要长。依据时间演化，量子游走被分为离散时间量子游走[24]和连续时间量子游走[25]。之后，基于不同模型的量子游走形式已经被证明广泛应用在量子信息处理任务中，如空间搜索问题[26]、元素甄别问题[27]、图形同构[28]等问题。且1维量子游走成功在核磁共振[29]、离子肼[30]以及光学体系[31]等不同物理系统上被实现。近期，Shang和Wang等人[32,33]讨论了基于量子游走的不同模型可以成功应用在量子隐形传输和量子态转移，强调以下两点：(1)用于隐形传输的纠缠态不必提前制备，它们可以由量子游走一步之后自动产生，就纠缠态制备困难而言，这是一种较大的创新；(2)当传输d 维量子态，基于量子游走的隐形传输具有更高的效率。因此，研究量子游走在量子通信协议中的应用是有意义的。
本文将应用基于量子游走的隐形传输到AQS方案中用于传输信息副本，设计一种新颖的基于量子游走的AQS方案。建议的方案具有如下优势：第一，基于量子游走的隐形传输无需提前制备纠缠态，它们可以在量子游走的一步之后生成；第二，应用基于 d 正则图的量子游走隐形传输转移d 维量子态，具有 n+d 个元素的两个投影测量替代之前的d 2个元素的联合测量被应用，更容易实现；第三，随机数r 和认证的公共板被雇用，可以抗击接收者接收信息序列之前的存在性伪造攻击和否认攻击。
本文的结构如下：第2节，描述图上的量子游走；第3节，呈现基于正则图上量子游走的AQS算法；第4节对提出的AQS算法给出安全性分析及讨论；第5节为结论。






参 考 文 献
[1]NIELSEN M A and CHUANG I. Quantum computation and quantum information[J]. American Journal of Physics,2002, 70(5): 558–559. doi: 10.1119/1.1463744.
[2]SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303–332. doi:10.1137/S0036144598347011.
[3]GROVER L K. Quantum mechanics helps in searching for a needle in a haystack[J]. Physical Review Letters, 1997,79(2): 325–328. doi: 10.1103/PhysRevLett.79.325.
[4]GUO Ying, LIAO Qin, WANG Yijun, et al. Performance improvement of continuous-variable quantum key distribution with an entangled source in the middle via photon subtraction[J]. Physical Review A, 2017, 95(3):032304. doi: 10.1103/PhysRevA.95.032304.
[5]ZHANG Zhaoyuan, SHI Ronghua, ZENG Guihua, et al.Coherent attacking continuous-variable quantum key distribution with entanglement in the middle[J]. Quantum Information Processing, 2018, 17(6): 1–18. doi: 10.1007/s11128-018-1903-0.
[6]MEIJER H and AKL S. Digital signature schemes for computer communication networks[J]. ACM SIGCOMM Computer Communication Review, 1981, 11(4): 37–41. doi:10.1145/1013879.802657.
[7]ZENG Guihua and KEITEL C H. Arbitrated quantumsignature scheme[J]. Physical Review A, 2002, 65(4):042312. doi: 10.1103/PhysRevA.65.042312.
[8]BARNUM H, CRÉPEAU C, GOTTESMAN D, et al.Authentication of quantum messages[C]. The 43rd Annual IEEE Symposium on Foundations of Computer Science,Vancouver, Canada, 2002: 449–458. doi: 10.1109/SFCS.2002.1181969.
[9]LI Qin, CHAN W H, and LONG Dongyang. Arbitrated quantum signature scheme using Bell states[J]. Physical Review A, 2009, 79(5): 054307. doi: 10.1103/PhysRevA.79.054307.
[10]ZOU Xiangfu and QIU Daowen. Security analysis and improvements of arbitrated quantum signature schemes[J].Physical Review A, 2010, 82(4): 042325. doi: 10.1103/PhysRevA.82.042325.
[11]GAO Fei, QIN Sujuan, GUO Fenzhuo, et al. Cryptanalysis of the arbitrated quantum signature protocols[J]. Physical Review A, 2011, 84(2): 022344. doi: 10.1103/PhysRevA.84.022344.
[12]CHOI J W, CHANG K Y, and HONG D. Security problem on arbitrated quantum signature schemes[J]. Physical Review A, 2011, 84(6): 062330. doi: 10.1103/PhysRevA.84.062330.
[13]张骏, 吴吉义. 可证明安全高效的仲裁量子签名方案[J]. 北京邮电大学学报, 2013, 36(2): 113–116.ZHANG Jun and WU Jiyi. Provable secure efficient arbitrated quantum signature scheme[J]. Journal of Beijing University of Posts and Telecommunications, 2013, 36(2):113–116.
[14]LI Fengguang and SHI Jianhong. An arbitrated quantum signature protocol based on the chained CNOT operations encryption[J]. Quantum Information Processing, 2015,14(6): 2171–2181. doi: 10.1007/s1112.
[15]YANG Yuguang, LEI He, LIU Zhichao, et al. Arbitrated quantum signature scheme based on cluster states[J].Quantum Information Processing, 2016, 15(6): 2487–2497.doi: 10.1007/s11128-016-1293-0.
[16]ZHANG Long, SUN Hongwei, ZHANG Kejia, et al. An improved arbitrated quantum signature protocol based on the key-controlled chained CNOT encryption[J]. Quantum Information Processing, 2017, 16(3): 1–15. doi: 10.1007/s11128-017-1531-0.
[17]ZHANG Yingying and ZENG Jiwen. An improved arbitrated quantum scheme with Bell states[J].International Journal of Theoretical Physics, 2018, 57(4):994–1003. doi: 10.1007/s10773-017-3632-z.
[18]GUO Ying, FENG Yanyan, HUANG Dazu, et al.Arbitrated quantum signature scheme with continuousvariable coherent states[J]. International Journal of Theoretical Physics, 2016, 55(4): 2290–2302. doi:10.1007/s10773-015-2867-9.
[19]FENG Yanyan, SHI Ronghua, and GUO Ying. Arbitrated quantum signature scheme with continuous-variable squeezed vacuum states[J]. Chinese Physics B, 2018, 27(2):020302. doi: 10.1088/1674-1056/27/2/020302.
[20]LOU Xiaoping, LONG Hu, TANG Wensheng, et al.Continuous-variable arbitrated quantum signature based on dense coding and teleportation[J]. IEEE Access, 2019, 7:85719–85726. doi: 10.1109/ACCESS.2019.2925635.
[21]BENNETT C H, BRASSARD G, CRÉPEAU C, et al.Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels[J]. Physical Review Letters, 1993, 70(13): 1895–1899. doi: 10.1103/PhysRevLett.70.1895.
[22]REN Lijie, HE Guangqiang, and ZENG Guihua. Universal teleportation via continuous-variable graph states[J].Physical Review A, 2008, 78(4): 042302. doi: 10.1103/PhysRevA.78.042302.
[23]AHARONOV Y, DAVIDOVICH L, and ZAGURY N.Quantum random walks[J]. Physical Review A, 1993, 48(2):1687–1690. doi: 10.1103/PhysRevA.48.1687.
[24]MEYER D A. From quantum cellular automata to quantum lattice gases[J]. Journal of Statistical Physics,1996, 85(5/6): 551–574. doi: 10.1007/BF02199356.
[25]FARHI E and GUTMANN S. Quantum computation and decision trees[J]. Physical Review A, 1998, 58(2): 915–928.doi: 10.1103/PhysRevA.58.915.
[26]CHILDS A M and Goldstone J. Spatial search by quantum walk[J]. Physical Review A, 2004, 70(2): 022314. doi:10.1103/PhysRevA.70.022314.
[27]AARONSON S and SHI Yaoyun. Quantum lower bounds for the collision and the element distinctness problems[J].Journal of the ACM, 2004, 51(4): 595–605. doi: 10.1145/1008731.1008735.
[28]DOUGLAS B L and WANG J B. A classical approach to the graph isomorphism problem using quantum walks[J].Journal of Physics A: Mathematical and Theoretical, 2008,41(7): 075303. doi: 10.1088/1751-8113/41/7/075303.
[29]DU Jiangfeng, LI Hui, XU Xiaodong, et al. Experimental implementation of the quantum random-walk algorithm[J].Physical Review A, 2003, 67(4): 042316. doi: 10.1103/PhysRevA.67.042316.
[30]SCHMITZ H, MATJESCHK R, SCHNEIDER C, et al.Quantum walk of a trapped ion in phase space[J]. Physical Review Letter, 2009, 103(9): 090504. doi: 10.1103/PhysRevLett.103.090504.
[31]PERUZZO A, LOBINO M, MATTHEWS J C F, et al.Quantum walks of correlated photons[J]. Science, 2010,329(5998): 1500–1503. doi: 10.1126/science.1193515.
[32]WANG Yu, SHANG Yun, and XUE Peng. Generalized teleportation by quantum walks[J]. Quantum Information Processing, 2017, 16(9): 1–13. doi: 10.1007/s11128-017-1675-y.
[33]SHANG Yun, WANG Yu, LI Meng, et al. Quantum communication protocols by quantum walks with two coins[J]. EPL (Europhysics Letters), 2019, 124(6): 60009.doi: 10.1209/0295-5075/124/60009.
[34]AHARONOV D, AMBAINIS A, KEMPE J, et al. Quantum walks on graphs[C]. The 33rd Annual ACM Symposium on Theory of Computing, Hersonissos, Greece, 2001: 50–59. doi:10.1145/380752.380758.
[35]BRUN T A, CARTERET H A, and AMBAINIS A.Quantum walks driven by many coins[J]. Physical Review A, 2003, 67(5): 052317. doi: 10.1103/PhysRevA.67.052317.
[36]BUHRMAN H, CLEVE R, WATROUS J, et al. Quantum fingerprinting[J]. Physical Review Letters, 2001, 87(16):167902. doi: 10.1103/PhysRevLett.87.167902.
[37]PÉREZ E, CURTY M, SANTOS D J, et al. Quantum authentication with unitary coding sets[J]. Journal of Modern Optics, 2003, 50(6/7): 1035–1047. doi:10.1080/09500340308234550.
Arbitrated Quantum Signature Scheme with Quantum Walks on Regular Graphs
SHI Ronghua FENG Yanyan SHI Jinjing
(School of Computer Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Quantum walks are raised for teleporting qubit or qudit. Based on quantum walk teleportation, an arbitrated quantum signature scheme with quantum walks on regular graphs is suggested, in which the entanglement source does not need preparing ahead. In the initial phase, the secret keys are generated via quantum key distribution system. In the signing phase, the signature for the transmitted message is created by the signer. Teleportation of quantum walks on regular graphs is applied to teleporting encrypted message copy from the signer to the verifier. Concretely, the sender encodes the ciphertext of message copy on coin state.Then two-step quantum walks are performed on the initial system state engendering the necessary entangled state for quantum teleportation, which can be the basis of signature generation and verification. In the verifying phase, the verifier verifies the validity of the completed signature under the aid of an arbitrator. Additionally,the applications of random number and public board deter the verifier’s existential forgery and repudiation attacks before the verifier accepts the true message. Analyses show that the suggested arbitrated quantum signature algorithm satisfies the general two requirements, i.e., impossibility of disavowal from the signer and the verifier and impossibility of forgery from anyone. The discussions demonstrate that the scheme may not prevent disavowal attack from the signer and that the corresponding improvements are presented. The scheme may be realizable because quantum walks have experimentally proven to be implementable in different physical systems.
Key words: Quantum cryptography; Arbitrated quantum signature; Quantum walk; Quantum teleportation
中图分类号：TN918.2
文献标识码：A
文章编号：1009-5896(2020)01-0089-09
DOI: 10.11999/JEIT190597
收稿日期：2019-08-07；改回日期：2019-10-29；网络出版：2019-11-13
*通信作者： 冯艳艳 fengyanyanhenu@163.com
基金项目：国家自然科学基金(61871407, 61872390, 61972418)，中南大学中央高校基本科研业务费专项基金(2018zzts179)
Foundation Items: The National Natural Science Foundation of China (61871407, 61872390, 61972418), The Fundamental Research Funds for the Central Universities of Central South University (2018zzts179)
施荣华：男，1963年生，教授，研究方向为量子密码协议、信息和网络安全.
冯艳艳：女，1991年生，博士生，研究方向为量子密码协议、量子游走及其应用.
石金晶：女，1986年生，副教授，研究方向为量子密码协议、量子神经网络及其应用.