随着量子计算的不断发展,针对大数分解难题和离散对数等困难数学问题,均出现了多项式时间的量子求解算法,因此,基于这些数学问题的公钥密码算法,如如RSA、ECC和DSA等标准算法,其安全风险日益增加,信息保密传输和网络通信安全受到极大挑战。为了研究和制定抗量子密码算法标准以应对量子计算带来的挑战,抗量子计算的困难数学问题,逐步成为密码学和计算代数的研究热点。由于格上的困难问题普遍被认为具有抗量子计算的性质,不存在多项式时间的量子求解算法,而且基于格上困难问题设计的密码算法往往还具有安全规约强、加解密高效等优势,因此,格上困难问题受到了广泛关注。作为格密码中最基本、最重要的计算问题之一,格上近似最短向量问题（Approximate Shortest Vector Problem,简称近似SVP）对分析和评估格密码体制的安全性具有非常重要的意义。一方面,格上最短向量问题具有较高的理论价值,大部分格上密码体制的安全性证明依赖于格上最短向量问题;另一方面,求解近似最短向量问题也具有较强的实践价值,近似最短向量问题的实际求解效率被用作格密码算法参数安全的评判标准。本文在研究分析近似SVP问题求解算法的理论和实践基础上,针对随机采样算法、离散剪枝算法和智能算法在近似SVP求解中的应用,进行了研究、改进和探索,主要工作包括以下三个部分:1.改进了一类随机采样约化算法,提出了有效可行的采样策略。随机采样约化算法近年来在SVP挑战中成绩很好,但还存在着理论基础不足、采样策略可行性较差的问题。本文利用格向量的“自然数表示”这一工具,结合启发式假设,证明了在特定的采样集合中自然数向量对应的格向量长度呈正态分布,并使用该定理在低维格上的近似结论提出了一种可行的类枚举的采样算法和其对应的参数选择策略,通过实验验证了该采样模型的准确度。在实际求解SVP挑战的实验中,通过对比不同采样策略,证明了本文提出的采样策略能够有效提高随机采样约化算法的求解效率,可行性较强;进一步,通过对比不同约化策略对算法求解效率的影响,说明了更强的格基约化算法能够提升随机采样约化算法求解近似SVP问题的效率。2.改进了用于求解近似SVP问题的离散剪枝枚举算法,并在实践中超过目前经典枚举算法的最优剪枝策略。格上带剪枝的枚举算法需要在不同格基上重复多次计算,经典枚举中的一般做法是简单地对格基进行重随机化并做LLL约化,策略简单,缺少优化。而对于离散剪枝枚举,其成功率和格基质量有着较大关联,因此本文针对离散剪枝枚举的重随机化过程,提出了三个改进策略:在由标签向量恢复格向量时,有技巧地修改标签的解码算法,保留一部分较短向量用于优化格基,同时将计算开销降低到最小;用格基的G-S平方和衡量格基约化质量,通过控制重随机化的过程以保证G-S平方和单调不增;引入One-tour BKZ算法对格基进行约化,充分平衡格基约化质量和约化效率。该算法相比经典枚举算法的各种剪枝策略有大幅的效率提升,并且超过了经典枚举算法中效率最优的剪枝策略——极值剪枝,而极值剪枝正是目前用于分析密码体制安全性的重要工具——BKZ2.0算法的子算法。3.探索了遗传算法在求解近似SVP问题中的应用,实现了一种用于求解近似SVP问题的遗传算法。遗传算法等智能算法在SVP求解中的探索应用较少,且结合方式平凡,因此效率不高。本文提出了基于自然数表示向量的染色体编码算法,将格向量编码成染色体,并定义了染色体交叉、变异等基本的基因操作;在算法的进化机制设计中,一方面,结合格上SVP求解需要利用正交基信息进行大量浮点计算这一特质,适当地简化了自然选择中的浮点计算过程,采用了基于排序选择的精英策略;另一方面,为了防止算法陷入局部最优,引入了遗传算法中的重启机制,即对格基进行重随机化。实验说明引入重启机制的遗传算法相比经典遗传算法的策略,能够更有效地提升近似SVP问题求解效率,且算法效率远高于经典枚举算法和线性剪枝枚举算法,并且与目前已知公开的最优枚举算法——极值剪枝枚举算法效率相近。本文研究工作紧扣当前密码学界研究热点,丰富了求解近似SVP问题的理论和实践成果,相关成果可以为格上密码体制设计、参数选取和安全评估等提供技术支撑,具有重要的学术理论意义和现实应用价值。