格上筛法研究现状与发展趋势

摘要：

最短向量问题(shortest vector problem,SVP)是格上的基础困难问题之一,是格密码方案安全性的基础假设,SVP求解算法是评估格密码算法具体安全性的关键技术.实用的SVP精确求解算法主要包括筛法和枚举两种类型,其中筛法的时间复杂性更低,是目前实用化格密码算法安全性评估主要使用的算法.筛法由Ajtai-Kumar-Sivakumar于2001年首次提出,其主要思想是将指数多个格向量通过一系列的筛取过程,互相约化,以得到一定数量的长度为O(λ1)的格向量,然后将这些向量两两相减以得到最短非零格向量,其中λ1表示格中最短非零向量长度.二十年来,研究者们不仅在理论上对筛法进行研究和改进,同时也给出了一系列在实际应用中更为高效的启发式算法.针对筛法中复杂度最高的部分,即约化时遍历指数多个格向量的过程,研究者们使用了多种技术对其进行改进,包括生日悖论、局部敏感技术、层次化、元组化、线性化等.本文按照技术发展及时间顺序介绍了格上筛法的发展历史、研究现状和将来的发展趋势.

关键词：格;最短向量问题;筛法

所属期刊栏目：8

分类号：TP309.7(计算技术、计算机技术)

资助基金：密码科学技术国家重点实验室开放课题;国家自然科学基金

在线出版日期：2021-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共23页

页码：735-757