前言

我第一次接触全同态加密是在2011年，当时看的是整数上的全同态加密的论文。论文里的新鲜概念，例如电路模型、Boostrapping技术、压缩解密电路等刷新了我对密码学的认知。花了半年时间，我才读懂了这篇论文。当时学界都觉得全同态加密很难，据说能看懂Gentry博士论文的人寥寥无几。正是因为全同态加密难，所以我对此产生了极大的兴趣，往往为了一个概念或者一个参数思索许久，之后走上了格密码的学习之路。没有格密码理论的基础是很难深入理解全同态加密原理的。所以，本书第2章系统介绍了格密码理论知识。为了读者能够更好地理解格密码理论，我做了很多图示以帮助理解，这也算是对我学习格密码理论的一次总结。

同态本天成，妙手偶得之，这是我对全同态加密设计方法的一点感悟。由于格密码是一种噪声加密的形式，密文、明文与噪声之间是一种线性关系，不像RSA加密算法里有指数的关系，因此格加密天生具有加法同态性，其实也蕴含着乘法同态性，只不过每次乘法都会成倍地增大密文的长度，以及密文中的噪声，所以做不了几次乘法。因此，全同态加密的构造重点都放在如何做更多次（无限）的乘法。本书第1章详细阐述了全同态加密的思想，尽量做到通俗易懂而不涉及过多的技术细节。如果只是想系统了解全同态加密思想与构造方法，而又不想过多涉及技术细节的读者，可以阅读第1章。

2009年诞生了第一个全同态加密，随后诞生了BGV算法（2011年）、Bra12(BFV)算法（2012年）以及GSW算法（2013年）。整个发展趋势是： 全同态加密的构造方法越来越简单，尤其是GSW算法，密文就是矩阵，同态加法与乘法就是矩阵的加法与乘法。GSW算法中没有使用密钥交换，这令我产生了极大的兴趣。2015年，我提出一个新的设计方法： 提升维数法，使用该方法可以去除密钥交换过程。而且提升维数法是一个通用框架，可以设计环LWE问题上所有无须密钥交换的全同态加密方案，因此提升维数法具有重要的理论意义。本书第4章和第5章详细阐述了使用提升维数法构造全同态加密的研究过程。

在提升维数法的基础上，为了研究解密结构与同态性之间的关系，我们抽象定义出一个重要概念： 抽象解密结构。基于抽象解密结构，我们定义了加法和乘法期盼解密结构的概念，将全同态加密的构造分解为两点： 一是如何获得期盼解密结构； 二是如何控制噪声大小。于是，同态性问题归结为如何获得期盼解密结构的问题，噪声控制问题归结为分析噪声依赖主要项的问题。通过抽象解密结构的观点，可以对现有全同态加密方法进行分析，通过期盼解密结构、噪声依赖主要项、最终解密结构等概念，有望统一全同态加密构造方法。此外，我们还提出“密文堆叠法”的概念，可以在最终解密结构与实际解密结构之间建立关于明文的等式关系，从而求解出一个全同态加密方案。整个推导过程具有“机械化”的特征，就像求解数学公式一样，该方法具有通用性。第9章有详细的研究论述。

影响全同态加密效率的原因之一是其参数尺寸过大，所以如何降低全同态加密方案的参数尺寸是一个重要的研究问题。第6章基于BinaryLWE问题，在Linder和Peikert的公钥加密方案基础上，设计一个LWE上参数更小的全同态加密方案，并且对该方案的具体安全参数进行了分析。此外，第7章研究如何通过BinaryLWE对已有全同态加密方案进行噪声控制与优化，并且分析改进前与改进后参数取值的变化。格上的加密算法都是按位加密，即一次加密一位（bit），为了提高全同态加密的计算效率，第8章研究如何设计一次加密多位的全同态加密方案。

尽管全同态加密是从理论开始发展起来的，但是全同态加密的应用一直备受工业界和学术界的关注。记得2011年的论文Can Homomorphic Encryption be Practical?就将全同态加密应用于机器学习中，从而检验其是否可应用落地。当时初识全同态加密，还很奇怪全同态加密和机器学习怎么会有关系。现在看来那些研究者真是高瞻远瞩，大数据时代，数据是生产要素，而数据的隐私计算非常重要，如何保障机器学习中的数据隐私安全是一个重要的研究课题。目前，在机器学习中广泛应用的全同态加密算法就是CKKS算法，第10章详细阐述了CKKS算法的原理。第11章介绍了SEAL全同态加密库的使用。

全同态加密在具体参数下能够保证多少位安全，这是工业界非常关心的一个问题，即全同态加密的具体安全参数问题。LWE问题本质上有3个参数： 维数n、模q、高斯参数r。对于固定的n，q/r与LWE问题的困难性成反比。而在LWE上的全同态加密方案中，高斯参数是事先固定的，所以q取值越大，方案的安全性越低。但是，为了获得更深电路的计算，q取值应尽可能得大。为了保证方案的安全性，在q变大时，可以增大n的值。所以，q与n在全同态加密方案中需要一种平衡。第3章提出了一个分析环LWE上全同态加密算法具体安全参数的方法。该方法引入了敌手优势，能够更真实地反映应用场景的安全需求。通过该方法给出了目前环LWE上的全同态加密算法的具体安全参数。此外，第3章还提出一个基于噪声依赖分析的环LWE上的全同态加密算法分类的方法。通过该方法对目前全同态加密算法的噪声增长进行详细分析，给出紧致的噪声界，为进一步优化算法提供指南。

本书的核心是我这些年的研究成果，也包括一些我在全同态加密领域的学习总结。希望本书对推动我国全同态加密的研究发展贡献一份力量。感谢浙江万里学院学术著作出版资助项目。

作者

2022年1月