iis7 静态网站,网页制作面试自我介绍,东莞公司建设网站制作,建站之星凡客目录
一. LWE公私钥对
二. 怎么加密#xff1f;
三. 怎么解密#xff1f;
四. 正确性分析
五. 安全性 在格密码中#xff0c;LWE(Learning With Errors)问题非常重要#xff0c;本文章将介绍一些基于LWE设计的公钥密码方案#xff0c;并详细讨论这些方案是如何运行的…目录
一. LWE公私钥对
二. 怎么加密
三. 怎么解密
四. 正确性分析
五. 安全性 在格密码中LWE(Learning With Errors)问题非常重要本文章将介绍一些基于LWE设计的公钥密码方案并详细讨论这些方案是如何运行的。
这些方案讲重点关注IND-CPA安全不可区分性-选择明文攻击安全。IND-CPA安全简单来讲就是窃听者获得公钥和密文不会学习到关于明文的任何信息。基于LWE问题也可以用来设计全同态加密此处就不作过多拓展。 一. LWE公私钥对
一些公共参数格维度为n模数为q噪声分布为且每个数均为整数样本个数为m。
私钥比较简单先说私钥。LWE问题中的秘密即为私钥。很明显私钥的尺寸为。
样本个数为这样取的话可以平衡安全性和效率感兴趣可以看Regev原始的LWE论文。
有一个概念叫LWE分布其中s代表秘密代表噪声分布如下 需要注意的是其中的值较小。
这个代表一个样本如果把m个样本组合在一起是n维组合成矩阵为维。为1维组合后为维向量也就是 LWE问题的困难性告诉我们将b和A公开也不会泄露s和e的信息由此可将A和b作为公钥如下 很明显公钥的尺寸为。
我们知道在一般的公钥密码系统中公钥和私钥之前是有关系的。在LWE公钥密码方案中我们来看一个有意思的计算 二. 怎么加密
取一个明文比特。密码学中加密的过程一定要引入随机数此处也不例外我们需要随机取m维向量利用公钥A进行加密如下 需要注意上面的“0”是一个N维的向量。其实这个加密过程有一个很专业的英语表达在这里分享给大家
“take a random subset-sum of the LWE samples”矩阵A就是LWE样本x向量只能取0或1所以其本质就是有些位置取该样本有些不取。最后再相加则是所谓的子集和。
“appropriately encodes the message bit in the last coordinate”这个就更好理解了因为明文比特就是放在最后一个位置。
很明显该密文长度为。
矩阵A中是随机的是伪随机的所以最终的公钥矩阵A也是伪随机的。
了解SIS(Short Integer Solution)问题的小伙伴知道这个加密的过程其实跟求SIS单向函数非常类似。刚好此处简单介绍下SIS单向函数的正向计算。根据单向函数的定义正向计算是简单的。给定随机的矩阵输入一个非零的向量,且满足计算如下 三. 怎么解密
加密肯定要用私钥s当然实际运算如下 将密文的表达式带入 根据私钥与公钥的关系带入可得 LWE的要求告诉我们非常小且x又只能取0或1所以第一个数与第二个数相差悬殊可得 解密的人最后只需要看该值是接近还是接近0便可以判断明文比特是1还是0.
当然发展到今天仅仅只加密一个比特未免效率过低。其实也可以将明文比特从中选后续只需要将以上方案中的q/2替代成q/p即可当然需要保证q/p足够大。 四. 正确性分析
解密是否成功的关键在于不能太大那么到底有什么限制呢
只需要误差处于0和q/2的平均值即可也就是 实现起来难吗
最直观的无非是让q尽量大一些让噪声分布的取值尽可能小一点让维度m尽可能小一点。
在这里我们用格密码最喜欢用的离散的高斯分布举一个例子。
假如噪声分布其中代表噪声分布代表离散的高斯分布。有关离散高斯分布的介绍可以看这篇博客
格密码离散高斯与子高斯分布-CSDN博客
Z代表整数格r代表离散高斯分布的标准差。
学习过概率论的小伙伴都知道如果向量e服从高斯分布,那么也为高斯分布并且其标准差的上限为。
高斯分布越往两边概率越小。密码学追求概率的渐近值也就是的长度小于的概率大于等于。简单翻译下就是的长度极大可能性小于。
举个例子。令LWE的噪声分布有一个很有意思的量叫误差率(error rate)计算如下 五. 安全性
密码安全性证明常用归约和hybrid argument等以后有时间再补上吧。
