关于com的网站,线上会议软件有哪些,广告费内包括网站建设,iis5.1 发布网站目录
一. 格密码的重要性
二. 格密码基础
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 一. 格密码的重要性
格密码的基础是研究格点上的困难问题#xff0c;这种格点使用…目录
一. 格密码的重要性
二. 格密码基础
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 一. 格密码的重要性
格密码的基础是研究格点上的困难问题这种格点使用抽象代数的观点则是上的子群。格密码近些年非常火热主要由于以下几点
抗量子攻击。基于传统数论的公钥密码系统是无法抵抗量子攻击的这也是格密码最大的优势效率很高可以平行操作。这个其实不能一概而论得看实际情况。但目前我们常见的格密码方案效率都挺高的可实现最坏情况与平均情况之前的归约(worst case to average case)利用格密码相关理论可解决以前比较棘手的困难问题这个地方的困难问题指的是密码界常说的open question
密码学的基础是LWE(learning with errors)和SIS(short integer solution)问题当然也包括这两个问题的环版本。通常Ring版本的计算效率会更高。这两个问题可以实现可证明安全由此让密码学家前仆后继。 二. 格密码基础
2.1 格点的另一种理解方式
有关格密码基础可以参看我之前的博客。今天可以从抽象代数的角度理解格点m维的格可以看成上的离散加法子群。
其中格的秩与矩阵的秩k类似满足在非满秩情况下格的维度比最大的维度要小。由此给定格基该格基由k个线性独立的m维列向量组成对该格基进行整数倍线性组合即可形成格如下 当然正常情况下研究格密码的论文大多是满秩格也就是常说的且如果涉及格上高斯采样有可能会出现非满秩格。 2.2 对偶格
格形成的整个空间通常叫做。如果从格上取一个格点接着再取一个向量点满足如下要求的点称之为对偶格 这个是从格点的角度看对偶格还可以从格基的角度出发。
如果格非满秩原始格的格基为B那么对偶格的格基如下 大家看这个式子可能有点复杂其实就是伪逆。在满秩格下对偶格的格基就是先求逆再转置如下 三. q-ary格
其实准确来讲应该分为q-ary垂直格和q-ary格。
很多格密码的方案都是建立在q-ary格上的之所以起这个名字是因为一定是q-ary垂直格的子格。 3.1 q-ary垂直格
我们先来看一个矩阵。对于正整数n和q选出密码学通常要求该矩阵随机取这个矩阵是公开的如果有一个向量z乘以该矩阵为0向量那么把满足此条件的向量z全部都组合在一起就称之为q-ary垂直格如下 很明显可以得出一定是该格的子格。 3.2 q-ary格
同样先选出一个矩阵接着遍历向量将两者相乘得到新的向量z即可形成q-ary格如下 3.3 二者结合
实际上q-ary格和q-ary垂直格互为q倍的对偶格如下 在这里就不证明了。
当然部分论文类推也会出现“1-ary”格也就是 此格既包含整数又包含小数可得为其子格。
如果我们将中的0改为任意向量就会出现平移格或者叫陪集格(coset如下 四. 论文中的q-ary格
密码学三大会中经常会出现q-ary格这里梳理一些常用的相关结论。
随机取一个假定q-ary垂直格的某个格基为。 4.1 定理1
对任意幺模矩阵都有 理解该定理描述了幺模矩阵与q-ary垂直格的关系。左边代表对每个q-ary垂直格进行幺模矩阵变换该新格的格基为。右边代表对矩阵A的变换看q-ary格的原始定理可直接列出。 4.2 定理2
对任意可逆的方阵,q-ary垂直格都满足 理解矩阵可逆的话可直接变为与原来的q-ary垂直格等效。注意矩阵H的顺序 4.3 定理3
设定矩阵的列秩大于等于n换句话说也就是矩阵A的列向量可构成。接着随机取矩阵以及矩阵满足如下 接着我们可以借助此性质对q-ary垂直格的矩阵A进行扩展形成新的q-ary垂直格该q-ary垂直格的格基为 另外我们知道格基是可以进行正交化的。其实S正交化后的矩阵如下 通过矩阵的表达形式不难看出该矩阵的模长与原始格基S正交化的模长相等也就是 这个定理的证明需要用到很多线性代数的基础如果有人感兴趣后期再补上吧。
