建筑设计网站issuu,广东建设信息网安管人员系统,儿童玩具网站建设实训报告,货源网目录
一. 介绍
二. SIS问题定义
2.1 直观理解
2.2 数学定义
2.3 基本性质
三. SIS与q-ary格
四. SIS问题的推广
五. Hermite标准型
六. 小结 一. 介绍
short interger solution problem短整数解问题#xff0c;简称SIS问题。
1996年#xff0c;Ajtai首次提出SIS问…目录
一. 介绍
二. SIS问题定义
2.1 直观理解
2.2 数学定义
2.3 基本性质
三. SIS与q-ary格
四. SIS问题的推广
五. Hermite标准型
六. 小结 一. 介绍
short interger solution problem短整数解问题简称SIS问题。
1996年Ajtai首次提出SIS问题由此设计出了单向函数one-way function抗碰撞的哈希函数collision resistant hash function身份验证方案identification scheme数字签名digitao signatures等等。这些在网络安全领域可以被称之为minicrypt原语。
本文章将介绍SIS问题探究它与最坏情况格问题的关系研究其基本的性质以及密码学中的应用。 二. SIS问题定义
2.1 直观理解
SIS问题的抽象代数表达形式
在一个有限但足够大的加法群additive group中所有的元素都是均匀且随机可以被取到的如何寻找一种整数倍的组合使他们的和为0且要求这种组合的足够短。这个问题是困难的。
如果给出一些参数问题会变得更加距离。
给出一个正整数n和q由此形成群 给定一个正实数从群中抽取m个样本。
在以上这些参数中m有的时候会被省略不写n是我们通常所说的安全参数比如n100要求和与n之间呈现多项式关系且满足 2.2 数学定义
给定m个均匀随机的n维向量将他们作为矩阵的列由此形成。如何寻找一个非零的整数向量且范数满足使其满足 理解
可以看成SIS函数A为公开的下标。很明显该函数正向计算容易逆向计算z困难。 2.3 基本性质
1z的长度
如果不限定向量z的长度那么可以直接借助高斯消元法Gaussian elimination找出一个答案z。另外z的上限肯定满足 如果不限定的话则会出现很多平凡解trivial比如 2扩展矩阵
将矩阵A可以扩展为 原来的z增加后续的0即可此时解z的范数是不会改变的。简单来讲就是当m增大时SIS问题会变得简单。当n增加时SIS问题会变得困难。
3参数的取值范围
向量z的范数上限以及向量的样本个数m都需要足够大来保证问题至少有解。根据鸽子洞理论pigeonhole argument我们考虑一个临界值如下 此时向量的空间至少大小为 说明在中至少有两个重复的解也就是存在不同的x,x满足 将两者相减可得 换句话说zx-x且其范围是 也就是保证了SIS问题的有解性。也就是SIS问题中的参数需要满足 4抗碰撞的SIS函数
将此处小整数解定义为只能取0或1那么可形成如下函数族 假定SIS问题是困难的说明找不到其对应的短整数解z也就找不到两个不同的x使其函数相等也就是 当然此处的小整数不仅仅只能取0和1推广其他较小的范围也可以。 三. SIS与q-ary格
网络安全领域有一个很有意思的m维整数格叫做q-ary垂直格。SIS问题可以看成平均情况的短向量问题如下 很明显是其子格。
借鉴编码理论coding theory此处的矩阵A可以看成q-ary垂直格的校验矩阵。SIS问题与SVP问题之间的关系
均匀随机选择ASIS问题的本质就是在q-ary垂直格上找到一个足够短的非零向量。 四. SIS问题的推广
SIS问题的推广也可以称之为inhomogeneous版本。也就是当均匀且随机选择矩阵A和向量u时尝试找出如下等式足够短的整数解x 如果不限定向量的长度此方程所有的解可以构成陪集格lattice coset如下 其中为方程的解。
选择合适的参数推广后的SIS问题和原来的SIS问题是等效的。 五. Hermite标准型
原始的SIS问题中的矩阵A为n行m列我们可以把该矩阵切成两个块状矩阵一个矩阵是n行n列一个矩阵是n行m-n列由此可得 很明显A1矩阵为方阵可以直接求逆。接着我们对A进行变换可得 将In作为可忽略的子矩阵。因为矩阵A2是均匀随机的与A1是互相独立的可得也是均匀且随机的。也就是以下两个矩阵的SIS问题的解是相同的 所以可得矩阵A和是互相等效的。
其实这个地方对矩阵的变换类似于网络安全纠错码error-correcting code中对称的生成矩阵。 六. 小结
随着网络安全的快速发展能够抵抗量子计算攻击且支持数据隐私保护和安全处理的密码算法是目前的迫切需求。基于格的密码体制被普遍认为能够抵抗量子计算攻击所以其研究近十年来发展迅速。从格算法应用于分析非格公钥密码体制如背包密码体制、RSA 体制的安全性发展到基于格计算困难问题的密码体制设计再到基于格计算困难问题设计全同态加密体制。
针对格中SVP问题的求解第一个格基约化算法是在1982年提出的 LLL算法。该算法可以在多项式时间内,输出近似短向量。LLL算法也是至今唯一可以证明是多项式时间运行的格基约化算法。LLL算法的提出对格理论的研究特别是公钥密码算法分析起到了很大的推动作用另外 LLL算法在计算代数和计算数论等领域也有广泛的应用已被公认为是20世纪最重要的算法之一。 推荐阅读
格密码LLL算法如何解决最短向量SVP问题1-CSDN博客
格密码LLL算法如何解决最短向量SVP问题2_lll算法复杂度-CSDN博客
格密码LLL算法如何解决最短向量SVP问题3完结篇-CSDN博客
