学院新闻

网安学院谷大武团队成果打破格密码LWE Challenge的世界纪录

时间:2022年2月24日 | 来源:网络空间安全学院 | 作者:王更

近日,网安学院谷大武教授领导的LoCCS实验室密码理论与算法小组成功破解了80维的LWE问题公开挑战,创造了格密码中新的困难问题求解世界记录。这一结果是谷大武教授指导的博士生夏雯雯和助理研究员王更博士等在后量子密码基础问题研究的最新进展,这一新记录已公布在格密码挑战的官方网站Learning With Errors(LWE) Challenge上。

格密码是后量子密码中最引人注目的主流公钥密码,有望成为量子计算时代公钥密码算法的主要代表,因而得到了世界各国密码学家的大量关注。自2005Regev提出LWElearning with errors,容错学习)问题以来,LWE问题一直在格密码的设计中占据着核心地位。当前主流的格密码方案,其安全性大多是归约到LWE问题及其变种RLWEMLWE等问题的困难性,并可通过LWE问题求解算法进行破解。因此,LWE问题的困难性和求解算法对格密码算法的标准化和现实应用至关重要。

当前,对LWE问题的最佳求解算法,大致可分为使用BKZ算法的格基优化阶段和使用筛法的最终求解阶段。BKZ算法对格基的优化程度决定了筛法求解的时间效率,直接影响到LWE问题是否可以成功求解。谷大武教授团队的工作提出了新的格基优化方法和策略,效果与当前国际上最好的求解算法相比有了实质性提升,从而刷新了LWE问题的求解记录。

格密码挑战(latticechallenge.org)由荷兰埃因霍温理工大学、美国加州大学圣迭戈分校和德国达姆斯塔特工业大学联合举办,是目前国际上最具公信力的格问题求解挑战。在LWE问题的求解方面,之前的记录自20189月以来一直由英国、荷兰、法国等欧洲密码学家组成的团队所保持。这也是两年多以来第一次在LWE问题上有新的记录诞生,这项工作由我校谷大武教授团队发起和牵头,参与者还有西安电子科技大学王保仓教授及其博士生王镭璋。

LoCCS实验室是信息安全与密码研究所(IISeC)的核心单位,也是国家密码管理局批准的商用密码检测(上海)中心的主要支撑单位,近期又受邀参加ATHENa项目中的轻量级密码(LWC)侧信道安全评估。后量子密码是LoCCS的主要研究方向之一,该实验室重点关注后量子密码的基础困难问题求解、算法设计与安全证明、典型算法安全分析、软硬件实现及侧信道分析评估、密文计算与隐私保护方案设计等,已经在CRYPTO、EUROCRYPT、CHES、PKC、USENIX Security、ACM CCS发表了系列论文,拥有一支朝气蓬勃、努力勤奋的优秀青年教师和博士生、硕士生科研队伍。

Copyright © 2017 - 2019 上海交通大学网络空间安全学院 沪ICP备05052060号