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

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

---

本文由陈智罡博士撰写。

前面（https://editor.csdn.net/md/?articleId=104844689）我们说了，通过“抽象解密结构”能够把密文、明文、密钥以及噪音联系起来。而全同态加密的本质是反映密文计算空间与明文计算空间之间的关系。如何把这两个空间联系起来，抽象解密结构是最好的工具。

接下来的问题就是探讨如何衡量获得同态性。

一、 期盼解密结构

提醒一下，当说到同态性的时候，本质上就涉及到了计算，没有计算就没有同态性而言。而密文计算结果的解密结构的形式反映了其同态性。

下面我们定义一个结构：期盼解密结构，如下所示：

期盼解密结构为我们揭示了，密文计算结果具有什么样的密文解密结构才可能获得同态性。因此将获得同态性的问题转化为  →  构造期盼解密结构 →密文计算形式。上述分析，为我们提供了技术路线，构造同态性可以从密文计算形式入手。

上篇文章说了，抽象解密结构的定义适用于所有格上的加密方案。

根据目前LWE以及环LWE上的已知加密方案，将其归类为3种类型的解密结构： 

第1种：c⊙s=<c,s>=⌊q/2⌋⋅m+e (mod⁡q)；

第2种：c⊙s=<c,s>=m+2e (mod⁡q);

第3种：c⊙s=c⋅s=s⋅m+e (mod⁡q)。

前两种存在于LWE或环LWE上的加密，最后一种存在于环LWE上的NTRU加密.

 那么问题来了，对于上述三种解密结构，通过什么样的密文计算形式才能够获得期盼解密结构呢？

二、 密文乘法期盼解密结构的构造

这里要说明一点，格上的加密方案天生具有加法同态性的，所以加法同态性我们不需要考虑。关键是研究乘法同态性。

同态性与两个因素有关，一是期盼解密结构，二是噪音的大小。其实，噪音并不影响同态性的具有，只是如果噪音大了让方案无法获得具有的同态性。因为噪音大了导致无法解密，就算具有同态性，方案也没有意义了。

为了研究密文乘法期盼解密结构的构造，假设密文中的噪音是小的，这样研究的重点就聚焦在密文乘法上。

可以通过以下两种形式构造密文乘法的期盼解密结构：

第1种形式：(c1⊙s) · (c2⊙s)

第2种形式：c1 ·c2 · s

第1种形式产生的结果

如果采用(c1⊙s) · (c2⊙s)形式构造密文乘法的期盼解密结构，则上述三种类型的解密结构都可通过该形式获得期盼解密结构，并且该形式构造密文乘法期盼解密结构的一个共同特征是密钥长度在计算过程中是改变并且增长的。

采用(c1⊙s) · (c2⊙s)角度出发构造密文乘法的同态性，适用于上述三种解密结构，因此具有通用性。但是其特征是会引起密钥长度的增长。所以为了获得更多的乘法次数，每次乘法后需要使用密钥交换约减密文长度。

尽管密钥交换操作是构造全同态加密的基石，但是影响了计算的效率，而且使得密文乘法非常复杂。因此，一个自然的想法就是如何能够在密文计算过程中保持密钥长度不变，从而密文的长度也不变。

第2种形式产生的结果

如果采用 形式构造密文乘法的期盼解密结构，则上述三种类型的解密结构中，只有第3种类型的解密结构通过该形式可获得期盼解密结构，并且该形式构造密文乘法期盼解密结构的一个共同特征是在计算过程中密钥长度是保持不变的。

上述分析清晰的给出了从解密结构出发构造期盼解密结构的方法，即构造同态性的方法，但是有个前提是密文计算的噪音是小的才能够保证同态性的获得。下面研究解密结构与噪音增长之间的关系。

感兴趣的朋友可以参考陈智罡博士的论文：

论文长文版：https://share.weiyun.com/5Qb4cyd

1. A General Design Method of Constructing Fully Homomorphic Encryption with Ciphertext Matrix. KSII Transactions on Internet and Information Systems, 2019,Vol.13(5)：2629-2650.

2. 基于抽象解密结构的全同态加密构造方法分析[J]. 电子与信息学报, 2018, 40(7): 1669-1675.

以上文章以及电子资源，都可以在陈智罡博士的主页上获得：

---

https://zhigang-chen.github.io/index.html

微信公众号：btc201800

国内第一个聚焦于全同态加密与区块链的公众号

陈智罡博士的个人主页

https://zhigang-chen.github.io/index.html

全同态加密资源汇总

https://zhigang-chen.github.io/FHE%20Resources.html

全同态加密与机器学习论文列表：https://zhigang-chen.github.io/FHE%20and%20Machine%20Learning%20References.html

区块链与密码学音频节目

https://www.ximalaya.com/zhubo/42927243/

————————————————

版权声明：本文为CSDN博主「格链致知」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/btc201800/article/details/104034933