天津大学讲席教授宗传明展示剖析后量子密码的数学基础

研究背景
量子计算被广泛认为将是一项革命性的高新技术。事实上，它是一把双刃剑。假如人们在不远的将来能够建造出高效的量子计算机，现在广泛用于加密通信的多种密码体系将会很容易被攻破。所以，提前构建能够抵抗量子计算机攻击的密码体系（后量子密码）成为保障未来通信安全的当务之急。
1994年，美国数学家P. Shor 发现了能够攻破RSA密码和ElGamal密码的量子算法。2007年，加拿大的D-Wave公司展示了首台量子计算模型机。这两个科技事件及其后续发展给保密通信带来了前所未有的危机。为了应对这一挑战，2016年，美国国家标准与技术研究院（NIST）在全球征集筛选后量子密码标准。2022年， NIST宣布了四种候选算法：CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon和Sphincs+。其中，前三种基于数学的格理论，最后一种基于哈希函数。2024年， NIST宣布了三项后量子密码标准： FIPS 203基于CRYSTALS-Kyber, FIPS 204基于CRYSTALS-Dilithium, FIPS 205基于Sphincs+. 基于Falcon 的第四项标准正在制定中。2024年11月12日， NIST 发布了一个后量子密码迁移白皮书，其中制定了具体的迁移路线和时间表。至此，基于格理论的密码（格密码）是后量子密码的核心。 
研究进展
格是高斯于1831年前后提出的一个数学概念。格密码的安全性基于如下两个数学问题及其推广的计算复杂性：1、最短向量问题（SVP）：给定一个n维格，计算确定它的最短非零向量。2、最近格点问题（CVP）：给定一个n维格和所在空间的一个点，计算确定离该点最近的格点。事实上，SVP是一个球堆积问题，CVP是一个球覆盖问题。换一个角度看， SVP 和 CVP 都可以等价地表述为正定二次型的算术问题。在过去的四百多年中，这些数学问题曾被开普勒，牛顿，高斯，厄密特，闵科夫斯基和许多当代数学家系统研究过。所以，后量子密码深深地根基于数学。
本文首先简要介绍了后量子密码及其安全性的基础，即最短向量问题和最近格点问题的计算复杂性理论。然后详细介绍论证了这两个问题的数学基础：SVP问题等价于球堆积问题，CVP问题等价于球覆盖问题，它们都等价于正定二次型的算术问题。其中，特别着重介绍了可能影响后量子密码进一步发展的一些基础数学问题：球堆积密度问题，球覆盖密度问题，Rogers常数，Dirichlet-Voronoi多面体，Rankin常数等。假如我们将后量子密码比作果实，格的计算复杂度理论就是果树，那么球堆积问题，球覆盖问题和正定二次型的算术理论就是树根。本文将它们完整有机地呈现出来，让密码学家和数学家都能看清自己所在的位置和在整个工程中对对方的依赖。 
未来展望
假如一项高新技术不仅能对社会带来革命性的进步也会带来严重灾难，那么提前布局预防这些灾难将异常迫切和重要。量子计算就是这样一项技术！它不仅能够解决许多科学难题，也能攻破许多现在广泛应用的加密通信系统。所以，尽快构建后量子密码体系是迎接量子科技时代的首要任务之一。这一重任给密码学家和数学家提供了前所未有的机遇和挑战。
不论后量子密码如何发展，数学都将是它不可避免的基础因为它总是需要像格理论那样的数学模型。当然，仅有数学是远远不够的。成功的后量子密码一定是密码学家，数学家和量子计算科学家共同合作的产物。
原文链接：https://spj.science.org/doi/10.34133/research.0801