云环境下基于属性策略隐藏的可搜索加密方案

周艺华，扈新宇，李美奇，杨宇光

（1. 北京工业大学信息学部 北京 100124；2. 可信计算北京市重点实验室 北京 100124）

0 引言

随着云计算的快速普及，许多组织将其数据和服务外包给云，但带来了严重的隐私泄露问题。因此，很多用户将敏感数据外包给云服务之前对其进行加密。然而，加密用户的数据妨碍了云应用程序的搜索功能。为了解决此类问题，Song等[1]首次提出了可搜索加密，它允许以加密形式外包数据，同时仍然能够进行搜索。这些方案通常包括以下步骤：数据拥有者（DO，date owner）生成其加密文档和可搜索加密索引，将加密文档和加密索引外包给云。当搜索关键字时，用户（DU，data user）生成一个陷门提交到云服务器上，云服务器可以搜索加密索引并返回相关文档。

目前，大多数方案以模糊关键词[2-4]和排序搜索关键字[5-6]为核心，Liu等[2]采用向量内积方式实现关键字搜索，文件解密密钥需要用户间进行密钥协商；Ahmed等[5]采用可搜索对称加密方式，根据文档与查询的相关性对文档进行排序，任何用户通过上传搜索陷门，都可以获取所需的文档。但近年来，受基于属性的加密（ABE，attribute-based encryption）概念的启发，将访问控制与可搜索加密相结合，加密索引可以通过关键字进行搜索，搜索权限由ABE控制，用户实现了更细粒度的关键字搜索。文献[7-10]提出基于属性的可搜索加密方案，由云端直接完成访问策略的验证，若成功，则只将密文返回给用户端解密，密文的解密与策略不相关，导致攻击者可能跳过访问策略直接进行索引匹配和文件解密。

Niu等[11]和Miao[12]、Wu等[13]分别将访问策略转化为访问树和“AND”门，与其方案相比，本文方案采取线性秘密共享矩阵的访问结构，能够支持任意表达的访问策略，并进行了策略隐藏。Yan等[14]和Waters[15]的方案采用访问策略对每个文件进行加密，并未通过关键字搜索，虽将访问策略转化为线性秘密共享矩阵，然后进行文件的加密，但并未通过对关键字搜索，文件获取效率不高。

针对现有问题，本文主要贡献如下。

1) 利用基于属性的加密和可搜索加密技术，采取线性秘密共享矩阵构造访问策略，将访问控制与关键字搜索、文件加密相结合，保证访问策略与关键字都正确才匹配成功，进行文件存储地址的解密。同时，对属性值进行隐藏，访问策略中任何有价值的属性信息都不会透露给未经授权的接收者。

2) 不同的文件采用不同的密钥加密，用户接收一个聚合密钥，就能解密出所需的文件。

3) 陷门不可连接性。保证即使多次查询的属性或关键字相同，攻击者也无法区分。

在Linux Ubuntu64位操作系统下利用双线性对包，并用 Python语言进行编程。实验结果表明，本文方案的效率高于文献[8]方案和文献[13]方案。

1 预备知识

1.1 双线性映射

令G和GT是两个阶为素数p的乘法循环群，存在双线性映射e：G×G→GT满足以下3个性质[16]。

1) 双线性。对于任意x,y∈G，存在a,b∈Zp，使等式e(xa,yb) =e(x,y)ab成立。

2) 非退化性。存在x,y∈G，满足e(x,y) ≠ 1。

3) 可计算性。对于任意x,y∈G，存在有效的算法计算e(x,y)。

1.2 线性秘密共享矩阵

令U是一个属性集，则

1) 选择秘密值s∈Zp；

2) 共享向量中每个元素对应U中的一个属性，共享向量中的所有元素都在域Zp中；

3) 对于U中的每个访问结构，存在一个l×n的矩阵M，称为共享生成矩阵。

在矩阵Ml×n中，有一个映射函数ρ，它将第i行映射到U中的属性Attr，即ρ(i) → Attr，Attr∈U，i= {1,2,… ,l}。再生成秘密值s∈Zp，考虑一个列向量v=(s,r2,… ,rn)T，r2,… ,rn∈Zp。λ=Ml×nv是l个秘密因子的向量，每个秘密因子λi对应属性ρ(i)。通常称(Ml×n,ρ)为访问策略。

线性重构特性：假设方案的访问结构是线性秘密共享矩阵[17]。设S是一个被授权的属性集，且I= {i:ρ(i) ∈S}。存在一组常数{ωi∈Zp}i∈I，满足，使如果{λi}是访问结构的有效秘密因子，则可以用来计算秘密值s，即。

1.3 基于LSSS的隐藏结构

在隐藏结构中，与矩阵M第i行相关联的属性{ti:vi}由属性类别ti和属性值vi组成，定义一个映射函数π:π(i) →ti，将每一行i映射到相应的类别ti，将{Ml×n,π}以明文形式作为访问结构，对属性值vi加密。云服务器根据用户的属性类别匹配到相应的矩阵行数，判别是否符合访问策略，从而无法获知用户的具体属性值，保证属性值的隐藏。

1.4 困难假设

CDH（computational Diffie-Hellman）假设[18]。根据系统安全参数选择一个阶为素数p的乘法循环群G,g是G的一个生成元，随机选择a,b∈Zp，如果不存在一种算法能够在多项式时间内以不可忽略的概率区分(ga,gb)和gab，则CDH假设成立。

DBDH（decisional bilinear Diffie-Hellman assumption）假设[19]。g是群G的一个生成元，给定两个元组(g,ga,gb,gc,e(g,g)abc)和(g,ga,gb,gc,e(g,g)z)，随机选择a,b,c,z∈Zp，如果不存在一种算法能够在多项式时间内以不可忽略的概率区分e(g,g)abc和e(g,g)z，则DBDH 假设成立。

DDH（decisional Diffie-Hellman）假设。g是群G的生成元，给定两个元组(ga,gb,gz)和(ga,gb,gab)，随机选择a,b,z∈Zp，如果不存在概率多项式时间的攻击者以不可忽略的优势区分gab和gz，则DDH假设成立。

1.5 符号描述

本节介绍本文中使用的一些符号和变量，符号描述如表1所示。

表1 符号描述Table 1 symbol description

2 本文方案

2.1 系统模型

本系统主要包括4类实体，分别是数据拥有者、用户、云服务提供商（CSP，cloud service provider）、属性授权中心（AA，attribute authorization）。系统模型及其流程如图1所示。

图1 系统模型及其流程 Figure 1 System model and its process

1) 属性授权中心。属性授权中心是一个完全可信的实体，负责生成系统的公钥、主密钥和公共参数。此外，负责为用户的属性分发属性密钥。

2) 数据拥有者。数据拥有者对共享文件进行加密，将密文上传到云服务器，获取文件存储地址。然后，用访问策略对关键字加密，生成关键字索引，与加密后的文件存储地址一并上传到云服务器。

3) 用户。每一用户都拥有与其属性集相关的私钥。同时，用户在AA的授权下，生成关键字搜索陷门，由云服务器进行搜索匹配。当符合访问策略、关键字匹配时，接收到返回的部分解密密钥和存储地址密文，解密得到文件存储地址，从而进一步访问云端。云服务器返回加密文件，用户对其进行解密，获取所需文件。

4) 云服务提供商。云服务提供商负责存储加密文件，并将所有匹配的文件密文发送给用户。同时负责关键字的匹配工作，检查用户属性值与访问策略是否匹配，关键字是否匹配，最后将存储地址密文与部分解密密钥返回给用户。

2.2 算法形式化定义

本文提出的方案包括以下算法。

1) 系统建立。SetUp(1γ) → (PP,MSK)：该算法由属性授权中心执行，输入安全参数γ，生成系统公共参数PP和主密钥MSK。

2) 密钥生成。Keygen(PP,MSK,ϕ) → (SK)：该算法由属性授权中心执行，输入公共参数PP、主密钥MSK和用户属性集ϕ，为用户生成私钥SK。

3) 搜索陷门。Trapdoor(PP,SK,q) →Tw：该算法由用户执行，输入公共参数PP、用户密钥SK、关键字q，输出陷门Tw。

4) 加密。 Encrypt(PP,A, KW,F) →(CT,Iw,C2)：该算法由数据拥有者执行，输入公共参数PP、访问结构A、关键字集KW、数据文件F，生成文件密文CT、关键字索引Iw和存储地址密文C2存储于云服务器。

5) 搜索。S earch(PP,Iw,Tw) → (Z,C2/⊥)：该算法由云服务器执行，输入公共参数PP、关键字索引Iw和搜索陷门Tw，若用户满足访问策略并关键字匹配成功，则返回部分解密密钥Z和存储地址密文C2；否则，输出⊥。

6) 解密。D ecrypt(PP,SK,Z,C2,CT) → (Add,F)：该算法由用户执行，输入公共参数PP、用户的私钥SK、部分解密密钥Z、存储地址密文C2，解出文件存储地址Add，然后解密文件密文CT，输出共享数据文件F。

2.3 安全模型

在本文方案中，假定授权中心是完全可信的，且在为数据用户生成密钥前验证数据用户的身份，而云服务器是“诚实但好奇”的实体，即它会诚实地为用户提供服务，但也会利用其拥有的信息从密文及陷门中探寻任何私有信息。

本文方案主要考虑关键字和陷门不可区分。通过攻击者A和挑战者B之间游戏来定义，保证语义安全和密文的不可区分。

游戏1关键字不可区分性。

1) SetUp阶段。挑战者B通过调用SetUp算法获取公共参数PP。A自适应地向B发出不同的询问。

2) 询问阶段。A向B请求对应属性集的私钥，B运行Keygen算法得到相应的私钥SK并返回给A。

3) 挑战。执行过一定数量的上述询问后，A向B发送两个大小相同的关键字 kw0和 kw1，B随机选择b∈ { 0,1}，利用kwb生成加密关键字Iwb且返回Iwb给A。

A能够向B对任意属性集ϕ进行密钥询问，任意关键字 kw(kw ≠ kw0*,kw ≠ kw1*)进行密文询问。

4) 猜测阶段。A输出b'∈{ 0,1}，当且仅当b'=b时A赢得游戏1。

游戏2陷门不可区分性。

1) SetUp阶段。挑战者B通过调用SetUp算法获取公共参数PP。A自适应地向B发出不同的询问。

2) 密钥询问阶段。A向B发出注册请求，B运行Keygen算法得到相应的私钥SK并返回给A。陷门询问阶段。A对关键字q做出询问，B运行Trapdoor算法得到搜索令牌Tw并返回Tw给A。

3) 挑战。执行过一定数量的上述询问后，A向B发送两个大小相同的关键字q0和q1，B随机选择b∈ { 0,1}，利用qb生成加密关键字Tqb且返回Tqb给A。A能够向B对任意关键字q(q≠q0,q≠q1)进行陷门询问。

4) 猜测阶段。A输出b′∈{ 0,1}，当且仅当b'=b时A赢得游戏2。A成功赢得这个游戏的优势为。

2.4 算法设计

步骤1属性授权中心分发属性密钥。

1) 系统初始化

输入安全参数γ，给定双线性映射e:G×G→GT，g为G的生成元，G和GT是素数阶为p的两个乘法循环群。此外，定义两个哈希函数H1:{0 ,1}*→G,H2:{0 ,1}*→G。随机选择μ,β,a∈Zp，生成系统公共参数PP和主密钥MSK，PP由AA公开，MSK由AA秘密保存。PP ={e(g,g)μ,gβ,ga,H1,H2},MSK = {μ,β,a}。

2) 用户密钥生成

① 用户注册时，属性授权中心为用户选择一个随机值r∈Zp，生成用户密钥k=gμgar,。同时，用户将其属性集ϕ以映射{Catex:形式提交给AA，AA根据属性集ϕ，对每个属性选取随机值t∈Zp，计算用户属性密钥D1,x=gat,D2,x=grH1⋅({Catex:Valuex})−t。

② 输出DU密钥，通过安全信道传送给用户。

步骤2数据拥有者上传加密文件。

文件加密：DO对每一个文件Fi∈F，文件所属id为Iid，为其随机选择τi∈Zp，计算加密密钥，生成密文D=Enc(F,k)。计算iisi，用于用户解密密文密钥。

步骤3数据拥有者上传存储地址密文和关键字索引。

关键字加密：DO将访问策略转换为LSSS访问矩阵Ml×n，与Mi相关联的属性{ti:vi}li由属性类别ti和属性值vi组成，Mi是M的第i行。映射函数π:π(i) →ti将每一行i映射到相应的类别ti。

因此，将{Ml×n,π}以明文形式作为访问结构，vi隐藏在密文中，保证属性值的隐藏。

1) 随机选择s∈Zp和一个向量v=(s,r2,…,rn)T∈Zp。

2) 计算λ=Ml×nv。

3) 将文件存储地址Add加密，C2= Add⋅e(g,g)μs,C3=gs；

对文件所属id进行加密，目的是云服务器为匹配文件生成聚合密钥，Y=g−τiIidi；1,i

用访问策略的秘密值s对关键字kw加密，

DO对关键字和存储地址加密，将{Iw,C2}上传到CSP。

步骤4用户上传搜索陷门。

陷门生成：设关键字集为 {q1,q2,q3,…,qn}∈Q,用户选取随机值ra∈Zp，保证陷门的不可连接。计算Valuex})−tra，对关键字q加密所以，陷门为

并将其存储于云服务器。

步骤5云服务器搜索

首先根据用户提交的搜索陷门，并根据用户属性密钥检测是否符合访问策略，进一步验证关键字是否匹配。

1) 根据用户上传的属性类别Catex和数据拥有者上传的映射函数π:π(i) →ti，找到第x个属性在矩阵Ml×n中对应的第i行。计算Ft，当符合访 问 策 略 时，存 在 一 组 常 数 {ωi∈Zp}i∈|ϕ|，使

2) 计算

验证H是否等于Cw=e(gβ,H2(kw)s)，若等式成立，表明搜索成功；若等式不成立，则表明搜索失败。用户的属性集不满足访问策略或者搜索时关键字不同，都会导致算法终止，返回⊥。

部分解密密钥

将 {Z,C2}返回给用户，用来解密存储地址Add和文件F。

步骤6用户解密

1) 解密存储地址

用户使用私钥k、ra、Ft对存储地址密文C2进行解密，保证只有用户自己才能计算，且需要用到访问结构中的秘密值s，防止攻击者跳过访问策略。用户计算

2) 解密文件密文

当用户解出存储地址Add后，用户访问云服务器，云服务器返回存储地址对应的密文CT ={Di,Y0,i}i∈CT，用户计算

解密Fi=Dec(Di,ksi)，得到相应文件Fi。云服务器只需返回一个聚合密钥kagg给用户，无须为每个文件都返回一个解密密钥，用户就可以解密出所有符合搜索条件的文件。

3 安全性分析

3.1 关键字安全

定义1 如果DBDH假设成立，所提方案在关键字攻击下和选择明文攻击博弈中是安全的。没有多项式的对手可以用挑战结构 (M*,ρ*)来破坏所提方案。

通过一个挑战者B和一个攻击者A模拟游戏来证明安全性。

1) 初始化：挑战者B随机选择θ∈{0,1},θ=1时，ZZ =e(g,g)c；θ= 0时，ZZ =e(g,g)μ，μ,c∈Zp，生成系统公共参数和主密钥，将PP ={ZZ,gβ,ga}发送给攻击者。

2) 阶段：A根据自己的属性集S适应地向B进行询问用户私钥，要求S不满足 (M*,ρ*)，B首先检查属性集S，对每个属性值计算SK，将SK发送给A。

3) 挑战：A提交两个长度相等的关键字 kw0和 kw1。B随机选择c∈{ 0,1}，随机选择s∈Zp和向 量v=(s,r2,… ,rn)T∈Zp。计 算λi=Miv,若θ=1，=Add ⋅e(g,g)cs； 若θ= 0，=Add ⋅e(g,g)μs。∀i∈Att，。

4) 猜测。因为A询问到的属性集均不满足访问策略，故A必须恢复关键字信息来判定是kw0还是k w1。A输出其猜测c′。若c′ =c，A输出c′ =c的概率为Pr[c′ =c|θ= 1]= 1/2。

因此攻击者打破DBDH问题的优势是可忽略的。

3.2 陷门安全

定义2如果DDH假设成立，所提方案在选择明文攻击博弈中是安全的。

通过一个挑战者B和一个攻击者A模拟游戏来证明安全性。

1) 初始化：挑战者B随机选择θ∈{0,1},θ=1时，ZZ =gc；θ= 0时，ZZ =ga，a,c∈Zp。生成系统公共参数和主密钥，将PP ={e(g,g)μ,gβ,ZZ}发送给攻击者。

2) 密钥询问阶段。B首先检查属性集S，对每个属性值计算SK，将SK发送给A。若θ= 0, SK = {D1,x=gat,D2,x=gr(H1({Catex:Valuex}))−t,x∈(1,2,… ,|S|),k=gμgar,，陷门询问阶段。A生成搜索陷门

3) 挑战：A提交两个长度相等的关键字q0和q1。B随机选择c∈ { 0,1}，B计算陷门Tw，并返回给A。

4) 猜测。A输出其猜测c′。若c′ =c，A输出c′ =c的概率为Pr[c′ =c|θ= 0]=1/2+ε。若c′ ≠c，A 输 出c′ =c的 概 率 为Pr[c′ =c|θ= 1]= 1/2。

因此，攻击者打破DDH问题的优势是可忽略的。

3.3 密文存储安全性

1) DO对文件加密，将密文CT={Di,Y0,i}i∈F上传到CSP，CSP返回文件对应的存储地址Add，但CSP无法知晓每个加密文件对应的Iid，无法解密密文。

2) DO对返回的存储地址加密，并将其与对应的关键字索引和文件Iid一并上传到CSP，当攻击者或者云服务器由于好奇心学习符合匹配条件的密文时，由于存储地址加密，CSP拥有Iid也无法匹配到对应的加密文件，CSP无法直接返回密文。因此，用户端需要解密存储地址密文，并通过CSP返回的部分解密密钥，计算加密文件密钥，才能获取对应的文件，保证密文存储的安全性。

3.4 策略隐私

在本文方案中，将DO的属性值进行隐藏，只公开所对应的属性类别以及对应的矩阵行号，以防止属性信息泄露。属性采用哈希函数加密，攻击者无法恢复有价值的属性信息。

定理1如果CDH假设成立，本文方案在离线字典攻击下是真正的匿名性。

分析：攻击者已知gs,ga，但攻击者无法计算gas，因此攻击者不能通过e(gas,grra)=发动离线字典攻击。

4 性能分析和实验仿真

4.1 功能特性比较

将本文方案与文献[8,11-13]方案进行对比，如表2所示。文献[11-13]都是基于关键字的可搜索加密，但不支持任何表达式的访问策略。与文献[8]相比，本文方案对不同文件分配不同加密密钥，采用聚合密钥方式对密文解密。

表2 功能对比Table 2 Functional Comparison

4.2 理论分析

将本文方案与现有方案在系统初始化、密钥生成、索引生成、陷门生成4个方面进行计算量对比，结果如表3所示。分别表示G、GT、ZP元素的长度，分别用|S|、|X|、 |N|表示用户的属性集、数据拥有者的属性集和系统总属性集。L表示陷门中搜索关键字的数量，W表示关键字密文中关键字的数量。由表3可知，本文方案与文献[12]方案计算开销代价基本相同，优于文献[11]方案和文献[8]方案；但在系统初始化方面，计算量略高于文献[13]方案。

表3 计算量对比Table 3 Comparison of the calculated quantities

4.3 实验分析

本文实验是基于Linux系统，在8 GB的内存，4核处理器下运行。采用Python语言，利用pbc等密码学工具库进行编程，实验使用的双线性对包是基于512 bit椭圆曲线群，G和GT中元素的大小是128 byte。实验对比了3个方案的两个主要算法（密钥生成、关键字加密）的计算开销，结果如图2所示。此外，固定属性个数为20个，通过改变关键字个数，对比索引生成阶段和搜索阶段的计算开销，结果如图3所示。本文方案效率高于文献[13]方案和文献[8]方案。在文件加密方面，与不采用聚合密钥方式加解密文件相比，本文方案效率较高，结果如图4所示。

图2 密钥生成阶段和关键字加密阶段计算开销 Figure 2 The key generation phase and the keyword encryption phase calculation overhead

图3 索引生成阶段和搜索阶段计算开销 Figure 3 Index generation phase and search phase calculation overhead

图4 无聚合密钥与本文方案(聚合密钥)计算开销 Figure 4 No aggregate key and the present scheme (aggregate key) calculation overhead

5 结束语

本文提出了云环境下基于属性策略隐藏的可搜索加密方案。本文方案采用搜索、访问控制与文件加密三者相结合的思想，利用LSSS技术实现访问控制，并将策略进行隐藏，保护了用户和数据拥有者的隐私。云服务器将聚合密钥发送给用户，数据拥有者无须与用户交互，用户端减轻了密钥管理的负担，同时，给出了安全性证明和性能分析。实验结果表明，本文方案有效地提高了密文检索效率。