▼本文由陈智罡博士撰写格上加密方案是一种噪音加密方案，这种方案与直觉非常吻合。
例如，你给一个非专业人士解释格加密的本质，就是往消息里添加一些噪音作为扰动。我相信对于非专业人士一定能够理解。因为这很形象。
但是你如果解释RSA，我相信一般人是很难想象出大整数分解的样子。所以格加密的几何特征非常明显。这也导致格加密本身与传统加密（RSA，离散对数，ECC）具有截然不同的性质。很多密码算法是无法直接从传统密码体质对到格加密体质上的。
更令人惊讶的是，全同态加密竟然能够在格加密上构造出来。
事实上，经过研究我们发现，（环）LWE加密本身就具有同态性，不但是加法，乘法也是，只不过只能进行有限次乘法。所以我们经常说一句，对于格加密上的全同态加密是：同态本天成，妙手偶得之。
同态性在格密码中是天然存在的，只不过被发现了。这和牛顿发现了宇宙的运动规律是一样的，宇宙本来就具有，只不过我们不知道罢了。
此外，（环）LWE加密的同态性会受到噪音的“淹没”。如果噪音大了，将无法获得同态性。因此，研究解密结构与噪音之间的关系就非常重要。01解密结构与噪音增长依赖主要项
不同的解密结构，其密文计算的噪音增长形式不同，可以通过噪音增长依赖主要项来刻画。
如果从形式构造密文乘法的同态性，则第1种解密结构噪音增长依赖的主要项是密钥的长度，第2种解密结构和第3种解密结构噪音增长依赖的主要项都是密文噪音的乘积。
如果从形式构造密文乘法的同态性，则其噪音增长依赖的主要项是密文的长度。

以上分析给出了密文乘积噪音增长的主要来源，因此对噪音依赖的主要项进行约减，可以降低密文乘积的噪音增长。
例如，噪音增长依赖的主要项是密钥的长度，则可将密钥表示为BitDecomp(s)，即将密钥按位展开，例如Bra12方案。
对于噪音增长依赖的主要项是密文噪音的乘积，则可使用模交换，例如BGV方案。
对于噪音增长依赖的主要项是密文的长度，则可将密文表示为BitDecomp(c1)，例如GSW方案。
注意，约减噪音的同时还需要满足期盼解密结构，否则同态性将丧失。
上面是将同态性与噪音分开讨论的，下面将其合在一起讨论，因为只有这样才能获得真正的密文计算的同态性。那么这样的解密结构具有什么形式呢？下面引出最终解密结构的概念。02最终解密结构如果该解密结构在某种密文乘法计算形式下，能够获得密文乘法期盼解密结构，并且密文的噪音增长是小的，则称之为最终解密结构。
从定义可知，最终解密结构包含两个核心部分：一是解密结构，二是密文乘法计算形式。其意义为：该解密结构在该密文乘法计算形式下，具有潜在的同态性，并且能够正确解密。从而获得同态性。
注意噪音约减技术与同态性都隐含在最终密文乘法计算形式中。所以具有最终解密结构的密文具有密文计算同态性，而且密文计算的噪音是小的，所以能够进行下一次同态计算。
最终解密结构同时解决了密文计算的同态性和噪音增长问题。但是有些全同态加密在密文计算的过程中密钥的长度是增长的（相应密文长度也增长）。因此在具体的全同态加密方案中，还需要额外通过密钥交换技术解决密文计算过程中的密钥长度增长问题。由此得到下面的结论。
如果密文在计算过程中始终保持最终解密结构，并且能够保持密钥长度（对应于密文长度）不变，则对应加密方案具有全同态加密的特性。
上述结论刻画了要想获得全同态加密，需要解决密文计算的同态性、密文计算中噪音增长以及密钥长度增长的问题。
而密文计算的同态性与密文计算中噪音增长的问题，可以通过构造最终解密结构来解决。
密钥长度增长问题是由密文乘法的期盼解密结构的构造形式决定的，可以通过密钥交换技术解决。
此外，如果密文计算的电路深度很浅（即密文乘法次数很小），为了提高效率可以不进行密钥交换，此时的加密方案称为有限同态加密（Somewhat同态加密）。
采用形式构造全同态加密时，第1种解密结构的最终解密结构中的解密结构是该形式将同态性与噪音约减形成一个完整的形式描述。密文乘法同态的计算形式是对应的密钥是。第2种解密结构，其最终解密结构中的解密结构还是。采用的噪音约减技术是模交换，密文乘法同态的计算形式是对应的密钥是，其中q* 是用于模交换的模。
第3种解密结构与第2种解密结构一样。 
采用形式构造全同态加密，能够应用于全部3种解密结构，其构造方法通过上述结论已经刻画的非常清晰。
注意，密文的加密形式在该形式构造全同态加密的过程中并没有改变，仍然使用基本加密形式。其原因是最终解密结构中的解密结构与最初的解密结构形式一样，所以加密形式也不变。
由于基本加密形式具有期盼解密结构（即潜在的同态性），主要面临的问题是控制密文计算过程中的噪音增长。因此为了获得同态性，在密文计算过程中加入了噪音约减技术。
但是根据前面结论，采用形式构造全同态加密只能应用于第3种解密结构。此外形式构造密文乘法的期盼解密结构，具有保证密钥长度不变的良好性质。而GSW方案恰好就是这种类型。
顺着这条线索追问下去，就可以得到GSW方案通用性的原因。感兴趣的朋友可以参考陈智罡博士的论文：
论文长文版：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.往期推荐为什么格上能够构造全同态加密-2为什么格上能够构造全同态加密-1生物特征密文认证系统2019年IDASH保护隐私安全的基因分析竞赛内容生物特征数据库导致数百万用户的数据泄露PySEAL：一个全同态加密的Python接口库2019年同态加密标准化会议召开谷歌隐私交集和技术解析2—技术概览
谷歌隐私交集和技术解析1—应用场景分析谷歌推出一种新型的安全多方计算开源库关于安装NTL的总结
NIST第二届后量子密码标准会议接受论文▼欢迎收听“区块链杂谈”节目，国内最有质量的区块链知识分享节目。


◆ ◆ ◆  ◆ ◆格密链专注于区块链上的密码学技术长按扫码可关注







长按二维码向我转账


受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

















已同步到看一看



取消
发送


我知道了








朋友会在“发现-看一看”看到你“在看”的内容
确定













已同步到看一看写下你的想法



最多200字，当前共字
发送







已发送







朋友将在看一看看到
确定



写下你的想法...









取消
发布到看一看
确定




最多200字，当前共字








发送中













微信扫一扫
使用小程序










取消
允许











取消
允许














知道了








确定