格密码学习笔记

对偶格

定义

对偶格也叫倒易格，对一个满秩格Λ，定义对偶格为：

只要y与对偶格的内积为整数就属于对偶格

一般情况（非满秩）下，

span(Λ)是格的张成空间

几何解释：

固定一个向量x，找出与向量x内积为整数的点，这些点都在同一个超平面（多维空间的平面）上，点之间的距离为1/||x||

对偶基

定义

对于一个基B(b1,b2….bn)，和它的对偶基D(d1,d2,….dn)满足两个条件：

张成空间相同
B的转置矩阵和D的乘积为I，I就是单位矩阵E所以对角线为1其余为0，也就是<bi,di>=1,<bi,dj>=0

D是唯一的，在满秩格的情况下，

$$ D=(B^T)^{-1} $$

一般情况下：

$$ D=B(B^TB)^{-1} $$

对偶格的性质

定理1

一个格的对偶格的基正好是这个格的基的对偶基

如果D为B的对偶基，那么(L(B))^* =L(D)

证明过程：

定理2

给定一个格Λ，$(Λ^*)^*=Λ$，

定理3

对偶格的行列式和原本格的行列式满足

$$ det(Λ^*)=\frac{1}{det(Λ)} $$

证明过程

对于满秩格来说：

依靠线性代数：矩阵的逆的行列式等于矩阵的行列式的倒数，矩阵的转置的行列式等于矩阵的行列式

对非满秩格：

原来的格行列式（体积）越小，对偶格的行列式（体积）就越大，格密度就大，格的分布就越稀

定理4

对任意秩为n的格Λ：

$$ λ1(Λ)⋅λ1(Λ^∗)≤n $$

λ1(Λ)表示最短向量长度

上下两个相乘就可以得到这个式子

定理5

对于任意秩为n的格Λ：

$$ λ_1(Λ)⋅λ_n(Λ^∗)≥1 $$

取原格中的最短向量v，使：

$$ ||v||= \lambda_1(Λ) $$

取对偶格Λ* 中的n给无关向量，x1,x2….xn（Λ为秩为n的格），它们不可能全部与v正交，因此存在某个i使得<xi,v>≠0，根据对偶格的定义<xi,v>∈Z，所以 $$ ||xi||≥ \frac{1}{||v||} $$ 因为λn(Λ )肯定>||xi||，所以结果成立

+++

对一组基b1,b2….bn，让πi投影到空间$span(b_1,…,b_{i−1})^⊥$，特别的，π1b1,π2b2,…..,πnbn，就是b1,b2,…,bn正交化后的结果

⊥叫“正交补”表示与该子空间中的所有向量都正交的向量构成的集合

+++

定理6

设B，D为一组对偶基，B’=(πi(bi),…,πi(bn))和，D’=(di,…,dn)也是对偶基

要证明B’和D’为对偶基，需要证明，span(B’)=span(D’)，和$B'^TD'=I$,等价于 ⟨bj,dk⟩=σ_ij

因为dj与b1,….,bn都正交，所以dj∈$span(b_1,…,b_{i−1})^⊥$，D’=(di,…,dn)，所以span(D’)=$span(b_1,…,b_{i−1})^⊥$

因为πi(bk)是把bk投影到$span(b_1,…,b_{i−1})^⊥$，所以span(B’)=$span(b_1,…,b_{i−1})^⊥$，所以span(B’)=span(D’)

定理7

设对偶格基为B,D，B=（b1,b2,…,bn），D=(d1,d2,…,dn)

所以B正交化后=

$$ \tilde{b}_1,....., \tilde{b}_n $$

D正交化=

$$ \tilde{d}_1,....., \tilde{d}_n $$

长度满足：

$$ \tilde{d}_i= \frac{\tilde{b_i}}{||\tilde{b_i}||^2} $$

证明采用对n的归纳法，假设对秩为n-1的格成立，来证明对秩为n的格成立：

Korkine-Zolotarev bases

定义

对一个秩为n的格Λ，其KZ基b1,b2…..bn递归定义如下：

令b1为格Λ中的短向量
令 Λ′为将Λ投影到span(Λ)中与b1正交的子空间所得的格
令c2….cn 为Λ′的KZ基
定义
$$ b_i=c_i+α_ib_i $$
αi∈（-1/2，1/2]，是让bi∈Λ成立的唯一数

参考链接

计算机科学中的格（2004 年秋季） — Lattices in Computer Science (Fall 2004)