PBKZ算法及其在格挑战中的应用

浏览次数： 12

分享到:

摘要:

格是欧氏空间R^n中的离散加法子群,格上的许多计算问题被证明是NP-hard,常用来作为公钥密码体制的底层困难问题.目前基于量子计算机模型的量子算法也难以高效求解格上的困难问题,因此后量子时代下格密码学受到了越来越多的关注.最短向量问题(Shortest Vector Problem,SVP)是格上的计算困难问题,格基约化算法是求解SVP问题的一个有效算法,该算法可以找到格中的一些短向量.YOSHINORI等人在2016年欧洲密码年会上提出Progressive BKZ算法,是目前格基约化算法中最为高效的算法之一.详细介绍了PBKZ算法,分析了它的运行机理及其内在特点,然后在Linux系统下成功调试了PBKZ算法库,并针对Darmstadt格挑战展开了一系列实验,最终在600维和725维两种情形下取得了目前国际上最好结果.

Lattice is a discrete addition subgroup in Euclidean space.Many computational problems in lattices have been proved to be NP-hard,so they can be used as the underlying difficult problems of cryptosystems.At the same time,quantum algorithms based on quantum computer models cannot efficiently solve difficult problems in lattices.Therefore,lattice-based cryptography has received more and more attentions in the post-quantum cryptography.The Shortest Vector Problem(SVP)is one of computational problems in lattices,and the lattice reduction algorithm is one of the effective algorithms for solving SVP problems.YOSHINORI et.al proposed the Progressive BKZ algorithm at Eurocrypt 2016,which is one of the most efficient lattice reduction algorithms.In this paper we first introduce the PBKZ algorithm detailedly,and then its operating mechanism and its inherent characteristics.Then we successfully debug the PBKZ algorithm library under Linux system.A series of experiments were carried out in response to the Darmstadt lattice challenge.Finally,the best known results were obtained in 600-dimension and 725-dimension respectively.

作者:

孙明豪屈龙江李超

Sun Minghao;Qu Longjiang;Li Chao(Department of Mathematics,National University of Defense Technology,Changsha 410073,China)

机构地区：

国防科技大学数学系

出处:

《betway官方app 学报：自然科学版》 CAS 北大核心 2020年第5期1-8,共8页

基金:

国家自然科学基金重点项目(11531002)。

关键词:

格格基约化算法 SVP问题 PBKZ算法 Darmstadt格挑战

lattice lattice reduction algorithm SVP problem Progressive BKZ Darmstadt lattice challenge