毕 蕾,路献辉,3,王鲲鹏

1.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 100093

2.中国科学院大学 网络空间安全学院,北京 100049

3.密码科学技术国家重点实验室,北京 100878

1 引言

格密码近年来广受关注.由于量子计算机的迅速发展,一些经典模型下的困难问题在量子计算环境下变得可以被有效求解.如果大规模的量子计算得以实现,现有的公钥密码安全将受到巨大的威胁和挑战.因此,许多国家的政府和研究机构已逐步发起了在量子计算模型下安全的公钥密码算法,即后量子公钥密码的研发工作.格密码由于在安全性、公私钥尺寸、计算速度上的优势,以及抵抗量子攻击的能力,是其中最受瞩目的类型之一.2020年,NIST后量子密码算法标准征集的第三轮7个方案中有5个是基于格构造的,格密码在未来有望替代RSA等现行公钥密码算法成为新一代的公钥密码标准.

格理论最初在密码学中是一种分析工具,曾被用于分析背包密码体制、RSA密码体制等[1,2].1996年,Ajtai[3]开创性地给出了格中唯一最短向量问题(unique shortest vector problem,uSVP)在worstcase下到小整数解(small integer solutions,SIS)问题在average-case下的归约证明,即这些困难问题在最坏情况下的困难性可以归约到一类随机格中问题的困难性,因此基于格的密码体制可以提供最坏情况下的可证明安全性.

1997年,Ajtai-Dwork[4]首次将其作为一种设计工具,构造了第一个具有可证明安全的基于格的公钥密码体制AjtaiDwork,该方案的安全性基于格上唯一最短向量问题(unique shortest vector problem,uSVP)的困难性.此外,初期的……