Lattice learning-4
Lattice learning-4 格归约算法 这一节我们会介绍LLL算法（终于到了）。在维度较小的情况下，LLL算法可以解决SVP以及CVP，但是当维度很大的时候，LLL算法就无能为力了。而现在基于格的密码系统的安全，就是建立在一系列格归约算法无法有效的解决apprSVP以及apprCVP之上的。 我们先说说二维的高斯格归约算法。 下面是实现代码 fr…
Tag
#Lattice
Lattice learning-3
Lattice learning-3 Lattice 学习记录 卷积多项式环 在介绍NTRU公钥密码体系之前，我们需要一些数学知识的铺垫。 定义：给定一个正整数N，卷积多项式的环（秩为N）是商环 同样的，卷积多项式的环（模q）是商环 我们知道，对于或都有可以写成的形式，而其中的系数分别在或中。而我们对取模，是为了更简单的运算，把高次项（指数大于N）化…
Lattice learning-2
Lattice learning-2 Lattice学习记录 格中的短向量 格中有两个基本问题 最短向量问题（SVP）： 在格中寻找一个向量，使它的长度最小。 最接近向量问题（CVP）： 给定一个向量，在格中寻找一个向量，使得最小。 当然这两个问题都可能有多解，从二维的平面坐标我们就可以知道这个事情。不过这两个问题，随着维度的变大，计算也就越困难…
Lattice learning——1
Lattice learning-1 Lattice学习记录 Intro 开始学习格密码（寒假学过，但是忘了，而且不会用，坏起来了）。这次学习主要参考《》，也会参考一些师傅的博客。 我们先来了解一个真实公钥密码系统中的一个简单模型。它的维度很低，不过说明了密码分析中如何出现格。此外，它还提供了对NTRU公钥密码系统的最低维的介绍。 选择了整数作为mod，选…