《中国科学报》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年还没有量子计算机的模型机，当时彼得·肖尔为什么能提出量子算法？人们又如何检验一个密码体系是否可以抵抗量子计算机的攻击？

宗传明：在科学技术的发展过程中，有时候是技术推动科学，而大多数情况下是科学推动技术。在没有公开运行的量子计算机模型机的情况下，彼得·肖尔依照量子科学的原理理论设计出量子算法，而其他数学家和密码学家也是如此设计攻击算法，来检验一个密码体系能否抵抗量子计算机的攻击。

假如把计算机比作一个人，硬件如同躯体，软件则如同智力。在物理学家和计算机工程师致力于设计建造量子计算机的同时，数学家和计算机科学家也在努力赋予它智能，并且防范其智能可能给信息安全带来的破坏。

《中国科学报》：在当下复杂的国际环境下，我们该如何应对量子科技可能带来的挑战？

宗传明：我不懂物理，也不懂计算机，只懂一个很小的数学分支——格理论。碰巧格理论成了后量子密码的数学基础，我有责任向公众科普这一可能的危机，以唤起大家的共识和重视。

欧美构建后量子密码标准是基于大批一流数学成果，没有“弯道超车”，也不靠“黑科技”，完全是水到渠成。

我国现代科学技术起步晚，现代数学进入中国仅一个多世纪。但大家已有共识，要摆脱被“卡脖子”困境，成为科技强国，就要有一流的基础科学，而一流的基础科学必须有一流的数学。

在量子计算机已成为各国竞争潜在战场的今天，我国急需一批数学家尽快迎头赶上，搞懂欧美数学家为后量子密码所奠定的基础，与我国的密码学家密切合作，共同打造我国的信息安全之盾。

中国科学报：

（编辑 刘晓艳 张佳丽）