这一部分主要讲了格中平均困难问题SIS，高斯分布与格的联系以及如何将SIVP规约到SIS上。针对格，我只是站在一个研究者的角度去学习，并非为了能够套脚本做ctf题目，所以每个定理都尽可能去理解原理，可能记录的比较繁琐。
一.格中困难问题分类
| Average-Case | SIS | LWE |
|---|---|---|
| Worst-Case | SIVP | BDD |
二.SIS问题
1.Average-Case Problems——The Small Integer Solution(SIS) Problem
(1)definition
Given:Random vectors $a{1}$,…,$a{m}$ in $Z^{n}_{q}$
Find:non-trivial(非平凡，不全为0) solution $Z{1}$,…,$Z{m}$ in {-1,0,1} such that
注：
1.当不限定$Z_i$的范围的时候，可以用高斯消元法很快得到满足条件的值，限定Z取值以后这就成为了数学困难问题。
2.与格的联系：令S为所有使得$a{1}z{1}+…+a{m}z{m}=0modq$的整数向量z组成的集合，由于满足条件的向量的线性组合仍满足条件（封闭性），故整个集合构成了格。所以SIS的困难性可以理解为在格S中找到一个短向量（范数为1{-1，0，1}），这就和最短向量问题联系起来了。
(2)Collision-Resistant Hash Function
基于SIS可以构造出抗碰撞hash函数
类似于前边定义的SIS问题，我们只需要选定向量簇$a{i}$，然后将要做hash的message转为二进制，每一位分别对应$z{i}$的值，同时为了保证数据做hash被压缩，还需要有：
那么，针对这样的哈希函数，若找到碰撞，则可以找到$a{1}z{1}+…+a{m}z{m}=0$以及$a{1}y{1}+…+a{m}y{m}$，两者做差就得到了$a{1}(z{1}-y{1})+…+a{m}(z{m}-y{m})=0,z{i}-y{i} \in {-1,0,1}$，这说明要破解类似的hash函数等价于解决一个SIS困难问题…
2.Gaussian Distributions and Lattices
(1)高斯分布
一维高斯分布（经典正态分布）：
二维或多维高斯分布：每一维度的取值都分别满足一维高斯分布，然后将多维的概率相乘：
二维或多维高斯分布有一个非常好的特性就是每一个点取得的概率只和它离原点的距离有关，并且分布关于0点对称。
随机取一个一维高斯分布上的点（期望）到原点的距离仅比标准差小一点点。所以n维的高斯分布上的点到原点的距离约等于标准差乘$\sqrt{n}$。
(2)高斯分布的性质
a.多维高斯分布等于几个一维高斯分布表达式相乘
b.高斯分布关于原点对称
c.这个性质就是高斯分布和格的联系，有点复杂，参考知乎大佬的总结，这是关键部分：
备注：B的$\lambda{n}$值的意思是B中存在n个格向量，这n个格向量的长度都小于B的$\lambda{n}$值。
关于XmodC均匀分布有点抽象，做一些解释：
因为高斯分布的S大于5$\lambda_n$，而$\lambda_n$大于C(本质上是格)每个维度的格基，所以每个维度都满足均匀分布，故整个高斯分布也均匀分布。
总结一下就是这个：
3.Reducing a Worst-Case Lattice Problem to SIS
核心问题仅一个：SIVP——>SIS，如何规约?（给定一个格和随意的格基，用SIS算法找到更短的格向量）
1.首先要做的是，得到在平行多面体上均匀分布的点。
(1)首先将格点区域划分为更小的块，每个格点之间间隔了三块，每块的边缘用周期性数字表示，那么格点坐标全都是（0,0）。
(2)然后依据高斯分布采样，图中标为彩色的点。红色点$r_{i}$是随机选择的格点，在实际实验中，无法随机取到这样的随机点；我们依据高斯分布在红点附件采样点，可能满足高斯分布的点不在网格上，可以采用舍入的方式来把它放在网格上。
(3)background：all the samples are uniform in $Z_{q}^{n}$ ，q = 3 why?
- 选取高斯分布的参数为比5$\lambda_n$更大的值，由上述总结的定理可知我们选取的点在平行多面体中是均匀随机分布的。
- 而这里的平行多面体，就是$Z_{q}^{n}$，每个区域划分为3份，所以是q为3。
(4)我们不知道$\lambda_n$的值，但只要取S够大，规约算法就可以不断执行；不断减小S的值（二分法等），直到算法停止，那么就可以找到和$\lambda_n$近似的值。
2.将采样的点用SIS处理找到最短向量或近似值 参考
