Lattice 作为全同态加密的基础代数结构,值得学习一下;最关键的一点,LBC 至今为止不能被量子计算机破解。这正如 20 年前的椭圆曲线代数结构,正如 40 年前的 RSA 代数结构一样。

Lattice 的本质是高维空间中几何学和代数学的组合,学起来会超级困难,一点也不亚于高考数学的挑战难度。密码学本身要求研究者对代数学有比较深入的理解,学起来很晦涩,所以我会尽全力将搜罗到的一些知识整合得更完整可读一些,并适当掺加一点自己的见解(如果都对的话)

在格理论密码系统出现之前,没有合适的问题可以用于构造同态加密系统。

没有哪个密码体系能有如此的抗量子攻击,格密码的算法效率令 RSA 望尘莫及,以及拥有超强的安全保障

格 定义

(lattice)v1,...,vnRm是线性无关向量组。我们称v1,...,vn生成了latticeL:即L中的元素是v1,...,vn的整系数线性组合。我们定义L的一个基(basis)是任何一个能生成L的向量组。显然lattice的两个基会拥有相同的向量个数;基所包含的的向量个数称为L的纬度(dimension).格(lattice)设 v_1,...,v_n \in R^m是线性无关向量组。\\我们称 v_1,...,v_n生成了 lattice L: 即L 中的元素是 v_1,...,v_n的整系数线性组合。\\ 我们定义L 的一个基(basis)是任何一个能生成 L的向量组。\\显然 lattice 的两个基会拥有相同的向量个数;基所包含的的向量个数称为 L的纬度(dimension).

L={a1v1+a2v2+...+anvn:a1,a2,...,anZ}L= \lbrace a_1v_1+a_2v_2+...+a_nv_n:a_1,a_2,...,a_n \in Z\rbrace

n维的格LRn的一个子集且满足:1L是一个加法子群2L是离散的【L的邻域中不包含其他的点】n维的格L是R^n的一个子集且满足:\quad \\(1)L是一个加法子群 \quad (2)L是离散的【L的邻域中不包含其他的点】

格的基

格就是从 R^m 中选择 n 个线性无关的向量,选取这些向量的全部整数组合构成的点集。(基向量的任意线性组合的集合)

L=L(B):=BZk=i=0kzibi:ziZL=L(B):=B⋅Z^k={\sum _{i=0}^{k}z_ib_i:z_i​∈Z}

这组生成格的线性无关的向量就是格的基,格可以有很多组基,但格的维数是相同的。

格的两组基之间可以通过一个行列式为 ±1 的矩阵进行转换,其基变换矩阵中的元素均为整数【格的基向量不是唯一的】

・这 k 个向量是格 L 的一组基

・格 L 的秩为 k

・格 L 的位数为 m

如果 m=n,那么我们称这个格式满秩的

从上图中可以看出这个二维的格中有两组基, v1' 和 v2' 的明显正交性更好(接近于正交),这样的基我们认为是优质基,反之 v 1 和 v 2 之间夹角就比较小,这类基,通常认为是劣质基。

在此补充一下线性代数相关的内容,因为 Lattice 涉及到很多行列式、基有关。

线性空间

线性空间 (vector spaces)

一个线性空间V,是Rm的一个子集,满足a1v1+a2v2Vv1,v2V,a1,a2R也就是说,一个线性空间,是对向量加法、标量乘法封闭的Rm的子集。一个线性空间 V,是R^m 的一个子集,满足 a_1v_1+a_2v_2 \in V \quad \forall v_1,v_2 \in V,a_1,a_2 \in R \quad \\也就是说,一个线性空间,是对向量加法、标量乘法封闭的R^m 的子集。

线性组合 (linear combinations)

v1,v2,...,vkV的一个线性组合是满足以下形式的向量:{w=a1v1+a2v2+...+akvk,a1,...,akR}称为{v1,...vk}的张成空间v_1,v_2,...,v_k \in V的一个线性组合是满足以下形式的向量:\\\lbrace w=a_1v_1+a_2v_2+...+a_kv_k, \quad a_1,...,a_k \in R \rbrace称为\lbrace v_1,...v_k \rbrace 的张成空间

线性无关 (linearly independence)

称一个向量集合v1,...vkV线性无关,当且仅当方程a1v1+a2v2+...+akvk=0的唯一解是a1=a2=...=ak=0.否则这个向量集合线性相关称一个向量集合v_1,...v_k \in V线性无关,当且仅当方程\\a_1v_1+a_2v_2+...+a_kv_k=0的唯一解是a_1=a_2=...=a_k=0.否则这个向量集合线性相关

基 (bases)

向量空间V的一个基,是可以张成V的线性无关向量集合v1,...vn.也就是说,任何一个向量都可以写成v1,...vn的线性组合的形式,其线性组合的系数是唯一的。向量空间V 的一个基,是可以张成V 的线性无关向量集合v_1,...v_n . \\也就是说,任何一个向量 都可以写成v_1,...v_n 的线性组合的形式,其线性组合的系数是唯一的。

  1. 任何一个线性空间 V 都有基。

  2. 任何两个基,含有的向量个数是相同的。基的向量个数称为 V 的维度 (dimension).

  3. v1,...vnV的一个基,是w1,...wn中的一个向量组。我们把wj写成vi的线性组合的形式:设 v_1,...v_n是 V的一个基, 是 w_1,...w_n 中的一个向量组。我们把 w_j 写成 v_i 的线性组合的形式:

    w1=a11v1+a12v2+...+a1nvnw_1=a_{11}v_1+a_{12}v_2+...+a_{1n}v_n

    w2=a21v1+a22v2+...+a2nvnw_2=a_{21}v_1+a_{22}v_2+...+a_{2n}v_n


wn=an1v1+an2v2+...+annvnw_n=a_{n1}v_1+a_{n2}v_2+...+a_{nn}v_n

w1,...wn也是V的一个基,当且仅当下列矩阵的行列式不为零则w_1,...w_n也是V的一个基,当且仅当下列矩阵的行列式不为零

(a11a12a1na21a22a2nan1an2ann)\begin{pmatrix} a_{11 }& a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{pmatrix}

度量向量长度和向量夹角

点积 (dot product)

v,wVRmv,w的坐标如下:v=(x1,x2,..xm),w=(y1,y2,...,ym).设v,w \in V \subset R^m \quad 记v,w的坐标如下:v=(x_1,x_2,..x_m),\quad w=(y_1,y_2,...,y_m) .

VW的点积为:vw=x1y1+x2y2+...+xmym记 V与 W的点积为: \quad v·w=x_1y_1+x_2y_2+...+x_my_m

vw=0,我们称vw正交(orthogonal).若 v·w=0,我们称 v与 w正交(orthogonal).

欧几里得范数 (Euclidean norm)

向量v的长度,或称欧几里得范数,为v=x12+x22+...+xm2,vv=v2向量 v的长度,或称欧几里得范数,为 ||v||=\sqrt {x_1^2+x_2^2+...+x_m^2}, \quad v·v=||v||^2

  1. θ为向量v,w之间的角(这里我们把v,w的起始点都放在原点0)。则vw=vwcosθ记 \theta为向量v,w 之间的角(这里我们把 v,w的起始点都放在原点0)。则 v·w=||v|| ·||w||cos \theta

  2. (CauchySchwarz不等式)两向量的点积的绝对值,不大于向量长度的积。vwvw(Cauchy-Schwarz 不等式) 两向量的点积的绝对值,不大于向量长度的积。\\ \quad |v·w|\leq ||v||·||w||

    正交基 (orthogonal basis)

线性空间V的一个正交基,是满足以下条件的基v1,...vnvivj=0ij线性空间V 的一个正交基,是满足以下条件的基v_1,...v_n :v_i·v_j=0 \quad \forall i \neq j

额外地,若这个基还满足 ||v||=1 ,则我们称这个基规范正交 (orthonormal).

Lenstra–Lenstra–Lovasz(格基规约算法 )

在 lattice 里面找短向量的算法,称为 lattice reduction(格基规约)算法

更新于

请我喝[茶]~( ̄▽ ̄)~*

1sme 微信支付

微信支付