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

发布时间：2021-10-24 00:34

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

【文章来源】：河南师范大学学报(自然科学版). 2020,48(05)北大核心

【文章页数】：8 页

【文章目录】：
1 基础知识
    1.1 格的基本概念
    1.2 格上求解困难问题
    1.3 格基约化算法
        (1)LLL算法
        (2)BKZ算法
2 PBKZ算法
    2.1 算法主要流程
    2.2 主要技术改进
        2.2.1 分块策略的最优选取
        2.2.2 枚举算法中参数的最佳选取
        2.2.3 终止策略
3 算法实现及格挑战实验
    3.1 Darmstadt格挑战
    3.2 实验及结果
4 总结及展望


【参考文献】：
期刊论文
[1]格密码学研究[J]. 王小云,刘明洁.  密码学报. 2014(01)



本文编号：3454221