基于量子游走的仲裁量子签名方案*

冯艳艳 施荣华 石金晶 郭迎

(中南大学计算机学院,长沙 410083)

1 引 言

量子签名是数字签名的量子相对物.类似于经典数字签名,依照仲裁的参与度,量子签名区分为真实量子签名(true quantum signature,TQS)和仲裁量子签名(arbitrated quantum signature,AQS).在TQS算法中,签名算法是隐秘的,验证算法是暴露的.只有在产生纠纷或者分歧的时候,仲裁才被需求.在AQS算法中,签名和验证算法均为秘密的.仲裁作为可信任的第三方参与算法的设计和实现过程.尽管TQS是有利的,AQS被证明在电子投票和电子支付场景是更加实用的[1,2].因此,本文重点关注AQS.

随着未来量子计算机[3]的出现,依据不可证明计算假设和许多难解数学难题的签名算法将被攻破.而依据物理特性的量子密码签名算法是信息安全的,加之量子保密通信技术在理论和实验上的不断发展[4-8],许多学者们对AQS方案的研究一直密切关注.2002年,Zeng和Keitel[2]首次基于Greenberger-Horne-Zeilinger (GHZ)态提出AQS方案.2008年,Curty和Lütkenhaus[9]对文献[2]方案的描述和操作给出了评论.同年,Zeng[10]对文献[2]给出了一个详细的证明并对文献[9]给出了回应.2009年,Li等[11]使用Bell态代替GHZ态提出了相对应的AQS方案,并展示了其在传输效率和实现具有低复杂度的优势.之后,研究者对AQS的安全性进行了深入研究.2010年,Zou和Qiu[12]宣称已有的AQS方案不能保证来自接收者的抵赖,并设计了可以抵抗接收者抵赖的AQS算法.2011年,Gao等[13]指出基于量子一次一密(quantum one time pad,QOTP)的AQS方案中存在签名的抵赖攻击和接收者的伪造攻击,并给出了相应的改进方法.同年,Choi等[14]强调已有AQS协议中存在一种通过修改传输消息和签名的伪造攻击,并提出了抵御这种攻击的方法.2013年,张骏和吴吉义[15]建议了一种能够抵抗验证者已知明文攻击的AQS协议.2015年,Li和Shi[16]使用链式受控非操作代替QOTP提出了AQS方案.2016年,Yang等[17]设计了基于簇态的AQS协议,其效率可以达到 1.2017年,Zhang等[18]设计了基于键控链式受控非(keycontrolled chained CNOT,KCCC)操作的改进的AQS方案.2018年,Zhang和Zeng[19]提出一个改进的基于Bell态 AQS方案.以上这些方案都是基于离散变量的AQS方案.在连续变量AQS协议方面,我们分别提出了基于相干态[20]和压缩真空态[21]的AQS方案.

依据信息副本从签名者到接收者被传输的方式,以上所提到的AQS协议可以分为两类：1)基于纠缠态的隐形传输方式,例如GHZ[2]、Bell[11]、连续 Einstein-Podolsky-Rosen (EPR)[20,21];2)简单的量子加密方式,例如QOTP[12]、链式受控非操作[16]、KCCC操作[18].第二种AQS协议又可以分为可以抵抗存在性伪造攻击和不可以抵抗存在性伪造攻击的协议.其中在基于QOTP的AQS[12-16]中,由于其一个比特对应一个比特的加密方式,签名者能够执行抵赖攻击且接收者在已知信息环境下可以执行存在性伪造攻击,基于KCCC算法的改进的AQS协议[18]可以较优地抵抗这两类攻击.相比于第二种信息传输方式,基于纠缠的量子隐形传输方式具有如下特性：第一,在传输过程中具有防窃听功能,即一旦有窃听者想要窃听信息,测量引起的扰动会被诚实的参与者发现;第二,可以避免传输载体本身,只是转移粒子所处的量子状态;第三,不受物理距离的限制,普通的加密方式仅限在地区性的网络上.因此,应用基于量子游走的隐形传输转移信息副本和KCCC算法执行中间过程的加密传输,本文提出一种新型的AQS协议.

量子游走是经典游走的量子对应.1993年,Aharonov等[22]初次提出量子游走模型.量子游走在多个方面展示了有意义的应用(详见综述文献[23,24]),其中量子游走在通信协议方面的应用[25-27]也开始暂露头角.例如,近两年,Wang等[25]和Shang等[26]提出了量子游走的不同模型在隐形传输的成功应用,文中指出必要的纠缠态无需提前制备,它们可以在量子游走的第一步之后被制备(相对于纠缠态的难以制备,这是一种很大的改进).而且,作者给出了一维量子游走的实现线路图.由于量子游走已经被证明可以在多种不同的物理系统和实验上实现[28-30],将其应用在量子通信协议中是有益的.

因此,本文通过将基于量子游走的隐形传输方式应用在AQS方案中传输信息副本,提出了基于量子游走的AQS方案.提出的方案具有以下优势：1)纠缠态不必提前制备,量子游走的第一步会产生信息传输必需的纠缠态;2)KCCC操作和随机数的应用可以抵抗已有AQS方案中的抵赖和存在性伪造攻击,本方案满足不可抵赖、不可伪造和不可否认特性;3)由于量子游走已经被证明可以通过现有的光学元素实现,提出的AQS方案实验上也许是可实现的.

本文的结构如下：第2节描述基于图的量子游走;第3节提出基于量子游走的AQS算法;第4节对提出的AQS算法给出安全性分析、讨论以及比较;第5节为结论.

2 基于图的量子游走

图上基于硬币的量子游走模型的定义由Aharonov等[31]给出.已知G=(V,E)为一个图,V代表G的顶点集,E代表G的边集.对于规则图形,图中的每个顶点具有相同的邻居,其希尔伯特(Hilbert)空间可以表述为位置空间和硬币空间的张量积,即

其中Hv是顶点态|v〉张成的Hilbert位置空间,其中v∈V.在每一个顶点j,有d条有向边连接到其他的顶点,Hc是边态|c〉张成的Hilbert硬币空间,其中c ∈{0,···,d-1},它们用来标记有向边.位置空间Hv和硬币空间Hc之间的条件移算符可以表示为

其中标签c指示游走者从顶点j游走到顶点k.

考虑一个包含l(l=4)个顶点的图(环),如图1所示,顶点标记为0,1,2,3,构成量子游走的位置空间为在每个顶点有两条边,它们的标记分别为0和1,构成量子游走的硬币空间为其条件移算符为

其中k代表环中的顶点.环上的相移规则见图1.

图1 具有四个顶点的环及其相移规则Fig.1.Shift regulations on a cycle with four vertexes.

3 基于量子游走的量子签名算法

本AQS算法中,Alice是信息的发送者和签名者,Bob是签名后信息的接收者和验证者,Charlie是值得Alice和Bob信任的第三方仲裁.对于一个安全量子签名算法[2],它应该遵循Alice对签名后的信息和签名的不可抵赖、任何人对Alice签名的不可伪造和Bob对接收到的签名信息或文件的不可否认特性.

3.1 初始化阶段

1)密钥制备和分发：Alice和Charlie制备共享密钥Ka,Bob和Charlie制备共享密钥Kb,Ka和Kb分别记为

2)系统配置：当Alice和Bob需要通信时,Alice或Bob向Charlie申请通信.

3.2 签名阶段

其中|φi〉(i=1,2,···,n)代表一个单量子比特,记为

2)Alice选择一个随机数r,并用其变换|φ〉为秘密的信息序列|φ′〉,可记为

3)应用Zhang等[18]提出的KCCC算法,Alice使用密钥Ka生成量子态|Sa〉,记为

其中EK代表改进的链式受控非加密操作,包含两步操作：第一步使用受控非操作加密|φ′〉,第二步使用二进制密钥控制的HadamardH门执行操作,当二进制密钥为0,H门执行单位矩阵I操作,反之,执行H门操作.EK′代表KCCC加密操作,关键点是引进了受控的转换操作,用以重组签名态中的量子比特位置,来规避QOTP中一个比特对应一个比特的加密方式引起的可能的抵赖和存在性伪造攻击[13,18].这个KCCC算法在文献[18]中已详细介绍,这里将不再赘述.

4)为了继续签名过程,考虑四个顶点的环上的基于两个硬币的量子游走模型,其线路原理图如图2所示.作用在位置和硬币空间的条件相移算符Tcircle重写如下：

Alice持有两个粒子A1和A2,硬币1的态编码在A1,位置态编码在A2.Bob拥有一个粒子B,硬币2的态编码在B.A1,A2和B的初始态分别为则游走系统的总初始态为

量子游走第一步的幺正演化操作符为

图2 两个硬币的环上的量子游走线路原理图Fig.2.Circuit diagram of quantum walks on cycles with two coins.

这一步使得位置空间和硬币空间产生了纠缠,即Alice和Bob之间有了纠缠.量子游走第二步演化算符为

我国职前体育教师在实习阶段大多只关注如何组织好体育课堂，鲜有参与其他活动。悉尼大学根据教师的终身专业发展需求，为实习生设定任务，在实习阶段要参与一部分班主任工作，契合了其培养全科型教师的目标。目前我国培养中小学教师还是采取明确学科分类的培养方式，教师往往只关注与自身学科相关的教学任务，但目前国内越来越多的中小学要求体育教师承担“副班主任”工作，这就对职前体育教师的能力提出了新要求。跳出单一学科的限定，丰富实习内容，可以激发职前体育教师突破自身专业限制，对各种影响教学过程的因素给予充分的关注，从不同的视角观察教育教学问题，促进教师专业化与综合化的发展，更好地迎合社会需求。

有必要提到的是对于本文系统量子态的表达,其所有的粒子是按照A2,A1与B粒子的顺序书写.

6)Alice 发送|S〉=(|Ma〉,|Sa〉)以 及信息|φ′〉的一个副本给Bob.

3.3 验证阶段

1)Bob通过KCCC加密算法应用密钥Kb加密得到

然后Bob传输|Yb〉给Charlie.

2)Charlie使用密钥Kb解密接收到的|Yb〉,得到|Sa〉和|φ′〉.接着 Charlie 用密钥Ka加密|φ′〉,获得|Sc〉.为了判断|Sa〉和|Sc〉是否连续,Charlie设计了验证参数t,

其 中|Sc〉和|Sa〉分 别 从|φ′〉和|Yb〉得到.接着Charlie应用KCCC加密算法使用密钥Kb加密|Sa〉,|φ′〉和t,生成|Ycb〉,

将其传输给Bob.

3)Bob使用密钥Kb解密接收到的|Ycb〉,得到|Sa〉,|φ′〉和t.基于t的值,Bob进行第一轮验证：如果t=0,签名也许被伪造,Bob立即拒绝来自Alice的信息|φ〉;如果t=1,它仅仅说明量子态|Sa〉是连续的,需要进行第二轮的验证.

4)在t=1 的情况下,首先Bob需要恢复出密文信息序列,然后与原密文信息序列|φ′〉进行比较.由于量子游走的第一步之后使得位置空间和硬币空间之间具有纠缠,Alice对位置和硬币1的测量使得传输的信息坍塌在Bob的硬币2上.基于Alice的A1和A2的测量结果Ma,Bob执行相应的泡利操作在硬币2,如表1所列.Bob的测量基表示为

如果|φ′〉/=|φ′out〉,B ob拒绝|φ′〉并放弃这次通信.否则,Bob发布一个请求Alice公布随机数r的通知.

根据表1,例如,基于Alice的位置和硬币1的测量结果Ma,Bob可以得到|φ′out〉.其相应的变换规则为：测量结果0与2分别对应于A2的|0〉与|2〉,测量结果1与—1分别对应于A1的|+〉与|-〉.假设Alice应用测量基|2〉在粒子A2,并得到测量结果为2,A1和B之间的纠缠态为

然后当Alice对粒子A1选择测量基|+〉,即测量结果对应为1,可以看到Bob应用单位矩阵I在硬币 2 得到,即|φ′out〉=|φ′〉.然而当Alice对A1应用测量基|-〉,Bob得到|φ′out〉为根据表1,Bob应用泡利Z操作在得到变换后结果为即其他两种情况可以类似的得到验证.因此,倘若密文信息序列|φ′〉中的n个量子比特都可以得到验证,那么确定Alice执行的签名是有效的,密文信息|φ′〉是完整且真实的.

表1 测量结果与对应的恢复操作Table 1.Measurement outcomes and the corresponding recovery operations.

5)Alice通过公共板公布r.

6)Bob使用r从|φ′〉恢复 | φ〉 并确认(|Sa〉,r)为Alice的信息序列|φ〉的签名.本AQS算法的方案原理图如图3所示.

4 安全性分析

首先,我们重述仲裁Charlie在所提出的签名算法中所起的作用.在初始化阶段,Charlie和Alice (Bob)通过量子密钥分发系统制作准备并分配了秘密钥Ka(Kb);在验证阶段,Charlie创造了验证参数t,用以判断量子态|Sa〉和|Sc〉的连续性,这一步骤有效地辅助Bob完成两轮的验证,如步骤3)和4).然后,基于一个签名算法的安全性规则,我们对提出的签名算法从不可抵赖、不可伪造与不可否认三个方面给出相应的安全性分析、讨论以及与已有典型AQS协议的比较.在这个过程中,我们说Charlie是绝对安全且值得信任的.

4.1 不可抵赖性

Alice不可抵赖自己完成的签名.从(9)式可以看到,量子态|Sa〉是通过Ka加密|φ′〉得 到,即其中Ka是 Alice和Charlie通过无条件安全的量子密钥分发系统制备.如果Alice抵赖了|Sa〉并因此与Bob陷入了纠纷,此时通过传输|Sa〉给Charlie.如果Charlie判定接收到的|Sa〉中 有Ka,则|Sa〉一定由 Alice 创造;否则,它也许被叛变的Bob或外部攻击者伪造.

而且,Alice抵赖|Sa〉的概率可以被量化.Alice对|Sa〉有抵赖或接受两种可能,因此Alice抵赖和接受的概率分别是1/2,将抵赖和接受看作二分变量.假设|Sa〉中的n个量子比特有m个被抵赖,那么Alice抵赖签名的概率为

其中

图3 签名方案原理图(QKD代表量子密钥分发)Fig.3.Schematic of the suggested arbitrated quantum signature scheme.QKD is short for quantum key distribution.

如图4所示,图中呈现了n=50,100,150 三种情况,横轴表示被抵赖的量子比特数m,纵轴为Alice抵赖m个量子比特的概率Pdisavowal(m),可以发现随着n值变大,抵赖概率的最大值在变小,可以推断当n非常大时,Alice抵赖的概率可以非常小或接近0.这时假定抵赖概率阈值为Pthreshold,我们规定如果Pdisavowal(m)小 于Pthreshold,认为不存在抵赖行为,否则认为有抵赖行为存在.当n是确定的,抵赖概率阈值可以选择为抵赖概率的平均值,即

图4n=50,100,150三种情况下Alice成功抵赖签名的概率Pdisavowal(m)Fig.4.Alice's disavowal probabilityPdisavowal(m)as a function of the amountmof the disavowed qubit in the signature state|Sa〉for the respectiven=50,n=100 and n=150.

4.2 不可伪造性

任何人无法伪造Alice的签名量子态|Sa〉.如果Bob是一个叛徒,他想要伪造|Sa〉.假设Bob成功伪造了|Sa〉,那他一定知道了生成|Sa〉的 元素Ka和|φ′〉.然而,获取这些元素对于Bob来说是不可能的.原因是Ka是Alice和Charlie通过量子密钥分发系统制备和分配的,它具有无条件安全性,Bob无法获取Ka,则Bob也就无法成功伪造正确的|Sa〉.不正确的|Sa〉在验证阶段将被Charlie检测得到t=0 .因此,在Charlie的辅助验证下,Bob无法伪造正确的|Sa〉.

任何外部的攻击者也一定是不可能成功伪造签名|Sa〉的.对于外部攻击者来说,在本算法中暴露的 参数是|S〉,|Sa〉,|Yb〉和|Ycb〉,它 们 均 通过KCCC[18]加密得到,具有很高的安全性.前面我们已经分析内部参与者Bob是不可能伪造出正确的|Sa〉,且推断外部的攻击者也一定是不可能的,也就是说,无条件安全的量子密钥分发以及高安全性的加密算法确保了本方案的安全性.因此内部参与者和外部潜在的攻击者都不能成功变造Alice的签名|Sa〉.

4.3 不可否认性

在提出的AQS算法中,Bob无法否认收到Alice的签名|Sa〉以 及信息|φ〉,即包含Alice签名的信息或文件.Charlie的存在使得Bob的否认攻击策略是不可能的,这种情况和Alice不可抵赖的情况是类似的.即使通过签名方案减少对Charlie的依赖,这个特性仍然是满足的.在验证阶段的第一步,Bob传输|Yb〉给Alice而不是Charlie.然后Alice实现新的签名|S′〉,即

随后将|S′〉传送给Charlie.在验证阶段的第二步Charlie制备新的|Ycb〉,即

这时可以看到|S′〉包 含Alice的密钥Ka和Bob的密钥Kb.一旦Bob想要否认,Charlie如果检测到|S′〉中 包含Kb,则Bob一定接收到了包含Alice签名的文件或信息.因此Bob是不可能成功否认接收到的Alice的文件或消息.

4.4 讨 论

根据Gao等[13]对AQS算法的密码学分析,讨论本方案是否可抵抗Alice的抵赖攻击以及Bob的存在性伪造攻击.例如在验证阶段的第二步,在Charlie完成判断之后,Charlie传输给Bob.此时,Alice有时机去修改签名态|Sa〉产 生使得它不再是信息序列|φ〉的有效签名.由于所使用的KCCC算法的特点,这种修改是无法成功的,Alice不再像QOTP算法中一样可以准确获取签名量子态中量子比特的位置和顺序.因此,KCCC算法在AQS中的使用可以规避此类攻击.

此外,Bob也是无法成功实现已知有效的签名信息对下的存在性伪造攻击.这种攻击是假如Bob拥有一个有效的信息签名对 (|φ〉,|Sa〉),他执行n次泡利操作(I,X,Y,Z)在|φ〉中的量子比特,同时相同的操作执行在|Sa〉的后n个量子比特,得到的新的信息签名对称为是一个成功的伪造,其中每一个泡利操作是四个泡利操作I,X,Y,Z之一,Bob至少可以实现 4n-1 种伪造,他可以选择对自己利益最大化的信息声称是Alice签的.这时Charlie总会站在Bob这边.然而由于KCCC加密算法的应用,这种攻击是不可能的.首先需要明确的是在Bob接收Alice的签名之前是不可能的,原因是信息序列是以密文|φ′〉的形式存在,在完成验证之后,Bob才可以通过公布的随机数获取原始信息序列|φ〉.在验证阶段之后,仍然是不可能的,因为Bob无法准确获取签名态中量子比特的准确位置和顺序,则Bob无法执行等效的操作在有效的信息签名对,无法成功获取签名|Sa〉的伪造.

4.5 比 较

基于量子游走隐形传输模型、KCCC操作、随机数以及公共板的应用,本文提出了一种目前较好的一种AQS方案.我们将其与已存在的几种典型的AQS协议进行比较,如表2所列：根据所使用的量子资源、信息副本的传输方式、加解密操作、Alice的抵赖攻击是否成功以及Bob的存在性伪造攻击是否成功进行对比.可以看到信息副本的传输方式分为三种：基于纠缠态的隐形传输[2,11,14,16],普通量子加密方式[12]以及本协议的基于量子游走不需要提前准备纠缠态的隐形传输方式.对于采用QOTP算法或者改进的QOTP的AQS协议,均不能抵抗Alice的抵赖攻击和Bob的存在性伪造攻击,这个现象在文献[13]中已做了分析,他们展示抵赖或伪造攻击成功的原因是QOTP加密的方式是一个比特对应一个比特,量子比特的位置和顺序在基于QOTP的AQS协议中是确定的,攻击者可以找到相应的量子比特位置并执行泡利操作对其修改.文献[16]中提出的采用受控非代替QOTP,仍然不能抵抗Bob的伪造攻击[18],幸运的是受控非修改了量子签名中的量子比特使其之间互相关联,可以有效防止Alice的抵赖攻击.本方案使用Zhang等[18]提出的KCCC操作作为中间量子态传输的加解密方法,使用量子游走隐形传输模型[25,26]传输信息副本,本协议具有文献[18]的所有优势.此外,相比于普通的量子加密方式,基于量子游走的隐形传输具有如下优势：第一,不需要传输载体粒子本身,传输的是粒子所处的量子状态;第二,没有物理限制,便于扩展传输距离,量子加密仅限在地区性的网络上,量子中继器还不存在;第三,由于纠缠的存在在传输过程中具有防窃听功能,即一旦有窃听者想要窃听信息,测量引起的扰动会被诚实的参与者发现.相比于普通的量子隐形传输,基于量子游走的隐形传输不需要提前制备纠缠态,必要的纠缠态可以在量子游走的第一步自动产生.此外,从通信效率来说,相比于典型的文献[2]和文献[11],本方案的验证阶段的第一步不需要传输测量基Mb,所以本方案的通信效率更高,通信负担更小.因此,本AQS方案目前来讲是较优的.

表2 协议比较Table 2.Protocols comparison.

5 结 论

本文设计了基于环上两个硬币的量子游走的AQS算法.不同于已有的AQS协议,在初始化阶段不需要制备纠缠态,而是在签名阶段量子游走的第一步产生Alice和Bob之间的纠缠态.基于量子游走的量子隐形传输模型,两步游走之后,Alice应用测量基|0〉,|2〉和|+〉,|-〉在自己的量子态,由于Alice和Bob之间纠缠的存在,Alice的测量使得传输信息塌陷在Bob的量子态.Bob执行相应的泡利操作恢复信息,进而验证签名的有效性以及信息的完整性和真实性.由于KCCC算法的使用,本算法满足签名方案的安全性规则.目前,Xue等[32]在实验上已成功证实了量子游走可以应用于量子通信,且量子游走在一维空间已经做到20步以上.所以,基于当前的技术,实现本文提出的AQS协议是切实可行的.