导　　师： 陈剑勇;王平

授予学位： 硕士

作　　者： (）;

机构地区： 深圳大学

摘　　要： 随着信息时代的快速发展,信息安全问题与我们密切相关,因而密码学逐渐成为人们日益关注的焦点。数据的安全性与保密性是密码技术的核心要素,而格基规约算法是密码学中核心要素的重要体现,它是一种典型的密码学分析技术。当前,LLL(Lenstra,Lenstra,Lovasz)是最经典的格基规约算法。而以LLL算法为基础的变体数不胜数,其目的都是为了优化。格基规约算法具有广泛的应用,例如:数论,整数规划,丢番图逼近以及密码学等方面。而本文主要从优化格基规约算法、用规约思想来初始化参数去解决球译码算法、格理论在0-1整数背包中的应用以及背包算法的并行化方面来阐述,具体内容如下:(一)格基规约是求解格中非零近似最短向量的问题,著名的LLL算法可在多项式时间内求解出可证明的约减基。l次规约是LLL算法的变体,有着更高质量的约减基,但是运行时间大幅度增加。而分块LLL规约则是约减基略差但运行时间减少明显的算法。因此,本文提出在分块LLL规约中加入l次规约的思想。有效汲取二者的优势,生成分块l次规约算法,其在时间-质量方面可达到相对权衡。(二)球译码算法是解决整数最小二乘问题的有效方法,而球译码算法的关键问题是搜索空间中初始化半径的选择。论文首先提出利用阿达玛比率选取一组高质量的基;其次提出用QR(orthogonal matrix,upper triangular matrix)分解,LLL优化规约以及带预测技术的宽度优先搜索算法K-Best(BFS+PEDS)叠加的方式来约减所选取的一组基;最后再利用球译码算法来求解,其过程等价于在格中求解最近向量问题。(三)背包问题是一个NPC(non-deterministic polynomial complete)问题,同时也是经典的组合优化问题。利用(一)中优化规约算法来提高密码分析的效率,缩短密码分析的时间。规约算法同样可应用在基于格的背包密码系统的分析上。为了

关 键 词： 格基规约 规约 分块规约 球译码算法 背包问题

领　　域： []