近年来，云计算环境下的安全事故时有发生，云环境的数据隐私问题引起了人们的高度重视。安全研究分析表明^[1]：云端的数据易被泄露，云计算的弱点主要集中在数据保护(30.29%)和身份管理(20.14%)。因此，保护云端数据的安全迫在眉睫。

目前，人们对于云环境中的数据隐私安全问题的应对方法是将数据存储到云服务器之前预先进行加密处理，需要时再由用户解密。常见的数据隐私保护技术有：用于区分数据使用者身份的代理重加密技术^[2]和属性加密技术^[3]，用于资源授权访问范围的访问控制技术^[4]，用于对密文数据进行检索访问的可搜索加密技术^[5]等。这些技术采用传统的加密保护，只能满足加密存储的功能，缺少能直接对密文进行计算的、更方便的隐私保护手段。

全同态加密技术^[6]在远程外包环境下具有良好的密文可计算性，支持密文运算、检索、排序，能保证传输、存储上的安全，是解决云环境隐私安全问题的有效方法。近年来，对全同态加密方案的研究主要集中在：基于近似最大公约数问题的全同态加密方案^[7-8]、基于容错学习(learning with errors, LWE)的全同态加密方案^[9-11]、支持访问控制和多用户共享的全同态加密方案^[12-15]。但以上研究并非针对云计算安全而开展的。

随着全同态加密技术的不断成熟，人们也将全同态加密技术应用于云安全服务，利用全同态加密的优良特性，提高云服务安全性。文[16]基于抽象代数度量空间技术和加密代理技术构造了满足云环境下多用户共享要求的全同态加密方案。文[17]提出了一个基于NTRU的多密钥全同态加密方法，但只允许最多M个不同公钥加密的密文进行计算。文[18]构造了基于策略的多用户全同态加密方案，可解决云环境中多用户密文计算、访问控制和共享等问题，但该方案的密文解密效率较低，密钥生成效率和加密效率会随着访问策略的复杂而下降。

云环境中用户的多样性和复杂性要求全同态加密技术必须满足多用户的密文计算、共享需求，但是现有的全同态加密算法仍存在一些不足。为此，基于属性加密技术和代理重加密技术，本文提出云环境中基于代理重加密的多用户全同态加密方案，旨在解决云环境中多用户共享和隐私安全问题。

1 问题描述

本文设计相关应用场景来描述面向云计算的用户隐私安全需求。公司员工根据其所在部门和职务被限制地访问公司数据；公司选购云服务提供商(cland service provider, CSP)提供的计算资源来完成公司的大型计算任务。在工作过程中，为了遵守公司的隐私规范，每个数据发送者必须设定适当的访问策略来加密数据，且其他员工必须在满足加密数据认证条件前提下才能访问该数据。这种情况下，不同部门员工上传的加密数据之间可能会被发送者的子集或者其他授权人员进行计算或进行其他处理，只有满足结果数据访问策略的员工才有资格对结果数据进行访问。

针对以上用户隐私需求，通常采用的保护数据的有效方法是加密。但是，传统的加密手段无法在云计算环境下对密文进行检索和查询。如果将加密信息取到客户端，解密后对数据进行处理，再加密上传至云端，这就需要频繁地存取加解密数据，将大大增加云端服务器和客户端的通信和计算开销。所以传统的加密方式不能满足云环境下用户数据隐私需求，而全同态加密技术就比较适合解决云环境下用户数据隐私的问题。

然而，现有的全同态加密算法大都针对单一用户全同态密文计算而设置，涉及多用户的全同态密文计算的算法甚少。图 1给出了云环境中单一用户全同态密文计算的系统模型。具体的加密、解密以及密文计算过程如下：

步骤1  密钥生成中心使用Setup(1^λ, 1^L)启动算法生成公共参数params；使用私钥生成算法SecKeyGen为用户生成私钥sk，使用公钥生成算法PubKeyGen生成公钥pk；最终将sk和pk返回用户。

步骤2  用户i使用加密算法Encrypt，对明文μ_i加密得到密文C_i，然后将密文上传到CSP的服务器。

步骤3  CSP根据运算符号op={+, ·}，使用密文计算算法Evaluation对不同密文C_i和C_j进行处理，最后把密文计算结果C返回给用户。

步骤4  用户使用解密算法Decrypt对返回的密文计算结果C进行解密，得到结果明文μ。

从图 1可看出，单一用户全同态密文计算模型中，只有使用相同公钥对不同明文进行加密，得到的密文才能进行全同态加密运算。在多用户环境下，不同用户数据肯定使用不同的公钥、密钥对作为加解密的工具，当用户将各自密文上传至远程服务器存储时，不同用户之间密文将是独立的。显然，单一用户全同态加密算法无法对不同用户之间的密文进行计算，也不能满足多用户共享要求。为了解决多用户的密文计算和共享问题，本文提出基于代理重加密的多用户全同态加密方案(PREB-MUFHE)。

2 PREB-MUFHE加密方案 2.1 近似特征向量技术和Flattening密文技术^[12]

近似特征向量技术是构造全同态加密方案的关键技术，使用该技术的密文乘积不会存在密文维数膨胀问题。Flattening密文技术能够在不影响向量点积的情况下改变向量。

定义1  假设a, b为Z_q上的k维向量，$l=\left\lfloor \rm{lo}{{\rm{g}}_{\rm{2}}}\mathit{q} \right\rfloor +1$，且N=k·l。定义BitDecomp(a)返回N维向量a′=(a_{1, 0}, …, a_{1, l-1}, …, a_{k, 0}, …, a_{k, l-1})，其中a_{i, j}是二进制形式a_i的第j位；BitDecomp^-1(a′)=(∑2^j·a_{1, j}, …, ∑2^j·a_{k, j})表示BitDecomp的逆过程；Flatten(a′)=BitDecomp(BitDecomp^-1(a′))，返回0/1系数的向量；定义Powerof2(b)=(b₁, 2b₁, …, 2^l-1b₁, …, b_k, 2b_k, …, 2^l-1b_k)。

对于矩阵A，BitDecomp(A)，BitDecomp^-1(A)以及Flatten(A)则是对矩阵A的每行应用上面的操作。应用Flattening密文技术，下面等式成立。

1) 〈BitDecomp(a), Powerof2(b)〉=〈a, b〉

2) 对于N维向量a′, 〈a′, Powerof2(b)〉=〈BitDecomp^-1(a′), b〉=〈Flatten(a′), Powerof2(b)〉

2.2 PREB-MUFHE加密方案

图 2为PREB-MUFHE加密方案的系统模型。该方案的设计思想是：1)以近似特征向量技术^[12]作为基础，密钥生成中心为数据拥有者生成公钥，为授权用户生成计算密钥或私钥；2)不同的数据拥有者设置自己的访问策略，并用加密算法和公钥对数据进行加密，然后将密文上传至云端；3)为了使不同用户之间密文的运算结果也能满足全同态性，当某个用户的密文上传到云端时，通过对该密文进行重加密，将它转化为对同一用户下的密文，然后再进行密文的计算。这样就有效地解决了云环境中多用户的密文计算、密文共享问题。

定义2  PREB-MUFHE方案由一组概率多项式时间算法组成，即有：ε_preb-mufhe{Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}。其中：

1) 密钥生成中心启动算法Setup(1^λ, 1^L)。该算法为所有用户生成公共参数pubParams= {n, q, χ, m}，其中λ、L是安全参数；格维度n=n(λ, L)；q为k的模数，有k=k(λ, L)；错误分布χ=χ(λ, L)；m=O(nlogq)，N=(n + 1)·($\left\lfloor \rm{lo}{{\rm{g}}_{\rm{2}}}\mathit{q} \right\rfloor +1$)。对于不同的用户，Setup生成的公共参数pubParams会有所不同。

2) 密钥生成算法SecKeyGen(pubParams)。密钥生成中心认证用户i的权限，并调用SecKeyGen为用户i生成解密私钥sk_i=s_i←(1, -t_{i, 1}, …, -t_{i, n})∈Z_qⁿ⁺¹, v_i=Powerof2(s_i)，其中向量t_i←Z_qⁿ。

3) 公钥生成算法PubKeyGen(pubParams, sk_i)。密钥生成中心对认证通过的用户，由PubKeyGen算法为用户i生成公钥pk_i。有矩阵B_i←Z_q^m×n以及向量e_i←χ^m，计算b_i=B_i·t_i+e_i。设矩阵A_i=(b_i|B_i)，输出公钥为pk_i=A_i。通过观察可知A_i·s_i=e_i。

4) 重加密密钥生成算法ReKeyGen(pubParam, sk_i，sk_j)。用户j与用户i通过多用户密文计算和密文共享协商之后，由用户j向密钥生成中心提交多用户密文计算和共享申请；密钥生成中心得到用户i的授权后，调用ReKeyGen为用户j生成重加密密钥rk_i→j。首先运行A_j←PubKeyGen(pubParams, sk_j), 接着计算R_i→j←A_j+Powerof2(sk_i), 输出rk_i→j=R_i→j。

5) 加密算法Encrypt(pubParams, pk_i, μ_i)。假设加密消息μ_i∈Z_q，有均匀矩阵U_i ∈{0, 1}^N×m, 输出密文C_i=Flatten(μ_i·I_N+BitDecomp(U_i·A_i)) ∈D^N×N。

6) 代理重加密算法ReEncrypt(C_i, rk_i→j)。对于用户i的密文C_i，由CSP经过代理重加密算法将生成用户j的密文C′_j。具体的计算是：对于给定的重加密密钥rk_i→j，输出C′_j←C_i·BitDecomp(R_i→j)。

7) 解密算法Decrypt(pubParams, sk_i, C_i)。对于用户i的密文C_i，该算法计算向量x=C_i·v_i=μ_i·v_i+U_i·A_i·s_i=μ·v_i+U_i·e_i，然后对x进行如下处理：bit_k=(min(x_k, q-x_k) ≥|x_k-q/2|), 最后得到解密结果result+=bit_k·2^l-1-k，其中k={l-2, l-1, …, 0}。

8) 密文计算算法Evaluation(C_i, C_j, op)。该算法可能是概率算法。对于用户i的密文C_i，用户j的密文C_j，若op=‘+’，则调用Add(C_i, C_j)做加法运算，输出Flatten(C_i+C_j)；若op=‘·’，则调用Mult(C_i, C_j)做乘法运算，输出Flatten(C_i·C_j)。其中C_i和C_j必须是由相同公钥加密而成的密文。

定义3  PREB-MUFHE的正确性：假设D为明文数据的定义域，op为操作运算符，则ε_preb-mufhe {Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}是正确的，应满足：

1) ∀μ∈D, ∃Decrypt(pubParams, sk, Encrypt (pubParams, pk, μ))=μ。

2) 若有C_i←Encrypt(pubParams, pk_i, μ_i)，且C′_j ←ReEncrypt(C_i, rk_i→j)，则〈C′_j, sk_j〉=μ_i·s_i+C_i·e_j+〈U_i, e_i〉.其中e_i, e_j←χ^m, U_i ∈ {0, 1}^N×m。

3) ∀μ_i, μ_j∈D, ∃Evaluation′ (μ_i, μ_j, op)=Decrypt (pubParams, sk, Evaluation(C_i, C_j, op))。

定义4  LWE问题^[11]。有安全参数λ，格维数n=n(λ), 整数q=q(λ)≥2，以及χ=χ(λ)是Z上的分布. LWE_{n, q, χ}问题是区分以下两个分布：分布1，从$\mathbb{Z}_{q}^{n+1}$中均匀取样(a_i，b_i)；分布2：首先从$\mathbb{Z}_{q}^{n}$中均匀取样s，a_i，从分布χ中取样e_i，记b_i=〈a_i, s〉+e_i。LWE_{n, q, χ}假设表示LWE n, q, χ问题不可行。

定义5  PREB-MUFHE的安全性：ε_preb-mufhe{Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}是基于LWE问题安全的。

3 正确性和安全性证明 3.1 正确性证明

定理1  PREB-MUFHE={Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}是正确的，∀μ∈D, ∃Decrypt (pubParams, sk, Encrypt(pubParams, pk, μ))=μ。

证明  密文C_μ是一个矩阵，计算C_μ=Flatten(μ·I_N+BitDecomp(U·A))。由C_μ·v=Flatten(μ·v+U·e), Flatten操作使得μ·v+U·e矩阵元素很小(不小于1)，密钥v是Z_q上的一个N维向量且至少包含有一个大系数v_i。

由于密钥v作为密文矩阵C_μ的近似特征向量，明文数据μ作为特征值这个本质可以得出通过提取密文C_μ的第i行c_i，计算x←〈c_i, v〉=μ·v_i+e_i，输出μ =[x/v_i]。因此，∀μ ∈ Z_q, ∃Decrypt(pubParams, sk, Encrypt(pubParams, pk, μ))=μ。

得证。

定理2  PREB-MUFHE={Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}是正确的，若有C_i←Encrypt(pubParams, pk_i, μ_i)，且C′_j ←ReEncrypt(C_i, rk_i→j)，则满足〈C′_j, sk_j〉=Flatten(μ_i·s_i+e_i)+C_i·e_j。其中e_i, e_j←χ^m, U_i∈{0, 1}^N×m。

证明

$ \begin{align} &\ \ \ \ \ \ \ \ \ \left\langle {{{{C}'}}_{j}}, ~\rm{s}{{\rm{k}}_{\mathit{j}}} \right\rangle ={{C}_{i}}\cdot {{\mathit{\boldsymbol{R}}}_{i\to j}}\cdot {{\mathit{\boldsymbol{s}}}_{j}}= \\ &\ \ \ {{C}_{i}}\cdot (({{\mathit{\boldsymbol{A}}}_{j}}+{\rm{Powerof}}2({{\mathit{\boldsymbol{s}}}_{i}}))\cdot {{\mathit{\boldsymbol{s}}}_{j}})= \\ &{{C}_{i}}\cdot ({{\mathit{\boldsymbol{A}}}_{j}}\cdot {{\mathit{\boldsymbol{s}}}_{j}}+{\rm{Powerof}}2({{\mathit{\boldsymbol{s}}}_{i}}))\cdot {{\mathit{\boldsymbol{s}}}_{j}})= \\ &\ \ \ {{C}_{i}}\cdot ({{\mathit{\boldsymbol{e}}}_{j}}+{\rm{Powerof}}2({{\mathit{\boldsymbol{s}}}_{i}}))\cdot {{\mathit{\boldsymbol{s}}}_{j}})= \\ &\ \ \ \ \ \ \ {{C}_{i}}\cdot ({{\mathit{\boldsymbol{e}}}_{j}}+{\rm{Powerof}}2({{\mathit{\boldsymbol{s}}}_{i}}))= \\ &\ \ \ \ \ \ \ \ \ {{C}_{i}}\cdot {{\mathit{\boldsymbol{e}}}_{j}}+{\rm{Flatten}}({{\mu }_{i}}\cdot {{\mathit{\boldsymbol{I}}}_{N}}+ \\ &{\rm{BitDecomp}}({{\mathit{\boldsymbol{U}}}_{i}}\cdot {{\mathit{\boldsymbol{A}}}_{i}}))\cdot {\rm{Powerof2}}({{\mathit{\boldsymbol{s}}}_{i}})= \\ &\ \ \ \ \ \ \ {{C}_{i}}\cdot {{\mathit{\boldsymbol{e}}}_{j}}+{{\mu }_{i}}\cdot {{\mathit{\boldsymbol{s}}}_{i}}+\left\langle {{\mathit{\boldsymbol{U}}}_{i}}, {{\mathit{\boldsymbol{e}}}_{i}} \right\rangle = \\ &\ \ \ \ \ \ \ {\rm{Flatten}}({{\mu }_{i}}\cdot {{\mathit{\boldsymbol{s}}}_{i}}+{{\mathit{\boldsymbol{e}}}_{i}})+{{C}_{i}}\cdot {{\mathit{\boldsymbol{e}}}_{j}}. \\ \end{align} $

因此，对于C_i←Encrypt(pubParams, pk_i, μ_i)，且C′_j ←ReEncrypt(C_i, rk_i→j), 满足〈C′_j, sk_j〉=μ_i·s_i+C_i·e_j+e_i。

得证。

定理3  PREB-MUFHE={Setup, SecKeyGen, PubKeyGen, ReKeyGen, Encrypt, ReEncrypt, Decrypt, Evaluation}是正确的，∀μ_i, μ_j∈D, ∃Evaluation′(μ_i, μ_j, op)=Decrypt(pubParams, sk, Evaluation(C_i, C_j, op))。

证明  首先，C_j=Flatten(μ_j·I_N+BitDecomp(U_j·A_j))，C_j·v_j=Flatten(μ_j·v_j+e_j)，其中C_i是用户j经过代理重加密算法对用户i的密文C重加密之后的密文。有C_i=C·R_i→j。由定理2可知，C_i·v_j=C·R_i→j′v_j=Flatten(μ_i·s_i+e_i)+C·e_j。

设C⁺=C_i+C_j, C^×=C_i·C_j。对于加操作，C⁺·v_j=Flatten((μ_i+μ_j)·v_j+(e_i+e_j))，由近似特征向量技术可知，容错向量e_i和e_j很小，Flatten操作使得加法运算后的容错向量e_i+e_j还是小，故密文矩阵加法的和即是明文的和。

对于乘操作，C^×·v_j=Flatten(C_j·(μ_i·v_i+e_i+C·e_j))=Flatten(μ_j·(μ_i·v_i+e_i)+C_j·C_i·e_j)=Flatten(μ_i·μ_j·v_i+μ_j·e_i+C_j·C_i·e_j), Flatten操作使得μ_j和C_j·C_i都很小，则C^×·v_j=μ_i·μ_j·v_j+small，由近似特征向量技术可知，密文矩阵乘法的积即是明文的积。

因此，∀μ_i, μ_j∈D, ∃Evaluation′(μ_i, μ_j, op)=Decrypt(pubParams, sk, Evaluation(C_i, C_j, op))。

得证。

3.2 安全性证明

定理4^[18]  任何可区分的算法以ε的优势抵御安全参数为n、m、q以及χ的方案的选择明文攻击(IND-CPA), 可以转换为至少以pε/2mζ²优势抵御LWE_{n, m, q, χ}问题的区分性算法，并且它们的运行时间几乎相等。其中，ζ表示Hash函数的查询域中的群元素总数范围，p是${{\mathbb{G}}_{0}}$的素数阶。

有关定理4的证明，请参考文[18]。

观察BitDecomp^-1(C)=μ·G+U·A，其中G=BitDecomp^-1