全同态加密——从理论到实践

本书以全新的视角“维数提升法”论述全同态加密算法的构造本质。全面介绍目前主流的全同态加密算法，以及全同态加密在机器学习和生物特征密文认证中的应用。
本书适合广大工程技术人员，以及高校师生和科研工作者。为业界人员提供全同态加密技术从理论到应用的全方面指导。

本书主要针对全同态加密的设计方法进行研究。一方面，从理论上提出一些更加有效的全同态加密方案以及优化方法；另一方面，从实践角度提出分析计算全同态加密具体安全参数的方法，并且给出每个方案的具体安全参数，保证了研究的系统性与全面性。本书主要研究如何去除全同态加密设计过程中的密钥交换（key switching）过程，提出一个新的设计方法： 提升维数法。提升维数法是一个通用框架，可以设计环LWE问题上所有无须密钥交换的全同态加密方案。因此，提升维数法具有重要的理论意义。在此基础上，提出两个重要概念： 抽象解密结构与密文堆叠法，以此为理论研究工具，从解密结构中分析密文、噪声与明文之间的关系入手，实现对全同态加密构造方法的理论抽象和规律总结，从而对全同态加密的构造方法进行形式化研究，解决为什么格上能构造出全同态加密、格上已有全同态加密算法之间的关系是什么、是否存在统一的形式化描述所有算法等问题。此外，本书还对基于BinaryLWE问题设计全同态加密以及优化进行了阐述。 本书主要面向密码技术的专业人员以及相关行业的工程技术人员。对于非专业人员，第1章全同态加密入门是非常好的入门学习内容。此外，对于想学习格密码的读者，第2章深入浅出地阐述了格密码的基础理论。

第1章全同态加密入门1
1.1全同态加密引言1
1.1.1为什么需要全同态加密1
1.1.2个全同态加密的诞生3
1.1.3为什么采用电路模型4
1.1.4全同态加密的构造框架5
1.2全同态加密入门7
1.2.1全同态加密的4部分8
1.2.2同态解密控制噪声10
1.2.3LWE上的全同态加密12
1.3详解同态解密思想16
1.3.1一个简化的整数上的加密算法16
1.3.2可怕的噪声17
1.3.3同态解密： 一个生硬的思路18
1.3.4解密电路的复杂度19
1.3.5压缩解密电路21
1.3.6实现算法24
1.4格密码学介绍25

第2章格密码理论基础27
2.1格密码在后量子密码中的优势27
2.2数学基础知识31
2.2.1向量空间简介31
2.2.2矩阵和行列式的一些重要概念33
2.3格理论基础33
2.3.1格的定义及性质33
2.3.2格上的计算问题35
2.4构建格公钥密码系统的方法38
2.4.1陷门单向函数38
2.4.2随机格39全同态加密——从理论到实践目录2.4.3构造单向哈希函数39
2.4.4构造陷门单向函数40
2.4.5格公钥密码系统的框架42
2.5LWE问题43
2.5.1LWE搜索问题43
2.5.2LWE判定问题44
2.5.3构造LWE单向哈希函数46
2.5.4构造LWE陷门单向函数46
2.5.5LWE问题的困难性48
2.5.6高斯分布49
2.6LWE私钥加密算法50
2.7LWE上公钥加密算法52
2.7.1LWE上Regev公钥加密算法 52
2.7.2LWE上Regev公钥加密变形53
2.7.3LWE上多位Regev公钥加密算法53
2.8环LWE问题54
2.9基于环LWE的公钥加密56
2.9.1环LWE上公钥加密算法  56
2.9.2环LWE上公钥加密算法变形56
2.9.3环LWE上的NTRU加密算法57
2.10坏情况下的困难问题58

第3章全同态加密的噪声依赖分析与安全参数分析60
3.1全同态加密61
3.1.1全同态加密定义61
3.1.2全同态加密分类61
3.2全同态加密关键技术62
3.2.1同态解密技术62
3.2.2模交换技术  62
3.2.3位展开技术63
3.2.4密钥交换  64
3.3基于噪声依赖分析的全同态加密算法研究66
3.3.1噪声依赖分析方法66
3.3.2噪声增长依赖于密文中噪声的全同态加密算法: BGV算法67
3.3.3噪声增长依赖于密钥的全同态加密算法: Bra12算法70
3.3.4噪声增长依赖于密文的全同态加密算法： GSW13算法75
3.3.5算法参数尺寸与噪声增长分析比较77
3.4全同态加密具体安全参数分析78
3.4.1具体的安全参数分析方法79
3.4.2Bra12算法和GSW13算法的具体安全参数80

第4章使用提升维数法设计NTRU型无须密钥交换的全同态加密83
4.1问题的提出83
4.2解决问题的主要思想84
4.3提升维数法85
4.4环LWE上NTRU基本加密方案与扩展加密方案87
4.4.1判定小多项式比问题87
4.4.2NTRU基本加密方案87
4.4.3NTRU扩展加密方案88
4.5同态属性89
4.5.1NTRU基本加密方案的同态性89
4.5.2扩展加密方案的乘法同态性89
4.5.3扩展加密方案的加法同态性90
4.6密文同态计算的噪声分析90
4.6.1加法噪声分析90
4.6.2乘法噪声分析91
4.6.3乘法计算优化91
4.7层次型全同态加密91
4.8选择具体安全参数92
4.8.1方案的参数属性92
4.8.2具体参数93
4.9总结94

第5章使用提升维数法设计环LWE上的无须密钥交换的全同态加密96
5.1问题的提出96
5.2解决问题的主要思想97
5.3提升维数法98
5.4密文是矩阵的环LWE上的加密方案99
5.5环LWE上的扩展加密方案100
5.6环LWE上扩展加密方案的同态性101
5.6.1加法同态性101
5.6.2乘法同态性101
5.7密文同态计算的噪声分析102
5.7.1加法噪声分析102
5.7.2乘法噪声分析102
5.8环LWE上扩展加密方案上的层次型全同态加密方案102
5.9密文是矩阵的LWE上加密方案103
5.10LWE上的扩展加密方案104
5.11LWE上扩展加密方案的同态性106
5.11.1加法同态性106
5.11.2乘法同态性106
5.12密文同态计算的噪声分析107
5.12.1加法噪声分析107
5.12.2乘法噪声分析107
5.13LWE上扩展加密方案上的层次全同态加密方案107
5.14选择具体的安全参数108
5.14.1方案的参数属性108
5.14.2具体参数109
5.15总结111

第6章一个基于BinaryLWE的全同态加密方案113
6.1问题的提出113
6.2解决问题的主要思路114
6.3BinaryLWE问题114
6.4改进的基本加密方案115
6.5方案的同态性116
6.5.1加法同态性116
6.5.2乘法同态性117
6.5.3密钥交换117
6.6层次型全同态加密方案118
6.7密文同态计算的噪声分析119
6.7.1加法噪声分析119
6.7.2乘法噪声分析119
6.8选择具体安全参数120
6.8.1方案的参数属性120
6.8.2具体参数121
6.9总结122

第7章基于BinaryLWE噪声控制优化的全同态加密方案改进123
7.1问题的提出123
7.2解决问题的主要思路123
7.3改进的基本加密方案124
7.4方案的同态性125
7.4.1加法同态性126
7.4.2乘法同态性126
7.4.3密钥交换127
7.5层次型全同态加密方案127
7.6密文同态计算的噪声分析128
7.6.1加法噪声分析128
7.6.2乘法噪声分析128
7.7选择具体安全参数129
7.7.1方案的参数属性129
7.7.2具体参数130
7.8总结131

第8章一个LWE上的短公钥多位全同态加密132
8.1一个多位的LWE加密方案132
8.2方案的同态性134
8.2.1加法同态性134
8.2.2乘法同态性134
8.3密钥交换135
8.4层次型全同态加密方案136
8.5噪声分析137
8.6具体安全参数138

第9章基于抽象解密结构的全同态加密构造方法分析141
9.1解密结构与同态性141
9.1.1抽象解密结构142
9.1.2密文乘法期盼解密结构的构造143
9.1.3解密结构与噪声增长依赖主要项144
9.1.4终解密结构145
9.2密文矩阵的解密结构146
9.2.1密文矩阵的解密结构147
9.2.2密文矩阵的终解密结构147
9.3密文堆叠的加密形式148
9.3.1密文矩阵的零次同态加密形式148
9.3.2密文矩阵的全同态加密形式149
9.4通用构造方法150
9.4.1构造思想150
9.4.2通用构造方法介绍150
9.5全同态加密的形式比较151
9.5.1解密结构151
9.5.2密文乘法同态计算形式152
9.5.3噪声控制153
9.5.4终解密结构153

第10章浮点数上的全同态加密算法CKKS155
10.1浮点数同态计算的重要性与挑战155
10.2近似同态计算例子158
10.3分圆多项式159
10.4编码与解码161
10.4.1?瘙綇［X］/(XN 1)→?瘙綇N的编码与解码161
10.4.2?瘙綄［X］/XN 1→?瘙綇N/2的编码与解码162
10.5再缩减技术163
10.6CKKS算法164

第11章SEAL全同态加密库的使用166
11.1设置参数166
11.2密钥生成与加密解密168
11.3示例169
11.4批处理编码172
11.5模交换链174
11.6CKKS算法的使用175
11.7密文中的向量旋转176

参考文献178

附录A注释表187

附录B如何学习全同态加密188

我次接触全同态加密是在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月