格密码学习（三）
今天在youtube上看了一个lecture巩固了一下
- A lattice may be represented as a matrix whose row vectors form the
basis - A lattice has many bases
格的基底并不是唯一的。正是因为一个格有多组格基使得格密码得以存在。一个整数矩阵是幺模的当这个矩阵的行列式为±1。
幺模
如果 A∈R是整数矩阵，r≡rank A=min{m，n}，而且A的所有非零r×r子式等于 1 或-1，则称A为幺模矩阵(unimodular matrix)。如果A是幺模矩阵，而且还有其各阶子式均等于0，1或-1，则称A为全幺模矩阵(totally unimodular matrix)。
引理
基底
B
1
B_{1}
B1,
B
2
B_{2}
B2生成相同的格
L
\mathcal{L}
L当且仅当存在一个幺模U∈
U
∈
Z
n
×
n
\mathbf{U} \in \mathbb{Z}^{n \times n}
U∈Zn×n使得
B
1
=
B
2
U
\mathbf{B}_{1}=\mathbf{B}_{2} \mathbf{U}
B1=B2U
证明
假设
L
(
B
1
)
=
L
(
B
2
)
\mathcal{L}\left(\mathbf{B}_{1}\right)=\mathcal{L}\left(\mathbf{B}_{2}\right)
L(B1)=L(B2)，或者
B
1
⋅
Z
n
=
B
2
⋅
Z
n
\mathbf{B}_{1} \cdot \mathbb{Z}^{n}=\mathbf{B}_{2} \cdot \mathbb{Z}^{n}
B1⋅Zn=B2⋅Zn，则
B
1
B_{1}
B1的每列都是
B
2
\mathbf{B}_{2}
B2的一个整数组合。反之亦然。也就是说，存在
U
,
V
∈
Z
n
×
n
\mathbf{U}, \mathbf{V} \in \mathbb{Z}^{n \times n}
U,V∈Zn×n使得
B
1
=
B
2
U
\mathbf{B}_{1}=\mathbf{B}_{2} \mathbf{U}
B1=B2U并且
B
2
=
B
1
V
=
B
2
U
V
\mathbf{B}_{2}=\mathbf{B}_{1} \mathbf{V}=\mathbf{B}_{2} \mathbf{U} \mathbf{V}
B2=B1V=B2UV。因为
B
2
\mathrm{B}_{2}
B2是可逆的，因此我们有
U
V
=
I
\mathbf{U V}=\mathbf{I}
UV=I，因此
det
(
U
)
det
(
V
)
=
1
\operatorname{det}(\mathbf{U}) \operatorname{det}(\mathbf{V})=1
det(U)det(V)=1行列式U和行列式V相乘为1.那么行列式U和行列式V为正负一因为两个矩阵都是整数矩阵。
那么，假设对于某个幺模U存在
B
1
=
B
2
U
\mathbf{B}_{1}=\mathbf{B}_{2} \mathbf{U}
B1=B2U，那么我们就可以得到这个公式：
L
(
B
1
)
=
B
1
⋅
Z
n
=
B
2
⋅
(
U
⋅
Z
n
)
=
B
2
⋅
Z
n
=
L
(
B
2
)
\mathcal{L}\left(\mathbf{B}_{1}\right)=\mathbf{B}_{1} \cdot \mathbb{Z}^{n}=\mathbf{B}_{2} \cdot\left(\mathbf{U} \cdot \mathbb{Z}^{n}\right)=\mathbf{B}_{2} \cdot \mathbb{Z}^{n}=\mathcal{L}\left(\mathbf{B}_{2}\right)
L(B1)=B1⋅Zn=B2⋅(U⋅Zn)=B2⋅Zn=L(B2)推论：
Z
n
\mathbb{Z}^{n}
Zn的基底正好是幺模矩阵
U
∈
Z
n
×
n
\mathbf{U} \in \mathbb{Z}^{n \times n}
U∈Zn×n。
推论：通过检查
B
1
−
1
B_{1}^{-1}
B1−1,
B
2
B_{2}
B2是否是幺模的。
格里面的一个重要概念
Fundamental Regions
格是在
R
n
R^n
Rn下的无线周期网格，因此考虑相应的定期“平铺”Rn由某物体的副本通常很有用。例如，考虑一下墙面砖的典型平铺（到棋盘格），或通过正六边形（以格点为中心）对平面进行平铺。基本区域的概念使这一概念正式化。
定义 集合
F
⊆
R
n
\mathcal{F} \subseteq \mathbb{R}^{n}
F⊆Rn是格
L
\mathcal{L}
L一个fundamental region，如果他的变换
x
+
F
=
{
x
+
y
:
y
∈
F
}
\mathrm{x}+\mathcal{F}=\{\mathrm{x}+\mathrm{y}: \mathrm{y} \in \mathcal{F}\}
x+F={x+y:y∈F}，取所有的
x
∈
L
\mathrm{x} \in \mathcal{L}
x∈L，组成
R
n
\mathbb{R}^{n}
Rn的部分。
** fundamental parallelepiped**
两个关于格的计算问题
1、SVP(shortest vector problem)
2、CVP(closest vector problem)格有好的与坏的基底
A lattice basis with reasonably short and orthogonal basis vectors is normally referred to as a ‘good basis’. On the contrary, a lattice basis with long and non-orthogonal basis vectors is normally referred to as a ‘bad basis’.
好的基底: 具有合理短和正交基向量的格基通常被称为好的基底
坏的基底:具有长且非正交基向量的格基称为坏基底
补充知识：正交向量的概念是只积为0的两个或多个向量
SVP算法
- LLL（Lenstra，Lenstra& Lovasz, 1982）
格维度内的多项式时间
保证能找到一个向量不大于实际最短向量倍数的向量
在低维度里，能找到非常短的向量
在高维度中找非常短向量是指数级别难度的
The LLLalgorithm was used to “break” cryptosystem based on Subset Sum (knapsack) problem, at practical dimensions.
LLL算法用于在实际规模上基于子集和（背包）问题“**”密码系统。
背包问题（现代密码学课程学过）
it is probably prudent to assume that shortest non-zero vectors in lattices can be found efficiently
LLL算法就是在格上找到一组基，使得
用这种方法生成的基具有如下性质：
Application
给定n个实数
α
i
,
…
,
α
n
\alpha_{i}, \ldots, \alpha_{n}
αi,…,αn，找到这n个数的有理线性逼近，即找到n个数
m
i
m_{i}
mi，使得
∑
i
=
1
n
m
i
α
i
\sum_{i=1}^{n} m_{i} \alpha_{i}
∑i=1nmiαi尽可能等于0。我们可以构造这样的矩阵，这里
m
i
m_{i}
mi是
α
i
\alpha_{i}
αi的有理逼近
A
=
[
1
0
0
⋯
0
c
a
1
0
1
0
⋯
0
c
a
2
0
0
1
⋯
0
c
a
3
⋮
⋮
⋮
⋱
⋮
0
0
0
⋯
1
c
a
n
]
A=\left[\begin{array}{cccccc}1 & 0 & 0 & \cdots & 0 & c a_{1} \\ 0 & 1 & 0 & \cdots & 0 & c a_{2} \\ 0 & 0 & 1 & \cdots & 0 & c a_{3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & c a_{n}\end{array}\right]
A=⎣⎢⎢⎢⎢⎢⎡100⋮0010⋮0001⋮0⋯⋯⋯⋱⋯000⋮1ca1ca2ca3can⎦⎥⎥⎥⎥⎥⎤
那么
A
A
T
=
[
1
+
a
1
2
a
1
a
2
a
1
a
3
⋯
a
1
a
n
a
2
a
1
1
+
a
2
2
a
2
a
3
⋯
a
2
a
n
a
3
a
1
a
3
a
2
1
+
a
3
2
⋯
a
3
a
n
⋮
⋮
⋮
⋱
⋮
a
n
a
1
a
n
a
2
a
n
a
3
⋯
1
+
a
n
2
]
A A^{T}=\left[\begin{array}{ccccc}1+a_{1}^{2} & a_{1} a_{2} & a_{1} a_{3} & \cdots & a_{1} a_{n} \\ a_{2} a_{1} & 1+a_{2}^{2} & a_{2} a_{3} & \cdots & a_{2} a_{n} \\ a_{3} a_{1} & a_{3} a_{2} & 1+a_{3}^{2} & \cdots & a_{3} a_{n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n} a_{1} & a_{n} a_{2} & a_{n} a_{3} & \cdots & 1+a_{n}^{2}\end{array}\right]
AAT=⎣⎢⎢⎢⎢⎢⎡1+a12a2a1a3a1⋮ana1a1a21+a22a3a2⋮ana2a1a3a2a31+a32⋮ana3⋯⋯⋯⋱⋯a1ana2ana3an⋮1+an2⎦⎥⎥⎥⎥⎥⎤
可以得到格的行列式为
1
+
∑
i
=
1
n
α
i
2
\sqrt{1+\sum_{i=1}^{n} \alpha_{i}^{2}}
1+∑i=1nαi2
证明如下
经过LLL算法后，可以获得
∥
b
1
∥
≤
2
n
−
1
4
(
1
+
∑
i
=
1
n
α
i
2
)
1
2
(
n
+
1
)
\left\|b_{1}\right\| \leq 2^{\frac{n-1}{4}}\left(1+\sum_{i=1}^{n} \alpha_{i}^{2}\right)^{\frac{1}{2(n+1)}}
∥b1∥≤24n−1(1+∑i=1nαi2)2(n+1)1
一般来说后一项在开n次方后趋向于1，因为
a
i
a_{i}
ai都是常数，一般不会与n相关，所以
∥
b
1
∥
≤
2
n
−
1
4
∗
k
\left\|b_{1}\right\| \leq 2^{\frac{n-1}{4}} * k
∥b1∥≤24n−1∗k
k比较小。此外，
b
1
b_{1}
b1又是原向量的线性组合，那么
b
1
[
n
]
=
∑
i
=
1
n
m
i
c
∗
a
i
=
c
∑
i
=
1
n
m
i
∗
a
i
b_{1}[n]=\sum_{i=1}^{n} m_{i} c * a_{i}=c \sum_{i=1}^{n} m_{i} * a_{i}
b1[n]=∑i=1nmic∗ai=c∑i=1nmi∗ai
显然如果c足够大，那么后面的求和必须足够小才能满足上面的约束。
Short Integer Solution
Collision-Resistant Hash Function
抽屉原理抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素
单词积累：
- corollary 必然的
- convex 凸的
- equalizer均衡器
- asymptotic 渐进的
- knapsack problem背包问题
- Collision-Resistant 抗碰撞性
- pigeonhole principle鸽巢原理