云存储下的多用户密钥聚合的关键字可搜索加密方案

王戌琦，程相国，程润辉

(1.青岛大学计算机科学技术学院，青岛266071；2.新华社手机电视台，北京100803)

云存储所具有的强大的分布式存储能力，更低的成本，更高的灵活性，以及按需购买使用的方式，使得越来越多的研究者将目光投向这个领域。现阶段，几乎所有的企业都会使用云来备份企业数据资料，企业用户也使用云在公司内部分享资源数据。在生活中，每天有数百万用户通过基于云存储的社交网络应用(如Facebook，微博等)与朋友家人分享个人数据。虽然云存储给共享数据带来了便利，但也带来了安全问题和隐私泄露等风险。恶意攻击者或恶意的云存储服务提供商会导致严重的个人隐私或商业秘密泄露的问题。为了保护用户隐私，通常的做法是数据拥有者将需要共享的数据进行加密然后上传到云，之后将密钥分发给要共享数据的人，这样持有密钥的人可以进行检索和解密[1]。但是数据加密会导致检索困难，用户检索能力因此受到限制。可搜索加密方案解决了这个问题，数据拥有者加密潜在的关键字和数据，并将加密后的内容上传到云，用户可以将对应的关键字陷门发送给云以实现对加密数据的检索。尽管上述方案可以解决基本的云存储安全需求，但如果涉及到大规模用户群体和大量文件集合应用的系统实现时，密钥的分发、传输保存和管理就将成为一个很难解决的问题。假设一种情景，数据拥有者选择性地与不同用户群组共享大量的加密数据。通常情况下，数据拥有者要为不同的文件使用不同的加密密钥，且给每个用户分发与共享文件数量线性相关的私钥数量，这样导致通信开销和用户密钥存储开销较大以及用户密钥管理困难的问题。另外，用户若想实现对加密文件进行关键字搜索，需要计算和提交大量的陷门给云，这对用户和云都带来了很大的负担，当文件数量规模较大时，上述方案将不再适用。多用户可搜索加密方案[2-4]中使用广播加密[5，6]来实现用户对共享文件的访问控制，但并没有减少共享密钥和陷门的数量，在聚合密钥加密方案[7]的启发下，Cui等[8]提出了密钥聚合可搜索加密(KASE)方案来解决任意群组用户共享大量加密文件的关键字搜索带来的密钥冗余问题。Zhou等[9]指出了KASE 方案的安全性缺陷，并提供了切实可行的陷门攻击模型。KASE方案需要在系统建立阶段规定最大文件上限数量，考虑到文件数量的增长性以及用户密钥的时效性，如果文件数量超过规定阈值或者用户密钥(不再安全)需要更新时，则需要重新构建系统并生成系统参数和数据拥有者的公私钥，这样会产生较大的计算和通信开销。考虑到现实场景，分享的文件的数量应是没有限制而且可以动态增长的。一般情况下，数据拥有者与用户共享文件时，是以用户群组为单位共享的，并且群组的数量远少于文件的数量。本文在文献[8]、[9]基础上，借鉴云访问控制以及多用户可搜索加密(MUSE)方案[10-13]，参照门限秘密共享的加密方案[14-16]和广播加密方案[17-20]构造了一个共享文件数量可动态增长的聚合密钥的关键字可搜索加密方案，该方案可抵抗文献[9]方案中提到的陷门攻击，无需在系统建立时设置文件数量的上限，用户只需要保存一个固定长度的聚合密钥，调整用户分享文件的权限时，只需在云服务器修改相应的增量即可。本文方案适用于更细粒度的云访问控制的可搜索加密的应用，支持分享文件数量动态增长的情形。与已有方案[10-12]相比，本方案部署较为简单，计算开销较小，有良好的应用前景。

1 预备知识

1.1 判定Diffie-Hellman(DDH)问题

设G 为素数p 阶的乘法循环群，g 是群G 的一个生成元，给定四元组(g，ga，gb，gc)，其中a，b，c ∈Zp，判定c＝ab(mod p)是否成立。

1.2 群上的多项式秘密共享

文献[16]使用了一个群上多项式插值构造秘密共享来构造门限的签名方案。

秘密分发:设G 是一个q 阶循环群，任选s∈G∗为要分享的秘密，选择t，n∈，满足1≤t≤n＜q，随机选取F1，F2，…，Ft－1∈G ，然后定义群上的类多项式函数(polynomial-like function，PLF)F:N ∪{0}→G ，令，为每个成员计算秘密值si＝F(i)，并且发送给成员i。

2 具体方案

2.1 结构介绍与方案描述

数据拥有者要与用户通过公共云存储服务分享一些机密文件，传统方法是数据拥有者使用不同的密钥对不同的文件加密，上传加密后的文件至云服务器，数据拥有者与用户分享加密数据时，需要把所有可搜索加密的安全密钥发送给用户，用户收到密钥后需要安全的保存，当用户执行关键字搜索时，必须使用这些密钥来生成所有的关键字陷门。当文件和关键字数量均较多时，会使得用户密钥存储开销和陷门生成的计算开销随之增大。

本文所提的方案能更好的解决这个问题，数据拥有者只需给用户分配一个聚合密钥，而不是与用户分享文件数量线性相关的密钥，用户也仅需要提交一个单独的陷门给云服务器，方案结构如图1所示。

在描述前，给出方案常用符号释义，如表1所示。

(1)系统建立(1λ):输入安全参数1λ，生成q 阶乘法循环群G 和p 阶乘法循环群G1，其中q|p－1，随机选择一个生成元g ∈G1，PKG 选取单向哈希函数H:{0，1}∗→G。 公布系统参数(q，p，g，G，G1，H)。

(2)密钥生成:随机选择F1，F2，…，Ft，s0∈G∗，定义群上的类多项式函数Func:N ∪{0}→G ，令，数据拥有者的私钥一部分为s0，且gF(0)＝gs0。随机选取t个数xi∈，构成集合Xt＝{x1，x2，…，xt}，生成公钥PK＝{gs0，gF(x1)，gF(x2)，…，gF(xt)}，再次随机选择t个不同的数ωi∈，生成私钥msk＝{s0，gF(ω1)，gF(ω2)，…，gF(ωt)}，用户最大分组数为t，i为用户所属群组。

表1 常用符号

(3)私钥提取(msk，j):数据拥有者使用该算法生成聚合密钥Kagg，为分组j 的用户计算任选αj∈作为用户私钥一部分skj，则第j 群组中用户的聚合密钥为

(4)加密(PK，skj，l):数据拥有者使用该算法在上传第l 个文件时加密数据并为用户j 生成关键字密文。任 选kl∈，kl作为该文件的可搜索加密的密钥。为授权分组j计算Δl，j＝，并公开存放在云上，关键字w 的密文为cw＝gkl(H(w)＋s0)。

(5)陷门生成(Kagg， w):用户使用该算法生成陷门来执行关键字搜索，Kagg＝(K1，K2)，为关键字生成唯一陷门

(6)测试(Tr，j，l):输入用户群组j，云服务器使用该算法在第l个文件上进行关键字搜索，将陷门Tr和Δl，j＝(c1，c2)作为输入，计算c′w＝Trc2·c1。 然后判定c′w是否等于cw。

(7)更新(Δl，i，j，l):数据拥有者使用该算法调整用户群组对文件的共享权限，输入用户群组j 和文件l，撤销用户群组j 对文件l的分享权限。任选Δk ∈Z∗q，可搜索加密密钥更新为kl·Δk，对云服务器存储的文件l的增量Δl，i＝(c1，c2)计算，其中i≠j，保存更新后的最后，更新关键字密文:。 云服务器删除增量Δl，j。

2.2 正确性分析

方案要求任何拥有聚合密钥的用户都对其所属群组授权的共享文件进行关键字搜索，云服务器收到用户提交的陷门Tr 后，根据用户所属的组别j，对第l个文件执行测试操作，进行关键字搜索

云服务器计算得到的关键字密文:c′w＝gkl(H(w)＋s0)＝cw。

2.3 安全性分析

为分析方案的安全性，应假设公有云是“诚实且好奇”的，即要求云可以提供方案的要求的合法服务，尽管它可能试图根据其所获得的信息恢复密文。假设用户可能尝试查询本群组之外的授权数据或其他群组的授权数据。借鉴文献[8]和文献[17]方案的安全性证明，从查询的隐私性和搜索有限性进行安全性分析。

定理1方案可保证用户的查询隐私，且攻击者无法从存储的关键字密文和相关公共信息中确定文档中的关键字。

由拉格朗日插值公式可知:

证明：攻击者(与云服务器同谋)可以尝试猜测用户查询的关键字信息。由关键字密文cw＝gkl(H(w)＋s0)∈G1以及用户提交的陷门Tr推测H(w)，但只有解决了离散对数问题才能成功计算得到H(w)，故攻击者通过上述方法计算得到H(w)是困难的。故定理1得证。由定理1的证明，可以推导引理1。

引理1 攻击者不能通过提交相同H(w)的方法恢复合法用户的聚合密钥。

证明：文献[8]提供了一种针对KASE方案的攻击模型，当恶意攻击者A 和受攻击者B 所共享的文件有交叉时，即设D 为共享文件的集合，DA∩DB≠Ø 。那么，攻击者在窃取用户提交的陷门Tr之后，猜测共享文件Yl∈DA∩DB中关键字w 的H(w)值，通过计算并多次向云提交验证的方式得到合法用户的聚合密钥。而在本方案中，攻击者若利用H(w)从用户提交的陷门中获得用户的聚合密钥，应首先获知用户密钥的一部分gαj或者成功解决离散对数问题，在这种情况下，攻击者若要发起成功的攻击必须首先解决离散对数难题，故引理1得证。

定理2即便云服务器与授权用户同谋，用户也无法对授权文件以外的文件进行关键字查询。

证明：好奇的云服务器可能试图从存储的数据和用户提交的陷门中学习一些东西。云服务器与用户j同谋时，令用户分组j 的聚合密钥为，其中秘密份额F(ωj)是由一个随机的t阶拉格朗日插值公式生成的，且αj，s0∈是随机选取的。令αj＝a，，s0＝b，则可生成元组(ga，gaP(j)，gab)，然后将元组(ga，gaP(j)，C)发送给攻击者，如果攻击者可以正确判断C 是否等于gab，则方案不安全，且可以利用攻击者的攻击结果构造算法D 解决DDH 问题。考虑一种极端情况，若云服务器与全部用户合谋，可获得元组(ga，gaP(1)，gaP(2)，…，gaP(t)，gab)，若攻击者可以区分gab和任一随机元素，则方案不安全。同理，可以利用攻击者的攻击结果构造算法D′解决DDH 问题。因为不存在多项式时间算法可以解决DDH 问题，所以即便云与所有用户同谋也无法推得gab，故无法使用结果计算关键字密文gab·gaH(w)以进行关键字搜索。故定理2得证。

引理2攻击者无法使用公开信息和已知的聚合密钥生成新的聚合密钥。

证明：只有当攻击者获得每个文件的可搜索加密密钥k 时，才可以尝试生成新的密钥。在定理1和定理2成立的前提下，k 和gs0的计算是困难的，故攻击无法生成新的密钥。

2.4 效率分析

本方案实现了恒定大小的关键字密文、陷门和聚合密钥设计。相比于KASE 方案，本方案虽然使得文件的增量Δ 数量与用户数量线性相关且增加了用户群组数量的限制，但解除了文件数量的限制，数据拥有者可以与授权的用户分享任意数量的文件。在具体环境中，应用前景广阔。考虑到存储开销，由于文件增量Δ 由云服务器保存，本地用户没有存储负担。在计算上，相比于已有的聚合密钥方案，本方案在加解密阶段没有使用双线性配对计算，且不需要在关键词搜索步骤执行调整算法，一定程度上减少了数据拥有者的生成关键字密文的计算开销，也减少了云服务器运行调整算法的计算开销。

将本方案与KASE[8]和Fc-MKA-KSE[9]方案在计算存储开销和系统特性等方面进行比较，令M 表示群G 上的乘法，M1表示群G1上的乘法，E1为群G1上的指数运算，设群G2为素数p′阶的乘法循环群，则有双线性映射e:G1×G1→G2。M2表示群G2上的乘法，E2为群G2上的指数运算，P 表示双线性配对运算。令S 为授权文件数量，n 为文件的上限值，t表示拉格朗日插值公式的阶数，方案对比如表2所示。

在本方案中，系统建立，密钥生成，私钥提取，加密和更新算法需要数据拥有者执行，其中加密算法可以由云服务器协助完成，测试算法由云服务器执行，陷门生成算法由用户执行。

通过实验仿真来验证上述计算效率分析。仿真环境:Intel Core i5-5200U 2.20GHz处理器，4G 内存；操作系统:Ubuntu 18.04 LTS；代码库:The GNU Multiple Precision Arithmetic Library(GMP)。

表2 本方案与其他方案的性能比较

数据拥有者需要执行系统建立，密钥生成，私钥提取，加密和更新算法。如图2(a)图2(b)和图2(c)所示，系统建立，密钥生成和私钥提取算法与最大用户数量线性相关；加密算法的计算时间耗费与文件数量和最大用户数量线性相关，图2(e)表示在1000个用户情况下文件数量的变化对加密时间耗费的影响，图2(f)表示在1000个文件情况下最大用户数量变化对加密时间耗费的影响。

表3 陷门生成和测试算法的计算耗时

云服务器可以使用公钥PK＝{gs0，gF(x1)，gF(x2)，…，gF(xt)}进行增量的辅助计算，以分担加密算法中数据拥有者的部分计算量，这并不会降低系统的安全强度。在云服务器辅助下，执行加密算法时，如图2(g)和图2(h)所示，云的计算时间耗费与用户数量线性相关，数据拥有者的计算时间耗费与文件数量线性相关，虽然增加了云的计算量，但是显著降低了数据拥有者的计算开销，在系统部署时，可以权衡数据拥有者的计算能力和云服务器的计算能力灵活调整加密方式；如图2(d)所示，更新算法与服务器存量的增量的数量线性相关。如图2(i)和图2(j)所示，云执行的测试算法和用户执行的陷门生成算法的计算时间耗费都是固定值，与文件数量和用户数量无关。

3 结论

本文给出了MU-KA-KSE的算法构造以及安全性证明。分析和仿真实验表明，本方案可以构建基于公共云的高效数据共享的系统。MU-KA-KSE 在保证安全的前提下，解决了之前方案中存在的文件上限问题，在云服务器计算和存储能力支持的前提下，数据拥有者可以与用户分享任意数量的文件，并且调整文件分享权限且无需更新密钥。当与少量用户分享数据时，本方案的综合性能表现要优于KASE 与Fc-MKAKSE的方案，但当用户量较大的时候，云服务器需要计算并保存大量的预设增量，这无疑会给服务器带来较大的负担。如何减少增量的数量和解除用户数量的限制是未来的工作方向，方案需要进一步扩展。