量子数学最快的算法
【来源:天津大学新闻网_媒体报道】
《中国科学报》2022年12月7日 第3版
今年,美国国家标准与技术研究院(NIST)公布了4项后量子密码标准,旨在抵御未来量子计算机的攻击。
科学家普遍认为,基于量子科学原理建造的量子计算机将大大超越电子计算机,而现代通信所利用的许多密码体系在量子计算的攻击下将不堪一击。抵抗这一攻击则需要“后量子密码”。
此次公布的4项后量子密码标准中的3项,是基于一个古老的数学学科——格理论。换句话说,假如量子计算机在不远的将来投入使用,格理论将是量子计算时代信息通信安全的“保护神”。
如何理解后量子密码?什么是格理论?《中国科学报》近日专访了格理论专家、天津大学讲席教授宗传明。
数学已成为现代密码学的基础
《中国科学报》:很多公众都会好奇,究竟什么是后量子密码?
宗传明:简单地说,密码是一种防范第三方窃取信息的通信保护手段。早在古罗马时期,凯撒大帝和他的将军之间就用密码传送命令,这就是著名的“凯撒密码”。他们的语言当时只有23个字母,情报官将命令内容的每一个字母依照字母表的次序后移固定的位置(比如5个位置),然后写成新的形式交给传令兵,前线将军收到命令后再由情报官还原回去。
第二次世界大战期间,密码成了某些重要战役胜负的决定因素,例如中途岛海战和击落山本五十六的座机等。为了破译密码,电子计算机应运而生。
随着计算机技术的快速发展,密码学也得到了空前发展。特别是进入互联网时代以来,密码学逐渐成为一项跨数学与计算机科学的科学技术。
现在,科学家普遍认为,不论是计算速度还是智能性,基于量子科学原理建造的量子计算机将大大超越电子计算机。许多电子计算机无法解决的科学问题对量子计算机来说易如反掌。特别是,现代通信所利用的许多密码体系在量子计算的攻击下将不堪一击。所以,科学家们在加速量子科学研究和量子计算机研制的同时,也在加速构建量子计算机时代安全的密码体系。这就是所谓的后量子密码。
《中国科学报》:我们能否设想有两个敌对国家,其中一国秘密发展了量子计算机,而另一国还在使用普通电子计算机的密码体系。如果前者利用量子计算机对后者的密码体系发动攻击,那么后者的信息安全体系将会瞬间崩溃。
宗传明:是的,就像科幻小说《量子间谍》描写的那样。
《中国科学报》:我们要研究密码学,数学是基础对吗?
宗传明:数学是最讲究逻辑、最精确的一门学问。无论是加密还是解密的过程都需要精确的规律性,而为了避免被破译,加密规律在计算上具有高度复杂性。因此,数学中的某些复杂问题成为密码学的基础是必然的。事实上,密码学的“鼻祖”凯撒密码就是基于数论中最简单的同余方程得来的。
随着电子计算机和互联网的高速发展,密码也变得越来越复杂。
1976年,两位密码学家惠特菲尔德·迪菲和马丁·赫尔曼提出了革命性方案“密钥交换协议”,改变了原来单一密钥的设计,进而提出加密密钥和解密密钥不同的密码思想,并因此荣获2015年度“图灵奖”。该方案为基础数学进入密码学开启了大门。
1977年,基于大整数分解的密码体系RSA诞生了,它是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)3位提出者的首字母而命名。早在两千多年前,古希腊数学家欧几里得就已经证明:每一个自然数都可以被唯一地分解为素数方幂的乘积。但是,具体分解一个大整数在计算上非常复杂耗时,正是其复杂性成就了RSA密码体系的安全性。他们由此荣获2002年度“图灵奖”。
随后,又有多种基于基础数学的密码体系相继被发现,比如基于椭圆曲线的密码体系、基于格理论的密码体系、GGH密码体系、NTRU密码体系等。
毫不夸张地说,数学已成为现代密码学的基础。
《中国科学报》:您提到的这些密码体系都能抵抗量子计算机的攻击吗?
宗传明:当然不是。
1994年,当代著名数学家和计算机科学家彼得·肖尔首次提出了大整数分解的多项式时间量子算法,并应用于密码学。他的工作表明,在量子计算时代,基于大整数分解和离散对数问题的公钥密码体系将被攻破。
随着量子科技的快速发展,以及多项广泛应用的密码体系在量子计算环境下被逐一攻破,各国科学家意识到,量子计算机可能给信息安全带来危机。
2016年,NIST向全世界征集抵抗量子计算机攻击的后量子密码标准。历经4轮遴选淘汰,2022年7月5日NIST公布了4项后量子密码标准。其中3项基于格理论、1项基于编码理论。
基于格理论的后量子密码标准
《中国科学报》:什么是格理论?
宗传明:1831年,高斯提出了格的概念。它是n维空间中最有规律的离散结构。历经高斯、厄尔密特、闵科夫斯基、西格尔等大数学家近两个世纪的系统研究,格理论已发展成为数论、代数与几何相交叉的一个重要数学分支。
在这一领域中,2021年洛瓦兹由于LLL算法的工作荣获“阿贝尔奖”,今年7月维亚佐夫斯卡由于8维堆球和24维堆球的工作荣获“菲尔兹奖”。三维格理论奠定了晶体学的基础,高维格理论则成就了NIST公布的4项后量子密码标准中的3项。
《中国科学报》:为什么格理论独占四分之三?格密码能抵抗量子计算攻击吗?
宗传明:一个给定的格必定有最短的向量。早在100多年前,闵科夫斯基就已经给出估计。给定一个格,空间中的任一点一定有一个最近的格点。但要找到一个好的算法来确定格的最短向量(SVP)或离给定点最近的格点(CVP)却极其困难。
而格密码在量子计算环境下的安全性都可以递归到这两个数学问题的计算复杂度上。20世纪80年代,众多著名数学家深入系统的研究证明,在电子计算机环境下求解这两个数学问题是非常困难的。
格密码最早由美国数学家米克劳斯·阿杰泰于1996年提出。由于上述数学家们的理论工作,格密码显然能够抵抗电子计算机的攻击。那时,彼得·肖尔的量子算法刚刚被提出,在其他密码体系纷纷被量子算法攻破的情况下,世界各地的密码专家更是使出“洪荒之力”试图利用量子算法攻破格密码,特别是在美国开始征集后量子密码标准以来的6年。
其实,在过去的近10年当中,每届世界密码学的三大会议(美密会、欧密会和亚密会)都会设一个分会专门研讨格密码。但是,人们至今没有找到有效的量子算法攻击格密码。数学家和密码学家反倒形成了一个共识(猜想):不存在多项式时间的量子算法能在多项式误差下求解格的最短向量问题和最近格点问题。
换句话说,格密码是能够抵抗量子计算机攻击的。
中国数学家需尽快迎头赶上
《中国科学报》:1994年还没有量子计算机的模型机,当时彼得·肖尔为什么能提出量子算法?人们又如何检验一个密码体系是否可以抵抗量子计算机的攻击?
宗传明:在科学技术的发展过程中,有时候是技术推动科学,而大多数情况下是科学推动技术。在没有公开运行的量子计算机模型机的情况下,彼得·肖尔依照量子科学的原理理论设计出量子算法,而其他数学家和密码学家也是如此设计攻击算法,来检验一个密码体系能否抵抗量子计算机的攻击。
假如把计算机比作一个人,硬件如同躯体,软件则如同智力。在物理学家和计算机工程师致力于设计建造量子计算机的同时,数学家和计算机科学家也在努力赋予它智能,并且防范其智能可能给信息安全带来的破坏。
《中国科学报》:在当下复杂的国际环境下,我们该如何应对量子科技可能带来的挑战?
宗传明:我不懂物理,也不懂计算机,只懂一个很小的数学分支——格理论。碰巧格理论成了后量子密码的数学基础,我有责任向公众科普这一可能的危机,以唤起大家的共识和重视。
欧美构建后量子密码标准是基于大批一流数学成果,没有“弯道超车”,也不靠“黑科技”,完全是水到渠成。
我国现代科学技术起步晚,现代数学进入中国仅一个多世纪。但大家已有共识,要摆脱被“卡脖子”困境,成为科技强国,就要有一流的基础科学,而一流的基础科学必须有一流的数学。
在量子计算机已成为各国竞争潜在战场的今天,我国急需一批数学家尽快迎头赶上,搞懂欧美数学家为后量子密码所奠定的基础,与我国的密码学家密切合作,共同打造我国的信息安全之盾。
中国科学报:
(编辑 刘晓艳 张佳丽)
声明:此文版权归原作者所有,若有来源错误或者侵犯您的合法权益,您可通过邮箱与我们取得联系,我们将及时进行处理。邮箱地址:[email protected]
","force_purephv":"0","gnid":"99b57fe015f60d8d6","img_data":[{"flag":2,"img":[{"desc":"","height":"855","title":"","url":"https://p0.ssl.img.360kuai.com/t01e258c6934d4c5590.jpg","width":"600"}]}],"original":0,"pat":"art_src_1,fts0,sts0","powerby":"hbase","pub_time":1670428191000,"pure":"","rawurl":"http://zm.news.so.com/92fa723bc981e22630795aaa4699b616","redirect":0,"rptid":"772171fa693874ad","s":"t","src":"九派教育","tag":[{"clk":"kscience_1:天津大学","k":"天津大学","u":""}],"title":"中国科学报:天津大学讲席教授宗传明: 数学奠定“后量子密码”的基础天津大学讲席教授宗传明: 数学奠定“后量子密码”的基础
乜瑞怖4228想自学量子 求学量子前 应该先学那些知识 为学量子做铺垫? 本人高二文科生 求详细学习 -
燕罡荀19410067965 ______ 你好,自学量子的话,就和你的学习背景无关了. 如果是认真学习,你需要按照如下顺序学习: 高中数学,物理,化学. 高等数学,线性代数(均为同济版) 数学物理方法(梁昆淼) 力学,理论力学 电磁学,光学,电动力学(大体学一学就行) 热学,热力学和统计物理学(大概的学一下就行) 原子物理学 (均为高教版即可) 以上铺垫完成后是这些: 量子力学导言(曾谨言) 高等量子力学(喀兴林) 然后,你已经入门了,剩下的路通向哪个方向,就需要自己走了. 如果是业余看着玩,只想随便了解一点,那么《上帝掷骰子吗?——量子力学史话》,《新量子世界》这些不错.
乜瑞怖4228未来量子计算机能有多快 -
燕罡荀19410067965 ______ 普通计算机的上亿倍
乜瑞怖4228量子计算机是什么? -
燕罡荀19410067965 ______ 量子计算机技术涉及利用量子粒子作为一个替代位今天的电脑. 该理论的量子计算机始于20年前与保罗贝尼奥夫,物理学家在阿贡国家实验室,谁使用的概念图灵机作为一种模式的量子计算机. 一个图灵机组成的一盘磁带无限期长度可分为大...
乜瑞怖4228求解非线性薛定谔方程有哪些方法 -
燕罡荀19410067965 ______ 普通的求解微分方程法对薛定谔方程还是有用的(格林函数,积分变化,展开逼近etc),有时候还能用代数空间的一些办法.
乜瑞怖4228量子力学需要的数学知识有哪些? -
燕罡荀19410067965 ______ 量子力学大体分为两类,一种是以薛定鄂方程(波函数能量方程)为代表的微分解析类,另一种是以海森保为代表的矩阵力学,无论哪种,本质都是相同的.显然需要的数学知识有:数学分析(微积分),代数学(矩阵论),数学物理方程(微分方程),复变函数等.量子力学的学习数学是基础,也要融会哲学知识,初学重在深刻改变对微观世界的认识观和思想,这是前提条件,很重要.
乜瑞怖4228亚历克西斯·勒迈尔是怎么做到快速计算次方根的? -
燕罡荀19410067965 ______ 因为他自己研究出一种心算的矩阵列图形,比我们常用的小99还在大,这个矩阵列图形只要算这个次方根,只要能找到,他就能找到对应的数字,所以他的心算快. 法国男子亚历克西斯·勒迈尔人称“人体计算机”.他能完全凭借心算能力,...
乜瑞怖4228如何求解量子力学久期行列式? -
燕罡荀19410067965 ______ 1 量子力学久期行列式的求解是一个复杂的过程,需要有一定的数学基础和物理常识才能进行.2 久期行列式是由任意两个波函数的内积所组成的行列式,在求解过程中需要先通过哈密顿量的本征值和本征函数,得到不同能量态下的波函数,然后通过正交化处理,得到标准正交基,最后根据久期行列式公式进行计算.3 求解久期行列式需要掌握量子力学的相关概念和数学方法,需要从量子力学的基础开始学习,包括薛定谔方程、本征值和本征函数等.同时,还需要熟练掌握矩阵的基本运算和行列式的计算方法,才能进行久期行列式的求解.
乜瑞怖4228量子力学的数学工具? -
燕罡荀19410067965 ______ 数学物理方法,高等数学,线性代数
乜瑞怖4228两行三列矩阵怎么算
燕罡荀19410067965 ______ 算两行三列矩阵:前一个矩阵的列数=后一个矩阵的行数,在数学中矩阵是一个按照长方阵列排列的复数或实数集合,最早来自于方程组的系数及常数所构成的方阵.这一...
乜瑞怖4228如何实现一台量子计算机 -
燕罡荀19410067965 ______ 就是用量子比特代替原来的普通比特. 从物理层面上来看,量子计算机不是基于普通的晶体管,而是使用自旋方向受控的粒子(比如质子核磁共振)或者偏振方向受控的光子(学校实验大多用这个)等等作为载体.当然从理论上来看任何一个多...