👻格密码3-格中计算困难性问题1
2023-7-26
| 2023-7-27
0  |  0 分钟
type
status
date
summary
password
category
slug
icon
👆
接着上一篇继续写,格中计算困难性问题
 

🧐最短距离

除了行列式,格的另一个基本量是格上最短非零向量的长度,即格中最短距离,其定义为
notion image
notion image
 
如图,两两格点构成的向量都可以通过平移得到起始点为原点的向量,通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小,记为1
同理可定义第二至第n连续极小,2,3……n
⛈️
在二维格上,可以用多项式时间算法求解出1,但在多维格上求解1则十分困难。注意,给定一组格基,最短向量不一定是格基之一

🤩距离函数(Distance Function)

给定任意一个点t(这个点不需要在Lattice上),我们可以定义距离函数为这个点到附近的Lattice点的最短距离。
notion image

🫣覆盖半径(Covering Radius)

左右移动t的位置,然后就可以找到在这个Lattice中可以得到的最大的。我们一般称这个最大值叫覆盖半径(Covering Radius)
notion image
✌️
假设在这个Lattice中,以每个格点为圆心画很多个圆,
如果逐渐把圆的半径扩大的话, 那么所有的圆就会逐渐开始覆盖整个空间
notion image

🥀格的平滑参数

如果在每个格点上叠加一个圆形范围内取值的随机噪音(生成一个随机值,将这个随机值与圆形范围内的所有格点元的半径相加或替换),那么当圆的半径达到覆盖半径之后,这个Lattice本身就和背后的连续空间合二为一了

浅浅理解高斯平滑的作用:

缩小r的值,半径对应的向量的每个分向量仅略大
notion image

为什么要用到平滑参数?

实际上,平滑参数只是定义了一个临界值,当格上的离散高斯分布的标准方差大于此参数时,那么从此分布中选取的点在模格的单元平行多面体中后,几乎将服从均匀随机分布,而当小于此参数时,则不服从均匀随机分布。

🥹Lattice的几何构造

❓为什么要构造

最简单的笛卡尔坐标系整数格,其基向量都是相互垂直的(orthogonal basis),如果我们可以把一个任意的LatticeΛ转换为一个垂直基的格,那么可以更方便简单的在几何空间分析格,比如找到一个格中一个距离t(随意给定的目标值)最近的非零向量v,将其转化为几何空间,只需要通过上下取整,就可以快速找到。

📑如何构造

把一个Lattice的基进行变换,找到一组非常接近垂直的基的,这一过程称之为Lattice Basis Reduction。
比较常见的Basis Reduction方法是Gram-Schmidt正交化过程
⛈️
回忆上一篇提到n维空间得到一组基
notion image
notion image
 

📑Lattice Rounding(取整)问题

刚刚Lattice的几何构造提到一个例子,“找到一个格中一个距离t(随意给定的目标值)最近的非零向量v,将其转化为几何空间,只需要通过上下取整,就可以快速找到”
那如何取整呢??
notion image
⛈️
👉,那么我们通过取整操作就能解决 👉如果落点在外圈圆的话,那么很有可能就会被取整到隔壁的格点上去,那么那个点就不是最近的了
 

🤔格中计算困难性问题

  • 最短向量问题 (Shortest Vector Problem,SVP)
  • γ-近似最短向量问题 (SVP-γ)
  • 连续最小长度问题 (Successive Minima Problem, SMP):
  • 最短线性无关向量问题 (Shortest Independent Vector Problem, SIVP)
  • 唯一最短向量问题 (Unique Shortest Vector Problem, uSVP-γ)
  • 最近向量问题 (Closest Vector Problem,CVP)

👇👇👇👇👇

✍️最短向量问题 (Shortest Vector Problem,SVP)

⛈️
给定格L及其基向量B,找到格L中的非零向量v使得对于格中的任意其它非零向量u,
notion image

γ-近似最短向量问题 (SVP-γ)

⛈️
给定格L,找到格L中的非零向量v使得对于格中的任意其它非零向量u,
notion image
时,就有多个结果啦

最短线性无关向量问题 (Shortest Independent Vector Problem, SIVP)

⛈️
定一个秩为n的格L,找到格L中n个线性无关向量 ,满足
就是找到格中n个向量,这n个向量全都小于格中最长向量
 

连续最小长度问题 (Successive Minima Problem, SMP)

⛈️
给定秩为n的格L,找到格L中n 个线性无关向量 ,满足 
 
 

唯一最短向量问题 (Unique Shortest Vector Problem, uSVP-γ)

 
⛈️
给定格L及其基向量B,找到格L中的非零向量v使得对于格中的任意其它非零向量u,
 

✍️最近向量问题 (Closest Vector Problem,CVP)

⛈️
给定格L和目标向量 ,找到一个格中的非零向量v,使得对于格中的任意非零向量 u,满足.
 
 
 

📎 参考文章

 
⛈️
我爱密码!!!!爱格密码!!! 🥲😅😥🤐🙃😖😭 今天半只脚踏进去了……接下来做题去,小师傅给滴,他说很简单,不知道我会不会难哭,浅浅不期待🫣
日常学习
格密码2格密码1
目录