文档介绍：全同态加密释疑（一）：四个算法（1）
陈智罡
 全同态加密（Fully Homomorphic Encryption）诞生，不仅是密码学界一个大突破（Breakthrough）,而且是计算机理论界一个突破。自从创建了全同态加密QQ群，从几十号人到现在快要200人，来自各个大学，包含国外。可见大家对全同态加密研究热情。
 
另外在网上有很多同学问我部分问题，有些问题很雷同，可能也是初学者必经之路。全同态加密入门确实比较难。作为一个过来者，很愿意分享我部分心得，所以这里我会把部分共性问题，用一个深入浅出方法讲述，期望每个人全部能看懂。
 
其实在全同态加密论文背后，有很多能够说出来秘密，只不过这个秘密在论文里没空间也不适合讲，那么这里就搞一个专题“全同态加密释疑”，细说从头每个让你迷惑秘密。假如有愿意加入好友，能够一起分享心得体会。
 
今天说说全同态加密四个算法。可能有些人会说，这个谁不知道，不过知道并不意味着清楚，只有深刻了解了这四个算法含义，尤其是第四个算法含义，才能清楚什么是部分同态加密方案，什么是实施自己解密电路等等概念。
 
通常一个公钥加密方案有三个算法：KeyGen算法（密钥生成），Enc算法（加密），Dec算法（解密）。不过在全同态加密中，除了上述三个算法之外，还包含第四个算法：Evaluate算法（密文计算），这个算法功效是对输入密文进行计算。
 
首先说说KeyGen算法（密钥生成）。该算法用于生成公钥和密钥，公钥用于加密，私钥用于解密，这个地球人全部知道。不过还可能生成另外一个公钥，即密文计算公钥，我们把它称之为Evk。
 
密文计算公钥Evk作用是在实施Evaluate算法时用到，而且Evk形式和使用全同态方案直接相关。比如，假如是经过开启技术（Bootstrapple）取得全同态加密，即每次密文计算前要用同态解密约减密文噪音，这时Evk就是对密钥每一位加密后生成密文，即密钥有多少位，Evk里包含公钥就有多少个。Evk中每个公钥大小就是使用Enc加密后产生密文大小。经典代表就是Gentry理想格方案和后续整数上方案。
 
当然还有其它情况，比如，假如使用密钥交换和模交换技术取得全同态加密，经典代表就是BGV方案。这时Evk中包含就是L–1个矩阵，L是方案中电路深度，该矩阵用于密钥转换。每次密文计算后，全部需要使用Evk中公钥将维数扩张密文向量转换成正常维数密文向量。
当然还有一个情况就是不需要Evk，比如在Crypto13会议论文GSW13中，Gentry使用密文是矩阵（方阵），所以密文乘积或相加不会产生密文维数改变事情，所以在密文计算时没有用到公钥，这也是该论文能够产生基于身份或基于属性全同态加密方案根本原因。
 
相关Evk就说了这么多，你认为简单么？一个成功男人背后，有多少……，那么一个概念背后就有多少个概念在支撑。千万别小看了概念，只有善于抓概念，才能体会方案脉络。
 继续说全同态加密中其它三个算法。
Enc算法（加密）和我们日常意义加密是一样，不过在全同态加密语境里，使用Enc算法加密密文，通常称之为新鲜密文，即该密文是一个初始密文，没有和其它密文计算过。所以新鲜密文噪音称之为初始噪音。这个相当关键。
 
Dec算法（解密）也和我们日常了解一样，就是对密文解密，不过这里解密算法不仅能对初始密文解密，还能够对计算后密文解密。不过因为部分同态加密方案中密文存在噪音，比如在整数上全同态加密方案里，密文乘积噪音是噪音之积，密文加法噪音是噪音之和。所以当密文计算到一定程度，其噪音将超出上限，所以对这么密文解密将可能失败。全同态加密关键就是对噪音控制，使之能对任何密文解密。
 
最终一个算法：Evaluate算法（密文计算），这个算法是整个全同态加密四个算法中关键。能够做个这么比方：前面三个算法是大楼地基，后面这个Evaluate算法就是大楼。这个比方在后面会体会到它用意。密文计算是在电路里进行，电路是分层，电路深度越深，层数越多，密文就能够进行更数次计算。随便提一句，密文计算次数等于电路深度对数。什么是计算次数？比如c1*c2，就是进行了一次计算，次数为2，c1*c2*c3就是进行了两次计算，次数为3。在全同态加密中，我们通常见乘法次数来衡量计算次数，这是因为乘法噪音比加法噪音增加快很多。
 
Evaluate算法有三个输入，第一个输入是计算公钥Evk，就是我们在上次博文里讲到。Evk能够没有。第二个输入是函数f，就是Evaluate算法所要实施函数，能够是任意函数，因为全同态加密目标就是对密文能够进行任意计算。当然这个函数也能够是“解密函数”，
Gentry经过观察发觉了一个秘密，等会我们说。第三个输入是密文，理论上能够有没有穷