第3章
同态加密
学习要求:掌握同态加密的特点、定义和分类;了解同态加密的发展历史;了解典型方
案的构造思想,理解同态加密的应用场景,能够运用不同类型的同态加密解决实际问题;理
解自举的概念;掌握理想格的概念及格上的两类难题;了解BGN,Gentry和CKKS方案设
计的主要思想;掌握基于Paillier的隐私信息获取的应用示例,以及基于SEAL的CKKS的
开发案例。
课时:2课时
建议授课进度:3.1节~3.2节用1课时,3.3节~3.5节用1课时
3.1 基本概念
3.1.1 定义
同态加密是一种加密算法,它可以通过对密文进行运算得到加密结果,解密后与明文运
算的结果一致,如图3-1所示。
图3-1 同态加密效果图
同态加密主要基于公钥密码体制构建,它允许将加密后的密文发给任意的第三方进行计
算,并且在计算前不需要解密,可以在不需要密钥方参与的情况下,在密文上直接进行计算。
同态加密方案由KeyGen,Encrypt,Decrypt和Evaluate4个函数构成。
(1)KeyGen(λ)→(pk,sk):密钥生成函数;在给定加密参数λ 后,生成公钥/私钥对
(pk,sk)。
第3章 同态加密
(2)Encrypt(pk,pt)→ct:加密函数;使用给定公钥pk将目标明文数据pt加密为密
文ct。
(3)Decrypt(sk,ct)→pt:解密函数;使用给定密钥sk将目标密文数据ct解密为明
文pt。
(4)Evaluate(pk,Π,ct1 ,ct2,…)→(ct'1,ct'2,…):求值函数;给定公钥pk与准备在密
文上进行的运算函数Π,求值函数将一系列的密文输入(ct1,ct2,…)转换为密文输出(ct'1,
ct'2,…)。
求值函数是同态加密方案不同于传统加密方案的部分。它的参数Π 支持的运算函数
种类决定了该同态加密方案支持的同态运算操作。
在给定以上4个函数后,同态加密方案应满足正确性、语义安全性和简短性。
(1)正确性:一个同态加密系统必须要是正确的。具体来说,也就是加密之后的密文
可以被成功解密,并且求值函数输出的密文也可以成功解密回原文。
(2)语义安全性:同态加密系统输出的密文必须难以分辨。具体来说,如果有一个网
络窃听者看到了所有的密文,那么这个窃听者并不能分辨出哪个密文是对应哪个原文的。
(3)简短性:同态加密的求值函数输出的密文的长度需要在一个可以控制的长度范围
内,确保了同态加密系统的实用性。
3.1.2 分类
根据同态加密算法所支持的同态操作种类和次数,可以将现有同态加密方案分为以下
几种类型。
(1)半同态加密(partialhomomorphicencryption,PHE):仅支持单一类型的密文域同
态运算(加或乘同态)。
(2)类同态加密(somewhathomomorphicencryption,SHE):能够支持密文域有限次
数的加法和乘法同态运算。
(3)层级同态加密(leveledhomomorphicencryption,LHE):能同时支持多种同态操
作(加或乘同态),并可以在安全参数中定义能够执行的操作次数上限。一般允许的操作次
数越大,该同态加密方案的密文空间开销及各类操作的时间复杂度就越大。
(4)全同态加密(fullyhomomorphicencryption,FHE):能够实现任意次密文的加、乘
同态运算。
3.1.3 发展历史
同态加密的发展历史如表3-1所示。
表3-1 同态加密的发展历史
类 型算法时间说 明
半同态加密
RSA算法1977年
非随机化加密,具有乘法同态性的原始算法面临选择明文
攻击
ElGamal算法1985年随机化加密,乘法同态
Paillier算法1999年加法同态,在联邦学习中广泛应用
55
续表
数据安全与隐私计算基础
类 型算法时间说 明
类同态加密BGN方案2005年支持任意次加法和一次乘法操作的同态运算
全同态加密
第一代
第二代
第三代
第四代
Gentry方案2009年自举操作,性能差
BGV方案2012年基于算术电路,基于模归约提升了自举性能
BFV方案2012年基于算术电路,使用SIMD操作提升了自举性能
GSW 方案2013年支持任意布尔电路,基于近似特征向量
FHEW 方案2015年支持任意布尔电路,可实现快速比较
TFHE方案2016年支持任意布尔电路,基于近似特征向量
CKKS方案2017年可实现浮点数近似计算
1. 半同态加密
(1)乘法同态加密是指存在有效算法..,使得Enc(x)..Enc(y)=Enc(xy)或者Dec
(Enc(x)..Enc(y))=xy 成立,并且不泄露x 和y。
典型乘法同态加密算法是RSA 算法和ElGamal算法。以RSA 算法为例,如果c1=
me 1modn,c2=me 2modn,那么c1c2=me1
me 2modn=(m1m2)emodn≡Enc(m1m2)。
(2)加法同态加密是指存在有效算法..,使得Enc(x)..Enc(y)=Enc(x+y)或者Dec
(Enc(x)..Enc(y))=x+y 成立,并且不泄露x 和y。
典型加法同态加密算法是Paillier算法,详见3.2节描述。
注意:加法和乘法同态是相对明文而言所执行的操作,而非密文上执行的运算形式。
2. 类同态加密
类同态加密方案能够同时支持加法和乘法的同态操作。但由于它生成的密文随着操作
次数的增加而逐渐增大,能够在密文上执行的同态操作次数是有上限的。
典型的类同态加密方案是Boneh、Goh和Nissim 在2005年提出的Boneh-Goh-Nissim
(BGN)方案①,它支持在密文大小不变的情况下进行任意次数的加法和一次乘法。该方案
中的加法同态基于类似Paillier算法的思想,而一次乘法同态基于双线性映射的运算性质。
虽然该方案是双同态的(同时支持加法同态和乘法同态),但只能进行一次乘法操作。
3. Gentry 方案(第一代全同态加密方案)
在同态加密概念提出后的30年间,并没有真正能够支持无限制的各类同态操作的全同
态加密方案问世。
2009年,Gentry② 基于所提出的类同态加密方案,提出了自举(bootstrapping)技术,可
以将满足条件的类同态加密方案改造成全同态加密方案。其基本思想是在类同态加密算法
的基础上引入自举方法来控制运算过程中的噪声增长(类同态加密算法操作次数过多会导
56
①
②
BONEH D,GOH EJ,NISSIM K.Evaluating2-DNFformulasonciphertexts[C]//TheoryofCryptography
Conference,2005:325-341.
GENTRYC.Afullyhomomorphicencryptionscheme[M].StanfordUniversity,2009.
第3章 同态加密
致噪声过大而无法解密),这也是第一代全同态加密方案的主流模型。
为了避免多次运算使得噪声扩大,Gentry方案采用了计算一次就消除一次噪声的方
法,而消除噪声的方法还是使用的同态运算。但是,由于解密过程本身的运算十分复杂,运
算过程中也会产生大量噪声,因此,Gentry方案性能极差,一次同态乘法可能需要30min。
现在的第四代全同态加密解决方案要比Gentry提出的方案要好得多,性能大概提高了
100万倍,并且已经开始制定相关的标准。
4. BGV 和BFV 方案(第二代全同态加密方案)
第二代全同态加密方案主要包括BGV① 和BFV②,通常基于容错学习问题(learning
witherror,LWE)和环上容错学习问题(ringlearningwitherror,RLWE)假设,其安全性基
于格困难问题。
第二代方案主要是解决自举操作带来的昂贵操作,通过引入层级同态加密等来提升性
能。此外,第二代全同态加密还提出了单指令多数据(singleinstruction multipledata,
SIMD)操作,通过批量处理来提高吞吐量,极大降低了均摊复杂度。简单来说,SIMD 操作
把密文切出上千个槽,把上千个明文放在这些密文槽中,这样,就可以并行处理各个槽中的
数据了。在此基础上,还可以利用同构性置换各个槽中的数据,各个槽中的数据也可以相互
运算。第
二代全同态加密方案的性能已经提升了很多,每个明文位的自举时间约为0.9ms,自
举一个密文能在10s左右完成,具有了一定的实用性。HElib和SEAL(simpleencrypted
arithmeticlibrary)两个全同态加密开源库均支持BGV 和BFV 方案。
5. TFHE 等方案(第三代全同态加密方案)
GSW③,FHEW④ 和TFHE⑤ 是第三代同态加密方案重要的代表作。与第二代FHE方
案相比,自举的性能得到大幅度提升,在常见的台式机平台上速度可以达到毫秒级别;但同
时因为缺少第二代FHE的SIMD特性,FHEW 只能处理若干位(典型值为2~7)的加法和
乘法操作,也就是说同态乘法的性能较差。
6. CKKS 等方案(第四代全同态加密方案)
CKKS方案⑥支持针对实数或复数的浮点数加法和乘法同态运算,但是得到的计算结
果是近似值。因此,它适用于不需要精确结果的场景。支持浮点数运算这一功能在实际中
57
①
②
③
④
⑤
⑥
BRAKERSKIZ,GENTRY C,VAIKUNTANATHAN V.(Leveled)fullyhomomorphicencryptionwithout
bootstrapping[J].ACM TransactionsonComputationTheory,2014,6(3):1-36.
BRAKERSKIZ.FullyhomomorphicencryptionwithoutmodulusswitchingfromclassicalGapSVP[C]//Annual
cryptologyconference,2012:868-886.
GENTRYC,SAHAIA,WATERSB.Homomorphicencryptionfromlearning witherrors:Conceptuallysimpler,
asymptotically-faster,attribute-based[C]//Annualcryptologyconference,2013:75-92.
DUCASL,MICCIANCIO D.FHEW:Bootstrappinghomomorphicencryptioninlessthanasecond[C]//
Annualinternationalconferenceonthetheoryandapplicationsofcryptographictechniques,2015:617-640.
CHILLOTTII,GAMAN,GEORGIEVA M,etal.TFHE:Fastfullyhomomorphicencryptionoverthetorus
[J].JournalofCryptology,2020,33(1):1-58.
CHEONJH,KIM A,KIM M,etal.Homomorphicencryptionforarithmeticofapproximatenumbers[C]//
AdvancesinCryptology-ASIACRYPT2017,2017:409-437.
数据安全与隐私计算基础
有非常重要的作用,如实现机器学习模型训练等。这个方案的性能也非常优异,大多数算法
库都实现了CKKS。
注意:有关全同态加密的发展历程,可以关注Gentry在EUROCRYPT2021上的邀请
报告,网络上有中文翻译版。
3.2 半同态Paillier方案
Paillier加密算法①是Paillier等于1999年提出的一种基于判定n 阶剩余类难题的典型
密码学加密算法,具有加法同态性,是半同态加密方案。
3.2.1 数学基础
1. 卡迈克尔函数
在数论中,卡迈克尔函数的定义如下:设gcd(a,n)=1,gcd为求最大公约数,使得am ≡
1modn 成立的最小正整数m ,将m 记作λ(n)。对于n=pq,p 和q 都是素数,则有λ(n)=
lcm(p-1,q-1),lcm 为求最小公倍数。
在数论中,对正整数n,欧拉函数是小于n 的正整数中与n 互质的数的数目。显然
.(1)=1,而对于m >1,.(m )就是{1,2,…,m -1}中与m 互素的数的个数,如果p 是素数,
则有.(p)=p-1。对于n=pq,p 和q 都是素数,则有.(n)=(p-1)(q-1)。显然,如果
p-1和q-1也分别为素数的话,那么.(n)=λ(n),否则,.(n)是λ(n)的倍数。
表3-2是卡迈克尔函数λ(n)与欧拉函数.(n)的对比表。
表3-2 卡迈克尔函数λ(n)与欧拉函数.(n)的对比表
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
λ(n) 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4
.(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8
1)示例
8的卡迈克尔函数是2,即λ(8)=2,即对于任意的a 满足gcd(a,8)=1,有am ≡
1mod8,也就是说12≡1mod8,32≡1mod8,52≡1mod8,72≡1mod8。
而对于欧拉函数来说,.(8)=4,因为欧拉函数是计算与8互素的数的数量,即1,3,
5,7。
对于n=15,因为n=3×5,令p=3,q=5,λ(15)=lcm(2,4)=4,.(15)=2×4=8。
2)卡迈克尔函数的性质
设n=pq,其中:p 和q 是大素数。那么.(n)=(p-1)(q-1),λ(n)=lcm(p-1,q-1)。
为便于描述,用λ 表示λ(n)。
对于任意g∈Zn*2 ,有如下性质:
58
① PAILLIERP.Public-keycryptosystemsbased oncompositedegreeresiduosityclasses[C]//International
conferenceonthetheoryandapplicationsofcryptographictechniques,1999:223-238.
第3章 同态加密
gλ≡1modn
gnλ≡1modn2 {
具体推导如下。
根据λ 的定义,可得λ=k1(p-1)=k2(q-1)
根据费马小定理gp-1=1modp,可得
gλ=gk1(p-1)=(gp-1)k1 ≡1modp
同理gλ≡1modq
所以gλ≡1modpq=1modn
所以gλ=1+kn,k∈Zn*
结合上式及二项式定理,可得
gnλmodn2=(1+kn)nmodn2≡(1+kn2)modn2≡1modn2
推导中使用了如下性质:对于1+n∈Zn*2 ,有
(1+n)2≡1+2n+n2≡(1+2n)modn2
(1+n)3≡1+3n+n3≡(1+3n)modn2
(1+n)v ≡1+vn+…≡(1+vn)modn2
2. 判定复合剩余假设
剩余类:也称同余类,指全体整数按照对一个正整数的同余关系而分成的类。对于一
个整数m ,可以把所有整数分成m 类,每类模m 后余数都相同,每一类都叫作m 的一个剩
余类。比如,给定整数5,有5个剩余类,对0同余的有{-5,0,5,…}。
复合剩余类:如果存在一个数x∈Zn*2 ,那么符合公式z=xnmodn2 的数z,称为x 模
n2 的n 阶剩余类。或者说,如果数z 被称为x 的模n2 的n 阶剩余类,则存在一个数x∈
Zn*2 ,使得z=xnmodn2。
判定复合剩余假设(decisionalcompositeresiduosityassumption ,DCRA):设n=pq,p
与q 为两个大素数,对于任意给定的整数z,判断它是不是模n2 的n 阶剩余类是一个难解
问题。
3.2.2 方案构造
1. 算法描述
1)密钥生成
(1)随机选择两个素数p 和q,尽可能地保证p 和q 的长度接近或相等(安全性高)。
(2)计算n=pq 和λ=lcm(p-1,q-1),其中lcm 表示最小公倍数。
(3)随机选择g∈Zn*2 ,考虑计算性能优化,通常会选择g=n+1。
(4)计算μ=[L(gλmodn2)]-1modn,其中L(x)=x-1 n 。
(5)公钥为(n,g)。
(6)私钥为(λ,μ)。
2)加密算法
对于任意明文消息m ∈Zn ,任意选择一个随机数r∈Zn* ,计算得到密文
59
数据安全与隐私计算基础
c=E(m )=gmrnmodn2
注意:密文c 要比明文m 更长。
3)解密算法
对于密文c∈Zn*2 ,计算得到明文
m =D (c)=L(cλmodn2)μmodn
2. 正确性
依据卡迈克尔函数的性质,对于任意g∈Zn*2 ,n=pq 和λ=lcm(p-1,q-1),有
gλ≡1modn
gnλ≡1modn2 {
如3.2.1节所述,gλ=1+kn,k∈Zn* ,基于上述三个性质,解密过程推导如下。
D (c)=L(cλmodn2)μmodn
=L((gmrn)λmodn2)μmodn
参考rnλ≡1modn2 性质可得
D (c)=L((gλ)m modn2)(L(gλmodn2))-1modn
=L((1+kn)m modn2)(L(1+kn)modn2)-1modn
参考(1+n)v ≡1+vn+…≡(1+vn)modn2 可得
D (c)=L((1+mkn)modn2)(L(1+kn)modn2)-1modn
=mkk-1modn
=m
3. 加法同态性
对于任意明文m1,m2∈Zn 和任意r1,r2∈Zn* ,对应密文c1=E(m1),c2=E(m2),满足
c1c2=gm1rn1
gm2rn2
modn2=gm1+m2(r1r2)nmodn2
解密后得到
D (c1c2)=D (gm1+m2(r1r2)nmodn2)=m1+m2
即c1c2=m1+m2,也就是,密文乘等于明文加。
注意:这里定义的密文加法运算形式是乘法运算,但是因为运算的结果是明文相加,因
此是加法同态。加法或乘法同态是相对明文而言所执行的操作,而非密文上执行的运算
形式。
4. 标量乘同态性
对于明文m1∈Zn 及其密文c1,给定一个整数a∈Zn ,满足
D (ca1
modn2)=D (gm1a(ra)nmodn2)=m1a
注意:这里定义的密文标量乘运算形式是指数运算ca1
,但是因为运算的结果解密是常
数乘明文m1a,因此是标量乘法。
3.2.3 应用示例
1. 典型应用
半同态加密虽然还不能同时支持加法和乘法运算,不能支持任意地计算,但是因为其与
60
第3章同态加密
全同态相比,具有较高性能,因此,仍然具有极为广泛的应用场景,且在现实应用中起到了重
要的作用。一类典型的应用体现在隐私保护的数据聚合上。由于加法同态加密可以在密文
上直接执行加和操作,不泄露明文,在多方协作的统计场景中,可完成安全的统计求和的
功能。
1)联邦学习
federatedlearning,FL)
在联邦学习(中,不同参与方训练出的模型参数可由一个第三方
进行统一聚合。使用加法PHE,可以在明文数据不出域且不泄露参数的情况下,完成对模
型参数的更新,此方法已在实际中应用(如FATE),如图3-2所示。
图3-2 联邦学习中的安全聚合示例
2)隐私集合求和
在线广告投放的场景中,广告主(如商家)在广告平台(如媒体)投放在线广告,并希望计算
广告点击的转化收益。然而,广告点击数据集和购买数据集分散在广告主和广告平台两方。
使用加法PHE结合隐私集合求和(privateintersection-sum-with-cardinality,PIS-C)协议可以在
保护双方隐私数据前提下,计算出广告的转化率。如图3-3所示,协议中的隐私保护求和功能
依赖于广告主将自己的交易数据用PHE加密发送给广告平台,使得广告平台在看不到原始数
据的前提下,完成对交集中数据金额的聚合。该方案已被Gogle落地应用。
图3-3 加法PHE在PIS-C中的应用
16
数据安全与隐私计算基础
3)数据库统计查询
在加密数据库SQL查询场景,在数据库不可信的情况下,可以通过部署协议和代理来
保护请求者的查询隐私。其中,PHE可以用来完成安全数据求和、均值的查询。
除了上述场景,加法PHE还可被用于多种行为数据和效益数据分离的商业场景,在应
用上有着很大的想象空间。
2. 实验环境安装
1)安装Python环境
在Windows操作系统下安装Python开发环境,可以进入官方网站https://www.
python.org/downloads/,下载Windows操作系统的Python安装包,下载后运行下载文件
并按照安装向导的指示安装即可。
注意:安装时一定要勾选Addpython.exetoPATH 复选框,这样会使得安装后的
Python程序路径直接加入时系统的环境变量中,在控制台可以直接使用Python命令。如
果忘记勾选,则需要右击“我的电脑”图标,在弹出的快捷菜单中选择“属性”→“高级系统设
置”→“环境变量”命令,在Path中将安装的路径手动输入。
安装完毕,打开控制台,输入Python命令,如图3-4所示。
图3-4 进入Python环境
这代表已经安装成功,并且进入Python运行环境。
(1)输入Python程序。
from phe import paillier
该命令将导入phe库的paillier功能,第一次执行会提示ModuleNotFoundError:No
modulenamed'phe'。这是因为,默认安装Python程序后,并没有安装phe库。
(2)输入退出命令。
exit()
该命令可以退出当前Python环境,切回控制台模式,如图3-5所示。
图3-5 退出Python环境
62
第3章 同态加密
2)安装phe库
输入如下命令。
pip install phe
完成phe库的安装,如图3-6所示。
图3-6 安装phe库
pip是Python语言的一个安装库的工具,可执行文件在Python程序安装目录下可以
找到。
3)验证环境正确性
再次进入Python环境,输入如下Python代码。
from phe import paillier
结果如图3-7所示。
图3-7 验证环境正确性
如果不出现错误信息,说明环境安装成功。
4)编写Python程序并运行
可以用三种方式调试和编写Python程序。
(1)在控制台运行Python命令,逐行编写Python程序并运行。
(2)用文本编辑器编写完整的程序并保存为x.py文件,通过控制台命令pythonx.py
的方式完成整个程序的调用。
(3)通过自带的集成开发环境IDLE完成开发和调试运行。通过开始菜单,找到IDLE
并打开,选择File→NewFile菜单项可以新建一个文件,编辑程序并保存后,选择Run→
RunModule菜单项运行,会看到运行的结果。
3. 简单示例
phe库的使用说明详见https://python-paillier.readthedocs.io/en/develop/usage.html
#usage。
实验3-1 基于Python语言的phe库完成加法和标量乘法的验证。
演示代码如下。
1. from phe import paillier #开源库
2. import time #做性能测试
63
数据安全与隐私计算基础
3.
4. #####################设置参数
5. print("默认私钥大小:", paillier.DEFAULT_KEYSIZE)
6. #生成公私钥
7. public_key, private_key = paillier.generate_paillier_keypair()
8. #测试需要加密的数据
9. message_list = [3.1415926,100,-4.6e-12]
10.
11. #####################加密操作
12. time_start_enc = time.time()
13. encrypted_message_list = [public_key.encrypt(m) for m in message_list]
14. time_end_enc = time.time()
15. print("加密耗时s:",time_end_enc-time_start_enc)
16. print("加密数据(3.1415926):",encrypted_message_list[0].ciphertext())
17.
18. #####################解密操作
19. time_start_dec = time.time()
20. decrypted_ message _ list = [private _ key. decrypt ( c) for c in encrypted _
message_list]
21. time_end_dec = time.time()
22. print("解密耗时s:",time_end_dec-time_start_dec)
23. print("原始数据(3.1415926):",decrypted_message_list[0])
24.
25. #####################测试加法和乘法同态
26. a,b,c = encrypted_message_list #a,b,c 分别为对应密文
27. a_sum = a + 5 #密文加明文,已经重载了+运算符
28. a_sub = a - 3 #密文加明文的相反数,已经重载了-运算符
29. b_mul = b * 6 #密文乘明文,数乘
30. c_div = c / -10.0 #密文乘明文的倒数
31. print("a+5 密文:",a.ciphertext()) #密文纯文本形式
32. print("a+5=",private_key.decrypt(a_sum))
33. print("a-3",private_key.decrypt(a_sub))
34. print("b*6=",private_key.decrypt(b_mul))
35. print("c/-10.0=",private_key.decrypt(c_div))
36. ##密文加密文
37. print((private _key.decrypt(a) + private _key.decrypt(b)) = = private _key.
decrypt(a+b))
38. #报错,不支持a*b,即两个密文直接相乘
39. #print((private_key.decrypt(a)+ private_key.decrypt(b))= = private_key.
decrypt(a*b))
如上述代码所示:第一,Python程序对运算符进行了承载,已经支持直接密文上的运
算;第二,只支持明文的加法,不支持明文的乘法,最后一句如果将注释符去掉,将报错。
4. 隐私信息获取示例
实验3-2 基于Python语言的phe库完成隐私信息获取的功能:服务器拥有多个数
值,要求客户端能基于Paillier实现从服务器读取一个指定的数值并正确解密,但服务器不
知道所读取的是哪一个。
64
第3章 同态加密
首先,基于Paillier协议进行设计。
对Paillier的标量乘的性质进行扩展,可以知道:数值0的密文与任意数值的标量乘也
是0,数值1的密文与任意数值的标量乘将是数值本身。
基于这个特性,可以进行如下巧妙设计。
服务器:产生数据列表message_list={m1,m2 ,…,mn}。
客户端:
(1)设置要选择的数据位置为pos。
(2)生成选择向量select_list={0,…,1,…,0},其中:仅有pos的位置为1。
(3)生成密文向量enc_list={E(0),…,E(1),…,E(0)}。
(4)发送密文向量enc_list给服务器。
服务器:
(1)将数据与对应的向量相乘后累加得到密文
c=m1*enc_list[1]+…+mn *enc_list[n]
(2)返回密文c 给客户端。
客户端:解密密文c 得到想要的结果。
然后,开发具体代码如下。
1. from phe import paillier #开源库
2. import random #选择随机数
3.
4. #####################设置参数
5. #服务器保存的数值
6. message_list = [100,200,300,400,500,600,700,800,900,1000]
7. length = len(message_list)
8. #客户端生成公私钥
9. public_key, private_key = paillier.generate_paillier_keypair()
10. #客户端随机选择一个要读的位置
11. pos = random.randint(0, length-1)
12. print("要读起的数值位置为:", pos)
13.
14. #####################客户端生成密文选择向量
15. select_list=[]
16. enc_list=[]
17. for i in range(length):
18. select_list.append(i == pos)
19. enc_list.append(public_key.encrypt(select_list[i]))
20. #####################服务器进行运算
21. c=0
22. for i in range(length):
23. c = c + message_list[i] * enc_list[i]
24. print("产生密文:", c.ciphertext())
25.
26. #####################客户端进行解密
27. m=private_key.decrypt(c)
28. print("得到数值:", m)
65
数据安全与隐私计算基础
扩展思考:在客户端保存对称密钥k,在服务器存储m 个用对称密钥k 加密的密文,通
过隐私信息获取方法得到指定密文后能解密得到对应的明文,如何设计实现?
3.3 类同态BGN 方案
1994年,Fellows和Koblitz提出第一个同时支持同态加法和同态乘法的类同态加密方
案①,其密文大小随着同态操作的次数呈指数级增长,且同态乘法的计算开销很大,无法投
入实际使用。2005年,BGN 加密方案②提出,它支持在密文大小不变的情况下进行任意次
数的加法和一次乘法。
3.3.1 数学基础
1. 群
群是一种由元素的集合和一个二元运算组成的基本代数结构。若元素集合G 和二元
运算“·”满足封闭性、结合律、单位元和逆元素四个要素,则称为群。
(1)封闭性:对于所有集合G 中的元素a 和b,a·b 的结果也在集合G 中。
(2)结合律:(a·b)·c=a·(b·c)对任意a,b,c∈G 成立。
(3)单位元:集合G 存在元素e,满足e·a=a·e=a,.a∈G。
(4)逆元素:对于集合G 中的任意一个元素a,存在集合G 中的另一个元素b 使a·b=
b·a=e。
若一个群还满足交换律(即a·b=b·a,对任意a,b∈G 成立),则可进一步称为交换
群或阿贝尔群。定义一个有限群的阶为群中元素的个数。对于二元运算“·”,定义元素的
乘方a2 为a·a,并以此推演出元素的更高次方。
若一个群G 的每一个元素都可以被表达成群G 中某一个元素g 的次方gm ,则称G 为
循环群,记作G=(g)={gm|m ∈Z},g 被称为G 的一个生成元,因为可以通过对g 的不断
自我运算来获得群中的所有元素。
注意:符号<g>与符号(g)相同,也经常被定义为由g 生成的循环群。
在一个有限群中,如果对不是生成元的其他元素a 进行这种次方运算,它最终会循环
遍历一个群G 的子集。可以证明,所有元素的这种遍历都会经过单位元e。将满足an =e
的最小正整数n 称为a 元素的阶,生成元的阶和群的阶相等。
以整数模6加法群Z6={0,1,2,3,4,5}为例,其群的阶为6,单位元为0。6个元素的阶
分别是1,6,3,2,3,6。其中:1,5为生成元。
以元素5为例,经过模加运算有
51=5
52=(5+5)(mod6)=4
66
①
②
FELLOWSM,KOBLITZ N.Combinatorialcryptosystemsgalore! [J].Contemporary Mathematics,1994,
168:51.
BONEH D,GOH EJ,NISSIM K.Evaluating2-DNFformulasonciphertexts[C]//TheoryofCryptography
Conference,2005:325-341.
第3章 同态加密
53=(5+5+5)(mod6)=3
54=(5+5+5+5)(mod6)=2
55=(5+5+5+5+5)(mod6)=1
56=(5+5+5+5+5+5)(mod6)=0=e
故称元素5的阶为6,为群G 的生成元。
可以很容易发现循环群的一个特性,即由生成元g 构建的循环群很容易满足加法同
态:gr1 ·gr2 =g(r1+r2)。根据上述例子,很容易验证:对于明文1和2,对应的密文是55 和
54,因为这里的运算符“·”就是加法,显然,55·54=59=(56·53)(mod6)=53=5(1+2)=3。
2. 环
在群的基础上,还可以使用两种运算和元素集合R 来构建环(ring),这两种运算一般写
作“+”和“·”。
(1)“+”一般表示环上的加法,其对应的单位元通常为0,由其定义的群为加法群,群上
的两个相同运算的“+”运算,可以记作a+a=2a。
(2)“·”一般表示环上的乘法,其对应的单位元通常记作e,由其定义的群为乘法群,群
上的两个相同运算的“·”运算,可以记作a·a=a2。
环可以认为是在加法交换群之上增加了乘法运算“·”,且满足如下性质。
(1)封闭性:对于所有R 中元素a 和b,a·b 的结果也在R 中。
(2)结合律:(a·b)·c=a·(b·c)对任意a,b,c∈R 成立。
(3)单位元:R 存在元素e,满足e·a=a·e=e,.a∈R,该元素常被称为乘法单
位元。
(4)分配律:乘法操作可以在加法之间进行分配。即给出任意a,b,c∈R,有a·(b+
c)=a·b+a·c 和(b+c)·a=b·a+c·a。
事实上,满足上述封闭性和结合律的(R,·)构成一个半群。再加上单位元,就构成一
个幺半群。如果再有逆元素,就构成了一个群。
(R,+,·)若满足:
(1)(R,+)构成交换群;
(2)(R,·)构成幺半群;
(3)(R,+,·)满足分配律。
则其构成一个环。
在一个环(R,+,·)中,若其子集I 与其加法构成子群(I,+),且满足.i∈I,r∈R,
i·r∈I,则称I 为环R 的一个右理想(rightideal)。若.i∈I,r∈R,r·i∈I 则称I 为环
R 的一个左理想(leftideal)。若同时满足左右理想,则称I 为环R 上的一个理想(ideal)。
理想对内具有乘法封闭性,对外具有乘法吸收性。
3. 域
域是环的一种特殊形式,它要求乘法运算必须满足交换律,因此域是交换环,还要求域
中的除0外的所有元素都有乘法逆元素。
有限域,就是一个包含有限个元素的域。一个有限域的具体例子就是模p 的整数域,
其中:p 是一个素数。通常有限域可表示为Zp 。
67
数据安全与隐私计算基础
从群到环,再到域,是一个条件逐渐收敛的过程。
4. 双线性映射
一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素的函数,
并且该函数对每个参数都是线性的。若B:V×W →X 是一个双线性映射,则V 固定,W 可
变时,W 到X 的映射是线性的;W 固定,V 可变时,V 到X 的映射也是线性的。也就是说,
保持双线性映射中的任意一个参数固定,另一个参数对X 的映射都是线性的。
存在一个加法循环群G1 和乘法循环群G2,这两个群的阶都为大素数q。定义e:G1×
G1→G2 为这两个循环点群之间的一个双线性映射,且该映射满足如下三个性质。
(1)双线性:对于所有的P ,Q∈G1 和a,b∈Z* q ,有
e(aP ,bQ)=e (P ,Q)ab
e[(a +b)P ,Q]=e(P ,Q)a ·e(P ,Q)b
其中,Z* q 表示不包含0的整数集,Z表示整数集,q 表示阶,*表示不包含0元素。
(2)非退化性:e 为非平凡映射,即e 不会将G1×G1 的所有值映射到G2 的单位元。
(3)可计算性:具有有效的算法对于任何的P ,Q∈G1 能够计算e(P ,Q)。
满足如上三个性质的双线性映射就称为可采纳的双线性映射。
Boneh等给出了关于双线性映射更具体的描述,提出了与双线性相关的数学难题,并用
于设计基于身份加密、基于属性的加密等密码原语。
5. 子群判定问题
子群判定问题是指给定(n,G,G1,e),其中:群G,G1 具有相同的阶n=pq;e:G×G→
G1 是一个双线性映射,给定一个元素x∈G,如果x 的阶是p,则输出1,否则输出0。
上述问题也可以描述为一个阶为n=pq(p,q 为素数)的合数阶群里,判定一个元素是
否属于某个阶为p 的子群的问题。
该判定问题为困难问题,BGN 方案的实现就是基于子群判定问题。
3.3.2 方案构造
BGN 能够同时支持加法和乘法的关键原因在于,它提出了一套能够构建在两个群G
和G1 之间的双线性映射e:G×G→G1 的方法。BGN 提出的方法能够生成两个阶相等的
乘法循环群G 和G1,并建立其双线性映射关系e,且满足当g 是G 的生成元时,e(g,g)为
G1 的生成元。
在执行乘法之前,密文属于群G 中的元素,可以利用群的二元操作进行密文的加法同
态操作。密文的乘法同态操作通过该双线性映射函数,将密文从群G 映射到G1 的元素当
中。执行乘法同态操作之后,处于G1 的密文仍然能够继续使用同态加法。
1. 密钥生成
(1)给出安全参数,选择大素数q1,q2 并获得合数n=q1q2,BGN 将构建两个阶为n 的
循环群G,G1 和双线性映射关系e:G×G→G1。
(2)从G 中随机选取两个生成元g,u,并获得h=uq2 。可知h 为某阶为q1 的G 的子
群的生成元。
68
第3章 同态加密
(3)公钥设置为(n,G,G1,e,g,h),私钥设置为q1。
2. 加密
对于消息明文m (某小于q2 的自然数),随机抽取0到n 之间的一个整数r,生成密文
c=E(m )=gmhr∈G
3. 解密
使用私钥q1,首先计算
cq1 =(gmhr)q1 =(gmuq2r)q1 =gmq1uq2q1r=gmq1unr=(gq1)m
然后,计算离散对数得到明文m =loggq1 (cq1)。
3.3.3 同态性
1. 密文上的同态加法性质
由生成元g 构建的循环群很容易构造加法同态,gr1 ·gr2 =g(r1+r2)。
对于两个密文c1=gm1 ·hr1 和c2=gm2 ·hr2 ,很明显c1·c2=g(m1+m2)·h(r1+r2)。
2. 密文上的同态乘法
密文上的同态乘法,则通过双线性映射函数实现,e(ua ,vb)=e(u,v)ab。
在密钥生成的时候,定义g1=e(g,g)和h1=e(g,h),且将h 写作h=gαq2 (因为g 可
生成u:u=gα),定义对c1 和c2 的同态乘法运算为
e(c1,c2)hr1
=e(gm1hr1 ,gm2hr2)hr1
=gm1m1 2h^r1∈G1
其中:r^是前文提到的随机抽取的0到n 之间的整数r。
由此可见,经过同态乘法之后的密文从G 转移到了G1,其解密过程在G1 上完成,即G1
的生成元g1=e(g,g)替代g。在群G1 上依然可以进行乘法同态操作,所以BGN 支持同
态乘法运算之后的同态加法运算。
但是,因为没有下一个群可以继续映射,BGN 加密的密文只能够支持一次同态乘法
运算。
3.4 全同态典型方案
3.4.1 数学基础
1. 格的定义
给定一个n 维向量空间Rn ,格(lattice)是其上的一个离散加法子群。
根据线性代数知识,可以构造一组n 个线性无关的向量v1,v2,v3,…,vn ∈Rn 。基于该
组向量的整数倍的线性组合,可以生成一系列的离散点,即
L(v1,v2,v3,…,vn)= Σn
i=1
{ αivi|αi ∈Z}
这些元素集合和对应的加法操作(L,+)称为格。这组线性无关的向量B(即v1,v2,
v3,…,vn)称为格基,其向量个数称为格的维度。
69
数据安全与隐私计算基础
2. 格的示例
格基(1,0)T 与(0,1)T 可以产生二维空间的所有整数格,如图3-8(a)所示。同时,使用
格基(1,0)T 与(1,1)T 同样可以生成二维空间的所有整数格,如图3-8(b)所示。也就是说,
一个格的基向量可以有多个,图3-8(a)的基向量正交程度好一些,称为“好基”,而图3-8(b)
的基向量正交程度坏一些,称为“坏基”。
图3-8 二维空间的格示例
再如,格基(1,1)T 与(2,0)T 不能产生二维空间的所有整数格。如图3-9所示,标有
图3-9 二维空间的格示例
“×”号的为可产生的格,其横纵坐标相加为偶数。
上面都是简单的二维例子,一个格可以由无限
多的维度和无限多的向量组成,所以虽然二维看起
来非常简单,但是随着基向量和维度的数量增加
时,问题很快会变得非常复杂。一般来说,对于达
到足够安全性的方案,格的维度在1000左右。
注意:通过图3-9可以看出,并非所有的基都
能生成一个格上的所有元素,而且通过“坏基”推测
一个“好基”是一个难题。
3. 格上的难题
尽管格也由基扩展获得,它和向量空间最大的不同在于,它的系数限制为整数,从而生
成一系列离散的空间向量。格上的向量的离散性质催生了一系列新的难题。
格上的主要难题是最近向量问题(closestvectorproblem,CVP)和最短向量问题
(shortestvectorproblem,SVP)。
定义3-1(最近向量问题) 给定一个格L 和一个在向量空间Rn 中但不在格L 中的向
量w∈Rn ,试图找到一个离w 最近的向量v∈L,即与w 的欧氏距离最小的向量。
欧氏距离也称欧几里得距离,以古希腊数学家欧几里得命名,是最常见的距离度
量,衡量的是多维空间中两个点之间的绝对距离。例如,在二维和三维空间中的欧氏
距离就是两点之间的距离,二维的公式是d= (x1-x2)2+(y1-y2)2 ;三维的公式是
d= (x1-x2)2+(y1-y2)2+(z1-z2)2 。
如图3-10所示,在二维空间中,给定非格上的向量,很容易找到格上的向量与其距离最
近。但是,当基向量和维度增加时,寻找最近向量将变得很困难。
定义3-2(最短向量问题) 对于给定的格L,找到一个非零的格向量v,使得对于任意
70
第3章 同态加密
图3-10 二维空间的格中的最近向量示例
的非零向量u∈L,有‖v‖≤‖u‖。
换种说法,该问题试图找到格L 上一个最短的向量v∈L,其与零点的欧氏距离最小。
通常使用符号‖v‖来表示向量v 与零点的欧氏距离。
同最近向量问题一样,在基向量和维度够大的情况下,寻找最短向量是一个难题。解决
这些问题的难度在很大程度上取决于其对应的格的基的性质。若格的基尽可能相互正交,
则存在多项式时间内解决SVP和CVP的方法。若格的基的正交程度很差,则目前解决
SVP和CVP的最快算法也需要指数级的计算时间。
因此,通过将正交程度差的基作为公钥,将正交程度好的基作为私钥,将解密系统设计
为解决格上的最短向量问题或者最近向量问题,就能够提供一种基于格的加密方案。以最
近向量问题为例,可以将数据编码到一个安全的格点,加密算法会生成一个离它近的密文,
解密的时候拥有私钥的一方可以在多项式时间内找到密文对应的最近向量,但是拥有公钥
和其他公开参数的一方在多项式时间内是无法完成求解的。
注意:在这里,也可以提前解释全同态加密的自举操作,因为加密后的密文是一个带噪
声的点,这些点如果反复做乘法等运算,会让噪声越来越大,产生过大偏差后会让最近或者
最短的格点无法正确求解出来,这时就需要自举运算来消除噪声。
基于格的密码系统具有以下两个优点。
(1)使用线性代数操作实现加解密,具有易实现、高效率的特点。
(2)安全性高。为达到k 个位的安全等级,传统基于大数分解或离散对数问题的加密
系统的加解密操作需要O(k3)的时间复杂度,而基于格的加密系统仅需要O(k2)的时间复
杂度。随着量子计算机的问世,大数因式分解之类的经典难题可以在多项式时间被解决,但
是量子计算机尚无法在多项式时间内解决格所对应的难题。
4. 理想格
循环格是一种特殊的格,循环格最显著的优点就是能够用一个向量来表示,可以采用相
关算法来加速运算,可以进一步解决基于一般格上的密码方案中密钥量大、运行效率较低的
问题。对于一系列向量v0=(v1,v2,v3,…,vn )T,v1=(vn ,v1,v2,…,vn-1)T,v2=(vn-1,
vn ,v1,…,vn-2)T,…vn =(v2,v3,v4,…,v1)T,以循环生成的n 个向量为基生成的格被称
为循环格。
理想格是对循环格概念的推广,一般格是群的子群,理想格指该格同时也是环上的理
想。在多项式环Z[x]/(f(x))上,循环格的基是通过给出一个多项式v∈L,然后对其连续
模乘x 得到{vi=v0·xi(modf(x))|i∈[0,n-1]}。可以证明,在多项式环上构建的循环
71
数据安全与隐私计算基础
格即为环的理想,也称理想格。
理想格具有以下两个优点。
(1)可以降低格表示的空间尺寸。格的表示方式需要比较大的空间,比如,用一个n×n
矩阵来表示一组基,则需要存储n2 个元素。而理想格的表示则非常简单,对于基而言,给出
一个多项式即可。
(2)理想格具有理想的特性,即对内具有乘法封闭性,对外具有乘法吸收性,这一特点
使得理想格很容易构造全同态加密方案。
3.4.2 Gentry 方案
尽管有很多关于部分同态加密和类同态加密的方案,然而在同态加密概念提出后的30
年间,并没有真正能够支持无限制的各类同态操作的全同态加密方案问世。直到2009年,
斯坦福大学的博士生Gentry在他的论文中提出了第一个切实可行的全同态加密方案①。
1. 自举操作
类同态加密方案可以支持有限次数的各类同态操作,不满足强同态。如果想要不断地
进行同态操作,一种简单直接的方法是将该密文解密并且再次加密,从而能够获得一个全新
的密文,这个过程简称为刷新。刷新之后的密文相当于被重置回刚刚加密的状态,从而继续
支持更多的同态操作。但是这样的话,需要使用密钥对密文进行解密,这违背了同态加密在
加密状态下进行持续运算的原则。
Gentry敏锐地察觉到,如果能够设计一种加密方案,它的解密操作本身能够做成同态
操作,就能够在全程不解密的情况下完成刷新操作,这个操作称为自举。
自举过程可简述如下。
(1)对于给定的同态加密方案ε。在生成公私钥对(sk,pk)之后,用公钥pk加密私钥
sk得到sk。
(2)在对密文ct进行同态加密之前,应用公钥pk再次加密得到两次加密的密文ct。设
解密操作为Dε,其中:ε 支持同态解密,使用密文ct和密钥sk进行同态解密Evaluate(pk,
Dε,ct,sk)。此时,更早被加密的密文已经被解密,生成密文为此轮刚加密的全新密文。
(3)在新密文上执行一系列同态操作。
通过自举技术可以将原来仅支持有限次同态操作的近似同态加密方案改造成支持无限
次同态操作的全同态方案。基于这一思想,Gentry提出了基于理想格的全同态加密方案。
2. 近似同态加密方案
1)具体实现
Gentry的基于理想格的近似同态加密方案的具体实现如下。
(1)密钥生成。
给定一个多项式环R=Z[x]/(f(x)),R 上的一个理想I 及其固定基BI,通过循环格
生成理想格J,满足I+J=R,生成两组J 的基(BJsk,BJpk)作为公私钥对。其中:私钥BJsk
72
① GENTRYC.Fullyhomomorphicencryptionusingideallattices[C]//Proceedingsoftheforty-firstannualACM
symposiumonTheoryofcomputing,2009:169-178.
第3章 同态加密
正交化程度较高;公钥BJpk 正交化程度较低。另外,提供一个随机函数Samp(BI,x)用于从
x+BI 的陪集中抽样。最终,(R,BI,BJpk,Samp())为公钥,BJsk 为私钥。
注意:I+J=R 表示I 和J 上的元素,运算+的结果在R 上。
(2)加密。
通过函数Samp(BI,x)随机选择向量r,g,使用BJpk 对明文m ∈{0,1}n 进行加密,有
c=Enc(m)=m +r·BI+g·BJpk
其中,g·BJpk 是理想格J 上的一个元素。
(3)解密。
通过私钥BJsk 解密密文c,得到
m =c-BJsk· (BJsk)-1·c (modBI)
其中, 表示对向量各维度坐标进行四舍五入取整。
2)正确性
在加密阶段,密文c 可以看作一个格J 中的元素g·BJpk 加上噪声m +r·BI。
在解密阶段,BJsk· (BJsk)-1·c 为应用取整估计法求解最近向量问题,即找到密文向
量在格J 中最近的向量,即BJsk· (BJsk)-1·c =g·BJpk。因此,有
m =c-BJsk· (BJsk)-1·c (modBI)=c-g·BJpk(modBI)=m +r·BI(modBI)
注意:应用取整估计法解最近向量问题要求m +r·BI 足够小,才能保证其加密的格
元素g·BJpk 和解密时找到的最近的格元素是相同元素,即BJsk· (BJsk)-1·c =g·BJpk。
3)安全性
上述加解密过程,安全性规约到最近向量问题的求解上,只有在格的基正交程度较高的
私钥上可以获得尽可能接近的格向量,正交程度较低的基BJpk 无法解密明文。
4)同态性
在该方案中,明文和密文之间的线性关系使得同态操作易于实现,直接密文相加即可实
现同态加法,即
c1+c2=m1+m2+(r1+r2)·BI+(g1+g2)·BJpk
结果仍在密文空间中,并且只要m1+m2+(r1+r2)·BI 相对较小,即可运用上述解密方法
得到明文m1+m2。其同态乘法也可以直接使用密文相乘,即
c1·c2=e1e2+(e1g2+e2g1+g1g2)·BJpk
其中:e1=m1+r1·BI;e2=m2+r2·BI。该结果仍然在密文空间中,并且当|e1·e2|足
够小时,可以通过上述解密方法获得m1·m2。
5)自举
随着加法同态和乘法同态的积累,密文中的噪声项逐渐积累增大,直至无法从密文中解
密明文,这时就需要借助自举技术消除噪声,使其支持无限次数的加法和同态乘法。因为
Gentry自举技术较为复杂,这里不详细介绍。
3.4.3 CKKS 算法①
1. 容错学习
容错学习是在格的难题上构建出来的问题,可以看作解一个带噪声的线性方程组:给
73
① BRAKERSKIZ,VAIKUNTANATHAN V.Efficientfullyhomomorphicencryptionfrom (Standard)LWE
[C]//Proceedingsofthe2011IEEE52ndAnnualSymposiumonFoundationsofComputerScience,2011:97-106.