密码学的未来：对加密数据进行计算
第三方云服务为企业降低了复杂性，提供了灵活性。然而，组织需要能够将其数据和客户数据委托给云服务提供商（CSP），这些提供商通常被激励将这些数据货币化。与此同时，美国加利福尼亚州的《加利福尼亚消费者隐私法案（CCPA）》、《美国消费者在线隐私权法案（COPRA）》、《欧盟通用数据保护条例（GDPR）》和《中华人民共和国个人信息保护法（PIPL）》等法规旨在保护消费者的隐私，不合规的组织将受到严重罚款以及名誉损害。这导致了组织在数据隐私和实用性之间的权衡。然而，全同态加密（FHE）允许组织确保其客户的隐私，而不损害他们从数据中获取见解的能力。
同态加密允许计算加密数据而无需解密。相反，计算结果保存在加密域中（将明文视为未加密域，密文视为加密域）。当解密时，其结果与在未加密域上执行的操作相同。FHE可用于私有存储和计算，允许加密数据，并将其外包给商业云环境，以便在加密时处理。
尽管FHE有很多应用，但请考虑两个用例：私有联系人发现和日志异常检测。例如，要将好友添加到消息服务中，用户必须将他们的联系人号码或电子邮件上传到应用程序的服务器上。尽管用户的联系人信息可以加密以防在传输到应用服务器期间被窃听，但是必须在服务器上对联系人信息解密以计算哈希值并检测与已经使用该服务的其他人是否匹配。未加密的数据可以以任何方式使用，用户被迫将其数据信任给应用程序。另一个用例是从日志数据中检测泄露事件（IoC）。第三方安全工具，如安全信息和事件管理（SIEM）系统和扩展检测和响应（XDR）工具，需要访问未加密的日志以检测异常。使用FHE，可以对加密数据执行这些操作，而不会损害用户数据的隐私。
全同态加密
FHE计划最初设想于1978年，即RSA计划发布一年内。支持加法或乘法的部分同态加密方案已经存在，包括：
- RSA，一种用于在线数据传输的非对称加密，基于将两个大素数的因式分解的实际困难
- ElGamal（乘法同态），一种基于Diffie-Hellman密钥交换的非对称密钥加密算法，用于公钥加密，提供了一种共享密钥的方法，但不允许安全通信
- Paillier（加法同态），一种基于计算n个余类的大计算量公钥密码学概率的非对称算法
美国计算机科学家Craig Gentry于2009年首次提出了基于格的FHE方案。格L（B）是n个线性独立向量的基B={b1，…，bn}的所有整数组合的集合。也就是说，格定义为：
L(B)={ B ‧ z : z ϵ Zn}
FHE方案支持加法和乘法（无限）操作，如下所示：
HE(a+b)=HE(a)+HE(b) and HE(a*b)=HE(a)*HE(b)
同态加密方案有三种类型：
- 部分同态加密（PHE）——仅允许对加密数据执行一组有限的操作
- 些许同态加密（SHE）——允许在一定复杂度下执行有限数量的操作
- 全同态加密（FHE）——允许无限次执行任何数学运算
用例
FHE可以在许多场景中实现隐私保护计算，包括应用私有信息检索（PIR）协议、私有搜索、私有联系人发现、安全多方计算（MPC）以及SIEM或XDR中的日志异常检测。例如，PIR协议允许从服务器检索条目而不显示检索到的内容。MPC为相关用户创建了安全算法以在共同输入计算函数（过程数据）的同时保持这些输入的隐私。实际上，Microsoft Edge将FHE应用于密码监控。
如图1所示，传统的（流行的）云计算和存储解决方案要求在执行操作（例如发现用户的联系人中有多少人正在使用消息服务）或从系统日志中检测任何异常之前，解密客户数据（通过对称或非对称加密方案）。这将潜在的敏感客户数据暴露给云供应商。客户必须信任提供商的数据隐私访问控制策略。
FHE利用了严格的数学证明，客户数据隐私通过加密技术得到保证。因此，CSP将无法访问未加密的客户数据以进行存储或计算。
同态计算
一些FHE（加法和乘法）包括Brakerski-Entry-Vaikuntanathan（BGV）、Fan-Vercauteren（FV）或Brakerski-Fan-Vercuteren（BFV），以及Cheon-Kim-Kim-Song（CKKS）。所有这些方案都基于环上容错学习问题（RLWE）的难易程度，在加密和密钥生成过程中添加噪声以实现难易属性。为了理解如何允许对加密数据进行计算，探索用于在RSA、ElGamal和Paillier中执行部分同态以及在BFV方案中执行全同态的底层数学很有帮助。
RSA密码系统（无界模乘法）
如果RSA公钥的模量为n，加密指数为e，则消息m的加密值为Ɛ（m）=me mod n。RSA中两条加密消息的乘法为：
Ɛ(m1) ‧ Ɛ(m2)=m1e m2e mod n
=(m1 m2)e mod n
=Ɛ(m1 ‧ m2)
如图2所示，背景较深（橙色）的单元格表示正确结果，只有当两个整数的相加为零或将任何正整数与零相加时，才会产生准确的结果。在所有其他情况下，它会生成一个不正确的和。
图3显示了RSA的乘法性质，如果乘法是非负的，则产生正确的结果，如果乘法为负，则产生不准确的结果。
ElGamal密码系统（无界模乘法）
在ElGamal密码系统中，在具有生成器G的q阶循环组G中，如果公钥为（G，q，G，h），其中h＝gx，x为私钥，则对于某个随机rƐ{0，…，q-1}，消息m的加密为Ɛ（m）＝（gr，m·hr）。ElGamal中两个密码的乘法为：
Ɛ(m1) ‧ Ɛ(m2 )=(gr1, m1 ‧ hr1) (gr2, m2 ‧ hr2)
=(gr1+r2, (m1 ‧ m2) hr1+r2 )
=Ɛ(m1 ‧ m2)
如图4所示，ElGamal无法预测两个整数相加的正确结果。然而，图5显示了ElGamal的乘法性质，它为负乘法和非负乘法生成了准确的结果。
Paillier密码系统（无界模加法）
在Paillier密码系统中，如果公钥是模n和基g，则对于某个随机rƐ｛0，…，n-1｝，消息m的加密为Ɛ（m）＝gm rn mod n2。在Pallier中添加了两条加密消息：
Ɛ(m1) ‧ Ɛ(m2)=(gm1r1n)(gm2r2n) mod n2
=gm1+m2 (r1 r2)n mod n2
=Ɛ(m1+m2)
图片来源于公共图片库
Fan-Vercauteren （FV） 或 Brakerski-FanVercauteren （BFV） 方案
FV/BFV和BGV方案非常相似，计算是在整数上进行的。然而，CKKS可以对精度有限的复数进行计算。这意味着BFV和BGV是获得准确结果的更好选择，而CKKS最适合机器学习（ML）任务，因为CKKS中的结果是近似值。
BFV和CKKS允许批处理将明文向量（批处理）放入单个密文中。这些所谓的批处理方案将多个值打包成单个密文（通常为数千个），并以单个同态操作的代价对所有值执行操作。批处理是自FHE发现以来最突出的加速来源之一。CKKS特别适合数字和ML应用，因为所暗示的近似值是可以管理的，并且使用的加密参数比BGV和BFV更快。
加密明文域P中的明文消息M：
- 从R_2生成一个随机多项式u，其中R_2是用于生成整数系数为-1，0或1的多项式的密钥分布。
- 从χ生成两个小的随机多项式e1和e2，其中χ是误差分布（通常是离散高斯分布），定义参数为均值μ和标准差σ / R，边界为整数β。e1和e2被称为误差或噪声项。
- 消息M的密文C是一对值C1和C2。加密域C中的C＝（C1，C2）可以描述为：
C1=[PK1 ‧ u+ e1+ ∆M]q
C2=[PK2 ‧ u+ e2]q
Rq是均匀随机分布。符号[·]q表示多项式运算应该对q进行模运算。
作为参考，两个密文的同态加法H+为：
H+ (C(1) ,C(2))=([C1(1)+C1(2)]q,[C2(1)+C2(2)]q )= (C1(3),C2(3)
=([PK1 ‧ (u(1)+u(2))+(e1(1)+e1(2))+ ∆(M(1)+M(2)])q,
([PK2 ‧ (u(1)+u(2))+(e2(1)+e2(2))]q
([PK1 ‧ u(3)+e1(3)+ ∆(M(1)+M(2))]q, ([PK2 ‧ u (3)+e2(3)]q
将错误添加到密码中提供了安全性，但随着密码的每一次乘法，错误都会增加，从而给乘法带来限制。如果错误变得足够大，则无法再成功解密密码。
结论
FHE是密码学的新兴倡导者，在PIR、MPC、私有联系人发现和隐私保护日志异常检测方面具有潜在用例。FHE允许在不解密的情况下对加密数据进行计算，从而可以帮助组织遵守隐私法规。部分同态方案（如RSA、ElGamal和Paillier）和全同态BFV方案的数学运算有助于希望深入FHE并将其纳入安全项目的从业者。科技巨头正在支持全同态加密方案（例如，IBM Security提供全同态加密作为服务）。然而，目前关于允许的操作类型和计算时间的计算限制仍然是立即采用FHE的障碍。
