研究背景

1994年，美国数学家Peter 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是一个球的格覆盖问题 (如图1、2所示)。换一个角度看，SVP和CVP都可以等价地表述为正定二次型的算术问题。在过去的四百多年中，这些数学问题曾被开普勒、牛顿、高斯、厄密特、闵科夫斯基和许多当代数学家系统研究过，但至今远未解决。所以，格密码深深地根基于数学。

图1. SVP等价于球的格堆积问题 (原文figure 2)

图2. CVP等价于球的格覆盖问题 (原文figure 3)

本文详细阐述展示了格密码背后的数学问题，让密码学家看到格密码的根基，让数学家感受到聚焦高科技问题的动力。它首先简要介绍了格密码及其安全性的基础，即最短向量问题，最近格点问题以及它们的推广。然后详细介绍了这些问题的数学基础：SVP问题等价于球的格堆积问题，CVP问题等价于球的格覆盖问题，它们都等价于正定二次型的算术问题。本文着重介绍了可能影响格密码进一步发展的一些基础数学问题：球堆积密度问题；球覆盖密度问题；Rogers常数问题；Dirichlet-Voronoi多面体问题；Rankin常数问题等。假如我们将格密码比作果实，格的计算复杂度理论就是果树，那么本文介绍的数学问题就是树根。

图3. 格密码的“根与果”

总结与展望

假如一项高新技术不仅能对社会带来革命性的进步也会带来严重灾难，那么提前布局预防这些灾难将异常迫切和重要。量子计算就是这样一项技术！它不仅能够解决许多以前解决不了的科学难题，也能攻破许多现在广泛应用的加密通信系统。所以，尽快构建后量子密码体系是迎接量子科技时代的首要任务之一。这一重任给密码学家和数学家提供了前所未有的机遇和挑战。

美国国家标准与技术研究院 (NIST) 的后量子密码标准已凸显格密码的重要性。格密码的进一步发展很大可能将基于人们对本文所列数学问题的进一步理解。当然，仅有数学是远远不够的。成功的后量子密码一定是密码学家，数学家和量子计算科学家共同努力的产物。

阅读英文原文：https://www.mdpi.com/2410-387X/10/1/10

• 作者信息

作者：宗传明教授，天津大学应用数学中心

研究方向：数的几何，离散几何，格密码。

• Cryptography 期刊介绍

主编：Prof. Dr. Josef Pieprzyk,  CSIRO (The Commonwealth Scientific and Industrial Research Organisation), Australia; Institute of Computer Science, Poland

主要方向包括密钥密码学、公钥密码学、哈希函数、密码分析、密码协议和量子安全密码学及其实践、实现、应用和相关标准。

2024 Impact Factor：2.1

2024 CiteScore：5.0

Time to First Decision：19.3 Days

Acceptance to Publication：3.9 Days

期刊主页：https://www.mdpi.com/journal/cryptography