云计算技术的快速发展使得各类衍生服务得到广泛应用, 通过云服务人们可以不受空间和自有终端数据处理能力的限制, 完成一系列海量数据的分析、处理、存储等工作, 企业将原本需要依托大型计算中心完成的任务外包给亚马逊、谷歌等运营商提供的云计算中心能够降低30%以上硬件成本, 不仅大大降低了终端开销, 同时为用户带来前所未有的计算能力、几乎无限的存储空间和巨大的经济潜力.2014年全球云计算业务所带来的营收已经达到1 480亿美元, 2016年全球云计算市场环比增长达到30%, 到2020年全球市值将达到2 700亿美元, 然而云计算环境本身的结构特点也给安全性带来较大隐患, 出于降低成本提升资源利用率上的考虑, 参与计算的节点大都异构并且类型多样, 物理分布稀疏, 服务商难以对所有节点进行有效控制.用户往往依靠可靠性较低的网络通信和半可信的云存储服务器来传输和存储数据资源, 必然存在暴露敏感信息的风险, 难以确保数据的机密性、完整性和可用性, 一旦敏感数据资源被窃取或者篡改, 所造成的严重后果难以估计.2015年全球近300多家大型公司由于数据泄露所导致的经济损失平均高达380万美元, JP Morgan、Home Depot等知名公司都遭受过此类损失, 有的公司面临的损失高达上亿美元, 隐私安全保护已经成为云计算技术进一步发展和应用亟待解决的重大问题.为此, 本文分析了当前云计算服务中面临的隐私安全问题, 用户隐私保护的关键技术——同态加密技术的发展现状、不足、下一步需要研究的方向和可能的应用场景, 以期为将来云服务中用户隐私安全的科研以及云计算产业发展做出探索.

本文第1节从总体上介绍云计算隐私安全的现状, 对云计算隐私威胁和已有隐私保护手段的优劣进行分析, 同时对同态加密技术的研究进展作总体概述.第2节介绍同态加密算法的相关理论和概念.第3节对同态加密算法的分类和相关技术研究进行分析.第4节重点介绍同态加密技术在云计算隐私保护中的应用情况.第5节总结当前研究现状, 对未来同态加密技术在云计算隐私保护领域的可能应用场景加以展望.

1 云计算隐私安全和同态加密研究进展 1.1 云计算隐私安全

云计算的兴起无法摆脱隐私安全的问题.首先, 与其他网络平台一样, 攻击者有可能绕过云平台的认证机制, 通过直接访问下层文件或原始数据的方式获取到用户的数据, 从而引发隐私泄露问题.此外, 云计算的数据外包和服务租赁的特点使得云计算还面临更严峻的数据计算时的隐私问题.如何安全、有效地在云计算环境中为用户提供隐私安全保护已成为当前学界研究的一个热点.近年来, 隐私信息检索(private information retrieval)^[1-3]、可搜索加密(searchable encryption)^[4-8]、多方安全计算(secure multi-party computation)^{[9, 10]}技术大量地应用到了云中数据的隐私保护中, 隐私信息检索和可搜索加密技术使用户可以对加密数据进行检索获取私有信息, 并保证第三方数据存储端无法获取其内容, 然而这些技术基本上只能满足有限的功能, 诸如关键词搜索、排序搜索、区间搜索、子集搜索等.大多已有方案的计算复杂度较高, 数据加密后不具备保序性, 搜索服务提供方要对所有数据遍历才能寻找到目的数据, 并且以这些技术为基础的隐私保护方案往往会将数据的访问模式泄露给敌手, 使其能够基于搜索结果进行学习.多方安全计算协议下数个参与计算的用户可以使用自有数据联合计算, 参与方的数据不需要聚合和交换, 从而保证了各自的输入数据不被泄露给其他参与方, 但是前提是需要按照特定的客户需求定制可以支持联合计算的软件和硬件系统, 这无疑大大增加了服务实现成本.传统加密算法, 如AES、ECC和RSA等, 只有在密钥足够长的条件下可以对用户敏感数据起到保护作用, 但是, 密文数据一旦存储到云端后, 当需要云服务商对这些密文数据进行计算处理时, 无法实现网络中的计算资源对加密的数据进行处理, 因为已有的大多数传统加密方法都不支持对密文的运算, 而云环境中许多应用场景都需要对密文数据进行操作, 例如通过成千上万的患者病历数据进行药物疗效分析, 统计使用搜索引擎的用户高频搜索词继而有针对性地推送广告, 对加密文件进行模糊检索, 对加密的公司财务信息进行统计分析等.按照传统的做法, 这些数据经过加密后发送到云端需要解密再进行处理, 用户本身在对数据进行处理时, 也需要向服务商申请密文数据, 下载到本地解密后再使用, 这样不仅同样会暴露隐私, 同时, 当用户频繁使用数据时, 需要消耗大量网络带宽和时间与服务商进行通信实现数据加密和解密以及加密数据的上传和下载等, 所带来的计算和通信消耗大大降低了云计算的可用性和用户体验.除此之外, 隐私安全问题在多方安全计算和数据挖掘领域也引起人们的关注.在进行数据挖掘时, 通常使用传统加密方法来保护数据的隐私性, 但是为了分析数据, 不可避免地要对加密数据进行处理, 例如进行SUM、AVG等运算操作, 然而传统的加密算法并不支持密文域运算, 因此, 利用加密方式保证数据挖掘隐私性的研究面临一定的困难.同样, 当多个用户利用多方安全计算协议完成某项计算任务时, 一方面利用各自计算资源进行协作, 另一方面又要求互不知悉各自数据内容, 这样就需要一种能支持对密文域运算的加密算法, 数据挖掘和多方安全计算领域的隐私保护研究取得了一定进展.在云服务环境下, 无论是进行数据挖掘、分析还是多方安全计算等应用, 它们都具备了共同的特征:数据拥有者的本身并不对数据进行操作, 而是委托给非可信或半可信第三方服务商来处理, 因此要满足支持隐私保护的外包计算, 就需要既能保护数据机密性, 又能按照用户需求支持密文域的某些运算操作, 例如检索、算术运算等的加密算法.

云计算技术一方面为用户提供了可观的存储资源, 另一方面也提供了强大的计算资源, 使用传统加密算法能够确保数据外包存储的安全, 却无法应对数据外包计算时的安全问题, 这无疑削减了云服务模式的优势.外包计算的参与者有数据拥有者、数据使用者和服务提供者, 他们之间的交互过程如图 1所示^[11], 在这种典型的交互过程中, 可能存在以下几种隐私威胁.

(1) 数据拥有者将数据传输到服务提供端的过程中, 外部攻击者可以通过窃听的方式盗取数据;

(2) 外部攻击者可以通过钓鱼软件、木马和无授权的访问等方式来破坏服务提供者对用户数据和程序的保护, 从而实现非法访问;

(3) 外部攻击者可以通过观察用户发出的请求, 从而获得用户的习惯、目的等隐私信息;

(4) 由于数据拥有者的数据存放在服务提供者的存储介质上, 程序运行在服务提供者的服务器中, 因此内部攻击者要发起攻击更为容易.

上述4种威胁中, 前3种是传统网络安全中涉及的问题, 人们通过访问控制机制可以有效限制攻击者的无授权访问, 通过VPN、OpenSSH或Tor等方法来保证通信线路的安全; 第4种是在云环境中外包计算模式下出现的新型隐私威胁, 也是破坏性最大并且较难防御的一种安全威胁.因此, 我们亟需一种技术能同时抵御以上4种隐私威胁.支持隐私保护的密文计算(如算数运算、检索运算)能够有效地解决这一问题, 通过对外包计算模式下的隐私威胁进行分析, 建立能够抵御以上4种攻击的计算.图 2所示支持隐私保护的计算模型反映了数据拥有者(owner)、数据使用者(user)和服务提供者(service provider, 简称SP)之间如何实现安全的计算, 可以说同态加密的问世为云计算中用户隐私安全提供了可靠、有效的保护手段.

1.2 同态加密研究进展

同态加密(homorphic encryption)源于隐私同态, 从诞生到现在经历了30多年, 尚未有统一的分类标准, 按照其发展阶段、支持密文运算的种类和次数可将其分为部分同态(partial homomorphic encryption, 简称PHE)加密、类同态加密(somewhat homomorphic encryption, 简称SHE)以及全同态加密(fully homomorphic encryption, 简称FHE).部分同态加密(PHE)仅支持单一类型的密文域同态运算(加或乘同态); 类同态加密(SHE)能够支持密文域有限次数的加法和乘法同态运算; 全同态加密(FHE)能够实现任意次密文的加、乘同态运算.同态加密技术对于云计算环境中的数据存储、密文检索和可信计算都有着很大的应用前景.用户隐私数据在云端始终以密文形式存储, 服务商无法知悉数据内容, 从而避免其在非法盗用、篡改用户数据的情况下对用户隐私进行挖掘, 为用户充分利用云计算资源进行海量数据分析与处理提供了安全基础, 尤其是可以与安全多方计算协议相结合较好地解决用户外包计算服务中隐私安全问题.

全同态加密是同态加密技术发展的一个新兴重要方向, 使用FHE方案对数据加密后发送到云端, 密文数据在云端可以完成安全存储、检索以及所有运算类型的操作, 有效避免了明文数据在传输过程中被窃取、拦截、窜改或伪造等风险, 也避免了服务商将客户的隐私数据泄露或云端服务器被恶意攻破.2009年Gentry^[12]提出第一个真正意义上的FHE方案以后, 全同态加密理论得到了迅速发展, 基本沿着两条研究主线, 一类以Gentry提出的FHE方案的构造方法为基础, Gentry的方案本质上是一种基于理想格陪集问题构造的层次型FHE方案, 首先构造一个对称型SHE方案, 满足低次密文多项式在计算时的同态性, 再压缩解密电路D(D是解密算法Dec的电路表示), 降低解密过程中多项式次数, 通过自举技术(bootstrappaping)实现全同态加密.随着量子计算机理论的快速发展, 不久的将来必然迎来量子计算机应用的大潮, 量子计算机能够解决整数分解、离散对数问题等几乎现行所有的密码学方案, 而格密码理论能够很好地抵御量子计算攻击.另一类是近年来同态加密技术研究的热点, 基于LWE(错误学习)和RLWE假设思想提出的方案, 它的安全性假设可以归约到一般格上的标准困难问题, 与Gentry构建方案的框架不同, 其首先构建一个SHE方案, 在密文计算后, 通过密钥交换技术来控制密文向量的维数膨胀问题, 最后使用模转换(modulus switching)技术降低密文运算过程中的噪声, 不需要使用同态解密技术就能构造一个层次型FHE方案来执行多项式级深度的电路.2005年Regev定义了LWE问题是“带噪声的奇偶校验学习”问题的一般化, 并证明了该问题在量子规约下具有类似的最坏情况特性.2010年Brakerski和Vaikuntanathan利用理想格构造了基于RLWE的FHE方案BV11.2011年Regev^[13]基于LWE问题提出的全同态密码方案, 是现今简单程度最高的全同态加密方法.2011年Stehle^[14]和Smart等人首次将NTRU算法引入以提高Gentry初始FHE方案的效率, 其安全假设基于RLWE(环上错误学习), 通过理想格最坏情况难解性保障安全性, 有许多在此基础上的改进方案也相继提出, 不过, 由于其在加密过程中按位进行加密, 因此计算效率、传输带宽和存储效率较低的问题使得其应用有一定局限性, 并且这类方案由于易受到密钥恢复攻击, 因此无法有效抵御选择密文攻击方式.2012年Brakerski^[15]和Gentry提出了BGV方案, 能够支持多比特运算, 计算复杂度为$t \cdot poly\log (\lambda ),$相比于Gentry的初始方案(计算复杂度为o(λ⁶))低得多, 也比2011年Gentry^[16]和Halevi实现其方案时的复杂度低两个数量级, 在密文的乘法同态运算效率上也高于Bra12方案.基于LWE和R-LWE的FHE方案都享有“加性密钥同态”的属性, 多个用户各自持有一对公钥私钥(pk_i, sk_i), 通过所有用户的公钥相加产生的新密钥$p{k^ * } = \sum\limits_{i = 1}^n {p{k_i}} $加密明文m产生的密文$c = Enc(p{k^ * },m),$可以使用各用户私钥相加所得的新密钥$s{k^ * } = \sum\limits_{i = 1}^n {s{k_i}} $来解密密文恢复明文$m = Dec(s{k^ * },m),$即$(p{k^ * },s{k^ * })$可以构成一对新的公钥与私钥来加密解密数据.

全同态加密技术发展趋势很快, 但是想获得纯粹的FHE方案, 还需要依靠同态解密技术.总体来说, 从现有研究情况来看, PHE方案在应用中执行效率更高, 但是仅能支持加法或乘法的同态运算, FHE方案在功能性上要优于SWHE、PHE方案, 但是由于FHE方案通过使用自举电路、维数归约技术即重线性化(dimension modulus reduction)等技术来降低噪声从而达到突破限制进行密文同态运算的目的, 复杂的计算过程成为其实际应用的瓶颈.

2 相关概念和理论基础

密文计算(cipher-text computation)是指在密文域上所进行的计算以及具有访问权限的用户对密文域上的计算结果可确认并可解密获得对应的明文.为了确保用户隐私数据安全, 需要将隐私数据进行加密处理后上传到云端存储, 参与计算的密文数据主要包括两部分, 分别由用户直接提供以及通过密文检索得到的数据(服务商受托方对用户交付的数据作外包计算).同态加密为云计算环境中存储与外包计算等服务的隐私安全问题提供了良好的解决方案, 理论上利用全同态加密算法能够从根本上解决在第三方不可信或半可信平台上进行数据存储和数据操作时的隐私保护问题, 用户将计算请求F和密文$\left\langle {{c_1},...,{c_t}} \right\rangle = (Enc({m_1}),...,Enc({m_t}))$发送给云端, 在云端对密文直接进行任意运算, 所得到的密文结果与明文运算后结果一致, 即$Y(K,F,(Enc({m_1}),...,Enc({m_t}))) = $ $E(K,F({m_1},...,{m_t})),$同态的概念源于近世代数中群与环的同态, 设 $\left\langle {{H_1}, \circ } \right\rangle $ 、 $\left\langle {{H_1}, \circ } \right\rangle $ 为两个代数结构, $f:{H_1} \to {H_2}$为H₁到H₂的一个映射, $\forall a,b \in {H_1}$都有$f(a \circ b) = f(a) * f(b),$则称$f:{H_1} \to {H_2}$是一个同态映射.一个同态加密算法ε包括4个部分, 分别是密钥生成算法Gen_ε、加密算法Enc_ε、解密算法Gec_ε、密文运算算法Cal_ε.

(1) 密钥生成算法Gen_ε:$U \to key$表示用户通过输入参数U生成密钥key;

(2) 加密、解密算法:$En{c_\varepsilon }:(key,{P_\varepsilon }) \to {C_\varepsilon },De{c_\varepsilon }:(key,{C_\varepsilon }) \to {P_\varepsilon },$P_ε为明文空间, C_ε为密文空间;

(3) 计算算法:$Ca{l_\varepsilon }:({P_\varepsilon },{F_\varepsilon }) \to ({C_\varepsilon },{F_\varepsilon }), \circ \in {F_\varepsilon },({p_1},{p_2},...,{p_n}) \in {P_\varepsilon },$${F_\varepsilon }$是${P_\varepsilon }$上的运算集合, 对于$ \circ \in {F_\varepsilon },({p_1},{p_2},...,$ ${p_n}) \in {P_\varepsilon },$Cal_ε将P_ε上进行的运算$ \circ $转化为C_ε上运算再进行计算, 结果是等价的.

定义1. 同态性:对于加密算法ε和明文域P_ε上的运算$ \circ $, 若$\forall {p_1},{p_2},...,{p_n} \in {P_\varepsilon }$都满足式(1):

$De{c_{\varepsilon 1}}(key,Ca{l_\varepsilon }(({c_1},...,{c_n}), \circ )){\text{ = (}}{p_1},...,{p_n}) \circ $

(1)

3 同态加密算法分类及相关研究 3.1 部分同态(PHE)加密

定义2. 对于加密算法ε和明文域P_ε上的运算(+, ×), 若$\forall {p_1},{p_2},...,{p_n} \in {P_\varepsilon }$仅满足加法或者乘法运算在式(1)中成立, 则称加密算法ε为满足部分同态的加密算法.

1978年Rivest提出了基于公钥密码体制的经典加密方案Unpadded RSA^[17], 并在其论文《On data banks and privacy homomorphisms》^[18]中首次提出同态加密的思想, RSA算法针对数值型数据进行加密, 在加密时无需将明文扩展至与公钥一致的长度, 能够支持乘法同态运算, 不支持加法, 密钥的产生过程也较为复杂, 其安全性假设基于大数因式分解, 加解密运算代价过高, 由于是确定性加密算法, 密钥一定的情况下加密明文会产生固定密文, 难以做到一次一密, 因此安全性受到影响; Elgamal^[19]提出了基于离散对数困难问题的ElGamal算法, 在加密时引入了随机数, 具有语义安全性, 算法满足了乘法同态的性质, 但是解密过程要对离散对数进行计算, 在实现上较为困难; Chen等人^[20]基于ElGamal的方法进行改进, 提出了NHE方法, 能够抵抗已知明文攻击(known- plaintext attack)和选择密文攻击(chosen-ciphertext attack).在对称型类同态加密体制方面, Goldwasser-Micali^[21]算法于1984年被提出, 它以合数为模的二次剩余困难性假设为基础, 该方案能够实现对异或运算的同态性, 但是只能逐位进行加密, 效率较低; Benaloh^[5]提出了第一种支持对密文进行有限次加法操作的公钥密码体制, 之后许多学者相继提出了不少支持密文加法运算的同态加密方案, 应用最为广泛的是Paillier^[22]加密方案, PHE方案由于构造简单、执行效率较高, 应用相对比较成熟.表 1列出了时下的主流PHE方案, 从密文同态运算属性、算法设计、密文膨胀、安全假设问题强度几个方面进行比较, 从表 1中可以看出, 除了RSA和MREA方案, 现有大部分PHE加密方案是基于对称加密体制和非确定性概率假设的, RSA和MREA方案支持乘法同态, 其他方案支持密文域的加法同态, 相对来说, RSA、EGM、Paillier方案的加解密效率相对较高, 由于表 1中几种PHE方案在效率上具备的良好性能, 被广泛应用到现实中(Paillier方案被大量应用到电子投票和生物计量应用中, 其加解密效率可以控制在毫秒级, 加密和解密每1 024位数据仅需要2.33s).

3.1.1 Paillier加密方案

Paillier是一种应用较为广泛的公钥体制PHE方案.方案的密钥生成过程Gen_Paillier如下:

随机选取p、q两个大素数以及$g \in {Z_{{n^2}}},$令$n = p \cdot q,\lambda = (p - 1)(q - 1),$设函数$l(u) = \frac{{u - 1}}{n},$且g、n满足:

$\gcd (l({g^\lambda }\bmod {n^2}),n) = 1$

(2)

这里, 公钥为$pk = (n,g),$私钥$sk = \lambda .$

加密算法Enc_Paillier:随机选取整数$r \in Z_{{n^2}}^ * ,$对于明文$m \in {Z_n},$加密后的密文c为

$c = {g^m} \cdot {r^n}\bmod {n^2}$

(3)

式(3)中, $c \in Z_{{n^2}}^ * ,Z_{{n^2}}^ * $为小于n²且与n²互素的正整数集合.

解密算法Dec_Paillier:对于密文c, 其对应的明文m为

$m = \frac{{l({c^\lambda }\bmod {n^2})}}{{l({g^\lambda }\bmod {n^2})}}\bmod n$

(4)

同态属性分析:

由于$Enc({m_1}) \cdot Enc({m_2}) = ({g^{{m_1}}} \cdot r_1^n) \cdot ({g^{{m_2}}} \cdot r_2^n) = {g^{{m_1} + {m_2}}}{({r_1}{r_2})^n} = Enc({m_1} + {m_2})\bmod {n^2}$即明文加法运算对应密文乘法运算, 所以方案具备加法同态性:

$De{c_{Paillier}}(key,Ca{l_{Paillier}}(({c_1},...,{c_n}), \times )){\text{ = (}}{m_1},...,{m_n}) + $

(5)

3.1.2 ELGaml加密方案

ELGaml也是一种以公钥密码体制为基础的PHE方案.方案的密钥生成过程为Gen_ELGaml.

随机选取大素数p, x∈(1, p-1), g为素数集$Z_p^ * $的生成元, 令$y = {g^x}\bmod p,$这里, pk=y为公钥, 私钥sk=x.

加密算法Enc_ELGaml:对于明文$m \in Z_p^*,$随机选取$k \in Z_p^*,$加密后密文c为

$c = Enc(m) = ({c_1},{c_2}),{c_1} \equiv {g^k}(\bmod p),{c_2} \equiv m \cdot {y^k}(\bmod p)$

(6)

解密算法Dec_ELGaml:对于密文c, 其对应的明文m为

$m = Dec(c) = \frac{{{c_2}}}{{c_{_1}^x}} = \frac{{m{y^k}}}{{{g^{xk}}}} = \frac{{m{g^{xk}}}}{{{g^{xk}}}}\bmod p$

(7)

同态属性分析:

因为

$\begin{gathered} Enc({m_1}) \cdot Enc({m_2}) = ({g^{{x_1}}}\bmod p,{m_1}y_{}^{{x_1}}\bmod p) \cdot ({g^{{x_2}}}\bmod p,{m_2} \cdot y_{}^{{x_2}}\bmod p) \hfill \\ {\text{ }} = ({g^{{x_1} + {x_2}}}\bmod p,{m_1} \cdot {m_2}{y^{{x_1} + {x_2}}}\bmod p) \hfill \\ {\text{ }} = Enc({m_1} \cdot {m_2})\bmod p, \hfill \\ \end{gathered} $

即密文乘法运算对应于明文乘法运算, 所以方案具备乘法法同态性:

$De{c_{ELGaml}}(key,Ca{l_{ELGaml}}(({c_1},...,{c_n}), \times )){\text{ = (}}{m_1},...,{m_n}) \times $

(8)

3.2 类同态(SWHE)加密

定义3. 对于加密算法ε和明文域P_ε上的运算(+, ×), 若$\forall {p_1},{p_2},...,{p_n} \in {P_\varepsilon }$同时加法和乘法运算在式(1)中成立, 但是仅能进行有限次的同态运算, 则称加密算法ε为类同态加密算法.

一个类同态加密方案能够同时支持在密文域上进行加法和乘法的同态运算, 但是由于要考虑降低密文产生时的噪声, 不得不限制某一类运算的操作次数以完成解密过程, 通常情况下, 同态加密算法在密文计算后的新密文中会伴有随机误差向量即噪声, 在解密时要尽可能地将噪声控制在安全参数允许范围内, 这个限制是为了密码系统模糊同态操作后可以正确解密密文, 换而言之, 类同态加密方案一般只能够对特定的数据集进行密文计算, 仅适用于现实中的特定应用场景, 例如医学数据^[28]、基因组和生物信息学数据^[29-31]、无线传感器数据^[32]、SQL数据^[33]以及整型数据, 不少研究开始对现有类同态加密方案改进, 为使其服务于自定义数据集计算, 如预测分析^[28]、回归分析^[34]、统计分析^{[29, 35]}和其他一些运算类型.2005年Boneh^[25]等人提出了具有语义安全的BGN方案, 这是第一个可以同时支持不限次数的密文加法和一次乘法同态运算的方案, 并且加密后密文没有发生膨胀.随后, Gentry、Halevi、Vaikuntanathan^[36]对BGN方案进行改良提出了GHV方案, 其安全性假设基于容错问题的困难性; Chan^[37]等人基于希尔密文及Rivest的加密思想提出IHC方法和MRS方法, 能够支持密文的加法, 但乘法只支持密文与明文相乘, 且这两种方法的安全性较低.Hojsík^[38]等人基于Polly Cracker技术提出的SymPC方法为指数级的复杂度, 通过选择合适的随机数, 可以将复杂度降到多项式时间, 但由于安全参数对效率的影响较大, 无法同时兼顾安全性与效率.黄汝维^[11]、桂小林等人提出了基于向量和矩阵运算的CESVMC加密方案, 能够支持加密字符串的模糊检索和密文数据的加、减、乘、除法运算, 但是方案仅支持一次乘法或除法运算, 虽然效率较高但是密文膨胀问题依然是其瓶颈.杨攀^[39]、桂小林等人提出一种对称体制的CESIL方案, 用理想格划分多项式系数向量环的剩余类, 建立商环及其代表元集合, 通过代表元所在剩余类的其他元素对其进行替换完成加密, 方案实现加法乘法混合同态运算, 密钥及密文长度较小, 并将其应用到加密图像的缩放、叠加运算, 效率较为理想.应当说类同态加密技术的发展奠定了之后全同态加密研究的基础, 后期许多全同态加密的方案也是由类同态加密方案改造而来.

3.2.1 BGN加密方案

BGN方案能够进行一次密文乘法运算和无限次加法运算.

密钥生成过程Gen_BGN如下:

设$\lambda \in {Z^ + }$为安全参数, 随机选取λ位的大素数q₁、q₂, 令$n = {q_1} \cdot {q_2},$G₁为q₁阶双线性群, $e:{G_1} \times {G_1} \to {G_{\text{2}}}$为n阶双线性映射, 随机选取$u,g \leftarrow {G_1},$令$h = {u^{{q_2}}},$h为G₁子群的生成元, 元素$x \in {G_1},$规定若其阶数为q₁, 则输出为1, 否则为0.这里, 公钥$pk = (n,{G_1},{G_2},e,w,g),$私钥$sk = {q_1}.$

加密算法Enc_BGN:明文空间定义为整数集合$M = \left\{ {0,1,...,T} \right\},T < {q_2},$随机选取整数$r \leftarrow \left\{ {0,1,...,n - 1} \right\},$对于明文m, 密文为

$c = {g^m}{h^r} \in G_1^{}$

(9)

解密算法Den_GBN:对于密文$c = {g^m}{h^r},$使用私钥$sk = {q_1}$解密, 令

$ {c^{{q_1}}} = {({g^m}{h^r})^{{q_1}}} = {({g^{{q_1}}})^m} \cdot {({h^r})^{{q_1}}}, {h^r} = \underbrace {({u^{{q_2}}}) \cdot ({u^{{q_2}}}) \cdot ... \cdot ({u^{{q_2}}})}_r,{({h^r})^{{q_1}}} = \underbrace {({h^r}) \cdot ({h^r}) \cdot ... \cdot ({h^r})}_{{q_1}} \in {G_1}, $

所以,

${c^{{q_1}}} = {({g^{{q_1}}})^m} \cdot {({h^r})^{{q_1}}} = {({g^{{q_1}}})^m} \cdot 1 = {({g^{{q_1}}})^m},$

由于${q_1},c,g$都为已知, 则明文为

$m = {\log _{{g^{{q_1}}}}}{c^{{q_1}}}$

(10)

同态属性:

很明显, 由于密文${c_1} \cdot {c_2} = ({g^{{m_1}}}{h^r}) \cdot ({g^{{m_2}}}{h^r}) = {g^{{m_1} + {m_2}}}{h^{2r}} = En{c_{BGN}}({m_1} + {m_2}),$所以方案满足加法同态性质.

定义${g_1} = e(g,g),{h_1} = e(g,h),h = {g^{\alpha {q_2}}}(\alpha \in Z),r,{r_1},{r_2} \in {Z_n},{c_1} = {g^{{m_1}}}{h^{{r_1}}},{c_2} = {g^{m_2^{}}}{h^{{r_2}}}({c_1},{c_2} \in {G_1})$根据双线性对性质定义密文域乘法为

${c_1} \otimes {c_2} = e({c_1},{c_2})h_1^r = e({g^{{m_1}}}{h^{{r_1}}},{g^{{m_2}}}{h^{{r_2}}})h_1^r = e{(g,g)^{{m_1} \cdot {m_2}}}h_1^r = {c_3} = {g_{\text{1}}}^{m_1^{} \cdot {m_2}}h_{\text{1}}^{r'}{\text{ = }}En{c_{BGN}}({m_1} \cdot {m_2})$

(11)

其中, $r' = {m_1}{r_2} + {r_2}{m_1} + \alpha {q_2}{r_1}{r_2} + r,r' \in {Z_n},$密文乘积${c_3} \in {G_1},$可以看出方案仅支持一次同态密文乘法运算, 超过一次运算时解密算法将无法对密文正确解密.

3.3 全同态加密方案(FHE)

全同态加密是当前同态加密领域研究的前沿, 到目前为止, 学界尚未形成统一的定义来描述全同态加密.现有的FHE方案主要通过电路来构造, 一个FHE方案的核心就在于其密文计算算法$Ca{l_\varepsilon }(pk,{C_\varepsilon },{c_1},...,c{}_n),$可以用电路来理解, 这里C_ε是一个电路集合, 可以等价于一个函数或功能, 公钥pk用于密文计算, 解密算法$De{c_\varepsilon }({c_1},...,$ ${c_n}) = ({m_1},...,{m_n}),$对密文进行运算后解密的结果要对应明文直接运算结果, 所以需要有正确性保证.

定义4. 若由密钥生成算法Gen_ε生成的任何一对密钥$(pk,sk),$任意电路$C \in {C_\varepsilon },$向Cal输入pk和密文序列$c = \left\langle {{c_1},...,c{}_n} \right\rangle $、电路C后, 输出的 ${c^ * } = Cal(pk,C,{c_1},...,c{}_n),$ 满足$Dec(sk,{c^ * }) = C({m_1},...,{m_n}),$那么称同态加密方案ε为正确的.

此外, $Ca{l_\varepsilon }(pk,{C_\varepsilon },{c_1},...,c{}_n)$输出的新密文应保证与$En{c_\varepsilon }({m_1},...{m_n}) = ({c_1},...,{c_n})$过程计算量一致, 即方案是紧凑的.

定义5. 对任意的安全参数λ, 始终存在一个多项式f, 同态加密ε的解密过程可以表示为一个上限规模(MAX SIZE)为f(λ)的电路W, 那么称方案ε是紧凑的.

定义6. 同态加密方案ε对某一电路C为正确且紧凑的, 则称ε关于电路C为紧凑的, 若上述条件满足任意一个电路$C \in {C_\varepsilon },$则称ε是一个全同态加密方案.

Gentry首次基于理想格构造了全同态加密方案, 方案在语义上具备安全性, 但是只能进行简单的密文运算, 复杂密文运算经过编码之后形成较深电路深度(噪声问题), 导致其解密算法无法正确得出明文.Smart等人^[40]改用整数和多项式实现全同态加密, 缩短了密钥和密文长度, 该方案加密解密过程实现简易, 但是生成密钥的过程过于复杂.Chen^[41]等人基于二元LWE, 设计了一个公钥和私钥更短的FHE方案, 其张量密文也短于Bra12方案.Gentry等人^{[16, 42, 43]}对全同态加密算法中的自举技术、加密算法的解密循环分解技术、方案实现手段等方面进行了改进, 在一定程度上降低了方案的复杂性, 但是由于Bootstrappaping在实现过程方面仍然十分复杂, 即使在安全性要求较低的情况下, 完成一次Bootstrappaping也要耗时30s左右, 因此, 这些加密方法在实用性上都比较受限.2010年Gentry^[44]与Dijk等人研究了整数环上的全同态加密算法, 即DGHV方案, 从同态操作与性能特性上, 该方案与基于理想格的构造方案非常相似, 均保持密文长度的紧凑性——密文长度完全不依赖于计算加密数据的函数的复杂性, 但是, 从概念性上看, DGHV方案并非基于格理论或在Gentry初始方案进行改进, 而是基于基本的模运算进行构造, 相较于基于理想格的构造方案更简洁, DGHV方案的安全性是基于近似最大公约(approximate greatest common divisor problem)和确定性最大公约数问题(approximate greatest common divisor problem), 不过方案同样使用了Gentry的自举技术, 最近许多研究^[45-48]通过提升自举技术和减小公钥的大小来提升其执行效率, 但是这些方案并没有完全解决FHE方案的噪声问题.之后, Brakerski等人^{[49, 50]}基于错误学习(learning with errors)、环上错误学习RLWE(ring-LWE)构造出不需要Bootstrappaping的全同态加密方法, 文献[30-32]也是基于LWE、RLWE的同态加密方法.基于公钥全同态加密的密文计算如图 3所示.

表 2、表 3分别是FHE方案在不同属性上的分类, 现有的FHE方案大多由SWHE方案进行改进而来, 不同之处在于FHE方案使用各类降噪技术使密文产生过程中的噪声不会随着密文计算过程而增加.从算法设计基础的角度来看, FHE方案可以分为3个主要类别:基于格理论、基于误差校正码和基于数论, 后两种是基于传统的数学方法.格密码学是近年来新兴的重要研究方向, 通过使用量子规约, 基于格的密码学可以从最坏情况的难题规约到一般情况难题, 因而攻击基于具体格问题构造的密码系统等同于求解相应的格困难问题.事实证明, 格密码能够有效地抵御量子计算攻击, 同时相比于过去的PHE方案(EGM方案包含幂运算), 基于格的FHE方案具有更简约的解密电路设计, 因此基于格上困难问题的全同态加密方案的构造成为了研究的焦点.

3.3.1 DGHV加密方案

DGHV方案首先需要构造一个SWHE方案, 再将其转换为FHE方案.

第1步.构造SWHE方案.

密钥生成过程Genʹ_DGHV如下:

设λ为安全参数, $\tau = \lambda + \gamma ,\eta = O({\lambda ^2}),$随机生成一个η位的大奇数$p \in (2Z + 1) \cap \left[ {{2^{\eta - 1}},{2^\eta }} \right),$从分布${D_{\gamma ,P}}(p)$中选取$\tau + 1$个整数${{x}_{i}}\leftarrow {{D}_{\gamma ,P}}(p),i\in (0,1,...,\tau )$, ${{D}_{r,}}_{q}(p)=\left\{ x=pq+r|q\in Z\cap \left[ 0,{}^{{{2}^{\gamma }}}\!\!\diagup\!\!{}_{p}\; \right],r\in Z\cap (-{{2}^{\rho }},{{2}^{\rho }}) \right\}$ , 其中, $\rho = \lambda ,$从x_i中选取最大的数x₀, 确保其为奇数, 且x₀ mod p为偶数, 这里, 公钥为向量$pk = X = ({x_0},{x_1},...,{x_\tau }),$私钥sk=p.

加密算法Encʹ_DGHV:随机选取一个子集$S \subseteq \left\{ {1,2,...,\tau } \right\}$和整数$r' \in ( - {2^{\rho '}},{2^{\rho '}}),\rho ' = 2\lambda ,$对于明文$m \in \{ 0,1\} $加密后密文c为

$c = \left( {m + 2r' + 2\sum\limits_{i \in S} {{x_i}} } \right)\bmod {x_0}$

(12)

解密算法Gecʹ_DGHV:对于密文c, 其对应的明文m为

$m = (c\bmod p)\bmod 2$

(13)

第2步.将SWHE转换为FHE方案.

DGHV方案利用稀疏子集对解密过程简化, 使构造的SWHE方案实现Bootstrappaping.方案的密钥生成过程Gen_DGHV如下:

设参数$\kappa ={\gamma \eta }/{{{\rho }'}}\;,\Theta =\varpi (\kappa \log \lambda ),\theta =\lambda ,$令随机选择一个汉明重量为θ的Θ位二进制向量$\mathop H\limits^ \to \in {\{ 0,1\} ^\Theta },$定义向量$\mathop H\limits^ \to $的元素下标集合$H = \left\{ {i|{h_i} = 1} \right\},$再随机选取整数${u_i} \in Z \cap [0,{2^{\kappa + 1}})(i = 1,...,\Theta - 1),$使其满足$\sum\limits_{i \in H} {{u_i} = {x_p}} \bmod {2^{\kappa + 1}}.$令${{y}_{i}}={}^{{{u}_{i}}}\!\!\diagup\!\!{}_{{{2}^{\kappa }}}\;,\overset{\to }{\mathop{y}}\,=({{y}_{0}},{{y}_{1}},...,{{y}_{\Theta -1}}),$这样便得到公钥$pk = (\mathop x\limits^ \to ,\mathop y\limits^ \to ),$私钥$sk = (\mathop H\limits^ \to ).$

加密算法Enc_DGHV:首先使用上一步构造的SWHE方案中的公钥对明文加密得到密文$c = En{c'_{DGHV}}(m),$再计算${z_i} = {\left[ {c \cdot {y_i}} \right]_2},$保留z_i的二进制序列小数部分$n = \log \theta + 3$位, 则新的密文为$c' = \left\{ {c,({z_0},{z_1},...,{z_{\Theta - 1}})} \right\}.$

解密算法Dec_DGHV:对于密文c, 其对应的明文m为

$m = \left( {c - \sum\limits_{i = 0}^{\Theta - 1} {{z_i}{H_i}} } \right)\bmod 2$

(14)

3.3.2 BV11加密方案

BV11是一种高效的层次型FHE方案, 采用密钥交换技术与模交换技术来控制密文膨胀(关于密钥交换技术与模交换技术将在后面详细介绍).BV11首先使用密钥交换技术将经过乘法运算后膨胀的密文乘积$c = {c_1} \cdot {c_2}$转化成与${c_1},{c_2}$维数相同的新密文$c',$进入下一层电路后使用模交换技术控制噪声.

$Step({1^\lambda },{1^\mu }):$设安全参数为λ, j层解密电路为$L{\text{ = }}\left\{ {{L_0},{L_1},...,{L_j}} \right\},$模${q_L}(L = 0,1,...,j)$为一个递减序列, 由随机选取的μ位奇数q生成.$f(x) = {x^n} + 1,n = n(\lambda ,\mu ) \in {2^k}(k \in N),$由q生成n维多项式$R_{^{q}}^{n}={Z\left[ x \right]}/{f(x)}\;,$随机选取μ位奇数q生成多项式环$R_{^{q}}^{n}={{{Z}_{q}}\left[ x \right]}/{f(x)}\;,$χ是$R_{^q}^n$上离散高斯分布.

密钥生成过程Den_BV11如下:

从L_j到L₀层电路, 随机选取向量$s \leftarrow \chi ,e \leftarrow R_{^q}^n,a \leftarrow R_{^q}^n,$令$b = as + 2e.$每层生成公钥、私钥分别为$s{k_L}{\text{ = }}{s_L} \leftarrow $ $(1, - s) \in R_q^n \times R_q^n,p{k_L}{\text{ = }}(a,b) \in R_q^n \times R_q^n,$这里, 向量乘法定义为向量间内积运算.

加密算法Enc_BV11:对于二进制明文$m \in \{ 0,1\} ,$将其明文序列转换为多项式$R_2^n,m$的二进制序列即为多项式R₂常数项的系数.随机选取$\sigma \leftarrow \chi ,\varsigma \leftarrow \chi ,\upsilon \leftarrow \chi ,$用公钥$p{k_L}{\text{ = }}(a,b)$加密明文m得到第j层密文cʹ:

$c' = ({c_0},{c_1}),{c_0} = a\sigma + 2\varsigma + m,{c_1} = b\sigma + 2\upsilon $

(15)

进入第j–1层电路, 计算$s' = s \times s \in ({R_q} \times {R_q} \times R_q^{}),SwitchKeyGen(s',{s'_{i - 1}}) \to {\tau _{j - 1}}$表示由$s',{s_{i - 1}}$通过密钥交换算法得到参数${\tau _{j - 1}},$以此类推直到第0层, 因此各层对应的私钥集合$sk{\text{ = }}\left\{ {{s_L}} \right\},$公钥集合$pk{\text{ = }}\left\{ {p{k_L},{\tau _L}} \right\}.$

解密算法Dec_BV11:对于密文c, 其对应的明文m为

$m = (({c_0} + {c_1} \times s)\bmod q)2$

(16)

只要保证$\left\| {{c_0} + {c_1} \times s} \right\| < q/2,$就能正确解密出明文m密文加法运算$Cal_{_{BV{\text{11}}}}^ + :$对于两个密文${c_{j,1}},{c_{j,2}},$若二者同属第j层, 所对应的密钥为${s'_j} \leftarrow (1, - {s_j}),$则直接按照多项式向量加法运算法则计算${c_{j,1}} + {c_{j,2}} = {c_{j,3}};$若密文${c_{j,1}},{c_{k,1}}$不同属一层, 先使用密钥交换算法将较高层的密文${c_{\max \{ j,k\} ,1}}$转换成底层密文${c_{\min \{ j,k\} ,1}},$再进行加法运算得到密文${c_{\min \{ j,k\} ,2}},$再使用模转换技术降低其噪声, 最终得到与执行加法运算前的密文维数相同的密文${c'_{\min \{ j,k\} ,2}}.$

密文乘法运算$Cal_{_{BV{\text{11}}}}^ \times :$与加法运算相同, 若两个密文同属一层, 则直接执行密文乘法运算, 若不属一层, 则按照上述操作方法完成计算.

目前现有的FHE方案在实现上仍然较为复杂且计算模型复杂度较高.构造一个FHE方案时Bootstrappaping过程的耗时较长, 在计算模型中, 程序需要以布尔电路形式编码, 由于要进行乘法运算, 一般的应用程序编码后对应层数很深的布尔电路, 为了保证语义安全阻止敌手获取任何明文数据相关信息, 方案所基于的安全假设问题带来的计算开销也很可观.另外, 表 2中的FHE方案都不能直接进行浮点数的运算, 需要转换为两个整数相除的形式.这些问题是现有FHE方案还无法适用于大型云服务应用的主要原因.尽管大部分现行FHE方案在执行效率上还无法满足大范围实际应用的需求, 但是全同态加密算法的研究从理论上使得在密文域进行各种运算操作成为可能, 这也是密码学研究领域的一个重大突破.

3.4 对称与非对称同态加密算法

与传统加密方法类似, 同态加密算法也通过使用相同的一对密钥(对称加密方案)或不同的一对密钥(非对称加密方案)来加密数据, 现有大多数的同态加密算法都基于非对称密码体制(公钥加密系统), 少数是对称HE方案, 主要是由于现行对称型方案的实现效率不高, 而且密钥管理较为复杂, 在实际应用中部署并不现实.此外, 大多数对称同态加密方案由于算法设计^[45-48]还存在安全漏洞, 从理论上还不能完全证明其安全性, 不过, 基于公钥加密体制的HE方案也存在明显的瓶颈, 由于方案的实现往往需要巨大的计算开销, 因而不能满足云环境中诸如外包计算这样的服务要求, 有的文献^[70-72]通过减小加密方案的计算开销来构造轻量化的密文计算方案, 但是仍无法满足云中海量数据的外包计算要求.

3.5 确定性与非确定性同态加密算法

大部分现有的同态加密算法通过概率特性而保证其语义安全^{[17-19, 21-26, 73]}, 如果敌手无法从密文中获得任何有用的信息来恢复明文, 则可以认为加密方案在语义上是安全的, 少数是确定性HE方案.在确定性HE方案中, 使用同一密钥对明文加密后始终得到同样的密文, 若同一明文经过同样的密钥加密后可以得到不同的密文, 则可以归类为概率性HE方案.

3.6 全同态加密的实现技术 3.6.1 同态解密技术

在一个FHE方案中密文计算后产生的噪声是面临的首要困难, 同态解密计算技术正是为了解决这一问题而提出的.以DGHV方案来说, 在第1步构造的SWHE方案中, 密钥sk=p是w bit的大奇数, 随机选取整数q, 对明文进行加密$c = m + 2r + pq,$这里, $m + 2r$即为噪声, 只有当$c\bmod p = m + 2r < P/2$时才能确保解密得到正确明文即$(m + 2r)\bmod {\text{2}} = m,$为了将SWHE方案转换成对电路深度没有要求的全同态加密方案, 在第2步中需要使用Gentry提出的自举技术, 选取大奇数p作为私钥sk, 公钥$p{k_i} = \left\{ {\left. {{x_i}\left| {p{q_i} + 2{r_i},0 \leqslant i \leqslant \eta } \right.} \right\}} \right.,$${r_i}$(较小)、q_i为随机选取的整数, 这实际上是一个刷新密文(recryption)过程:用公钥pk₂加密明文m, 公钥pk₁对私钥sk的二进制数逐位加密得到密钥向量SK, 将二者作为输入后输出pk₂加密的密文, 即$De{c_{en{c_{p{k_2}}}}}(E{n_{p{k_2}}}(E{n_{p{k_1}}}(m)) = En{c_{p{k_2}}}(Dec(sk,$ $E{n_{p{k_1}}}(m))) = En{c_{p{k_2}}}(m),$反复刷新密文以降低噪声, 使密文能够正确计算直到完成所有运算, 从而突破SWHE方案中密文计算次数的限制, 不过, 在解密过程中存在密钥多项式函数次数过高的问题, 为此, Gentry使用Squash技术, 给公钥向量1/p一个提示信息(CLUE), 引入稀疏子集, 集合$S = \left\{ {{x_i}\left| {i = 1,2,...,N} \right.} \right\}$存在一个子集$T = \{ {b_i}\left| {{b_i} = {\sigma _i}} \right.{x_i},$ ${\sigma _i} \in \{ 0,1\} \} $使得集合T中所有元素相加之和为公钥向量1/p, 将$\sigma {\text{ = [}}{\sigma _1},...,{\sigma _N}]$作为新密钥, 对集合S中元素做变换得到${z_i} = {x_i} \times c,$这样, 解密过程由$m = c - [\omega \times c]\bmod 2$变为$m = c - \sum\limits_i {{\sigma _i}{z_i}} \bmod 2,$可以将转换后的解密函数写成次数为集合T中的元素个数的σ_i的多项式表达式, 这样的话, 只要控制T中元素数目为较小的数就可以解决解密函数中多项式次数太高的难题.后续的很多同态加密方案^{[13, 16, 41-43, 74, 75]}也都使用Gentry的Bootstrappaping技术, 这些方案对文献[12]中所提方案都有不同程度的改进, 2010年Stehle和Sheinfeld^[27]提出了一种快速刷新密文的算法来提升Bootstrappaping技术表现; Gentry和Halevi^[27]通过减小公钥大小以及使用批处理技术来提高这项技术的性能, 但是这些改进仍然没有显著提升其效率.例如在一台处理器配置为Intel Xeon E5450 64位4核的终端上对大小为380bit密文重加密(re-encryption)过程中, 按照最低安全要求也要超过1.5分钟来运算^[43], 除了存在计算效率的问题外, Gentry和Halevi的方案需要超过78万位的密文来加密一位二进制明文, 过大的密文体量在传输密文的带宽方面也造成瓶颈, 2011年Gentry、Halevi^[16]又提出了一种无需Squash技术来实现解密电路的方案, 但是这些对Bootstrappaping技术的改进方法由于Gentry的初始方案存在的内在瓶颈与现实商用还有距离.

3.6.2 模交换技术

模交换技术是为了降低密文运算后噪声呈数量级增加的问题而提出来的, 源自以下引理:对于奇数p、q和向量C, $C' \approx (p/q)C,$且$C' = C\bmod 2,$如果对某个S有式(17)成立, 则有式(18)及式(19)成立, 具体如下:

$\forall S,\left\| \left\langle C,S \right\rangle \bmod q \right\|<q/2-({p}/{q}\;)l(S)$

(17)

$\left\langle {C',S} \right\rangle \bmod p = \left\langle {C,S} \right\rangle \bmod q\bmod 2$

(18)

$\left\| \left\langle {C}',S \right\rangle \bmod p \right\|<({p}/{q}\;)\left\| \left\langle C,S \right\rangle \bmod q \right\|+l(S)$

(19)

其中, l(S)为S的范数, 〈C, S〉为向量内积运算.

通过上述引理可知, 当密钥S未知时, 只要知道其长度边界, 就能将密文从模p下转换为模q, 并且$\left\langle {C',S} \right\rangle $ $\bmod p = \left\langle {C,S} \right\rangle \bmod q\bmod 2$仍然成立, 即解密正确.

例如两个噪声为x的密文, 经过一轮相乘后噪声达到x², 若取模$p = {x^n},$密文经过lbn轮相乘就达到了噪声上限从而使解密算法无法正确解密, 如果在第1轮密文相乘后对噪声除以x, 噪声则恢复为原来大小, 模降为$p = {x^{n - 1}},$经过k轮操作, 模为p/x^k, 模形成一个递减系列, 如式(20)所示:

${{p}_{i}}=\left\{ {{x}_{i}}\left| {}^{{{x}^{k}}}\!\!\diagup\!\!{}_{{{x}^{i}}}\; \right.,0\le i\le k \right\}$

(20)

其中, 噪声始终控制为x, 这样, 密文可以进行n轮相乘才会达到噪声上限, 比未使用模转换的lbn轮达到噪声上限时可以做到数量级上的提升, 通过降噪和模递减使方案可以对最高次数为任意的多项式密文做计算并保持同态性, 不需要使用Bootstrappaping来实现, 提升了方案的可用性和效率, BGV方案是应用此项技术的典型方案, 也是目前效率最理想的FHE方案.

3.6.3 密钥交换技术

在所有基于LWE的FHE方案中, 密文C和密钥S都是向量, 密文在计算时乘法定义为张量积形式${C_1} \otimes {C_2},$相应密钥为${S_{\text{1}}} \otimes {S_{\text{2}}},$因此密文在计算后维数将极速上升, 很快达到计算边界, 通过密钥交换技术来降低维数膨胀的问题, 其本质是将一个矩阵B和密文C₁相乘得到新的密文, 即${C_1}^T \times B \to {C_2}$(B行数是S₁的维数, 列数是S₂的维数, S₂的维数小于S₁), 通过密钥交换可将维数是h₁的密文转换为维数h₂的密文, 即$\left\langle {{C_1},{S_1}} \right\rangle \to \left\langle {{C_2},{S_2}} \right\rangle ({h_2} < {h_1}),$模p保持不变, 达到降低密文维数的目的, 对较小的密文明文C₂执行解密算法$m = ((\left\langle {{C_2},{S_2}} \right\rangle \bmod q)\bmod2),$这样既可省去Squash操作也能正确完成脱密.但是这种方法的缺陷是每次密钥交换时密文都需要乘以一个矩阵, 这会影响到FHE方案的执行效率.此外, 新的密文C₂在计算后的噪声也略高于C₁.

3.6.4 并行计算技术

密文打包技术、批处理技术、单指令流多数据流(SIMD)技术都被用于提升FHE方案的执行效率.2010年Smart和Vercauteren^[13]首次提出了密文打包技术, 并由Gentry和Halevi应用到FHE方案中^[16], 不同于以往逐位对明文进行加密的方式, 利用这种方法可以将二进制明文的多位打包成向量元素, 通过中国剩余定理来加密成一个新的单个密文.单指令流多数据流技术可以将密文重加密过程并行处理, 能够显著提升速度并且降低所需带宽和通信成本, 在Coron^[57]等人的方案中, 原本加密4MB的明文数据需要在网络中传输74TB的密文数据, 通过并行计算技术^[62]改进FHE方案, 利用SIMD技术对AES十轮操作并行处理, 这样, 每个操作平均耗时12min, 最终可以将通信成本降低到接近280GB^[76], Smart^[77]等人通过中国剩余定理对明文序列进行批处理, 然后利用SIMD技术实现了明文序列的并行计算, 在文献[53]中采用密文打包技术对FHE方案进行优化, 将AES的十轮操作并行化处理, 平均每个操作花费40min, 比Gentry、Halevi^[16]的方案在速率上高出几个数量级, 文献[42, 53, 54]的FHE方案都使用了并行计算技术来优化以提升方案的效率.

4 同态加密技术在云计算隐私保护中的应用 4.1 云计算中保护隐私的检索(privacy-preserving search)

随着云计算技术深入拓展到各个领域, 云端数据的存储和使用呈几何爆炸式增长, 对加密数据的检索成为一个亟待解决的难点问题, 目前已有的研究工作通常都是采用一种数据结构来存储明文对应的多个可能的模糊关键字的密文, 通过精确匹配来实现模糊检索, 但是它们只适用于小规模数据的检索, 且代价高效率低.基于全同态加密的数据检索技术能够直接在加密的数据上直接检索, 避免检索数据被统计分析, 不仅能做到保序检索, 还能对检索的数据进行比较、异或等简单运算.Gopal^[78]和Singh基于Gentry的FHE方案提出了一个PPS方案, 利用密钥加密文件中每个关键字和查询, 这样, 云端在不知道密钥的情况下, 只能对密文数据进行操作返回密文结果.Cao^[79]等人提出了一种多关键字排序搜索技术, 方案的思想是使用密钥加密向量时添加虚假关键字, 进行分割或相乘操作(密钥由一个向量和两个矩阵组成), 用户端也将应用相同的操作(作少许更改)对查询向量使用相同的密钥加密然后发送到云端, 云端接收后对加密的向量(查询和索引)进行处理再生成相似向量.Li^[80]等人提出了一种用于对加密数据进行模糊关键字检索的技术, 数据所有者通过构造一个模糊关键字集合来构建一个索引, 然后通过数据所有者和授权用户之间共享的密钥计算门陷集, 数据所有者再将此索引发送到云端, 检索数据集时, 授权用户使用与数据所有者间共享的密钥计算查询关键字的门陷集, 然后将其发送到云端, 云端接收查询后, 与索引表进行比较, 根据模糊关键字返回所有可能的加密文件标识.

4.2 多方安全计算中的应用

在现实中, 某个应用场景中需要多方参与计算, 但是各方互相可能为可信也可能为不可信, 当需要对私有数据进行检索、分析、处理时, 大家都不希望数据内容被其他参与方掌握, 所有参与方将自有数据以密文形式进行联合计算, 使用全同态加密算法, 可以使除用户和授权者外的第三方利用其同态特性在密文上直接操作, 将结果返回后得到明文计算相同的结果, 从而完成用户的需求.Bendlin等人^[81]对多方安全计算和同态加密技术的关系进行了系统论述, 文献[82]基于同态加密算法来解决了“百万富翁”难题, Goethals等人^[83]在向量点积多方安全计算问题中同样借助了同态加密算法.现实中, 很多应用场景需要通过多方安全计算协议来实现, 例如电子投票、多人参与的网上棋牌游戏等, 密钥分配协议、不经意传输协议等都是多方安全计算协议的特例, 而同态加密算法则是构建多方安全计算协议的重要基础.

4.3 密文数据库

CryptDB是麻省理工计算机科学和人工智能实验室(CSAIL)以PHE方案为基础实现商用化的应用实例, 它能够实现用户对存储在SQL数据库的数据进行多种查询操作, 通过SQL能够“识别”的4种操作(order comparison、equality checks、join、aggregate)来分解所有原始查询语句以对数据按列进行加密, 从内到外层层采用不同加密方案来加密不同查询功能, 其安全性由内层的低强度到最外层满足语义安全.另外, CryptDB系统对用户身份密码和加密算法密钥进行捆绑, 这样用户如果不使用正确的身份密码将无法登录对数据项进行解密, 连数据库管理员也无法对密文数据解密, 即使服务器被攻破, 只要用户没有登录, 攻击者也无法解密用户的密文数据, 并且CryptDB主要采用对称型HE方案, 因此所有操作对系统效率影响较小.Tu等人^[84]提出Monomi算法, 对CryptDB进行改进使其能处理更复杂的查询.近期, 国外研究者在CryptDB基础上提出了MrCrypt^[85]、Crypsis^[86], MrCrypt应用于云计算系统的开源系统Hadoop中的并行计算模型MapReduce、Crypsis用于支持如Pig Latin这样的高级数据流语言, Crypsis和MrCrypt都使用Pai、EGM方案分别来实现密文数据的加法和乘法同态运算, 为了支持多种类型的查询服务, CryptDB中的每一条数据和变量都需要使用不同的同态加密方案进行加密(例如, Paillier加密方案支持统计查询, EGM方案支持关键词搜索), 这导致额外的存储消耗, 当外包数据频繁进行传输时也会增加与第三方云服务商的通信开销.

4.4 其他应用研究

Brenner等人^[87]针对云计算环境中的数据隐私问题, 采用全同态加密技术实现了机密程序在第三方服务器上的安全执行.Hsu等人^[88]针对云计算环境中的多媒体信息检索问题, 提出了一个基于Paillier的安全尺度不变特征变换(SIFT), 从而实现隐私保护的特征抽取和表示, 并基于量子的安全比较策略实现了同态比较.Ren等人^[89]针对无人值守的无线传感器网络(unattended wireless sensor networks, 简称UWSN), 基于同态密钥共享和同态加密机制设计了一个数据传输方案H2S, 提高了数据传输效率, 并为数据的机密性和完整性提供了保障.Zhu等人^[90]针对分布式计算模Map-Reduce中的隐私保护问题, 基于BloomFilter和加法同态算法实现了隐私保护的密文检索.Zhu等人^[91]描述了同态加密算法在加密的声音信息检索中的应用.Igor等人^[92]描述了同态加密技术在移动设备的隐私保护中的应用.Liu等人^[93]针对无线传感器网络中的隐私安全问题, 采用同态密钥共享和同态加密的方法来保证数据的安全和检索.Upmanyu等人^[94]基于安全的多方计算和同态加密算法Paillier实现了隐私保护的分布式k-均值聚类.Yi等人^[95]针对UWSN中安全和高效的存储问题, 提出了基于同态加密和密钥推导的方案.Lipmaa^[96]基于全同态加密技术实现了外包数据的安全更新.马进等人^[97]提出了分布式环境下的基于随机数值片拆分统计机制的匿名均值统计和匿名方差统计方法, 并结合加法同态加密算法Paillier, 设计了分布式环境下的随机数据交换方法, 实现了分布式环境中匿名数据交换机制.方炜炜等人^[98]针对分布式决策树挖掘的隐私保护问题, 提出一种基于同态加密技术的决策树挖掘算法, 使各参与方在不共享其隐私信息的前提下达到集中式挖掘的效果.Jaideep等人^[99]基于同态加密技术改进了贝叶斯分类方法, 保证了分类过程中的数据隐私安全.Vaidya等人^[100]也是基于同态加密技术实现了支持向量机的分类.应当说, 加强同态加密技术在云计算隐私保护领域中的应用, 不仅能够利用同态加密算法的优势来解决云计算安全问题, 同时还可以帮助同态加密自身发展, 从而达到互利双赢的目的.

5 总结与研究展望

目前, 同态加密技术在云计算隐私安全的应用领域不断扩展, 这同时也加速了同态加密技术本身的改进与发展, 虽然不少研究者提出了新的FHE方案, 但当前基于各种传统数学难题假设的方案在运算效率上还比较低, 所要求的计算量和密文膨胀率都不理想, 许多已有方案往往要求数据拥有者在数据外包的过程中做大量的协助工作, 例如建立并维护目录, 或者要求通过一个第三方才能实现对密文的运算, 前者会使用户的使用体验大打折扣, 后者增加了接触数据的参与者, 即增加了数据泄露的风险, 大范围商用还不现实.此外, 密文空间膨胀是现有同态加密算法所面临的共同问题, 大部分建立在公钥体制上语义安全的同态加密算法都有这个问题, 这也是概率性加密算法固有的问题, 密文过大也使用户从客户端上传加密数据到云端以及从云端下载加密到客户端会面临传输带宽瓶颈.现阶段从技术上彻底解决密文膨胀的问题还不现实, 还需要从减小密文空间大小的角度进行改进和探索, 现有FHE方案主要通过同态解密技术来降低密文膨胀问题, 这样确实从理论上看能够克服计算边界的问题, 但从实现角度上看非常复杂.此外, 安全性与适用性问题也必须加以考虑.首先, 大部分同态加密算法无法有效抵抗自适应选择密文的攻击, 最高安全级别只能达到抵抗选择明文攻击; 其次, 由于可关联性是同态加密算法的内在属性, 导致其不能应用在需要不可关联方案支持的场景中.掌握同态加密方案的适用范围, 可以明确在什么场景下应用, 什么情况下要避免使用同态加密算法而使用传统加密算法, 以免误用造成安全隐患; 最后, 现有大多数FHE方案都是以Gentry的FHE方案为原型, 这类方案在构造过程中一般分两个阶段, 首先设计一个SWHE方案, 然后通过噪声管控技术将其转换为一个FHE方案, 因此, 如何不经过SWHE方案阶段直接构造一个FHE方案仍然是一个开放问题.以上都是需要进行研究的重点问题.本文对云计算隐私安全面临的威胁和同态加密技术的研究进展进行了介绍, 对现有同态加密方案作了分类和总结, 分析了各种方案的优缺点, 重点对全同态加密算法的构造、实现技术、安全基础作了分析.全同态加密技术是未来云计算隐私保护的重要依托, 现有方案在加、解密效率上较低, 构造方式和实现技术也很复杂, 这些问题都有待解决, 需要研究者持续而有创造性地进行工作, 我们认为, 未来可以在以下几个方面作进一步研究.

(1) 对称密码体制同态加密方案.

在大多数公钥同态加密算法中, 都面临公钥尺寸过大、加密后明文对应密文过大问题, 如在Dijk等人的整数FHE加密方案中, 1Bit明文加密后产生λ⁵ Bit(λ为安全参数)的密文, 当前的同态加密算法, 无论是电路同态加密算法还是代数同态加密大多基于公钥私钥体制来构建, 使用公钥压缩技术减小公钥大小, 同时扩大明文空间, 缩小密文空间是有效降低密文计算复杂度的方法, 但是以这种方法为构建基础的一个明显缺点是算法的计算复杂度较高, 明文的加密速度很慢.因此一般情况下, 非对称公钥加密算法并不适用于用户在云服务器上进行外包计算这类需要对大量数据进行加密的场景, 要实现云环境中密文的快速稳定存储等应用, 就迫切需要研究计算复杂度低的对称类同态加密算法.

(2) 可验证的同态加密方案.

若用户将计算函数也外包存放在网络空间中, 也会带来用户无法对返回的计算结果予以正确性验证的问题.尽管同态加密方案用来保证云环境中用户数据外包给半可信或不可信云服务商进行运算的安全性, 但用户更加关注计算结果的准确性, 以及这些不可信的服务供应商是否正确执行用户提出的计算要求或只是将近似的结果返回给用户, 要解决这个问题, 需要将同态加密技术与可验证计算技术一起使用, 以保证用户外包计算数据的完整性, 而现有的同态加密算法均未对计算结果的正确性予以考虑.因此, 研究一种可验证的同态加密方案成为当前迫切需要解决的问题, 即设计一种支持高效且安全性高的同态加密方案, 并研究出针对该算法的验证方案, 用以满足云计算存储服务中对于安全性、可靠性、可用性的需求.

(3) 无噪声FHE方案.

无噪声(没有密文膨胀)FHE方案是近期的另一个热点研究方向, 在加密方案中并不使用任何噪声管理技术, 这些无噪声是基于经典的数理论概念构建的对称加密方案, 如基于八进制代数、交换环和非交换环.现有的无噪声FHE方案中除了Nuida^[101]提出的方案是基于非对称密码体制的以外, 大部分都是对称型, 但是大部分现行的无噪声FHE方案在安全性上并不可靠, Kipnis^[74]等人基于交换环的方案无法抵御选择明文恢复密钥的攻击, Yagisawa^[102]等人基于离散对数问题的方案无法抵御量子攻击, 未来无噪声FHE方案需要在安全性分析上进行更深入的探索, 以求构建真正安全可靠的加密方案.

(4) 基于人工智能技术的FHE方案.

近期微软公司将人工智能技术引入到同态加密中, 按照CryotoNets^[103]的报道, 一家公司利用基于RLWE和LWE的FHE方案对数据进行加密上传到云端, 云服务提供商使用人工前馈神经网络可以基于密文进行预测分析, 但是所使用的神经网络模型需要提前用密文数据进行训练, 并且训练神经网络所消耗的时间较为可观, 将来是否有其他人工智能技术与同态加密技术相结合也值得研究.

(5) 支持“多对一”模式的同态加密方案.

现有的同态加密方案大多采用“一对一”部署模式, 一方使用公钥对明文进行加密, 另一方使用私钥对密文解密, 这种形式的加密方式在“一对多”“多对一”和“多对多”的应用场景下效率很低.在现实中, 存在不少“多对一”的应用场景, 尤其是在云服务模式下, 作为数据接收者的服务提供商数量远远小于作为服务请求者的用户数量, 一个服务提供者常常要求为数以万计的数据发送者提供服务.传统的“一对一”同态加密方案在这种“多对一”的应用要求下是低效的.因此研究支持“多方加密、一方解密”应用场景的同态加密方案对于云服务模式下隐私保护非常有意义, 设S为数据接收方, 拥有一对公钥与私钥(pk, sk), P_i(i=1, …, n)为多个数据发送者或服务请求者, 各自拥有一对公钥私钥(pk_i, sk_i).“多对一”模式同态加密方案除了要满足典型公钥加密系统的特性外, 对于明文空间M内任意m∈M, m₁, m₂∈M应满足以下特性:

${D_{sk}}({E_{pk}}(m)) = m$

(21)

${D_{s{k_i}}}({E_{p{k_i}}}(m)) = m$

(22)

${D_{s{k_i}}}({E_{p{k_j}}}(m)) \ne m$

(23)

${D_{sk}}({E_{p{k_i}}}(m)) = m$

(24)

${D_{sk}}({E_{pk}}({m_1} \circ {m_2})) = {D_{sk}}({E_{pk}}({m_1}) \circ {E_{pk}}({m_2}))$

(25)

${D_{s{k_i}}}({E_{p{k_i}}}({m_1} \circ {m_2})) = {D_{s{k_i}}}({E_{p{k_i}}}({m_1}) \circ {E_{p{k_i}}}({m_2}))$

(26)

${D_{sk}}({E_{p{k_i}}}({m_1} \circ {m_2})) = {D_{sk}}({E_{p{k_i}}}({m_1}) \circ {E_{p{k_i}}}({m_2}))$

(27)

${D_{sk}}({E_{pk}}({m_1} \circ {m_2})) = {D_{sk}}({E_{p{k_i}}}({m_1}) \circ {E_{p{k_j}}}({m_2}))$

(28)

$ \circ $为密文运算符号, 式(21)~式(23)表示不同用户仅能够使用各自的一对公钥私钥对进行加解密, 式(24)体现了“多对一”加密方式的特性, 不同的用户用各自私钥加密数据发送给同一数据接收者S后, S能够使用自有私钥sk进行解密, 式(25)、式(26)表示P_i(i=1, …, n)、S在密钥对(pk_i, sk_i), (pk, sk)下各自支持关于$ \circ $的同态运算, 式(27)表示P_i与S在密钥对(pk_i, sk)下支持关于$ \circ $的同态运算, 式(28)表示P_i、P_j、S在(PK(pk_i, pk_j), sk)下支持关于$ \circ $的同态运算.