杨理-量子密码学的理论基础

好

沿

量子密码学的理论基础

因杨理

世界上有两门学问公认比较难院一门是密码学袁一门是量子物理遥难的原因完全不同院密码学难是因为世界上有人太聪明袁难在巧夺天工的构造和叹为观止的分析曰量子物理难是因为大自然深奥难测袁其微观规律远离人们的直觉袁难在真正的理解和把握遥玻尔渊N.Bohr冤曾经说过院一条深刻真理的反面可能是另一条深刻的真理遥这句话集中体现了量子物理的辩证本质遥量子密码学要把两者结合起来袁其难度可想而知遥

戈德瑞克渊O.Goldreich冤在其叶密码学基础曳渊Foun鄄dationsofCryptography冤第二卷卷首引用了本家族长者的名言院野没有基础可以盖一间简陋的小屋袁却不能建成永久的大厦遥冶从这句话可以看到戈德瑞克长期以来苦心孤诣袁力图为密码学建立可靠基础的动机遥现在为了建立能涵盖量子密码协议的完整密码学理论大厦袁也必须重新考虑密码学基础的有关问题袁未来的工作任重而道远遥

现代密码学是一门高度发展的学问袁有许多高超的技巧和深刻的论述袁从事量子密码理论工作的人袁一方面需要虚心学习袁认真借鉴曰另一方面袁由于量子系统的极端特殊性袁还需要对量子理论的深刻把握和对密码学概念的大胆创新袁才能完成重建密码学理论基础的任务遥下面从量子理论与密码学深层次结合的角度来考察未来密码学的理论基础问题遥

单向函数存在曰基于散列函数渊hashfunction冤的消息认证码尧鉴别和承诺协议等要求抗碰撞单向函数存在遥总体而言袁现代密码学离不开单向函数袁犹如鱼离不开水遥

可以把密码学粗略地划分成两部分院一部分是基于随机性或信息论的理论曰一部分是基于困难问题或单向函数的理论遥这两部分密切相关院单向函数蕴涵硬核渊hardcore冤谓词袁硬核谓词蕴涵伪随机性遥换句话说袁虽然真随机数存在与否是个哲学问题袁不必奢求袁但算法能否生成伪随机数仍然依赖于困难问题或单向函数是不是真正存在遥一个无法回避的问题是院困难问题的困难性即单向函数的单向性并没有获得证明袁这就是密码学的困惑遥

目前量子密码学方面的理论工作主要是基于非正交量子态的叠加和混合的性质来构造算法袁利用此类量子态在物理上的不可区分性保证算法的安全性袁实现经典密码学目标遥已经构造的算法包括密钥分配尧远程掷币尧私钥加密尧公钥加密尧交互式无密钥传输尧秘密分享尧消息认证尧鉴别尧不经意传输渊OT冤尧比特承诺等等遥其中量子远程掷币是姚期智教授提出并研究了很多年的一个方向曰较早提出的量子交互式无密钥传输协议包括2002年3月笔者和吴令安教授提出的量子无密钥协议袁以及同年5月国外学者提出的乒乓协议遥一个重要的理论问题是院能够统一刻画经典密码学和量子密码协议的完备尧自洽的理论框架是什么钥

量子密码学有广义和狭义之分遥狭义量子密码学主要指量子密钥分配等基于量子技术实现经典密码学目标的结果袁广义量子密码学则是指建立在希尔伯特

杨理院副研究员袁中国科学院研究生院信息安全国家重点实验室袁北京100049遥

YangLi:AssociateResearchProfessor,StateKeyLaboratoryofInforma-tionSecurity袁GraduateUniversityofChineseAcademyofSciences,Beijing100049遥

经典密码学与量子密码学

密码学根本性的概念之一是单向函数遥公钥加密要求陷门单向函数存在曰私钥加密的语义安全性蕴涵

空间上的密码学袁给出能统一刻画狭义量子密码学和经典密码学的一个理论框架遥笔者和裴定一教授2002年提出的观点是院经典密码学和一切与量子性质有关的密码学结果可以统一在野量子信息密码学冶框架下遥

科学

13

好

前沿

FRONTIER

这里野量子信息冶概念十分重要遥把量子态视为信息袁对量子态提出信息论问题袁是人类在信息概念上的巨大飞跃袁是基于自然界基本定律对信息概念的自然推广袁是量子信息科学的基石遥经过近四十年的努力袁量子信息论已经完整建立起来了遥因为经典信息是量子信息的一个子集袁在量子信息上建立的密码学才是一个自洽完备的理论遥经典密码学和狭义量子密码学只是作为这个普遍理论的两个退化形式而存在遥

量子信息能否表达为不确定性经典信息尧香农信息论能否涵盖量子信息论是一个意义重大的基本理论问题遥基于量子力学的现代发展袁这个问题其实不难回答遥

第一袁经典信息的不确定性与某随机变量相联系遥由于量子态是希尔伯特空间的向量袁满足线性叠加原理袁不同叠加分量之间发生干涉袁而决定干涉结果的是各分量的相位和幅度袁即概率幅遥量子物理的一个重要特征就是相位本质性地进入物理学袁由于概率幅的相位信息在其模平方袁即概率中消失袁量子物理不可能表达为基于概率而不是基于概率幅的理论遥所以量子信息不可能表达为此类不确定性经典信息遥

第二袁经典的不确定性信息表达为包含某实参数的信息遥如果量子信息的性质可以用此类经典的不确定性信息来表达袁则意味着量子力学可以表达为包含某实参数的理论袁这其实就是长期以来进行了大量研究的隐参量理论遥著名的贝尔定理指出袁定域隐参量理论一定会满足贝尔不等式袁而量子力学则可以破坏贝尔不等式遥二十余年来众多的实验证明物理世界存在大量破坏贝尔不等式的现象袁这表明定域隐参量理论不可能存在袁因而量子信息不可能用此类经典的不确定信息表达遥

发展量子信息密码学的目的是研究量子信息的密码编码和密码分析问题袁探索希尔伯特空间野量子信息密码学冶的理论体系袁一方面致力于对量子信息系统安全性问题的解决袁一方面希望为有限域上传统密码学的发展开辟新的道路遥这与应用方面的理念完全不同遥想想从牛顿力学到狭义相对论的推广遥虽然如今建筑尧水利尧机械尧航空航天等仍然只是应用牛顿力学袁但铭刻在爱因斯坦墓碑上的那个不朽公式在使人类长期受到毁灭威胁的同时袁也给人类带来了无限的希望遥这就是理论的力量遥可见袁理论上做一件事与应用有着完全不同的出发点袁将来的作用也不一样遥

发展量子信息密码学需要传统的密码学理论和方法袁也需要量子信息和量子计算理论袁如量子信息论和量子计算复杂性理论袁但是这些可能还远远不够遥由于希尔伯特空间与有限域差别巨大袁上述问题并不是一

（62卷6期）14科学2010年11月

个把经典密码学概念平移过来的问题袁正如不能说量子力学是从牛顿力学平移过来一样遥发展量子信息密码学必然涉及到概念的创新袁必须重新考察密码学的理论基础尧研究对象和研究方法遥

量子单向函数与量子概率加密算法

现在广泛应用的各类陷门单向函数袁如RSA函数在后量子时代单向性消失遥为此人们定义了第一类量子单向函数院在野量子计算机存在而且不能求解NP完全问题冶假设下具有单向性的经典函数袁并基于此研究了后量子时代的各类密码学问题遥

第二类量子单向函数是作用在量子态上的诱导量子单向函数袁这是在发展量子信息密码学的时候所考虑的内容遥它由经典单向函数诱导生成袁是计算安全的遥可以证明袁只有基于陷门单向函数才能诱导出此类量子单向函数袁不过陷门从此消失遥所以作用于量子态的单向函数怎样构造陷门就是一个问题遥2003年笔者基于量子计算理论和麦克利斯渊McEliece冤公钥密码体制构造出第一个作用在量子态上的陷门单向函数和公钥加密算法袁并与胡磊和冯登国两位教授一起提出了量子消息的公钥认证算法遥

第三类量子单向函数是把经典序列随机映射到某一量子态上去遥此类函数用于承诺协议时可具有信息论安全的隐藏性渊即单向性冤袁但同时不可避免地存在基于量子纠缠态的攻击袁所以不具有计算无关的绑定性,此即量子比特承诺的不可行定理渊no-go定理冤遥2006年基于这种映射袁笔者和李宝教授构造了具有双向物理安全性的量子比特承诺协议袁目前笔者和学生向憧已证明这一量子比特承诺协议的安全性确实超越了经典比特承诺协议安全性的理论极限遥

概率加密思想在现代密码学体系中至关重要遥最近笔者所在课题组认真考察了量子概率加密算法的有关问题袁探讨了量子公钥算法在信息论意义上的加密不可分辨性遥已经完成的算法包括量子公钥算法尧量子私钥算法和量子无密钥算法遥其中基于第三类量子单向函数的公钥加密算法在选择明文攻击尧选择密文攻击和适应性选择密文攻击下满足信息论意义上的加密不可分辨性遥这样的结果在经典密码学中是无法想象的遥

基于消息和密钥是否为量子态袁可以将公钥加密算法分成四类院第一类消息和密钥都是经典的袁这就是经典密码学所研究的公钥算法袁包括基于第一类量子单向函数的量子公钥密码体制袁如2000年美国密码学年会上冈本渊栽.Okamoto冤等人报告的工作袁它们是计算安全的曰第二类是量子消息尧经典密钥袁这是笔者在

好

沿

2003年做的一项工作袁也是计算安全的曰第三类是经典消息尧量子密钥袁较好的结果是2005年川内渊栽.Kawachi冤等人在欧洲密码学年会的一篇文章袁得到了计算安全的结果袁2006年证明该方案是有界信息论安全的袁笔者和学生潘江游今年6月份完成的一个工作通过改变公钥算法的结构做到了真正的信息论安全曰还有一类是量子消息尧量子密钥袁对于最后一种情形现在的结论是它一定会回到基于量子计算的无密钥加密算法遥

无密钥密码体制是密码学家沙米尔渊A.Shamir冤二十年前提出的独立于公钥密码体制和私钥密码体制的第三类密码体制袁遗憾的是在经典密码学框架下其实现方式与公钥密码体制类似袁只能具有计算安全性袁而且不能对抗中间人攻击遥2002年笔者和吴令安教授给出的无密钥密码体制的第一个量子形式具有了无条件安全性袁此后建立并完善量子无密钥密码体制一直是

笔者所在课题组考虑的基本问题之一遥2003年笔者基于量子计算和量子纠缠的方案发展了可对抗中间人攻击的形式袁2006年笔者和胡磊教授应邀在美国陆军研究实验室渊ARL冤人员主持的一个国际会议上作量子无密钥协议的报告袁2009年笔者和学生伍扬发展了无密钥协议的实用化方案遥

形式知识理论与量子信息密码学

不能等同于信息遥信息的知识属性依赖于给定环境中所存在的问题袁知识的本质就是问题的答案遥可以基于模型中的问题给出知识的一种新的形式化定义遥笔者猜想信息是生命和非生命系统共有的袁而知识则是生命系统尧尤其是智能生命系统渊包括人工智能系统冤特有的遥形式知识理论的研究可能为理解智能生命尤其是人的思维尧探寻知识创新模式尧以及对抗计算机病毒

野数据爆炸但知识贫乏冶现象的普遍存在表明知识

科学

15

好

前沿

FRONTIER

和网络入侵提供理论模型遥

形式知识理论的基础包括院关于符号序列及其相互关系用熵函数刻画的信息论曰关于语言和语法的自动机和形式语言理论曰关于问题的可计算性和计算复杂性理论曰关于知识的渊交互式冤证明和零知识理论曰关于形式推演尧论域和语义的逻辑理论袁以及人工智能中发展的知识推理和学习理论袁等等遥

目前看来与上述各种知识有关的理论大多已成为密码学研究的理论基础袁这绝非偶然遥密码学是研究知识的保密尧认证和证明的理论袁是野形式知识理论冶的一个重要分支遥其实很显然袁如果不是知识袁为什么要保密它袁认证它袁证明它钥只不过由于保密和认证面对的知识千差万别袁为了以不变应万变袁构造和分析协议时袁合理的选择是从随机明文出发考虑问题袁这就是香农渊C.Shannon冤和西蒙斯渊J.Simmons冤基于信息论的理论袁仅考虑知识流的信息论性质曰而零知识证明渊ze鄄ro-knowledgeproof冤则由于其知识的具体性凸显了密码学的知识性遥基于这种认识袁笔者认为要建立量子信看起来建立形式量子知识理论和量子信息密码学的基本条件已经具备袁但真正去完成这项工作仍然十分困难袁需要数学尧物理学尧计算机科学等多学科研究人员的长期努力遥

纵观现代密码学半个多世纪的发展袁安全性定义的变革起到了举足轻重的作用遥从基于熵函数分析的完善保密性和唯一解距离袁到基于计算复杂性理论和单向函数存在假设的计算安全性袁再到后来基于概率加密思想的语义安全性尧不可分辨性和不可延展性等袁每一次变革都引领了密码学的大发展遥现在的问题是院下一步提出的是什么安全性钥

从形式知识乃至形式生命理论的角度考虑袁借鉴人工智能等学科的成就发展密码学袁使信息安全体系具有更强的自动化尧自适应尧自学习能力袁将会有助于使信息安全体系的功能完成赵战生教授所归纳的从保密尧保护到保障的历史性转变遥

未来的密码学就是智能密码学吗钥这一切与量子密码学的发展有关系吗钥

息密码学首先应该考察量子知识的概念和理论遥目前

典密码学不能实现的目标才有意义遥设计出更多的安全性超越计算假设的量子密码协议可以让密码学更加完美袁让信息安全体系更加牢固遥

量子计算机的研制对当前的密码体制构成严重威胁袁不过密码学要想对抗量子计算机攻击其实是有办法的遥量子计算机的计算能力会受到一些来自物理学的限制遥2007年笔者和陈玉福教授的一项工作发现袁量子计算机物理实现方案中最成熟的一类方案袁即相干场驱动类方案袁包括冷离子阱方案袁当考虑到场的量子化效应和容错量子计算的阈值定理时袁对于运行其上的量子算法的逻辑深度会有很大的限制遥这是任何技术上的改进所无法超越的理论极限遥最近一年多这方面的工作取得了新的进展袁笔者和学生杨碧瑶已经对于这一重要结论给出了比较充分的论证遥

一个尖锐的问题是院这个结果是不是表明量子计算机不能破译公钥密码钥回答是否定的遥例如整数因子分解量子算法袁由于其逻辑深度上界已经改进到待分解整数位数的对数袁基于容许逻辑深度给出的限制意义不大遥但是袁对于求解离散对数的量子算法袁尤其是对于求解椭圆曲线离散对数的量子算法而言袁如果它们的逻辑深度不能有重大改进袁相干场驱动类量子计算机从原理上就无法可靠地运行它们遥

量子密码学的理论基础目前正在探索和创建之中袁远没有完成袁没有人能看清它的庐山真面目袁没有人能真把它讲清楚遥多年来笔者所在的量子密码课题组在老一辈密码学家的悉心指点和年轻密码学家的热情帮助下袁在实验室历届领导的大力支持和直接参与下袁一直致力于发展量子信息密码学理论袁希望给经典密码学和现有的狭义量子密码学一个统一的理论基础袁使我们能够从一个更高的层次上理解密码学遥相信基于量子知识理论袁在一个更大的空间上发展密码学有可能使密码学的结构更清晰尧基础更牢固遥为此建立的形式量子知识理论有可能启发我们从一个新的角度认识生命袁认识智能袁认识我们自己遥

咱本文据笔者在野第九次中国科协论坛冶上所作的主旨报告野量子密码学的理论基础冶整理而成袁删去了学术性较强的内容遥本文相关研究工作得到了国家自然科学基金面上项目野量子信息密码学研究渊批准号院60573051冤冶尧973项目野量子通信与量子信息技术渊2001CB309300冤冶和信息安全国家重点实验室自主研究课题野量子信息密码学探索冶的资助袁特此致谢遥暂关键词院量子密码学

量子单向函数

量子信息密码学

量子信息密码学形式知识理论

有关应用问题

从应用方面来看袁量子密码系统研制的目标是在信息安全体系当中作为重要部件发挥作用袁使国家的信息安全体系更完善尧更牢固遥经典密码学经过长期发展已形成完整体系袁体现了人们对密码学的要求袁从事量子密码研究的人首先需要考虑的问题是如何使用量子性质进行加强遥一项量子密码技术必须是实现了经

（62卷6期）16科学2010年11月

阴

本文来源：https://www.bwwdw.com/article/v1xe.html