网站建设与管理试题,懒人之家网站模板,2014年沈阳建设银行网站,企业小程序制作的公司目录
一. 回顾ZSVP问题
二. 基于ZSVP问题的密码系统
三. 格基旋转与Gram矩阵
四. 补充矩阵QR分解
4.1 矩阵分解
4.2 举例 前序文章请参考#xff1a;
【格密码基础】详解ZSVP问题-CSDN博客 一. 回顾ZSVP问题
根据之前的讨论我们知道解决ZSVP问题的计算复杂度为#x…目录
一. 回顾ZSVP问题
二. 基于ZSVP问题的密码系统
三. 格基旋转与Gram矩阵
四. 补充矩阵QR分解
4.1 矩阵分解
4.2 举例 前序文章请参考
【格密码基础】详解ZSVP问题-CSDN博客 一. 回顾ZSVP问题
根据之前的讨论我们知道解决ZSVP问题的计算复杂度为 在实际应用中可利用随机算法将ZSVP问题归约到y-SVP或者y-uSVP问题其中。在2023年论文[Duc23]中出现了一个确定性的算法没有近似因子。也就是直接从ZSVP问题归约到SVP问题。但遗憾的是归约前格维度为n归约后为n/2. L´eo Ducas. Provable lattice reduction of Zn with blocksize n2. Cryptology ePrint Archive, Paper 2023/447, 2023. https://eprint.iacr.org/2023/447. 5, 27 在本文章中我们重点关注将格旋转后的格。 二. 基于ZSVP问题的密码系统
众所周知如果ZSVP问题是困难的那么就可以设计新的公钥密码方案public key encryption。
另外有两个显然可得的优点
旋转格非常的简单对应的格困难性假设也比较特别
在格中任意两个相邻的格点距离为1所以其译码半径unique decoding radius为1/2.另外根据格密码的基础概念格的行列式determinant也为1.
如果想设计一个比格更稠密的格则可以选择 其中为缩放因子。选取不同的值格的稠密程度也不一样。
当然利用ZSVP问题除了可以形成加密方案外还可以形成签名方案signature scheme以及零知识证明zero-knowledge proof.
在这些方案中无一例外都会涉及到worst case到average case的证明。当然也可以利用攻击算法来破解这些方案比如对偶dual攻击。
其实在严格的格密码证明中可证明安全的格基该怎么选一直是一个问题。目前学者很喜欢用离散高斯基discrete Gaussian bases。
由此便出现了接下来要讲的格基旋转。 三. 格基旋转与Gram矩阵
将格的格基进行正交变换之后的基记为格基B其也可以看成旋转格的格基。
实际应用时这种正交变换怎么选
最直接的肯定是均匀且随机的选取了 一方面我们现在对格基矩阵B做一个运算可以得到 在另一方面我们先把格基做一个旋转得到RB接着再做同样的运算 很神奇前后结果是一样的。其实实际上Gram矩阵就是 在以上我们将旋转矩阵R隐藏了。或者换句话说Gram矩阵是抗旋转的rotation independent。
这个矩阵非常优秀每个元素的值一定为整数平方效果。
由此我们又给出一个新的格密码困难问题
给定矩阵G且满足 求出特定的整数矩阵。
这个问题也是困难的更进一步将这个问题本质还是ZSVP问题的变式情况。
现在我们尝试思考一个问题以上旋转格中旋转角度该怎么选
一种方法是对Gram矩阵进行Cholesky分解。
另一种方法是满足如下等式 上式子中B是上三角矩阵R为正交变换。根据矩阵QR分解的理解以上等式中B和B是一一对应的。实际上在格基的LLL约化算法中也出现了QR分解。
由此可见QR分解的重要性接下来我们将补充QR分解。 四. 补充矩阵QR分解
4.1 矩阵分解
如果一个矩阵m行n列则可以认为该矩阵包含n个m维的列向量。
假如矩阵A有3列则包含3个列向量记为a,b,c
采用正交化的思想可以将矩阵A变为一个正交矩阵Q也就是包含3个列向量记为。通常转化为后的这3个列向量都是标准的正交向量也就是长度均为1.
熟悉线性代数的同学都知道这种变换过程也可以用一个矩阵来衡量。也就是矩阵A通过乘以另外一个矩阵可以变为矩阵Q。
更加具体化向量a可以用向量表示向量b可以用表示向量c可以用表示。
来看一张投影图 向量a与q1共线
向量a,b与q1,q2共面
同理向量a,b,c与q1,q2,q3共体。
从图中我们可以看出可以将向量b用分量q1,,q2来表示具体分析如下 同理向量c也可以用q1,q2和q3来表示即为 将以上转化过程表示为矩阵的运算则为AQR如下 其中R为上三角矩阵upper triangular。 4.2 举例
请将如下矩阵A进行QR分解并写出计算过程 解
将矩阵A的第一列记作向量a第二列为向量b第三列为向量c如下 第一步找出正交矩阵Q
已知q1与向量a共线且长度为1.那么很明显可得 接着去掉向量b在q1上的分量可得 将向量B标准化使其长度为1可得q2 接着去掉向量c在q1和q2上的分量可得 可以发现向量C的长度本身就为1所以无需标准化长度可直接得到q3.
综合以上正交矩阵Q便可得 第二步计算上三角矩阵R
接着根据QR分解的公式可分别计算 由此矩阵A完整的QR分解如下 补充一个有意思的性质上三角矩阵R的对角线处有个三个元素其实对应着向量a,B,C的长度q1,q2,q3标准化前的长度。
