高等研究院师生获得国际密码学会

2023年亚密会最佳论文奖

2023年12月5日，由国际密码学会（International Association for Cryptologic Research，IACR）主办的2023年亚洲密码会议（ASIACRYPT，简称亚密会）在中国广州顺利开幕，来自全球10多个国家和地区的500多名科学家、研究人员和工业界人士参会，创下了亚密会的参会人数新纪录。亚密会（ASIACRYPT）是国际密码研究协会（IACR）主办的年度国际会议之一，与美密会（CRYPTO）、欧密会（EUROCRYPT）一起被列为国际密码学领域的三大会议。

本届大会共收到来自全球的376篇投稿论文，刷新了历年亚密会论文投稿数量的记录，最终录取论文106篇。大会最终评选出两篇最佳论文奖，其中一篇全部由清华大学王小云院士团队完成，作者包括高等研究院教师王安宇（通讯作者）、喻杨和王小云，研究生江锴杰，罗横溢和刘国霄；另外一篇是王小云院士团队骨干成员喻杨（通讯作者）跟2位国际密码专家Thomas Espitau, Alexandre Wallet合作完成。两篇最佳论文是由于在后量子密码算法设计与后量子密码数学难题等价性证明的杰出贡献而获此荣誉。

1994年，Peter Shor提出了可在多项式时间内完成大整数分解的量子算法，这标志着已被广泛使用的RSA公钥密码算法在真正的量子计算机算力下将不再安全。尽管目前的量子计算机进展还未能够影响实际应用中的RSA的安全性，但抗量子计算机攻击的公钥密码已经在国际密码领域提前部署并成为目前以及未来较长时间内国际主流密码研究方向。早在2006年，王小云院士就带领团队转向最有潜力的抗量子计算攻击的密码领域——高维格密码的研究。在国家973和国家重点研发计划等项目支持下，团队从抗量子计算机攻击的基础数学难题入手，攻坚克难，通过十多年的积累，取得了多项国际同行认可的工作，特别是在高维格密码设计理论与高维格数学难题SVP等研究方面取得了系列优秀成果。美国国家标准与技术研究院（NIST）于2016年启动了在全球征集第一批后量子密码标准的评选工作，在6年的标准竞赛过程中，后量子密码算法的实用化设计水平有了较大提升，国际三大密码会议总计发表了7个后量子实用化算法。其中清华大学喻杨以通讯作者与国际专家合作设计了MITAKA签名（EUROCRYPT 2022）、提出安全而高效的格签名设计技术（CRYPTO 2022），以第一作者提出紧致gadget陷门技术（CRYPTO 2023），以上3个格密码算法设计工作在安全性与有效性等方面综合指标均到达国际领先水平。

本次亚密会最佳论文“Exploiting the Symmetry of Zⁿ Randomization and the Automorphism Problem” 针对整数格 (即同构于Zⁿ 的格) 提出了一种随机化的归约框架，并得到了一系列全新的归约结果。本工作证明了在随机归约的意义下，求解整数格与Zⁿ之间的同构与求解一个整数格的非平凡自同构是等价的，揭示了整数格的高度对称性与其计算困难问题之间存在着深刻的内在联系。此外，本工作还首次证明了整数格最短向量问题与最短特征向量问题的等价性、最短向量问题与常数因子最短向量问题的等价性等结果。本工作拓展了人们对于整数格计算困难问题的认知，并为格的随机归约提供了新颖的理论工具。

本次亚密会最佳论文“On Gaussian Sampling, Smoothing Parameter and Application to Signatures” 系统研究了格上高斯采样。高斯采样是格密码核心算法组件，在格密码算法设计、格困难问题归约中有重要应用。通过分析一般格扩张和线性变换作用下格上高斯测度的性质，本文对Klein-GPV采样算法和Peikert采样算法这两类高斯采样主流技术路线分别做了扩展，提出了短正合列采样（short exact sequence sampler）和线性变换采样（linear sampler）两类通用算法框架。基于级数反演，给出格光滑参数新的估计公式，揭示了格光滑参数与其对偶格吻合数和最短非零向量长度的数量关系。在此基础下，针对根格、Leech格、Barnes-Wall格等几类特殊格结构，设计了专属采样算法，实现高效、高质量的采样。通过将上述结果应用到格密码算法设计，进一步提升了Yu-Jia-Wang陷门体制（CRYPTO 2023）和Mitaka签名算法（EUROCRYPT 2022）的参数尺寸和安全强度。本工作丰富了格上高斯采样和高斯测度理论结果，为格密码设计提供了高效算法支撑和新的设计思路。