为什么格上能够构造全同态加密-1

为什么格上能够构造全同态加密-1

本文由陈智罡博士撰写。

目前只有在格上能够构造全同态加密方案。

为什么呢？

早在2015年，这个问题就萦绕在我脑海。当时对GSW这个方案很感兴趣，GSW方案中密文被表达成了一个矩阵，矩阵与矩阵的乘积不会导致密文维数的增长，所以不需要使用密钥交换来约减密文的维数。此外，对噪音的约减也包含在了GSW密文的乘法中，使得GSW方案非常简洁。

最重要的是该方案具有通用性。你把（环）LWE加密方案，NTRU加密方案，整数上的加密方案直接带进去，就可以得到一个GSW风格的全同态加密方案。这种通用性是来自于什么呢？

学术界最大的特征是对问题的追问。工业界最大的特征是对应用场景的追问。

抽象解密结构

通过对GSW方案的分析，发现GSW在解密过程中的结构是：sm+e mod q，其中s是密钥，m是消息，e是噪音，q是模。这种结构不是GSW独有的，而是在格上NTRU加密方案中就是这样的结构。于是我们的目光转向了解密过程。

在全同态加密中分析同态性时，都是以解密作为出发点。这是为什么？

以LWE加密方案的解密为例：<c,s>=(q/2)m+e mod q，其中c是密文，s是密钥，m是消息，e是噪音，q是模。仔细观察解密式子，会发现这里面把密文、明文、噪音以及密钥的关系都呈现出来了。而全同态加密的本质就是密文计算对应于明文计算，所以密文和明文之间的关系很重要。它们之间的关系是能否获得同态性的关键。

除了上述解密形式，格上加密方案还有其它解密形式吗？

有的，格上NTRU加密方案的解密形式是：cs=sm+e mod q。

LWE加密方案还有一种变种，其解密形式是：<c, s>=m+2e mod q。

此外，你也可以把整数加密方案上的解密形式拿来，是类似的。为了研究如何获得同态性，我们定义了一个结构：抽象解密结构。如下所示：

c⊙s=xm+e mod q；

其中是⊙抽象计算符号，x是常数。 该等式称为密文 c 与密钥 s 计算结果的抽象解密结构。由于每次加密时密文、明文和噪音都是变化的，而密钥是不变的，可将 c、 m 和 e视为变量， s 视为常量。

从抽象解密结构 c⊙s = x⋅m + e 可以清楚的看到密文 c、明文 m 和噪音 e 三者之间的关系是一次形式，即线性关系。这种线性关系直接蕴含了同态性，这也是为什么格上能够构造全同态加密的根本原因。我们的论文中对其进行了详细论证。

定义这个“抽象解密结构”有什么用呢？

非常有用。通过我们定义的这个工具能够衡量如何获得同态性，分析噪音增长主要项，如何表示全同态加密特性的获得，以及解释GSW为什么具有通用性。