后量子密码算法
由郁昱教授带领的PQMagic团队在国际顶尖密码学会议上发表或合作发表过多个后量子密码算法，其中包括基于格的后量子KEM/SIG算法Aigis（PKC 2020）、基于哈希的后量子签名算法SPHINCS-𝛼（CRYPTO 2023）以及基于vole-in-the-head的后量子签名算法ReSolveD（PKC 2024）。
Aigis——基于非对称(M)LWE和(M)SIS的数字签名和密钥封装机制
基于格的密码系统在密钥和密文（签名）大小方面不如数论密码系统（基于RSA、离散对数等）有效。为了获得足够的安全性，前者通常需要数千个字节，而后者最多只需要数百个字节。这种显著差异已成为用基于格的密码系统替换当前部署的公钥密码系统的主要问题之一。通过观察现有基于格的密码系统中固有的不对称性，团队提出了（module-）LWE和（module-）SIS假设的不对称变体，与标准对应物相比，这些假设产生了进一步的大小优化KEM和签名方案。遵循Lindner和Peikert（CT-RSA 2011）和Crystals-Kyber提案（EuroS&P 2018）的框架，团队提出了一种IND-CCA安全KEM方案，该方案来自非对称模块LWE（AMLWE）的困难度，充分利用其不对称性来获得更短的公钥和密文。为了实现 128 位安全性，我们的 KEM 的公钥（resp.，密文）只有 896 字节（resp.，992 字节），这比 Kyber 提高了 192 字节（resp.，160 字节）。我们的标志性方案与Crystals-Dilithium方案（ToCHES 2018）最相似，并对其进行了改进。通过充分利用底层非对称module-LWE和module-SIS假设，并仔细选择参数，我们在计算成本、存储开销和安全性之间获得了更好的折衷，从而构建了具有更短公钥和签名的SUF-CMA安全签名方案。对于 128 位安全性，我们的签名方案的公钥（resp.，signature）只有 1312 字节（resp.，2445 字节），这比 Dilithium 提高了 160 字节（resp.，256 字节）。
Aigis与NIST算法的比较如下表所示，关于算法性能详见测试页面。
SPHINCS-𝛼——基于哈希函数的后量子数字签名算法
随着量子计算理论和量子计算机技术的推进,现有的经典（图灵计算模型下的）密码学的发展遭遇理论危机，例如 Shor 量子算法可在多项式时间内解决大整数分解、离散对数等经典困难问题。然而,量子计算机的指数级加速并不适用于所有困难问题,对于某些问题量子算法相较于经典算法并不具备太多的优势，这些问题包括编码困难问题、格问题、哈希问题等。数字签名算法用于验证数字信息的完整性、真实性和来源，是密码学体系中的基础原语。郁昱教授团队基于哈希函数设计了一种后量子数字签名算法（SPHINCS-α），可以有效地抵抗量子计算攻击。一次性签名（OTS）方案是基于哈希签名的核心构建模块，它的效率很大程度上主导了基于哈希的签名，目前WOTS+ 是NIST标准化签名方案所采用的最先进的OTS。本团队采用了一种新颖的常量和编码方案重新构造了WOTS+，并证明了该签名方案不仅在 Winternitz 的 OTS 框架下，而且在所有基于树的 OTS 设计中都是大小最优的。此外，团队指出基于有向无环图（DAG）的 OTS 设计中的一个缺陷，该设计先前在 Asiacrypt 1996上被证明是尺寸最优的。最后，团队通过实验证明，该签名算法在签名时间和大小方面均优于NIST标准化的SPHINCS+方案，如表所示。
- 突破性：国内首个基于哈希的（无状态）后量子签名算法,仅依赖哈希函数(
椭圆曲线、格和编码、多变量)- 技术领先：性能优于美国 NIST PQC 定标的SPHINCS+ 算法
- 理论贡献和创新：给出了最优的消息编码方案（理论证明）
- 多种参数下：签名时间和大小均减少（验签时间增加约200%,但均小于4ms）
- 发表于美国密码年会 (CRYPTO 2023) [eprint]
美国NIST PQC第四轮候选签名算法 [点击查看]
- View on Gitee
ReSolveD——基于vole-in-the-head的后量子签名算法
ReSolveD是一种在随机线性编码的常规校验子解码（RSD）假设下的新的候选后量子签名方案，它是众所周知的校验子解码（SD）假设的一个完善的变体。该签名方案是通过设计一种新的零知识证明来证明对最近的VOLE-in-the-head框架中RSD问题解决方案的知识，使用sketching方案来验证向量的权重恰好为1。与最先进的基于编码的签名方案相比，该签名方案在常见的”签名尺寸+公钥大小”指标方面实现了1.5倍至2倍的改进，同时保持了计算效率的竞争力。与发表在美国密码年会的FEAST（Crypto 2023）在“签名尺寸+公钥大小”与算法耗时的比较如下表所示：
- 发表于国际公钥密码年会 (PKC 2024) [eprint]
- 原创性：国际首个基于vole-in-the-head的后量子签名算法
- 多样性：基于编码算法中的校验子解码（SD）困难问题
- 技术领先：耗时和尺寸方面优于国际优秀密码协议FEAST