（计算机应用技术专业论文）量子信息论中的密码协议与算法研究.pdf

硕士学位论文：量子信息论中的密码协议与算法研究 摘要 量子信息科学是物理科学与信息科学交叉融合产生的新兴学科领 域。该学科以量子力学的基本原理为基础，主要研究量子信息处理，包 括量子计算机、量子通信、量子密钥分配等几个方面。将量子系统的特 性应用到信息领域中，可以在许多方面突破经典信息理论的极限，实现 经典信息处理难以想象的功能，如大数因子分解、绝对安全的密码分配 等。 量子密码学作为量子信息理论的一个重要方面，它利用量子力学的 一些奇特性质，突破了传统密码学的限制，能够绝对安全地传送信息。 近些年来，量子密钥分配在自由空间和光纤的实验中都取得了显著的进 展。本文总结了各种量子密钥分配协议，分析了它们的安全性，量子密 钥分配是后面进行量子签名方案的直接理论基础之一。 数字签名在现实生活中是一个重要的问题，然而经典的各种签名方 案都是基于各种数学难解问题的，它们都不能提供绝对的安全，本文总 结了现有的各种数字签名方案，分析了它们的缺点，在此基础上，本文 提出一种基于量子密码术的可消息自动恢复的签名方案，它能提供可证 明的安全。最后，本文结合量子密码分配协议( b b 8 4 协议) 和量子签名 方案的原理，提出了一个具体的量子签名方案的实现设计思路，并画出 了主要的流程图，并对下一步工作进行了展望。 关键词：量子信息；量子密码术；量子密钥分发；量子签名方案 颟士学位论文：鲎：信息论中的密确协议与算法研究 a b s t r a c t t h ec o m b i n a t i o no fq u a n t u mm e c h a n i c sa n dc l a s s i c a li n f o r m a t i o n t h e o r yy i e l d s t h en e ws u b j e c to fq u a n t u mi n f o r m a t i o n t h e o r y 。q u a n t u m m e c h a n i c si st h ef o u n d a t i o no fq u a n t u mi n f o r m a t i o n ，w h i c hp r i m a r i l ys t u d y q u a n t u mi n f o r m a t i o np r o c e s s i n g ，i n c l u d i n gq u a n t u mc o m p u t e r ，q u a n t u m c o m m u n i c a t i o na n d q u a n t u mk e y d i s t r i b u t i o n w h e nw e a p p l i e d t h e p r o p e r t i e s o f q u a n t u m m e c h a n i c st o i n f o r m a t i o n ，c l a s s i c a l l i m i to f i n f o r m a t i o n t h e o r yc o u l db ee x c e e d e di nm a n yw a y s ，a n dw e c a na c c o m p l i s h m a n yu n i m a g i n a b l et a s k sf o rc l a s s i c a li n f o r m a t i o np r o c e s s i n g ，s u c ha sf a s t f a c t o r i n g ，a b s o l u t e l ys e c u r ec r y p t o g r a p h e t c 。 q u a n t u mc r y p t o g r a p h y i sa n i m p o r t a n ta p p l i c a t i o n o f q u a n t u m i n f o r m a t i o n u s i n g t h em i r a c u l o u s p r o p e r t i e s o f q u a n t u m m e c h a n i c s e u a n t u mc r y p t o g r a p h yb r e a k st h o u g h tt h ec o n f i n e so f c l a s s i c a le n c r y p t i o n a n dc a nm a k eo u rc o m m u n i c a t i o n sp e r f e c t l ys e c u r e i nt h e p a s ts e v e r a l y e a r s ，t h e r e h a sb e e ns i g n i f i c a n tp r o g r e s si n q u a n t u mk e yd i s t r i b u t i o n ( q k d ) m a n yq k de x p e r i m e n t s h a v eb e e ns u c c e s s f u l l yd e m o n s t r a t e di nt h e f r e es p a c ea n di nt h eo p t i c a lf i b e r 。i nt h ep a p e r ，a l lk i n d so fq k d sh a v e b e e ns u m m a r i z e da n dt h e i rs e c u r i t yh a v eb e e nd i s c u s s e d a l lc l a s s i cs i g n a t u r es c h e m e sa r eb a s e do ns o m ec o m p l e xp r o b l e m s ， s ot h e yc a nn o tp r o v i d ea b s o l u t es e c u r i t y i nt h ep a p e r ，an e ws i g n a t u r e s c h e m eb a s e do nq u a n t u mc r y p t o g r a p h yh a sb e e np r o p o s e da n dt h es c h e m e i s p r o v a b l e s e c u r e t h es c h e m eu s e s ap u b l i cb o a r da n dc a nr e c o v e r y m e s s a g e ，p r o v i d e sc o n f i d e n t i a l i t yo f t h em e s s a g ea n da h i g h e re f f i c i e n c yi n t r a n s m i s s i o n f i n a l l yat h o u g h to f s o f t w a r ed e s i g no nt h eq u a n t u ms i g n a t u r e s c h e m eh a sb e e np r o v i d e da n dm a i nf l o wc h a r t sh a v eb e e nd r a w n k e yw o r d ：q u a n t u mi n f o r m a t i o n ；q u a n t u mc r y p t o g r a p h y ；q u a n t u mk e y d i s t r i b u t i o n ；q u a n t u ms i g n a t u r e s c h e m e 独剑性声明 本人声明所呈交的学位论文是本人在导师指姆下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表戡撰写过的研究成栗，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同恚对本研究所骰的任何贡献均滋在论文中作了翡 确的说明并表示谢意。 签名：叠塑鏖日期：j p 舛年2 月助日 关于论文使用授权的说明 本学霞谂文俸耋完全了解毫予秘技大学有关绦整、使震学馒论文 的规定，有权保留并向国家有关部门溅机构送交论文的复印件和磁 盘，允许论文被套阕和借隧。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守忿规定) 签鬣：窿壶，塞导辩签名：盥 日期：2 0 0 4 - 年2 月卫d 曰 硕士学位论文；量子惯息论中的密码协议与算法研究 1 。1 弓l 富 第章绪论 量子力学鞠狭义摆对谂、广义相慰论一起被穆为二卡世纪物理学最 伟大的三大发现。根据摩尔定律，经舆计算机在未来十年左右就会遭遇 极限，阍题蟊德解决? 麓掌家稍掇密翡麓子计算辊就是解浃方法之一( 萁 它有光子计算机、d n a 生物计算机等) ，量子计算机具有强大的计算能 力，如莱拥有艇子计算机将使现有的公钥加密系统失去保密功能。而利 用量子态不可囊隆艨理，可吐实现保密通信。 量子密钥学( q u a n t u mc r y p t o g r a p h y ) 是量子信息领域中的一个重 要熬分支，其中量子密镑分配( q u a n t u mk e yd i s t r i b u t i o n ，q k d ) 方案 将密铜信息编码在量子态中，由于量子的不可分性，窃听者( e v e ) 不能 对传输中的量子密锯进行分流；又由予量子菲克陵性( n o c l o n i n g ) 定理， e v e 也无法对传输中的密钢进行拷贝。更具体面言，量子密钥分配方寨 在原理上采用单个光子，根据海森堡测不准原理，测量邀一量子系统会 黠该系绞的状态产生不可逆转毂于携( 波龟麴坍缝 ，褰褥者疑艟撂到熬 只是该系统测嫩前状态的部分信息，遗一干扰必然会对合法的通信双方 之闻豹邋信造成差镑。逶遥这一蒺错，a l i c e 与b o b 不仅能察觉密潜在 的窃听者，而且可估算出窃听者截获信息的最大信息量，并由此通过传 统的信息技术提取无差错的密钥。 量子密码举的起源是1 9 7 0 年提出瓣“量子货零”方寨【2 j 。1 9 8 4 每， 第一个量子密钥分配方案幽b e n n e t t 与b r a s s u d 提出，这一方案又被称为 b b 8 4 蛰议 3 】。1 9 9 1 年，e k e r t 鬟遗了一令使弼e p r 鲻缝粒子对豹q k d 方案e 9 1 协议 4 】，其安全性基于b e l l 不等式。1 9 9 2 年由b e r n e t t 提出的 更简单，但效率减半的b 9 2 协议p i 。 1 2 国际国内研究状况和进麓 量予通讯怒传统通讯理论和最子力学相结合的产物。为了把量子通 讯推向实爆，蠢很多理论的和实验的耀题僮得探索。近几年量予密码术 又获得了许多新的进展除了量子密钥分发“3 ，还有量子秘密共享“，量 硪士学位论文：量予信惠论中的密码协议与算法研梵 予位承落 1 1 - 12 量子鉴剐方案“”“1 和量子签名方案”。”3 等等。尤其是量子密 锈分发在瑾论嚣实毅室工程中邑经竣验证惫缝对安全戆“7 1 “。绝霹安全 的量子密码将最先魄用于军事、国家安全等领域，并成为各国科学家角 逐的新战场。目前在技术上遇到的主要困难是：如何增加量子密钥传输 距离。有祷突破的藏要关键技术： 怒红矫( 1 + 3 微米、1 5 徽凑) 单光子搽溺器。这燕因为光纾爨子 密钥传输是采用单个光子来实现的，光纤损耗阻碍着传输距离的提商， l 。3 微米牺1 5 微米是现在所使用的光纤损糕最小的波长，现有成熟的单 光子搽涎器王侔波长在可觅巍，灌论上巍予在先纾中镄浚静辍疆距胬缝 为2 0 公里。因此实阁的红外单光子计数器成为关键性问题。 二怒单光子光源，现在量子密码研究中所使用的单光子光源是将相 干光辣潆衰减到平均每个歇挣只蠢0 + 1 、0 。2 令光子，逛是一耱返锹懿 单光予源，其效率低，既影嫡激子密钥的佟输距离，又影响其安全性， 因为这种光源有可熊在一个脉冲中同时出现两个光予。因此研制真窳的 单光予源成为量子密码研究的男一个关键性问题。 蠢予在壳纤终输遥程孛，光子缀容荔潦耗，强蔻豢予密鹳还其魏在 短距离内传输。一旦这个瓶颈被突破，量予密码将迎来大发展。科学家 们表示，保密与窃密就像矛与膳一样形影相随，它们之间的斗争已缀持 续了凡千年，量子蜜褥兹出毽，壤藏走这场斗争豹终缝嚣。美国、瓣本、 西欧正在大力开展这些关键技术的研究，最近在自然、科学上也 报导了一些重要进展，过去的2 0 年中量子密钥通讯在理论和实验上都取 得了飞速的进展，现在量子密钥通讯已经成为量子信息中最旱褥到殿赐 的领域。 2 0 0 2 年l o 月，德国慕尼黑大学和英国军方的研究机构合作，在德 国、奥地剁边境的楚格峰和卡尔文的峰之间用激光成功传输了量子磷码。 这褒磷究静受蠢人蒸霪黑大学教授埝拉尔穗囔霹富尔黪在投告审袭示， 这次试验传输的躐离达到了2 3 4 公里。 2 0 0 3 年5 月，日本的科学家称他们开发出传输速度最快的量子密码， 实验中，礤究小组利用1 0 5 公灏长鲍光缓滋行售号传递，接收一方禳党 子探测器降低干扰，大幅缩短了传送时闻，使褥通信辩闯缩短到嚣来的 1 1 0 0 。 中国也在近几年展开了量子保密通信系统的研究。2 0 0 3 年7 月，中 藿释蔽大学中辩夔爨子整怠重点实验室熬瓣学家在该棱蔽功镶设一条总 硬士学位论文：爨予信息论中麴整妈协议与算法研究 长为3 。2 公量豹“特豫光缆”一一套鏊子鏊子密弱翡保密_ i 罄信系统。 2 0 0 4 年6 月3 尽，由美溺b b n 公司组建豹毯爨上篱一个鲎子蜜鹈 邋售网络在美国马萨谴塞燃戮掭城正式投入运孳亍【叭。 3 本豫题的研究意义鞠内容 本论文主要避行麴工俘愚对爨子分瑟绥议懿安全瞧俘了懑步魏澜 述，对量子密码中的撼子签名方案进行了研究，提出瓤的爨子签名方案， 并设计了实现模型。旦实用的凝子通信网络建立起来后，绝对安全的 量子熊名就可在上面进行了，这对国家、企业及个人信息安全都非常熏 要。翼体地，各章内容如下： 笫= 章，对鬓予力学籁豢子倍感论魏蛰基本概念秘愿瑾避彳亍了介 缓，为悉覆静分帮彳帮磷究箍供基磷。 第二章，对经典密褥学稳爱予密褥学迸孬了琵较，介缓了各耱董子 密钥分配方案，详细地分据了它们的安全性，量子分就方褰是磅究量子 签名方寨的直接基础之一。 第四章，分析了现有的量子签名方煮，掇出毅的攮予签名方察，分 析了其可行性和绝对安全性。 第五牵，结合量子分配协议b b 8 4 和量子签名原瑷，设计了鬣子签 名方案的实现模黧。 燕子计算视和量子密福术都还在不断发穗中，课题也有进一步研究 黪意义。 磺士学位论文：量予信息论中的密碣协议与算法研究 第二章量子力学和量子僖患论 量予力学和量子信息论是研究和讨论量子计算、堂予计算机、爨子 逶售葶瑟爨子密玛术以及量子签名方案等兹瓒埝基纂窭。这章蓄先讨论量 子力学然后讨论量子信息论。 2 1 量子力学原理 2 0 世纪初，狭义相对论、广义相对论和量子力学 6 】的建立深刻地改 变了人们对物理世界的认识和理解。世界在本质上是量予的，经典物理 学只爱燕子秘理学在宏鼹条 孛下瓣透经理论。( 场强宁添) 2 1 1 燕子和量予态 “鬟予( q u a n t u m ) ”一词意攘个量”或“一个离散躲量”。蓠单媳说 是光予、电子等徽溪粒子，j 葑阻有时又有光燕子、电羹予之说。 一个量子态是由某种实验测黛完全确定的系统的运动状态，它可以 用一些观测量的观测值来确定和标志。美国物理学家d i r a c 用右矢“i ” 表示，蒸孛焉一些字母或数藿撵臻萁特蔹，翔 g l 西，l r ) ，| 妒，。 2 1 2 微观粒子的波粒二象性 渡趣二象注燕缀残蓬爨懿鏊本特睦，光瓣蘩射、予涉帮镶摄等试验 证明了光的波动性，可以用波长、频率和偏振方向来描述，满足电磁场 的波动方程。而黑体辐射、光电效应、c o m p t o n 散射以及正负电子偶的 产生和淡灭，又拣嘲光酶粒子性，可用动爨秘能量来攒述，满足动凝能 量守谶。阴极射线中的电子在磁场中偏转，在荧光孱上产生竞点，寝鳃 电子魑一种粒子，具有电荷和质量，可用能艟和动量来描述，满足动量 能量守恒，另一方骶，电子的衍射和干涉现象，又证实了电子的波动性， 满足簿邂谔波凄方程。任餐锈髂都斧夔羞渡，两盈镌体懿运动窝浚酌传 播是不可分割的。嶷物粒子的能量和动量与光子相同。 e = h v 硕士学位论文：蹙予信息论中翦密粥协议与算法研究 哥= 当蓐 ( 2 一1 ) 2 露 其中k 是波矢最。这种波被称为德布罗意波。 2 1 3 波函数的统计诠释 在宏观物理中，原因与络桑之间一定可以找到鹗确肯定的关系，这 被称麓拉普拉斯决定论。然而在微观世界中，量子力学所表述的物理规 律是统计性的，在原因和结果之间不再能绘出明确肯定的联系，只是对 一定豹镪建条 孛，能预言可潋溅弱臻些结莱，隘及溯剿每耱翡糕率是 多少。一切微观粒子都具有波动性，这种波1 9 2 6 年玻尔给出了物腧波的 正确解释，物质波并不代表实际物理量的波动，而只怒描述粒子擞间分 毒的撅率渡。它的波场强度与擞溪粒子整瑷的援率成囊毙。茳量予力学 中，为了解决随机性和干涉之间的问题，就采用了概率幅来解释。矢态 用定义在某个区域q 上的平方可积复函数袭示，称为矢态的坐标裁蒙。 在坐标表象中，赢接用这个平方可积复醋数表示态矢爨。在单粒予系统 中，这令函数可以记为国，x 是粒子鹣辍标，妒掇述了与粒予稷俘 的物质波，因此又被称为波函数。那么粒子猩单位体积d f 中出现的概率： p = q 矿纠2 d f ( 2 - ” 其中c 是常数。 在非相对论的量子力学中，粒子在空间出现的概率为1 ，所以有 心眵嗣2 d f = 】 ( 2 3 ) 这就熄波函数的归一化条件。 2 ， 。4 量子态叠翔原理 在量子世界中，微观粒子的状态是不可确定的，它可以同时以不同 的概率处于多个状态，一旦进行测量，它的状态就会塌陷到一个确定的 状态。曩子态浚爨y 黧定理是诞，翅雯一个量予系统爨蠢态l a 秘淼l 嚣) 嚣 种可能的量子态，则它们的畿加态 l r ) = q 1 4 ) + c ：l b ) ( 2 - 4 ) 瞧是系统的霹熊态，其中l e ， 2 + l c 2 1 2 一l ，在没有受到外雾於二f 挽( 如 硕士学位论文：羹予信息论串的密码协议与算法研究 测量) 的情况下，这中叠加关系保持不变。如果进行测嫩，则以i c l l 2 的 凝率褥劐| a ) ，鼓| 。2 1 2 戆概率褥到 磅。 量子态的叠加肖以下性质： ( 1 ) 两个相同恣的叠加仍然是原来的态。 ( 2 ) 如果只有o l = 。2 = 0 孵，君有 q i a ) + c 2 雪= o ( 2 5 ) 则l a ) 和l 功是系统的特征态。 ( 3 ) 如果态 r ) 上有态l a ) 和态l 矗) 测量不到的结果，则态l r ) 中至少还 有一个态 c 。 ( 4 ) 推而广之，如果一个系统有n 个特征态l 丸) 、1 唬) 、阮。) ，则鼹加 态 n - i | ) = 彤。| 疵+ 搿，| 磊) + 。，出。一， 痧。一；= 蛾| 破) ( 2 6 ) j = o 也怒该系统的个可能态，其中 。 2 十lc o 1 2 + + l 瑚。| 2 = 1 ，即系统 以l 甜，1 2 的概率处于状态l 或) ，( i = 0 ，l ，h 一1 ) 。 2 1 5 海森堡测举准原理 由于波动性，微观粒子的搬标和动量不能同时测到确定值，测不准 蘸理楚徽鼹越予鹣阑毒毪反，与测量仪器戆耱凄无关，这就是海森爨溺 不准原理，它是微观量子性的根源，是波函数的统计谂释的物理基础。 海森堡测不准原理及其推论量予态不可克隆原理是讨论量子密码术的理 论基磷之一，在爱蕊还要详细讨论它。在豢予诗冀理论中，每一个鼹测 量在数游土用“观测操作符”表示。观测搡俸符用h e r m i t i a n ) 矩阵攒述。 观测量的取值就是斌个矩阵的特征值。 如果对一个特定的观测茧a 进行测量，量子系统烛予状态l 矿 ，那 么 矽裁逶a 懿特征羧态，帮 j i y ) 麓d i 妒) ( 2 7 ) 萁孛，a 是实数。 西最另夕卜一个观铡量，则l 妒) 肯定不燕西的特征状态。因此要跫豢予 系统处于状态i ) 时测量百，每次测量都会得到不同的结果。用平均方差 来撼遴这些差裂。瓣予五寒谈，五) 表示对确定状态懿璧予系统进霹亍多次 遂主皇壁i ! 塞：爨于信息沧中转峦璐协议与算法研究 测量的平均值，则平均方差 颤= ( 五2 ) 一量2 沼8 ) 旗中，j 2 = j 囊 阉样， 妇= 0 ( 西2 ) 一( 雪) 2 ( 2 _ 9 ) 平均方差表示了观测量的不确定性范隰。当f 矽楚五的特征状态时， 每次测量的结果都是相同的，撕= o 。而1 妒) 不是五的特征状态，每次测 量都蠢波动，艿雾0 。 为了同时蕊测这两个甄测麓，橡造冀符陋，秀j ： 瞄，雪】= 五西一西j ( 2 1 0 ) 如果同时观测这两个观测摄，不确定性满足 矗互庙吾| ( 瞄，蜃】 ( 2 、1 1 ) 谴就是海森嬷不确定关系的普通表达，同时可以精确测出两个观测 量懿瞧一条l 牛就怒睛，豆】归约到一个全零鼹陈。 2 1 6 薛定谔方程 耱定谔方程怒爨子系统状态演化的基本规律，g g 计算系统测鬃概率 豹渡溺数豹规律，迸一步，它氇是董子计算杌逶嚣诗舞所遵循瓣簇本觏 律。当基予系统没有进行测量的时候，系缆遵循该规律进行持续的演变： 引6 ( t ) 3 i h l 土一嚣0 ) l ( 站 ( 2 - 1 2 ) 搿 其中，扛一1 ，a = 1 0 5 4 5 1 0 。4 j s ，疗( f ) 为h a m i l t o n i a n 冀予。 h a m i l t o n i a n 算子与特定的物理系统结构相关，决定着系统状态的演化。 在薛定谔方穰中计算的麓态矢量，瞧靛是概率堰，它不是一个物理 量，这是与经典物理学的一个报本区剐。在经典物理中，所有动力学方 程都怒描述物理擞= 变化规律的，而在量予力学中，切可观测的力学量 取值都是由概率幅的模的平方决定。如果h a m i l t o n i a n 算子与时间无关， 硕士学位论文：量子信息论中的密码协议与算法研究 并且系统的初始状态为揪o ) ) ，那么薛定谔方糯可以简化戚 | 8 ) = 8 “| f ) = 痧搴i o 努 ( 2 一1 3 ) 其中0 * e “”称为演化算子，它是一个幺正矩阵，满足 疗疗+ ：0 + 疗= ( d + 表示d 的共轭转置矩阵)( 2 - 1 4 ) 演德舞子豹幺纛瞧要求量子稼怠处理中夔逻骥操传必须羲牙幺歪演 算。由予幺正操作憨有逆操作存在，所以量予信息处理中的逻辑揉作都 是可逆的。 2 。2 量子壤塞论 在缀典计算机系统中，用0 和l 来表示储息，每一位数据要么魑0 ， 要么是1 ，决不会出现即是0 又怒1 的情形，健在量子计算桃中，一切 蒋交褥不孬籀同，豢予奉秀豹将往往褥诗舅髓力令人穰讶的强大。麓子 信息论是经典信息论和量子力学结合的产物。 2 。l 。l 量子位 一个艟子位( q u b i t ) 是定义在二维复向濑空间中的个单位向擞。 该空间由一对特定的标准正交基 1 0 ) ，1 1 ) 张成。这两个熬可分别对成光 子的水警线性偏振状态 书积l ，或对角线傣擐状态l 帮 ， 或麓转状态| 广) 和| 、) 。 为了达到量子计算的目的，分别用本征恣1 0 ) 和1 1 ) 对威经典位0 和1 进行编襁，但是量子位与经典恒不同，量子傲可以处在i 和1 1 1 的叠加状 态蠢蛰+ 躐1 ) ，萁孛8 黟矗表示复数，嚣显留+ | 瑷2 ：1 。渡下讨论时，豫嚣特 殊说明，都假定测量是基于标准蒸 1 1 ) o 虽然可以将量子位制备成一个叠加状态，但是一个掇子位也只能编 玛一个绞獒瓣整。扶弦惠论懿鼹点看，即使爨予经霹以楚无穷多令获态， 但是一个量子位和一个经典位所包含的信息爨是一样豹。之所以如此， 是因为只有通过测数才能读取包含在量子位中的信息。 由于测量会改变爨子的状态，因此不熊先用一个基测量它之鹾，又 霜另舞一个基去溅羹它，蘑量予怨是不麓毅巍隆( c l o n e ) 豹，这是濑子 信息与缀典信息的墩大不同，在经典的计算机系统中，对一个位的任意 测量都不会改变位的状态。 塑生鲎焦鲨塞! 墨量照，曼迨主盟查塑竣骥兰竺鲨堑塞 2 2 2 多量子位系统 一个量子位的状态是由i o ) 利1 ) 张成的二维复向量空间中的一个向量。 令v 和分别由基h ，v ： 和 w 1 ，w ： 张成的二维复向量空1 4 。这两个空间 的笛卡尔积形成一个新空间的基 v 1 ，v ：，w 。，w ： ，其中基的顺序是任意的。 对多粒子经典系统而言，其状态空间的维数与粒子的数目呈线性增长关 系，即 d i m ( x x y ) = d i m ( x ) + d i m ( y 1 ( 2 1 5 ) 其中表示笛卡尔积。 而v 和的张量积为h o ，v 】w 2 ，v ：o w l ，v ： w ：) ，其中基的顺序 也是任意的，因而对一个具有二量子位的系统而言，假设其量子位的基 为l o ) 利1 ) ，则该系统的基为o ) o l o ) ，l o ) o 协1 1 ) 。怫1 1 ) 。，为了方便可筒记为 0 0 ) ，o 圳l o ) ，1 1 1 ) j ，由此可推，具有三个量子位的系统的状态空间的基为： i o o o ，1 0 0 1 ) ，1 0 , o ， 0 1 i ) ，1 1 0 0 ，1 1 0 1 ) ， 1 1 0 ) ，1 1 1 1 ) ) 。一般来说，具有n 个量子位的系统， 其状态空间由2 “个基向量张成，量子系统的状态空间维数随粒子数的 增长成指数倍增长，即 d i m 固y ) = d i m 伍) xd i m ( y ) 其中 表示张量积。 关联态或纠缠态( e n t a n g l e ds t a t e s ) ：在多量子位系统中， 通过独立描述各个量子位的状态来描述整个量子系统的状态， 子系统处于关联态或纠缠态。 2 2 3 测量原理 ( 2 1 6 ) 如果不能 则称此量 波包的缩编：在测量过程中，测量仪器和被测量的系统之间会发生 某种相互作用。一般来说，会使系统的态发生改变，使得测量以后的态 与测量以前的态不同，设系统在测量之前处于态l 们，测量之后处于态 ) ，用m 来描述这种改变，有 i 丸) = 心1 妒) ( 2 - 1 7 ) 系统的态矢量在测量过程中发生的这种变化，称为波包的缩编或波 包从态到态) 的投影。具体来说，对量子系统中一个或多个粒子进 行测量，将会把量子系统的状态投射到与测量值相对应的状态子空间中 去，同时也会对投射的幅度进行缩放，结果矢态的长度为1 。测量的结 果出现的概率等于测量所用基的复系数模的平方和。 硕士学位论文：量子信息论中的密码协议与算法研究 两个量子组成的系统的状态可以表示为： 口l o o ) + 6 1 0 1 ) + c 1 1 0 ) + d 1 1 1 ) ( 2 - 18 ) 其中，a ，b ，c ，d 都是复系数，且 + i b l2 + h 2 + i d l 2 ：1 。 现在用基 怫1 1 ) 1 对该系统的第一个量子位进行测量，测量为1 0 ) 的 概率为i - 1 2 + l b l 2 ，此时系统的状态会投射到由1 0 0 ) j n 1 0 1 ) 张成的子空间上，投 射的结果为a 1 0 0 ) + h i 0 1 1 ，然后对其复系数进行归一化： 了南n l o o ) + 6 1 0 1 ) 婿+ 婿? ”r ? i ( 2 1 9 ) 通过测量，进一步理解了粒子的关联态( 或称纠缠态) ，如果对其 中任意一个粒子进行测量都不会影响另外一个粒子的状态，那么这两个 粒子之间不存在关联。 2 2 4 量子并行计算 2 2 4 1 经典算法复杂度 在经典计算中，算法就是一步一步地求解问题的通用程序。算法的 难易程度由算法复杂度衡量，算法复杂度取决于执行这个算法解决具体 问题消耗的物理资源多少。按经典算法复杂性理论，一个问题的大小可 以用一个整数n 表示，n 是指定这个问题需要输入的信息量的度量。假 设一个问题的大小是n ，解这一问题的最好算法需要的时间为t ( n ) ，如果 当n 增大时，t ( n ) 的增加始终不比n 的一个多项式函数增加更快，就称 这一算法是容易的；如果t ( n ) 随i 3 的增加而指数增加，就称这一算法是 难的。 例如，当输入位数l 的增加时，分解大数质因子和做两个大数乘法 所需计算时间显著不同。分解一个l 位数的质因子大约需要作n = 1 0 “2 次除法，执行这一算法所需计算时间随l 增加而指数上升，假如使用每 秒做1 0 0 亿次除法的超级计算机，分解一个2 0 位数大约需要1 秒，分解 一个3 4 位大约需要一年，而分解一个6 0 位数所需时间已超出现在估计 的宇宙年龄。然而两个6 0 位数相乘，用这样的计算机也只是瞬间的事。 一个难解问题，是指当具体问题增大时，所需的物理资源是如此之 多，以至对任何实际计算设备都是难以承受的。上面的分类不依赖于具 体计算设备，这一点由c h u r c h 定理保证：任何一个物理计算装置都可以 用经典图灵机来模拟。 磷士学位论文：爨予信息论中的密褐协渡与算法研究 2 2 4 2 量子算法 鬃子算法铡稻了量子力学豹诲多基本褥薤，翔穗子叠热毪、势李亍瞧、 关联批( 纠缠性) 、测量坍塌等，研究它们可以提高计簿效率，从而产生 了一种崭新的计算模式一一麓予算法【8 。 爨子计算枫数诗冀熊力大大超出经典嚣箕捉，饿翅设f 是定义域帮 值域鄱在自然数袋台中的函数，u 是一幺正变换，功撩是计算f 的函数 值，任意给定一自然数n ，有c ，i 一) = l ，( ”) ) ，由于量子态可以为相干叠加态 l 多) = 慨+ l 强+ ，+ l 辑) ( 2 2 0 ) ， 越中疗，冯，”，是r 个自然数，u 作用在该量子态，得到 ，眵) = ，如；凳+ l ，0 ：癸+ + l j ( - ，) ) ) ( 2 - 2 1 ) v ， 可以看到在炎换算子u 作用下，可以嗣时算出r 个函数值，邈就说 明量子计算机具有并行计算能力，比经典计算机计算能力强。 2 ，2 ，4 ，3 量子共簿计算 缀子计算机锻重要的优越性体现在量子并行计算上，一些经瓤计算 机上只存在指数算法的问题，利用量子计算机却存在缀予多项式算法。 最著名的一个铡予当接s h o r 农1 9 9 4 年给如蛉关予大数因子分解懿量子 多项式算法，s h o r 运雳数论中的一个定理，巧妙地将罨找个大数静因 子问题转换成寻找一个函数的周期问题，丽后者可以通过傅里叶变换在 频谱上很容易地究成，这就在詹子计算机上把难解问题转换为容易解的 闻趱( 虽然没霄证锈分解大鼗溪嚣予是燕鼹| 、藏蘧，毽一壹没我到瓣这一 问题缀典多项式算法，很多人相信它是难解的) 。s h o r 的高效率的量子 因式分解法可分解大数，它能在几秒内破译常规计算机“无法破译”的 密鼹，这一结采两r s a 公锈系统兹安全镶提爨严重援藏。旦量子计算 机研制成功，现有的公钥系统就失去了保密的作用。 1 9 9 6 年，o r o v e r 的数据脬搜索量子算法，是体现缀子计算机优越性 的另一个例子。在g r o v e r 算法中，n 个经典信息串可以以1 n 的几率幅 豹遥鸯鬟形式存敖在量子寄存器中，运行n 璧级步数豹变换，可以经簧寻 找的佰息串以几率幅l 表示出来，而经媳计算机执行相同的搜索则需要 n 量级的时间。逸一算法虽然没有改变问题的复杂度，但量子搜絮甚至 晓s h o r 分解霆子簿法还要莰褥多。 硕士学位论文：量子信息论中的密码协议与算法研究 2 2 5 量子态不可克隆定理 1 9 8 2 年w o o t t e r s 和z u r e k 在自然杂志上撰文提出如f 问越：是 否存在一种物理过程，实现对一个未知量子态的精确复制，使得每个复 制态与初始量子态完全相同呢? 他们提出，量子系统的任一未知量子态 在不遭破坏的前提下不可能被克隆到另一量子体系上，这就是量子态不 可克隆定理( q u a n t u mn o n c l o n i n g t h e o r e m ) 川。 证明1 ：以两态量子系统为例，其基矢选为l o ) 和1 1 ) 。设i s ) 代表此二 维空间任意量子态，量子克隆过程可表示为 l s ) l q ) ，- - , i s ) l s l q , ， ( 2 2 2 ) 式中右端i s l s ) 表示初始模和复制模均处于i s ) 态，iq ) ，和l q ) ，分别为 装置复制前后的量子态，复制后装置的量子态i g ) ，可能依赖于输入态 l s ) ，假如存在式( 2 2 9 ) 这样的变换，那么对于基矢i o ) 和1 1 ) 应有 q ) ，- l o l o l q o ， q ) ，- + ) 旧) ， ( 2 - 2 3 ) 现假定i s ) 是任意一个叠加态，即 l s ) = n i o ) + 6 1 1 ) ( 2 - 2 4 ) 其中，l a l 2 + 盯= 1 由式( 2 - 3 0 ) 及量子操作的线性特性，可知在操作后，1 s ) 将变为 l s ) l o ，= 纠o ) + 6 1 1 ) 】q ) ，一a i o ) 1 0 1 q o ，+ 6 l xq 1 ) ， ( 2 2 5 ) 如果复制机的态i q o ，和iq i ) ，不恒等，那么式( 2 - 3 2 ) 给出的初始模和 复制模均处于i o ) 和f 1 ) 的混合态；如果i q o ) ，利q 1 ) ，恒等，则初始模和复制模 将处于纠缠态a i o l o + b p l a 。无论哪种情况，初始模和复制模都不可能处 于直积态l s ) l s ) 。因此，即使一个量子态复制机能够精确复制态i o ) 和1 1 ) ， 它也不可能复制两态的叠加态i s ) 。证毕。 2 3 本章小结 这一章主要对量子力学和量子信息论两个方面进行了初步介绍，了 解了一些基本概念和原理，它们是讨论和研究量子密钥分配和量子签名 方案的基础。 硕士学位论文：量子信息论中的密码协议与算法研究 第三章量子密码学及其安全性 密码学是一门古老又年轻的学问。在远古时代的战斗中，人们就开 始使用密码术，早期的密码如p o l y b i o s 、c a e s a r 、h i l l 、p l a y f a i r 、v i g e n e r a 等都是建立在一些原始的置换法和替代法基础上的，但这些密码术过多 依赖一些个人技巧，没有系统的理论。1 9 4 8 年香农在贝尔系统技术期 刊上发表了一篇论文保密系统的通信理论【1 ，这篇论文为密码学 的研究做了奠基性的工作，从此密码学的理论体系开始建立。在当今社 会，信息化程度空前提高，人们除了注重信息的高效传输外，还对一些 敏感信息( 如个人档案、公司财务、商业秘密等等) 在交换和存储中的 安全性提出了越来越高的要求。密码学，作为保密通信的一门数学科学， 早以从军事外交领域走出来，应用在现代生产、生活的各个领域。在本 章中，首先对经典密码学【3 4 】做一个简要的回顾，然后引出量子密码学， 描述量子密钥分配方案，讨论其安全性。 3 1 经典密码学 3 1 1 对称密码体制 对称密码体制( s y m m e t r i c k e ys y s t e m ) 又称为单密钥体制( o n ek e y s y s t e m ) ，其信息流程图3 1 ： 图3 1 对称密钥体制的信息流程图 硬士学位论文：量予信息论中的密玛将议与算法研究 一个密码体制照一个五元组( p ，c ，k ，e ，d ) ，它需要满足以下条件： ( 1 ) p 是可戆明文懿套羧黛； ( 2 ) c 是可徽密文豹有陵集； ( 3 ) k 是可能密钥的有限浆； ( 4 e 是加密溉则( 函数) 集； ( 5 ) d 是解爨舰娴( 函数) 集。 对称密钥体制有时又叫传统密码体制，就是加密密钥能从解密密钥 中推算溅来，反之亦然。在大多数对称算法中，加密解象密钥是相同的， 嚣隧要袋a l i c e 霸b o b 在逶售蓦誊，裁囊定一个密锾，对禳算法熬安全毪 依赖于密钥，泄漏密钥就意味稽任何人都可对消息进行3 n 解密，只要 通信需鼷保密，密钥就必须保密。 对称算法的搬密可表示为： 最p 净c( 3 一1 ) 对称算法的解密可表示为： d k ( c ) 一p ( 3 2 ) 对称算法可分藏为两类： ( 1 ) 序列算法( s t r e a ma l g o r i t h m ) 或序列密码( s t r e a mc i p h e r ) 序列算法是一次只对明文中的单个位( 有时字节) 进行运舞的 算法。 ( 2 ) 分组算法( b l o c ka l g o r i t h m ) 或分组密码( b l o c kc i p h e r ) 分组算法鼹一次对明文中的一个分组( b l o c k ) 谶行运算的簿法 域代诗算机密褥算法的典爨分组长度位6 4 位这个长度大到足 以防止分章厅酸译，僵又，j 、到足暖方便筏蠲。著名静d e s 就是采瘸6 4 位的分组加密鳟法。 3 。1 。2 公舞窘钥体剡 公开密钥体制( p u b l i ck e ys y s t e m ) 也称非对称密钥体制 ( n o n 。s y m m e t r i ck e ys y s t e m ) 或双密钥体制( t w ok e ys y s t e m ) 。麒信 息流程妇霆3 2 黪示。 在公开密钥体铡中，热密密钥与解密密钥是完全不同的，而盟解密 密钥不能根据加密密钥计算出来( 至少在合理假定的长时间内) ，正因为 这个原嘲，加密密钥可以完全公开，即陌生辫可以用加密密钥加密消息， 颦士学链论文：燕子信息论串静密码协议与算法研究 但只能用相应的解密密钥才能解密消息。因而称加密密钥为公歼峦钥 ( p u b i ck e y ，簿豁公锈) ，麟密密锈力熬人密锈( p r i v a t e k e y ，麓穆程 钥) 。 图3 - 2 公开密钥体制热密信息流程圈 用公开密钥k 加密可表示为： e ；p ) = e 用私人密钥k7 解密可表示为： 一 d 。( c ) = p ( 3 3 ) ( 3 4 ) 3 3 一次一密乱码本 一次一密乱谒本( o n e t i m ep a d ) 3 5 1 是由g i l b e r tv e r n a m 在1 9 17 年发爨鳇，今天仍育应用场蠹，主要用于赢度枧密鼹低带宽信道，许多 翁苏联间谍传递的信息是采鞠一次一密鬣璃本鸯霸密韵。一般说采，次 一警乱码本不外乎是一个大的不重复的巅随机密钥字母集也称密钥空 间，这个密钥空间就是一个飘码本，在乱码本中的每一密钥仅仅对个 瀵慧壤霜一次。发送者霹爱发送豹滇惠热密，然轰镇羧蔑玛本中麓遭弱 密钥熊。接收者有一个同样的乱码本，并依次使用乱码本上的每个密钥 信息去解密文的每个字符，接收者在解密信息后销毁乱码本中用过的密 锯集。藏黪消息测疆琵码本中耨数蜜钥热密。壹姥霹恩，除龚密瓣分辑 者稔好圜到那个年代，并得剽加密信息的一次一密乱褥本，否则能们都 不可能阅读前苏联间谋用一次密乱码本加密的信息。这里密钥字母必 须是随橇产生战，对这种方案的攻击实际上依赖于产生密锣序列的方法。 亘 | | 蕃 里 重 一暑 硕士学位论文：量予信息论中的密码拂议与算法研究 由于明文消息是等概率的，所以密码分析者没有办法确定哪一明文消息 是正碜静。夔艇塞锾痔残异或夔撬的骥文瀵崽产生一完全睫爨瓣蜜 文消息，再大的计簿能力也无能为力。由此可见，使用一次一密乱码本 加密的倍息是不可敬破的。 然蕊，如果次一密乱玛本真验是无法攻破的，那么先侍么它没有 褥到广泛豹使焉褥? 这个闫题赣要涉及到密钥的产生、分配帮管理阏题 ( 其宴遮在其它的密码系统中也涉及到) 。荫先，a l i c e 必须生成一必真 正的随机数，而这也并不像想象中的那么容易。例如，猩计算机上一个 燕单熬缀夔疆数生艘器凝本无法提供密锈，这是鑫为黠予菜一绘定麴耱 子值它总是生成一个相同随机数序列。为了避免这种不合理的情况，在 密钥生成过程中使用了一个物理“噪声”。 一曼a l i c e 己缀生成用于加密系统中磁蔫要鲍足够密锈集，姥必须 在傈谣e v e 无法获得任何属予这个密钥爨中的密钥子集的前提下使得 b o b 可以获得这个鬻钥集的个备份。实际上，真正传输一次一密乱码 本的唯一安全的方法是需要再次使用一次一密乱码本对蕤进行加密。解 决这个密锯分配瓣戆静传统方法跫在a l i c e 秘b o b 之阕建立一个秘密通 道，这个通道依赖于一种使第三方( e v e ) 很难获得密钥信息的“物理 安全性”，并且他们必须秘密地保存这些密钥赢到它们被使用。 综主蹶述，塞鹳系统要取褥重大的突酸嚣要在“公开”售遵上采取 一种全新的通信方式，这种通信方式允许a l i c e 和b o b 建立些安全可 靠的密钥，并且在通信过程中他们可以探测出e v e 是否在窃听。这种通 信系绞允许a l i c e 翔b o b 在加密信息过程中瓣要密钥黔时候生成密钥。 这个密铜甚至氇楚个一次爨乱弱本，觚蕊也避免了箭面嚣讨论瀚那 些安全性问题。下面所论述的爨子密钥分配(