格密码基础:q-ary格

发布时间:2023年12月24日

目录

一. 格密码的重要性

二. 格密码基础

2.1 格点的另一种理解方式

三. q-ary格

3.1 q-ary垂直格

3.2 q-ary格

3.3 二者结合

四. 论文中的q-ary格

4.1 定理1

4.2 定理2

4.3 定理3


一. 格密码的重要性

格密码的基础是研究格点上的困难问题,这种格点使用抽象代数的观点则是R^n上的子群。格密码近些年非常火热,主要由于以下几点:

  1. 抗量子攻击。基于传统数论的公钥密码系统是无法抵抗量子攻击的,这也是格密码最大的优势;
  2. 效率很高,可以平行操作。这个其实不能一概而论,得看实际情况。但目前我们常见的格密码方案效率都挺高的;
  3. 可实现最坏情况与平均情况之前的归约(worst case to average case);
  4. 利用格密码相关理论可解决以前比较棘手的困难问题,这个地方的困难问题,指的是密码界常说的open question;

密码学的基础是LWE(learning with errors)和SIS(short integer solution)问题,当然也包括这两个问题的环版本。通常Ring版本的计算效率会更高。这两个问题可以实现可证明安全,由此让密码学家前仆后继。

二. 格密码基础

2.1 格点的另一种理解方式

有关格密码基础可以参看我之前的博客。今天,可以从抽象代数的角度理解格点:m维的格\Lambda可以看成R^m上的离散加法子群

其中,格的秩与矩阵的秩k类似,满足k\leq m(在非满秩情况下,格的维度比最大的维度要小)。由此,给定格基B=\lbrace b_1,\cdots,b_k\rbrace,该格基由k个线性独立的m维列向量组成,对该格基进行整数倍线性组合即可形成格,如下:

\Lambda=\lbrace Bz:z\in Z^k\rbrace

当然,正常情况下,研究格密码的论文大多是满秩格,也就是常说的\Lambda\subset Z^mk=m(如果涉及格上高斯采样,有可能会出现非满秩格)。

2.2 对偶格

格形成的整个空间,通常叫做span(\Lambda)。如果从格上取一个格点x\in \Lambda,接着再取一个向量点v\in span(\Lambda),满足如下要求的点,称之为对偶格\Lambda^*

\langle v,x\rangle\in Z

这个是从格点的角度看对偶格,还可以从格基的角度出发。

如果格非满秩,原始格\Lambda的格基为B,那么对偶格的格基如下:

B^*=B(B^tB)^{-1}

大家看这个式子可能有点复杂,其实就是伪逆。在满秩格下,对偶格的格基就是先求逆再转置,如下:

B^*=B^{-t}

三. q-ary格

其实准确来讲,应该分为q-ary垂直格q-ary格

很多格密码的方案都是建立在q-ary格上的,之所以起这个名字是因为qZ^m一定是q-ary垂直格子格

3.1 q-ary垂直格

我们先来看一个矩阵。对于正整数n和q,选出A\in Z_q^{n\times m}(密码学通常要求该矩阵随机取),这个矩阵是公开的,如果有一个向量z乘以该矩阵为0向量,那么把满足此条件的向量z全部都组合在一起,就称之为q-ary垂直格,如下:

\Lambda^\bot(A)=\lbrace z\in Z^m:Az=0 \quad mod\ q\rbrace

很明显可以得出qZ^m一定是该格的子格。

3.2 q-ary格

同样,先选出一个矩阵A\in Z_q^{n\times m},接着遍历向量s\in Z^n_q,将两者相乘,得到新的向量z,即可形成q-ary格,如下:

\Lambda(A^t)=\lbrace z\in Z^m:\exists s\in Z_q^n\ s.t.\ z=A^ts\quad mod \ q\rbrace

3.3 二者结合

实际上,q-ary格和q-ary垂直格互为q倍的对偶格,如下:

q\cdot \Lambda^\bot(A)^*=\Lambda(A^t)

在这里就不证明了。

当然,部分论文类推,也会出现“1-ary”格,也就是:

\frac{1}{q}\Lambda(A^t)=\Lambda^\bot(A)^*

此格既包含整数,又包含小数,可得Z^m为其子格。

如果我们将Az=0中的0改为任意向量u\in Z_q^n,就会出现平移格或者叫陪集格(coset),如下:

\Lambda_u^\bot(A)=\lbrace z\in Z^m:Az=u \quad mod\ q\rbrace

四. 论文中的q-ary格

密码学三大会中经常会出现q-ary格,这里梳理一些常用的相关结论。

随机取一个A\in Z_q^{n\times m},假定q-ary垂直格\Lambda^\bot(A)的某个格基为S\in Z^{m\times m}

4.1 定理1

对任意幺模矩阵T\in Z^{m\times m},都有:

T\cdot \Lambda^\bot(A)=\Lambda^\bot(A\cdot T^{-1})

理解:该定理描述了幺模矩阵与q-ary垂直格的关系。左边T\cdot \Lambda^\bot(A)代表对每个q-ary垂直格进行幺模矩阵变换,该新格的格基为T\cdot S。右边代表对矩阵A的变换,看q-ary格的原始定理可直接列出。

4.2 定理2

对任意可逆的方阵H\in Z_q^{n\times n},q-ary垂直格都满足:

\Lambda^\bot(H\cdot A)=\Lambda^\bot(A)

理解:矩阵可逆的话,HAz=0可直接变为Az=0,与原来的q-ary垂直格等效。(注意矩阵H的顺序)

4.3 定理3

设定矩阵A\in Z_q^{n\times m}的列秩大于等于n,换句话说也就是矩阵A的列向量可构成Z_q^n。接着随机取矩阵A'\in Z_q^{n\times m'}以及矩阵W\in Z^{m\times m'},满足如下:

AW=-A'\quad mod\ q

接着我们可以借助此性质对q-ary垂直格的矩阵A进行扩展,形成新的q-ary垂直格\Lambda^\bot ([A'|A]),该q-ary垂直格的格基为:

S'=\left[ \begin{array}{cc}I&0\\W&S \end{array} \right]

另外,我们知道格基是可以进行正交化的。其实S'正交化后的矩阵如下:

\tilde S'=\left[ \begin{array}{cc}I&0\\0&\tilde S \end{array} \right]

通过矩阵的表达形式不难看出,该矩阵的模长与原始格基S正交化的模长相等,也就是:

||\tilde S'||=||\tilde S||

这个定理的证明需要用到很多线性代数的基础,如果有人感兴趣,后期再补上吧。

文章来源:https://blog.csdn.net/forest_LL/article/details/135119839
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。