格密码学简介(第1部分)

扫码链接5000+新基建产业链上下游从业者,入群请备注“机智地+姓名+公司+岗位

什么是格?

在数学中有两个完全不同的对象都称为格,我们现在说的格是定义为向量空间的离散子空间。在此,离散意味着在格中不能存在任意彼此接近的两个向量。换句话说,存在一个正实数λ,使得格中的任何两个向量都不能小于距离λ。

子空间一词告诉我们,如果您的格中有两个向量,那么你可以几何地从另一个向量中减去另一个,而最终的位置将是格中的另一个向量。这意味着零向量始终在格中。

在视觉上,二维的格看起来像这样,每个点不是连续的,而是离散的:

格密码学简介(第1部分)

距离产生美,格是具有很好性质的数学对象,因为它们可以用相对少量的数据来描述。通常使用的描述是给出格的基,基是由若干向量组成的。通过这些基础向量的整数线性组合来生成所有其他点。

每个格都有一个基,但它远不是唯一的,实际上每个格都有无限的数量,而且并不是所有的格都一样好用。回到我们的示例格,我们可以添加一些基,在这种情况下是向量对:


格密码学简介(第1部分)

格密码学简介(第1部分)

直观上,我们可以注意到蓝色和绿色的基向量比黄色或紫色的基向量要好看(向量比较短)。实际上,使用短向量意味着使用较少的存储来描述格。在二维空间中,求短向量并不是一个困难问题,可以使用Lagrange算法求短向量。但是随着维数的增加,在随机给出一个基的情况下,求解该问题将会变得非常困难。

格上的基本问题

这引出了格中的第一个基本困难的问题,即最短向量问题(SVP)。给定格的一个基,问题就是在格中找到一个非零向量,该向量的长度在所有非零格向量上最短。

再重复说一遍,必须找到一个长度为的向量,其中是λ的最大可能值,λ可以对上面所述的离散性进行解释。众所周知,对于随机归约来说,这个问题是NP困难问题(非确定性多项式困难问题)。

由于这个问题非常困难,自然要考虑这个问题的一个放宽问题,即近似最短向量问题。所谓近似问题,就是并不准确求出该问题,而是某一范围内。

这里,给了一个近似因子γ,只需要在长度不超过γ的格向量中找到一个非零向量。

在密码学中,人们经常考虑是多项式格维数范围之内的近似因子γ。目前已知最好的多项式时间内求解近似SVP问题的算法,其近似因子都是亚指数格维数范围内。也就说求解出的向量长度并不短,尽管在有限时间内。反之,如果你想求解出多项式格维数范围之内的近似因子γ,即求解出长度不超过γ的格向量中找到一个非零短向量,其求解时间将不是多项式时间了。

其实密码学家更感兴趣的是判断问题。下一期将解释该问题。

声明: 本文由入驻基智地平台的作者撰写,观点仅代表作者本人,不代表基智地立场;基智地发布此信息的目的在于传播更多信息,与本站立场无关。

发表评论

邮箱地址不会被公开。 必填项已用*标注