admin管理员组

文章数量:829161

格密码LLL算法:如何解决最短向量SVP问题(1)

目录

前言

一. LLL算法的应用

二. 格基约化

总结


前言

在本节中,提出一个解决最短向量(SVP)问题的算法。在1982年,A.K.Lenstra,H.W.Lenstra,Jr和L.lovasz提出一种解决SVP问题的算法,通常称之为LLL算法。

在1801年,Gauss曾给出一个解决二维空间的SVP算法。某种意义上,LLL算法可以看成解决多维空间SVP问题的算法。在1987年,Schnorr改进过LLL算法,将计算复杂性改进到。

一. LLL算法的应用

1. 在整数和有理数的范畴内,分解多项式。

2. 找到多项式方程足够精确的代数解。

3. 确定线性关系。给定实数集合,如果能找到一个整数集合,使得,其中不全为0,则称此实数集合满足整数关系。

4. 整数规划。整数规划属于典型的NP完全类问题,对于有限变量数量的整数规划问题,LLL算法可以在多项式时间内输出最优解。

5. 可规约到格的另一个基本问题:最近向量问题(CVP)。

6. 在密码分析中应用广泛,例如攻击密码协议。LLL算法可以攻击基于背包向量的密码系统,以及攻击基于低公共指数的RSA系统。

例1:如将分解成和。

例2:如的输出解为1.414213,的输出解为0.645751。

例3:如,确定的整数关系。经过LLL算法可输出:(此等式又被称为Machin 公式)。

为了方便分析,后续统一讨论在满秩格以及l2正则下的LLL算法。为了全方位了解LLL算法,可以分为以下三个部分:

1. 定义LLL格基约化;

2. 确定格基约化算法;

3. 分析运行时间;

二. 格基约化

在求解SVP问题时,最先想到的就是对格基的多种线性组合尝试,其中最难的部分就是让两个坐标同时变小,如下图:

首先需要Gram-Schmidt正交化知识的铺垫。

定义1

给定n个线性独立的向量,对的Gram-Schmidt正交化过程定义为:

                      

正交基不改变基本区的面积,而且当基向量比较接近时长度最短,如下图:

定义2 格基约化需满足如下两个条件:

LLL算法最终输出的基称为LLL约化基。

格基约化性质(1) 总存在算法能实现格基约化。

格基约化性质(2)是该算法的一个特例,LLL算法成立的前提条件。

格基约化性质(3)

根据LLL约化基的定义可得:

由于与 相互垂直,可得:

由此可得不会比短太多。

格基B在经过正交化处理后,可以看成如下:
 

LLL约化基的定义保证了上三角的值不到同行的一半,由此可将上述矩阵改为:

从相邻基向量的长度关系推导,以矩阵为例,可得如下:

Schnorr就在此矩阵的基础上。类推到矩阵(k>2)。

总结

格密码作为抗量子密码的候选算法之一,在欧美布局已久,成果丰富,国内起步较晚,目前缺乏对本领域的创新性贡献。

2012年美国NIST立项后量子密码标准项目,计划2024年推出产业标准;

2015年欧盟地平线科技2020计划抗量子旗舰项目,整合欧盟力量参与NIST标准竞选;

欧盟联合组队,在国际抗量子密码算法竞赛中遥遥领先。

本文标签: 格密码LLL算法如何解决最短向量SVP问题(1)