格密码：LWE设计公钥密码系统

目录

一. 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"，等以后有时间再补上吧。