|
全同态学习（i春秋课程https://www.ichunqiu.com/course/50441 课时二：基于格上最小整数解的密码研究）
一、平均困难问题之SIS
继续把格问题分解后，得到以下关系：
小整数解问题：给定 上的m个随机向量，find m个非平凡（不能同时为0）的解 in {-1,0,1}，使得图中式子成立。
注意：1.若 的值没有限制，则可以简单用高斯消元法求得。
2.可以用于构造非碰撞哈希函数
3.与格之间的关系：
格的表示方法：
构造防碰撞哈希函数：
所以，如果你能破解防碰撞哈希问题，就相当于破解了SIS。
二、高斯分布和格
1、高斯分布
一维：
二维：
N维：
重要的性质（当一维时）：
满足：若x取高斯分布，则对于所有m<M，x模m取的点都几乎是均匀分布的。（此时要使s=5M）
 
（当N维时：模的是平行多面体）
如何实现呢？先看简单的情况：
一般情况下呢：
证明：
视频看到43：07，先不看这集了。。。难。。
| 
转播
