发布时间:2024-11-02 18:01
隐私计算(Privacy compute)是指在保护数据本身不对外泄露的前提下实现数据分析计算的技术集合。
与传统数据使用方式相比,隐私计算的加密机制能够增强对于数据的保护、降低数据泄露风险。因此,包括欧盟在内的部分国家和地区将其视为“数据最小化”的一种实现方式。同时,传统数据安全手段,比如数据脱敏或匿名化处理,都要以牺牲部分数据维度为代价,导致数据信息无法有效被利用,而隐私计算则提供了另一种解决思路,保证在安全的前提下尽可能使数据价值最大化。
目前主流的隐私计算技术主要分为三大方向:
第一类是以多方安全计算为代表的基于密码学的隐私计算技术;
第二类是以联邦学习为代表的人工智能与隐私保护技术融合衍生的技术;
第三类是以可信执行环境为代表的基于可信硬件的隐私计算技术。
多方安全计算(Secure Multi-party Computation, MPC)由图灵奖获得者姚期智院士于1982年通过提出和解答百万富翁问题而创立, 是指在无可信第三方的情况下,多个参与方共同计算一个目标函数, 并且保证每一方仅获取自己的计算结果,无法通过计算过程中的交互 数据推测出其他任意一方的输入数据(除非函数本身可以由自己的输 入和获得的输出推测出其他参与方的输入)。
百万富翁都想比较到底谁更富有,但是有都不想让别人知道自己有多少钱。在没有可信的第三方的情况下如何进行?
1. 不经意传输的解决方案
张三找10个一模一样的箱子,按照1~10的顺序摆好,并按照自己的财富值分别往里面放入苹果梨和香蕉,具体放法为:如果序号小于自己的财富之,放入苹果,相等,则放入梨,大于自己的财富值,放入香蕉;
把10个盒子都叫上锁;并叫李四过来(或者寄给李四)
李四根据自己的财富值对相应的箱子再加一把锁。然后把其他所有箱子销毁。并把这个选择的箱子送给张三。
张三看到送回来的箱子,但他不知道李四选择的是第几个箱子,因为每个箱子都是一样的
张三李四分别开锁,看里面是什么水果:
– 如果是苹果,张三比李四富有;
– 如果是梨,两人一样有钱
– 如果是香蕉,李四比张三富有https://www.jianshu.com/p/5a220e95cee2
联邦学习(FederatedLearning, FL),又名联邦机器学习、联合学习、联盟学习等。联邦学习是实现在本地原始数据不出库的情况下, 通过对中间加密数据的流通与处理来完成多方联合的机器学习训练。联邦学习参与方一般包括数据方、算法方、协调方、计算方、结果方、任务发起方等角色,根据参与计算的数据在数据方之间分布的情况不 同,可以分为横向联邦学习、纵向联邦学习和联邦迁移学习。
可信执行环境(Trusted Execution Environment, TEE)通过软硬件方法在中央处理器中构建一个安全的区域,保证其内部加载的程序 和数据在机密性和完整性上得到保护。TEE是一个隔离的执行环境,为在设备上运行的受信任应用程序提供了比普通操作系统(Rich Operating System, RichOS)更高级别的安全性以及比安全元件(Secure Element, SE)更多的功能。
同态加密(Homomorphic Encryption, HE)是指满足密文同态运算性质的加密算法,即数据经过同态加密之后,对密文进行特定的计算,得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算,实现数据的“可算不可见”。同态加密的实现效果如图1所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t2GzCj7k-1640341099318)(img/1.png)]
如果一种同态加密算法支持对密文进行任意形式的计算,则称其为全同态加密(Fully Homomorphic Encryption, FHE);如果支持对密文进行部分形式的计算,例如仅支持加法、仅支持乘法或支持有限次加法和乘法,则称其为半同态加密或部分同态加密,英文简称为SWHE(Somewhat Homomorphic Encryption)或PHE(Partially Homomorphic Encryption)。一般而言,由于任意计算均可通过加法和乘法构造,若加密算法同时满足加法同态性和乘法同态性,则可称其满足全同态性。
目前,同态加密算法已在区块链、联邦学习等存在数据隐私计算需求的场景实现了落地应用。由于全同态加密仍处于方案探索阶段,现有算法存在运行效率低、密钥过大和密文爆炸等性能问题,在性能方面距离可行工程应用还存在一定的距离。因此,实际应用中的同态加密算法多选取半同态加密(如加法同态),用于在特定应用场景中实现有限的同态计算功能。
结合其他技术,FHE还可以有选择地限制解密功能,因此人们只能看到他们有权访问的文件部分,这是他们完成工作所必需的。
满足有限运算同态性而不满足任意运算同态性的加密算法称为半同态加密。典型的半同态加密特性包括乘法同态、加法同态、有限次数全同态等。
(1)乘法同态加密算法
在实际应用中,密文乘法同态性的需求场景不多,因此乘法同态性通常偶然存在于已有的经典加密算法中。满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法等。
ElGamal算法是一种基于Diffie-Hellman离散对数困难问题的公钥密码算法,可实现公钥加密和数字签名功能,同时满足乘法同态特性。ElGamal是一种随机化加密算法,即使每次用相同密钥加密相同明文得到的密文结果也不相同,因此不存在与RSA算法类似的选择明文攻击问题,是ISO同态加密国际标准中唯一指定的乘法同态加密算法。
(2)加法同态加密算法
Paillier算法是1999年提出的一种基于合数剩余类问题的公钥加密算法,也是目前最为常用且最具实用性的加法同态加密算法,已在众多具有同态加密需求的应用场景中实现了落地应用,同时也是ISO同态加密国际标准中唯一指定的加法同态加密算法。此外,由于支持加法同态,所以Paillier算法还可支持数乘同态,即支持密文与明文相乘。
2005年提出的Boneh-Goh-Nissim方案是一种基于双线性映射的公钥密码方案,支持任意次加法同态和一次乘法同态运算。方案中的加法同态基于类似Paillier算法的思想,而一次乘法同态基于双线性映射的运算性质。由于双线性映射运算会使得密文所在的群发生变化,因此仅能支持一次乘法同态运算,但仍支持对乘法后的密文进一步作加法同态运算。一般支持有限次数的加密算法,LHE 的优点是同时支持加法和乘法,并且因为出现时间比 PHE 晚,所以技术更加成熟、一般效率比 FHE 要高很多、和 PHE 效率接近或高于 PHE,缺点是支持的计算次数有限。
支持无限次的任意运算法则 f,FHE 有以下类别:基于理想格的 FHE 方案、基于 LWE/RLWE 的 FHE 方案等等。FHE 的优点是支持的算子多并且运算次数没有限制,缺点是效率很低,目前还无法支撑大规模的计算。
(1)主流算法
全同态加密算法的发展起源于2009年Gentry提出的方案,后续方案大多基于格代数结构构造。目前已在主流同态加密开源库中得到实现的全同态加密算法包括BGV方案、BFV方案、CKKS方案等。
① 第一代全同态加密方案——Gentry方案
Gentry方案是一种基于电路模型的全同态加密算法,支持对每个比特进行加法和乘法同态运算。Gentry方案的基本思想是构造支持有限次同态运算的同态加密算法并引入“Bootstrapping”方法控制运算过程中的噪音增长,这也是第一代全同态加密方案的主流模型。“Bootstrapping”方法通过将解密过程本身转化为同态运算电路,并生成新的公私钥对对原私钥和含有噪音的原密文进行加密,然后用原私钥的密文对原密文的密文进行解密过程的同态运算,即可得到不含噪音的新密文。但是,由于解密过程本身的运算十分复杂,运算过程中也会产生大量噪音,为了给必要的同态运算需求至少预留足够进行一次乘法运算的噪音增长空间,需要对预先解密电路进行压缩简化,即将解密过程的一些操作尽量提前到加密时完成。
② 第二代全同态加密方案——BGV/BFV方案
Gentry方案之后的第二代全同态加密方案通常基于LWE/RLWE假设,其安全性基于代数格上的困难问题,典型方案包括BGV方案和BFV方案等。
BGV(Brakerski-Gentry-Vaikuntanathan)方案是目前主流的全同态加密算法中效率最高的方案。在BGV方案中,密文和密钥均以向量表示,而密文的乘积和对应的密钥乘积则为张量,因此密文乘法运算会造成密文维数的爆炸式增长,导致方案只能进行常数次的乘法运算。BGV方案采用密钥交换技术控制密文向量的维数膨胀,在进行密文计算后通过密钥交换将膨胀的密文维数恢复为原密文的维数。同时,BGV方案可采用模交换技术替代Gentry方案中的“Bootstrapping”过程,用于控制密文同态运算产生的噪声增长,而不需要通过复杂的解密电路实现。因此,在每次进行密文乘法运算后,首先需要通过密钥交换技术降低密文的维数,然后通过模交换技术降低密文的噪声,从而能够继续进行下一次计算。
③ 第三代全同态加密方案——GSW方案
GSW(Gentry-Sahai-Waters)方案是一种基于近似特征向量的全同态加密方案。该方案基于LWE并可推广至RLWE,但其的性能不如BGV方案等其他基于RLWE的方案。GSW方案的密文为矩阵的形式,而矩阵相乘并不会导致矩阵维数的改变,因此GSW方案解决了以往方案中密文向量相乘导致的密文维数膨胀问题,无需进行用于降低密文维数的密钥交换过程。
④ 浮点数全同态加密方案——CKKS方案
CKKS(Cheon-Kim-Kim-Song)方案是2017年提出的一种新方案,支持针对实数或复数的浮点数加法和乘法同态运算,得到的计算结果为近似值,适用于机器学习模型训练等不需要精确结果的场景。由于浮点数同态运算在特定场景的必要性,HElib和SEAL两个全同态加密开源库均支持了CKKS方案。
HElib是一个基于C++语言的同态加密开源软件库,底层依赖于NTL数论运算库和GMP多精度运算库实现。现了支持“Bootstrapping”的BGV方案和基于近似数的CKKS方案。
SEAL(简单加密运算库)是微软密码学与隐私研究组开发的开源同态加密库,目前最新版本为3.5,支持BFV方案和CKKS方案,项目的参与人员包括CKKS的作者之一Song。SEAL基于C++实现,不需要其他依赖库,但一些可选功能需要微软GSL、ZLIB和Google Test等第三方库的支持。
联邦学习是一种带有隐私保护、安全加密技术的分布式机器学习框架,旨在让分散的各参与方在满足不向其他参与者披露隐私数据的前提下,协作进行机器学习的模型训练。
经典联邦学习框架的训练过程可以简单概括为以下步骤:
联邦学习框架包含多方面的技术,比如传统机器学习的模型训练技术、协调方参数整合的算法技术、协调方与参与方高效传输的通信技术、隐私保护的加密技术等。此外,在联邦学习框架中还存在激励机制,数据持有方均可参与,收益具有普遍性。
Google首先将联邦学习运用在Gboard(Google键盘)上,联合用户终端设备,利用用户的本地数据训练本地模型,再将训练过程中的模型参数聚合与分发,最终实现精准预测下一词的目标。
除了分散的本地用户,联邦学习的参与者还可以是多家面临数据孤岛困境的企业,它们拥有独立的数据库但不能相互分享。联邦学习通过在训练过程中设计加密式参数传递代替原有的远程数据传输,保证了各方数据的安全与隐私,同时满足了已出台的法律法规对数据安全的要求。
Paillier 加密系统,是 1999 年 Paillier 发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密,满足加法和数乘同态。即支持密文与明文相乘。
对于正整数n,小于n &&与n互质的正整数(包括1)的个数记作 $\phi(x) $
通式: ϕ ( x ) = x ∏ i = 1 n ( 1 − 1 p i ) \phi(x) = x \prod_{i=1}^{n} (1- \frac{1}{p_i}) ϕ(x)=x∏i=1n(1−pi1)
p i p_i pi 是x的质因数
例: 当x = 120 时, 分解质因数:120=2^3*3*5
欧拉函数:φ(120)=120*(1-1/2)*(1-1/3)*(1-1/5)=120*1/2*2/3*4/5=32
互质是公约数只有1的两个整数,叫做互质整数。
给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。即两个整数除以同一个整数,若得相同余数,则二整数同余。
欧拉定义: gcd(a,n) = 1,则 a ϕ ( n ) ≡ 1 m o d ( p ) a^{\phi(n)} ≡ 1 mod(p) aϕ(n)≡1mod(p) , ϕ \phi ϕ(n)为欧拉函数
gcd(最大公约数) =1 , 即 a, n 互质
lcm ( 最小公倍数 )
费马小定理:若p是质数,gcd(a,p) = 1 , 则 a^(p-1) ≡ 1 (mod p);
卡迈克尔函数 λ \lambda λ 满足 a λ ( n ) ≡ 1 ( m o d n ) a^{\lambda(n)} ≡ 1 (mod n) aλ(n)≡1(modn),其中a与n互质。
例: λ ( 8 ) = 2 \lambda (8) = 2 λ(8)=2 则 7 2 = 1 ( m o d 8 ) 7^2 = 1 (mod 8) 72=1(mod8)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lpgNYaEZ-1640341099320)(img/4.png)]
首先选择两个大素数 p 和 q,计算出 n 为 p 和 q 的乘积。并取一个随机数 g(通常取 n+1)。n和 g 作为公钥。
然后根据卡迈克尔函数计算私钥 λ 为 p−1 和 q−1 的乘积。
随机选择两个质数 p 和 q 满足 gcd(pq,(p-1)(q-1)) =1,这个条件保证了 p 和 q 的长度相等;
计算 N=pq 和 λ=lcm(p−1,q−1),其中 lcm 表示最小公倍数;
随机选择$ g∈Z∗_{N2}$,满足 g c d ( L ( g λ m o d N 2 ) , N ) = 1 gcd ( L ( g^λ modN^2 ) , N ) = 1 gcd(L(gλmodN2),N)=1 ,后面会发现这里的 g=n+1。其中 Z 表示整数,下标表示该整数集合里有多少个元素;
$L(x)= \frac{x − 1} N $
$ μ = ( L ( g ^ λ m o d N ^ 2 ) ) ^{− 1} m o d N$
公钥为 (N,g);
私钥为(λ,μ)。
加密时取一个随机数 r,计算出 c ≡ g m r n ( m o d n 2 ) c≡g^mr^n(mod n^2) c≡gmrn(modn2)。
解密有一点复杂。首先我们可以得到:
c λ ≡ ( g m r n ) λ ≡ g m λ r n λ ( m o d n 2 ) c^λ ≡ (g^mr^n)^λ ≡ g^{mλ}r^{nλ}(mod n^2) cλ≡(gmrn)λ≡gmλrnλ(modn2)
根据卡迈克尔函数,即对于任何 ω ∈ Z n 2 ∗ ω∈Z^∗_{n^2} ω∈Zn2∗,必定存在以下结论:
ω n λ ≡ 1 ( m o d n 2 ) ω^{nλ}≡1(mod n^2) ωnλ≡1(modn2)
那么可以得到 c λ ≡ g m λ ( m o d n 2 ) c^λ≡g^{mλ}(mod n^2) cλ≡gmλ(modn2)
然后看看生成元 g,实际上是通过 g = ( 1 + α n ) β n g=(1+αn)β^n g=(1+αn)βn得到的,并且 α , β ∈ Z n ∗ α,β∈Z^∗_n α,β∈Zn∗。由此可得:
c λ ≡ ( 1 + α n ) m λ β n m λ ≡ ( 1 + α n ) m λ ( m o d n 2 ) c^λ≡(1+αn)^{mλ}β^{nmλ}≡(1+αn)^{mλ}(mod n^2) cλ≡(1+αn)mλβnmλ≡(1+αn)mλ(modn2)
再根据公式 ( 1 + n ) x ≡ 1 + x n ( m o d n 2 ) (1+n)^x≡1+xn(mod n^2) (1+n)x≡1+xn(modn2),可以得到:
c λ ≡ ( 1 + n ) α m λ ≡ 1 + n α m λ ( m o d n 2 ) c^λ≡(1+n)^{αmλ}≡1+nαmλ(mod n^2) cλ≡(1+n)αmλ≡1+nαmλ(modn2)
然后我们在此处定义一个函数 L ( x ) = x − 1 n L(x)=\frac{x−1}{n} L(x)=nx−1,则 L ( c λ ) = α m λ L(c^λ)=αmλ L(cλ)=αmλ。
对于密文c , $ c∈Z_{N2}^*$
那么我们可以得到明文的计算公式为 m ≡ L ( c λ m o d ( n 2 ) ) L ( g λ m o d ( n 2 ) ) m o d ( n ) ≡ α m λ α λ ≡ m ( m o d n ) m≡\frac{L(c^λmod(n^2))}{L(g^λmod(n^2))} mod(n)≡ \frac{αmλ}{αλ}≡m(mod n) m≡L(gλmod(n2))L(cλmod(n2))mod(n)≡αλαmλ≡m(modn)。
对于任意明文$ m 1 , m 2 ∈ Z_N $ 和任意 $r 1 , r 2 ∈ Z_N^∗ $ ,对应密文 c 1 = E [ m 1 , r 1 ] , c 2 = E [ m 2 , c 2 ] c 1 = E [ m 1 , r 1 ] , c 2 = E [ m 2 , c 2 ] c1=E[m1,r1],c2=E[m2,c2]满足:
c 1 ⋅ c 2 = E [ m 1 , r 1 ] ⋅ E [ m 2 , r 2 ] = g m 1 + m 2 ⋅ ( r 1 ⋅ r 2 ) N m o d N 2 c_1⋅c_2=E[m_1,r_1]⋅ E[m_2,r_2]=g^{m_1+m_2}⋅(r_1⋅r_2)^N modN^2 c1⋅c2=E[m1,r1]⋅E[m2,r2]=gm1+m2⋅(r1⋅r2)NmodN2
解密后结果
D [ c 1 ⋅ c 2 ] = D [ E [ m 1 , r 1 ] ⋅ E [ m 2 , r 2 ] m o d N 2 ] = m 1 + m 2 m o d N D[c_1⋅c_2]=D[E[m_1,r_1]⋅E[m_2,r_2]modN^2]=m_1+m_2modN D[c1⋅c2]=D[E[m1,r1]⋅E[m2,r2]modN2]=m1+m2modN
即我们得到了:$c_1 ∗ c_2 = m_1 + m_2 $。密文乘等于明文加。
Diffie-Hellman是一种建立密钥的方法,而不是加密方法。Diffie-Hellman(DH)密钥交换是一种密钥协定的协议,它使两个团体在不安全的信道上生成共享密钥成为可能。以这种方式协商共享密钥时不会收到被动攻击的威胁,但主动攻击者却可以劫持通信信道,冒充对端。这就是DH交换通常与身份验证联合使用的原因。
抛开算法的细节,DH的诀窍是使用了一种正向计算简单、逆向计算困难的熟悉函数,即使交换中某些因子已被知晓,情况也是一样。最恰当的类比示例是混色:如果有两种颜色,那么很容易将其混在一起得到第三种颜色;但是如果只有第三种颜色的话,就很难确定它究竟是由那两种颜色混合而成的。
DH密钥交换需要6个参数;其中两个(dh_p和dh_g)称为域参数,由服务器选取。协商过程中,客户端和服务器各自生成另外两个参数,相互发送其中一个参数(dh_YS和dh_YC)到对端,再经过计算,最终得到共享密钥。
// ServerDHParams块并发送:
struct{
opaque dp_p;
opaque dp_g;
opaque dp_YS;
}ServerDHParams;
// 客户端响应并发送其公开参数(dh_YC);
struct{
select(PublicValueEncoding){
case implicit:
// 空的,当客户端公共参数嵌入其客户端时
case explicit:
opaque dh_YC;
}dh_public;
}ClientDiffieHellmanPublic;
ECDH密钥交换发生在一条由服务器定义的特定的椭圆曲线上。这条曲线代替了DH中域参数的角色。理论上,ECDH支持静态的密钥交换,但实际使用时,只使用了这种临时的变种(ECDH)。
密钥交换由服务器发起,它选择一条椭圆曲线和公开参数(EC point)并提交:
struct{
ECParameters curve_params;
ECPoint public;
}ServerECDHParams;
// 服务器可以为密钥交换明确指定任意一条曲线,但TLS(传输层安全性协议)并未使用这个功能。作为替代,在TLS中,服务器通过指定某个名称引用一条可能预先定义好参数的曲线(EC point):
struct{
ECCurveType curve_type;
select(curve_type){
case explicit_prime:
case explicit_char2:
case named_curve:
NamedCurve namedcurve;
};
}EcParameters;
// 然后客户端提交自己的公开参数。在那以后,就可以计算主密钥:
struct{
select(PublicValueEncoding){
case implicit:
case explicit:
ECPoint ecdh_Yc;
}ecdh_public;
}ClientECDiffieHellmanPublic;
使用预定义参数,以及ellipic_curve扩展(客户端可以提交支持的曲线),可以使用服务器选择一条双方都支持的曲线。
移位法和替换法
移位法和替换法
Enigma密码机,被图灵破解。
散列函数(哈希函数)
md5、SHA-1、SHA-256
对称加密
“数据加密标准”(DES)
“高级加密标准”(AES)
加密方式和解密方式使用的是同一把秘钥
非对称加密
有两把秘钥,使用公钥加密,必须使用私钥解密
一句话概括:后量子密码,是能够抵抗量子计算机对现有密码算法攻击的]新一代密码算法。
同态加密的实现原理是什么?在实际中有何应用?
联邦学习|同态加密:实现数据的“可算不可见”
后量子密码是什么?为什么RSA"不行了"?有什么用?研究和应用现状如何
FATE (Federated AI Technology Enabler) 是微众银行AI部门发起的开源项目,为联邦学习生态系统提供了可靠的安全计算框架。
现原理是什么?在实际中有何应用?](https://www.zhihu.com/question/27645858/answer/37598506)
联邦学习|同态加密:实现数据的“可算不可见”
后量子密码是什么?为什么RSA"不行了"?有什么用?研究和应用现状如何
FATE (Federated AI Technology Enabler) 是微众银行AI部门发起的开源项目,为联邦学习生态系统提供了可靠的安全计算框架。