一种云存储环境下基于隐私保护的可搜索加密方法

摘要

本发明公开了一种云存储环境下基于隐私保护的可搜索加密方法，令L＝{li|1≤i≤card(L)}表示IBS‑SSE的系统模型中所有的card(L)种用户身份类型，每个数据使用者均属于其中一种身份类型，1≤x≤card(L)；对于文档F，若文档所有者指定可访问文档F的数据使用者的身份类型属于基数为x的集合则通过布鲁姆过滤器的h个独立的哈希函数HASH＝{H1,H2,...Hh}将中的x个元素映射至长度为q的位串向量P中，P即为绑定于文档F的访问控制策略；当某个数据使用者想访问F时，访问控制的执行者通过布鲁姆过滤器、根据P判断该数据使用者的身份类型l是否属于授权集合若属于则匹配成功，不属于则匹配失败。本发明解决了现有对称可搜索加密方案难以高效、安全地适用于多源数据用户模型并针对多类型数据使用者进行访问控制的问题。

说明书

技术领域

本发明涉及一种云存储环境下基于隐私保护的可搜索加密方法。

背景技术

随着网络带宽的增加及移动互联网的普及，云存储良好的灵活性与经济节约性吸引了个体与企业的目光，让他们将本地复杂的数据管理系统外包给云。云存储已经成为云计算最广泛的应用之一，Dropbox、Google Drive、金山快盘、微盘等公用云存储应用的用户数量飞速增长(其中Dropbox的用户数量已突破5亿)，Eucalyptus、3A Cloud、minicloud等平台也正在为越来越多的企业提供安全办公私有云。云存储用户能够在不同的地方，利用不同的终端(如台式电脑、笔记本电脑、平板电脑、智能手机等)访问数据，云存储为这些设备间共享数据提供了一种最适合的解决方案。

然而，由于数据所有权和管理权的分离，一些数据安全的隐患亦随之涌现，云用户对云存储服务提供商的不信任已成为云存储在推广途上的重要制约因素。在云存储模式下，用户的数据(包括政府和公司的财政数据、个人的医疗信息、邮件、相册、金融交易等敏感数据)完全由云服务提供商(Cloud Service Provider，CSP)进行管理和存储。CSP可以获取、搜索用户存储在云端的敏感数据；由于系统故障，CSP可能丢失用户的数据；攻击者也可能通过攻击CSP的服务器获取用户的数据导致信息泄露。这些安全隐患使得云存储的安全性成为一个不容忽视的问题。

为了保护数据隐私，在将数据上传到CSP之前，必须由数据所有者对之进行加密。然而，这无疑使得一些传统的基于明文关键词搜索的数据使用服务无法正常进行。有一种解决方案是下载所有数据并在本地解密，然而由于在云系统中将产生巨大的带宽成本，该方案显然是不实际的。再者，把减轻本地存储管理负担暂且放在一边，如果不能方便快捷地搜索、利用和共享数据，那么将数据存储到云端将是没有意义的。因此，为加密云数据探索有效率且保证其隐私安全的可搜索加密方案是不容忽视且十分具有现实意义的。考虑到云端潜在的大量用户与外包数据，要同时满足私密性、系统可用性、可扩展性和高效率的要求，这个研究课题将是极其困难、极其具有挑战性的。

典型的具备隐私保护功能的密文搜索系统包括数据所有者、数据使用者和CSP三个参与者。通常采用AES(Advanced Encryption Standard)之类的密码算法来加密数据，采用特制的可搜索加密方案生成安全索引。可搜索加密方案主要包括两类：基于对称密钥的可搜索加密(Searchable Symmetric Encryption，SSE)和基于非对称密钥的可搜索加密(Searchable Asymmetric Encryption，SAE)。

对称可搜索加密方案的基本模式是数据所有者与数据使用者共享无差别的密钥。对单一关键词的可搜索加密通常会建立一个加密的可搜索索引，对服务器隐藏索引内容，除非服务器得到了适当的由密钥生成的陷门。这类方案由Song等人首次提出，他们用一种特殊的双层结构加密方法一一加密文档中的每个单词，搜索密文时需遍历整个文档来确认是否存在所求关键词，如此一来搜索效率是比较低下的。之后，Goh,Chang和Curtmola等人为SSE给出了更深入的安全定义。Goh提出的方案采用伪随机函数(PseudorandomFunction)和布鲁姆过滤器(Bloom Filter)为每个文档构建一个安全索引，搜索时间与文档数量成正比，但由于Bloom Filter而导致的误差使得搜索结果的正确性不够完全。Chang等人和Curtmola等人几乎于同一时间提出了采用伪随机技术为关键词生成索引、为用户生成查询请求的方案，提高了搜索效率，但方案对数据的更新支持不足，需极大计算量进行更新，甚至可能重构全部索引。之后，Kamara等人提出了可支持文档更新的密文检索方法。Wang等人研究了支持安全排名的关键词搜索问题，利用反向索引(Inverted Index)和保序加密(Order Preserving Encryption)技术加密文档内的关键词频率，按关键词频来排序搜索结果，而不是返回无差别的结果。近来，Naveed等人提出的一种基于盲存储(BlindStorage)机制的可搜索加密方案能够大大提升搜索效率，更重要的是，盲存储的运用使得数据使用者的搜索模式(Access Pattern)得以隐藏，这是绝大部分已有方案无法实现的。Cao等人为各文档构建索引向量，采用矩阵加密并通过查询后向量内积值的大小来进行加密数据的多关键词搜索，并将查询结果中的前n个文档返回，但由于需遍历所有文档，搜索效率和搜索精确度较低。

非对称可搜索加密方案的基本模式是任何持有公共密钥的人都能够写入存储于服务器的数据，但只有持私钥的授权用户方可进行密文搜索。Boneh等人首先提出了基于非对称密钥的可搜索加密方案，后Abdalla等人对SAE进行了改进。再之后，布尔关键词查询、子集查询、范围查询等可搜索加密技术相继出现。Kerschbaum等人提出了基于身份加密的非对称可搜索加密技术。Lin等人减少了在非对称密钥可搜索加密方案中不可避免的双线性对的使用，提出了支持单一关键词搜索、适用于网络鉴证的密文搜索方案。Hwang等人提出了满足固定关键词(非自由)并集查询的可搜索加密方案并允许服务器通过用户列表控制搜索权限，该方案可适用于企业环境下的多用户场景，遗憾的是可扩展性较低，当应对大量用户时效率将大幅下降。Li等人采用谓词加密提出了满足多用户场景并可授权的非对称可搜索加密方案，然而该方案中数据使用者的查询请求需由可信第三方生成，效率不高。Sun等人首次提出了一种基于属性加密技术的授权可搜索加密方案，数据所有者采用访问控制策略生成索引，只有当数据使用者的陷门所暗示的使用者属性满足索引所包含的访问策略且该索引对应于使用者所搜索的关键词时，才能访问目标文档。该方案同时支持单一关键词与固定多关键词的并集搜索，可扩展性较强。

综上可知，现有的对称可搜索加密技术效率较高，可满足对多关键词的自由查询，但由于对称加密的密钥共享性，传统的基于对称密钥实现的可搜索加密大多不支持复杂的多用户场景，在用户数量庞大且有访问控制需求的情况下所暴露的灵活性与可扩展性较低的问题，导致了其应用情境的局限性。相对地，非对称可搜索加密技术更适用于复杂的多用户模型，且能够利用双线性对(Bilinear Paring)计算被表示为关键字向量的范围数据来实现对称加密普遍难以支持的密文数据范围搜索功能，然而也正是因为对双线性对不可避免的使用，导致了搜索效率低下的问题，加之大部分方案无法满足多关键词的自由查询，亦影响了该类方案的实际应用。总而言之，现有研究缺少在“多数据所有者-多数据使用者”这一复杂用户模型下同时对复杂查询条件、密文数据更新以及访问控制的支持，或实现成本过高，效率与可用性偏低。

发明内容

本发明所要解决的技术问题是，针对现有技术不足，提供一种云存储环境下基于隐私保护的可搜索加密方法。

为解决上述技术问题，本发明所采用的技术方案是：一种云存储环境下基于隐私保护的可搜索加密方法，该方法主要实现过程如下：令L＝{l_i|1≤i≤card(L)}表示IBS-SSE的系统模型中所有的card(L)种用户身份类型，card(L)表示集合L的基数；每个数据使用者均属于其中一种身份类型，1≤x≤card(L)；对于文档F，若文档所有者指定可访问文档F的数据使用者的身份类型属于基数为x的集合则通过布鲁姆过滤器的h个独立的哈希函数HASH＝{H₁,H₂,...H_h}将中的x个元素映射至长度为q的位串向量P中，P即为绑定于文档F的访问控制策略，P随F的标识符一起写入索引文档并存入IBS-SSE系统模型中；当某个数据使用者想访问F时，访问控制的执行者在获取到F相关的索引文档后，通过布鲁姆过滤器、根据P判断该数据使用者的身份类型l是否属于授权集合若属于则匹配成功，不属于则匹配失败。

访问控制策略P的生成过程包括：首先建立一个长度为q的位串向量P，并将位串向量P各位的值初始化为0；对于任一元素利用哈希函数组HASH中的每个函数一一对l_i进行哈希并得到h个哈希地址H₁(l_i)，H₂(l_i)，...H_h(l_i)，根据这h个地址更新布鲁姆过滤器向量，令布鲁姆过滤器向量这些位置的值由0改置为1，最终返回更新成功的布鲁姆过滤器向量作为访问控制策略；

访问控制匹配的具体实现过程包括：首先生成整型数flag＝0，对于访问者的身份类型l，利用哈希函数组HASH中的每个函数一一对身份类型进行哈希并得到h个哈希地址H₁(l)，H₂(l)，...H_h(l)；逐一检查向量P中由这些地址索引到的位值，若值为1，则flag+＝1；若值为0，则匹配失败。最终，若flag＝h，则匹配成功。

文档包含文档标识符ID、文档属性组合内容和文档普通内容f，文档属性组合的维度记为Dim＝n+m，由Dim个属性域构成且每个属性域均包含一个属性值，其中r_k代表范围类属性R_k的属性值，w_y则代表关键词类属性W_y的属性值；令|R_k|表示R_k域所有可能的属性值数目，|W_y|表示W_y字段所有可能的属性值数目，那么在文档集合FILE中，令Α为所有文档属性组合的集合，则Α的基数为card(Α)＝|R₁|×|R₂|×...×|R_n|×|W₁|×|W₂|×...×|W_m|；其中，1≤k≤n；1≤y≤n。

获取F相关的索引文档的具体过程包括：

1)在接收到来自数据使用方的访问陷门Q描述了数据使用者的数据搜索条件，其中描述了数据使用者对目标文档各个属性域值的不同要求，UID则表明了访问请求者的身份，具体地，D_R描述了对一个范围类属性的值的要求，它可以是一个数值或一个数值范围；而D_W描述了对一个关键词类属性的值的要求，它可以是任意数目的关键词。当数据使用者以[r_x1,r_x2](r_x1≤r_x2)定义属性字段R_x时，利用保序变换函数X对作变换可得其加密形式当数据使用者以z个关键词定义属性字段W_x时，利用全域伪随机函数Ψ对进行加密可得其加密形式)之后，访问控制的执行者CA会根据Q在二维查询表中查询符合条件的索引文档标识符(IID)s，并由所有相应的元组(addr)s组合生成子集由S_Q索引到的数据块总数记为size_Q；当Q中的范围类属性域条件至少有一个非空时，选出给定范围值域最小的属性R_min，1≤min≤n；CA根据给定的最小数值范围定位按R_min排序的二维查询表T_min中满足的元组，在再利用进行其他属性域的匹配；当Q中的范围类属性域条件全部为空时，则直接利用来对二维查询表集T中任一张表的元组进行匹配；

2)得出S_Q后，CA选择一个随机数τ并生成一个伪随机整型数列V←Γ(τ)，以V的前β·size_Q个不同的整型数组成伪随机子集V_Q是为访问陷门Q的访问操作准备的混淆子集；Γ为伪随机数生成器；n_B＝α·b_max；α和β分别是IBS的扩展因子和混淆因子，b_max是数组B中可供存储的数据块数目上限。

3)CA将由S_Q和V_Q索引到的数据块打乱并共同下载至本地，利用解密由S_Q索引到的数据块并恢复出相应的索引文档；B[i]为B中的第i个数据块，B为含有n_B＝α·b_max个数据块的数组；Φ是伪随机函数，K_Φ是用于Φ的密钥，v_i是第i个数据块的版本号，即利用Φ和K_Φ对字符串(v_i||i)作伪随机处理。

4)在恢复出标识符为(IID)s的索引文档后，CA根据(IID)s遍历中转站列表FS，若FS中存在对某份索引文档的更新请求，则先对之进行更新，清除该条请求，再将更新后的索引文档作为相应的索引文档；

5)当需要添加新的索引文档时，先检查待添加的索引文档标识符是否已存在于T中，若存在，则执行写入操作；若不存在，则按下述步骤添加索引文档：

5a)将索引文档集IND、数据块数目上限b_max、二维查询表集T和K_IBS作为输入，将索引文档集IND中的每份索引文档I_i拆分为size_i个数据块，当索引文档I_i的总字节长度length_i不能被ω整除时，前length_i/ω个数据块大小为ω，最后一个大小不足ω的数据块由0s填充至ω，所有数据块均包含两个头字段，其中一个负责记录IID_i，另一个则负责记录I_i的版本号v_i，v_i初始化为0；

5b)令B为含有n_B＝α·b_max个数据块的数组并将B中所有数据块初始化为0s，对IND中的每个索引文档I_i，以σ＝IID_i为种子，生成一个整型数序列S←Γ(σ)，从序列S的开头起选择size_i个不同的整型数，并确保由这些整型数索引到的B中的数据块均为空；以表示由σ和伪随机数生成器Γ生成的前个整型数，创建一个伪随机子集S_i＝Λ[σ,size_i]；

5c)按升序将由I_i拆分而成的size_i个数据块写入由S_i索引到的B中的数据块，这些数据块被标记为非空；

5d)将二维查询表集T中与I_i相对应的元组的addr_i字段更新为S_i；

5e)利用伪随机函数Φ将B中的所有数据块进行加密。

与现有技术相比，本发明所具有的有益效果为：本发明解决了现有对称可搜索加密方案难以实现同时支持任意多维关键词查询与范围查询的复杂条件搜索的问题；解决了现有对称可搜索加密方案难以高效、安全地适用于多源数据用户模型并针对多类型数据使用者进行访问控制的问题。

附图说明

图1为本发明一实施例的数据上传模型；

图2为本发明一实施例的数据搜索(访问)模型；

图3为BS与IBS不同的索引存储模型；

图4为本发明IBS方案在数据搜索阶段的关键操作流程；

图5为在属性维度固定时，数据集建立索引实验结果图；

图6为当以同一查询陷门Q发起搜索请求时，索引获取的计算开销与数据集大小的关系；

图7为当数据集文档的属性维度固定为Dim＝9时，以不同的陷门Q₁、Q₂与Q₃对不同大小的数据集进行搜索时的计算时间开销；

图8为当数据集属性维度为Dim＝9时，在一次索引获取操作中更新一份索引文档所需的时间开销占索引获取操作的总开销的比重；

图9展示了在不同属性维度和数据量的数据集下完成一次访问控制匹配的时间；

图10展示了添加一份文档的计算时间开销与数据集属性维度和数据量之间的关系。

具体实施方式

IBS-SSE的系统模型由四个实体组成：数据所有者、数据使用者、权威中心机构CA以及云服务提供商CSP，图1和图2分别展示了该方案的数据上传模型和数据搜索(访问)模型。IBS-SSE主要由IBS-SSE.Setup，IBS-SSE.IndexGen，IBS-SSE.Enc，IBS-SSE.Trapdoor，IBS-SSE.Search，IBS-SSE.Dec和IBS-SSE.AddUser，IBS-SSE.AddDoc八个多项式时间算法组成。为了在多源数据用户模型下同时高效安全地实现复杂条件搜索和用户访问控制，本发明设计并在这些主要算法中采用了两个关键技术：索引盲存储IBS(Index BlindStorage)及密文相关的用户身份访问控制方法，本发明将首先介绍这两种关键技术，再阐述IBS-SSE的算法定义。

1.IBS存储机制

IBS是受到盲存储机制BS的启发，为索引文档而非文档本身的存储管理设计的，致力于为基于IBS建立的可搜索加密方案提供包括任意多维关键词查询和范围查询在内的复杂条件搜索的加密存储机制。为实现这一目标，本发明对BS的架构与算法实现细节进行了修改，采用了一系列伪随机函数，并引入了由MySQL实现的二维查询表集合T、访问陷门Q、混淆因子β和中转站列表FS。IBS由三个运行于CA端的多项式时间算法构成(与BS原方案不同，为了适应企业类环境中“多所有者-多使用者”的复杂用户模型，在IBS中，这些算法的主要执行方与相关参数选择方由数据所有者本身的客户端更改为权威中心机构CA的客户端，由CA端为来自多数据所有者的数据统一建立索引并处理来自多数据使用者的数据搜索请求，图3展示了BS与IBS不同的索引存储模型。

IBS.KeyGen(λ)：

密钥生成算法将安全系数λ作为输入，为伪随机函数PRF输出密钥K_Φ，为全域伪随机函数FD-PRF输出密钥K_Ψ。最终输出K_IBS＝(K_Φ，K_Ψ)并将K_IBS保存于CA客户端。

IBS.Initial(IND,b_max,T,K_IBS)：

初始化算法将索引文档集IND、数据块数目上限b_max、二维查询表集T和K_IBS作为输入。将索引文档集IND中的每份索引文档I_i拆分为size_i个数据块，每个数据块的大小均为ω，size_i的计算方法如下：

$>{\mathrm{size}}_i=\left\{\begin{array}{cc}{\mathrm{length}}_i/\omega & \left(\begin{array}{cccc}if& {\mathrm{length}}_i& \mathrm{mod}& \omega =0\end{array}\right)\\ ({\mathrm{length}}_i/\omega )+1& \left(\begin{array}{cccc}if& {\mathrm{length}}_i& \mathrm{mod}& \omega \ne 0\end{array}\right)\end{array}\right\}$>

当索引文档I_i的总字节长度length_i不能被ω整除时，前length_i/ω个数据块大小为ω，最后一个大小不足ω的数据块由0s填充至ω。所有数据块均包含两个头字段，其中一个负责记录IID_i，另一个则负责记录I_i的版本号v_i，v_i初始化为0。

令B为含有n_B＝α·b_max个数据块的数组并将B中所有数据块初始化为0s。对IND中的每个索引文档I_i执行以下操作：

(1)以σ＝IID_i为种子，生成一个足够长的整型数序列S←Γ(σ)，从序列S的开头起选择size_i个不同的整型数，并确保由这些整型数索引到的B中的数据块均为空。以表示由σ和伪随机数生成器Γ生成的前个这样的整型数，创建一个伪随机子集S_i＝Λ[σ,size_i]。

(2)按升序将由I_i拆分而成的size_i个数据块写入由S_i索引到的B中的数据块，这些块被标记为非空。

(3)将二维查询表集T中与I_i相对应的元组的addr_i字段更新为S_i。

之后，CA利用伪随机函数Φ将B中的所有数据块进行加密，并将加密后的B发送至CSP。对B中的第i个数据块而言，其加密形式为

IBS.Access(Q,op,T,K_IBS)：

数据访问算法将访问陷门Q、操作说明符op、二维查询表集T以及K_IBS作为输入。在所有文档操作op∈{read,write,alter,delete}中，写入操作write、修改操作alter和删除操作delete均通过延时懒惰更新方法附着于读操作read中，以减缓CA的运行负担。

(1)在接收到来自数据使用方的之后，CA会根据Q在二维查询表中查询符合条件的(IID)s并由所有相应的(addr)s组合生成子集可由S_Q索引到的数据块总数记为size_Q。具体地，当Q中的范围类属性域条件至少有一个非空时，选出给定范围值域最小的属性R_min(1≤min≤n)，由于T_min中元组是根据属性值按升序排列的，CA即可根据给定的最小数值范围快速定位T_min中满足的元组，接着在减少了元组查询范围的前提下，再利用进行其他属性域的匹配；当Q中的范围类属性域条件全部为空时，则直接利用来对T中任一张表的元组进行匹配。此阶段的匹配操作主要由MySQL完成。

(2)在得出S_Q后，CA选择一个随机数τ并生成一个足够长的伪随机整型数列V←Γ(τ)。以V的前β·size_Q个不同的整型数组成伪随机子集V_Q是为陷门Q的访问操作准备的混淆子集。

(3)CA将由S_Q和V_Q索引到的数据块打乱并共同下载至本地，利用解密由S_Q索引到的数据块并恢复出相应的索引文档。

(4)在恢复出标识符为(IID)s的索引文档后，CA会根据(IID)s遍历中转站列表FS。若FS中存在对某份索引文档的更新请求，则先对之进行更新，清除该条请求，再将更新后的索引文档投入接下来的任务中。在对I_i的写入操作write中会碰到两种情况：

(a)若更新后I_i'的数据块数目size_i'与更新前一致，CA只需将待写入的数据data_new写入I_i的最后一个数据块，令I_i的所有数据块版本号v_i＝v_i+1，然后加密这些数据块并与混淆块一同返送回B以完成更新。

(b)若更新后I_i'的数据块数目size_i'大于更新前的CA则需要计算子集从B处取回由S_new索引到的空数据块和(β-1)·(size_i'-size_i)个混淆数据块(S_new的生成方法见IBS.Initial步骤1)。将S_wen与S_i合并得到S_i'＝S_i∨S_new，在完成数据的写入、版本号的更新和数据块的加密后将属于I_i'的数据块连同混淆块一同返送回B。最后，将I_i在T中的addr_i字段更新为S_i'。

修改操作alter与删除操作delete的实现步骤和写入操作write基本一致，区别只在于更新内容的不同(删除操作将数据块内容用0s替换并标记为空)。图4展示了IBS方案在数据搜索这一阶段的关键操作流程。

另外，当需要添加新的索引文档时，只需先检查待添加的索引文档标识符是否已存在于T中。若存在，则执行写入操作write；若不存在，则按IBS.Initial的步骤添加索引文档即可(需要注意的是，执行初始化算法时B在本地，而之后再添加文档I_i时B已存储在CSP，此时需计算S←Γ(IID_i)并从S中确定长度为size_i的子集和长度为α·size_i的子集从B中下载由索引的数据块回本地，再用待添加的数据对由S_i索引的块进行覆盖)。

2.密文相关的用户身份访问控制方法

在基于IBS-SSE的系统设计会涉及到不同身份类型的数据使用者，数据所有者有权为其文档指定访问控制策略。本发明为此设计一个简易的密文策略相关的用户身份访问控制方法，该方法主要以布鲁姆过滤器(Bloom Filter)为实现的核心。令L＝{l_i|1≤i≤card(L)}表示IBS-SSE的系统模型中所有的card(L)种用户身份类型，每个数据使用者均属于其中一种身份类型。对于文档F，若文档所有者指定可访问该文档的数据使用者的身份类型属于基数为x(1≤x≤card(L))的集合则通过布鲁姆过滤器的h个独立的哈希函数HASH＝{H₁,H₂,...H_h}将中的x个元素映射至长度为q的位串向量P中，P即为绑定于文档F的访问控制策略，将随F的标识符一起写入索引文档并存入IBS。当某个数据使用者想访问F时，访问控制的执行者CA在运行IBS.Access获取到F相关的索引文档后，会通过布鲁姆过滤器、根据P判断该数据使用者的身份类型l是否属于授权集合若属于则匹配成功，不属于则匹配失败。访问控制策略P的生成和访问控制匹配的具体实现方法分别如算法1、算法2所示：

3.IBS-SSE方案

动态对称可搜索加密方案IBS-SSE主要由以下8个多项式时间算法组成，通过它们与盲目的服务器进行交互。本方案采用索引盲存储机制IBS进行索引文档的存储与管理，通过它实现复杂条件的搜索。

IBS-SSE.Setup：运行于CA端。将安全参数作为输入，为方案中所有密码学原语输出密钥K_SSE；创建用户列表，为已有用户分配用户ID并制定身份类型。

IBS-SSE.IndexGen：运行于CA端。将一个文档集合和其内所有可能的文档属性组合作为输入，为每份文档分配文档标识符并按密文相关的用户身份访问控制方法生成访问控制策略；生成索引文档集合并以IBS.Initial算法初始化IBS机制来处理索引文档。

IBS-SSE.Enc：可能运行于CA端或用户端。将需添加的文档进行加密并发送至CSP；同时将该文档的标识符、文档属性和访问控制策略发送至CA以更新索引(当运行于用户端时)。

IBS-SSE.Trapdoor：运行于用户端。访问者利用搜索条件和本人身份生成搜索陷门Q并将Q发送给CA。

IBS-SSE.Search：运行于CA端。CA收到Q后运行IBS.Access算法以获取与搜索条件对应的索引文档，并根据访问控制方法对访问者身份和目标文档进行授权匹配，最终要求CSP返回匹配成功的目标文档。

IBS-SSE.Dec：运行于用户端。以密文作为输入，解密并还原出文档明文。

IBS-SSE.AddUser：运行于CA端。首先检查新用户是否已存在与用户列表中，若无，则为其分配用户ID并指定身份类型。

IBS-SSE.AddDoc：运行于用户端和CA端。其中用户端负责加密和上传新文档，并将新文档的标识符、文档属性和访问控制策略告知CA；CA端负责根据所得信息更新索引。

相比现有的对称可搜索加密方案，第一，本发明提供了包括任意多维关键词查询与范围查询在内的复杂条件搜索，改善了现有方案搜索条件单一的缺陷；第二，在保证搜索与其他关键操作的高效率的同时，展现了应对大量数据的高可扩展性；第三，能够适用于“多数据所有者-多数据使用者”的复杂应用模型，保证数据内容、搜索陷门以及用户身份的私密性，隐藏数据访问接入模式，并允许数据所有者指定访问授权策略。

这里主要通过功能性对比和实验数据来证明本技术的优点。实验在运行Windows7操作系统、配备Intel Core i5-3210M处理器和4G内存的笔记本电脑上实现，代码由Java语言、SQL语言和开源库编写，其中Crypto++应用于分组密码(AES)和耐撞击哈希函数(SHA256)的实现。

表1给出了本发明提出的IBS-SSE方案、Naveed等人提出的BSTORE-SSE^[11]方案和Li等人提出的EMRS方案^[56]间的功能性对比。这三个方案均是基于盲存储机制设计的。BSTORE-SSE通过盲存储的运用隐藏了接入模式，但该方案只允许单一关键词搜索，因此难以满足实际应用中多样化的搜索需求。在BSTORE-SSE的基础上，EMRS实现了多关键词的排名搜索和访问控制，但该方案与前者均无法满足多数据所有者(即多数据来源)的应用情境。汲取了Naveed等人方案的精华，本发明所提出的IBS-SSE方案不但向CSP隐藏了接入模式，还实现了包括任意多维关键词查询和范围查询在内的复杂条件搜索。此外，以IBS-SSE建立的EMRM系统能够灵活适用于“多所有者-多使用者”的用户模型，并提供解决不同类型用户的访问需求和隐私需求的访问控制方法。

表1

接下来通过实验结果，就索引建立、搜索访问和文档添加三部分对IBS-SSE进行评估。在实验中：令α＝β＝4以保证IBS机制在数组B中已被占用的数据块数目少于n_B/4的情况下意外中止的可能性p_err≤2^-40；令哈希函数组HASH的函数个数h＝7，以保证在card(L)＝3和向量P的长度为32位的情况下访问控制方法中布鲁姆过滤器的误判概率最小。实验分别在文档属性维度为Dim＝3、Dim＝6、Dim＝9的数据集上进行，并从这三类数据集中分别取128MB、256MB、512MB、1G、2G的子集来测量计算开销，令n_B＝2×10⁴。

1.索引建立：

索引建立阶段的性能测量涵盖了IBS-SSE.IndexGen算法中除明文索引生成(含步骤(1))之外的全部操作，主要包括索引文档命名和IBS.Initial算法(包括索引分块、二维查询表写入与数据块加密)。明文索引的生成与可搜索加密方案的索引生成性能无关，且所有其他相关研究工作都默认忽视该操作。在这一阶段，索引文档命名耗时较少，时间复杂度为O(card(Α))，只与数据集属性组合数目(即索引文档个数)线性相关；IBS.Initial(IND,T,K_IBS)占据了大部分计算开销，其时间复杂度可记为O(card(Α)+n_B)，只与数据集属性组合数目card(Α)和B的长度n_B相关，而与数据集的数据量无关。图5验证了这一点：card(Α)随文档属性维度Dim的增加成倍增长，索引建立时长随card(Α)的增加线性增长；当card(Α)一定而数据集大小不同时，索引建立时长基本一致，如图所示，当Dim＝6时，索引建立所需时间基本维持在13s～15s之间。可见，在属性维度固定时，本方案能够以稳定的时长为不同量级数据集建立索引。

2.搜索访问：

搜索访问阶段主要包含索引获取和访问控制两个主要操作(注意此处只考虑Situation-1的操作，因为Situation-2中的文档获取操作与本发明关注的搜索性能无关，且其时间开销相对而言可忽略不计)。

索引获取操作中包括了陷门的生成和索引的搜索还原(含更新)：前者由IBS-SSE.Trapdoor完成，时间复杂度为O(Dim)，后者主要由IBS.Access算法完成，两者均不受数据集大小影响。图6展示了当以同一查询陷门Q(含多维关键词查询和范围查询条件)发起搜索请求时，索引获取的计算开销与数据集大小无关，受属性维度影响亦甚微。另外，就本发明所知，关于支持任意多维关键词查询和范围查询的复杂条件可搜索加密方案的实验结果十分有限，对比功能类似的APKS方案，当Dim＝9且索引数目一致时，APKS需要42s来完成索引搜索而IBS-SSE只需0.5s(且IBS-SSE还计入了陷门生成、索引还原与更新的开销)。因此，当Q固定时，本方案在搜索不同数据量大小与属性维度的数据集时展现出了高可扩展性和高效率性。

图7展示了当数据集文档的属性维度固定为Dim＝9时，以不同的陷门Q₁、Q₂与Q₃对不同大小的数据集进行搜索时的计算时间开销，其中描述于Q₁的、Q₂和Q₃的搜索条件分别为：如图所示，当搜索条件一定而数据集大小不同时，索引获取的时间开销基本一致；当搜索条件不同而数据集大小相同时，索引获取的时间开销亦维持在0.5s左右。因此，在属性维度固定时，本方案能够以稳定的效率在不同大小的数据集上根据不同的Q完成搜索。

由于IBS.Access中采用的延时懒惰更新方法，索引获取阶段还需承担索引更新的计算开销。在本方案中，索引更新所耗时长只与待处理的相应更新请求数目相关。图8展示了当数据集属性维度为Dim＝9时，在一次索引获取操作中更新一份索引文档(添加一行数据)所需的时间开销占索引获取操作的总开销的比重，可见更新操作占比很少且不随数据集大小变化，基本不会影响索引获取的时间开销。

还原索引文档后，文档的需要按访问控制方法完成授权匹配。图9展示了在不同属性维度和数据量的数据集下完成一次访问控制匹配的时间，由匹配总时长除以匹配文档总数所得，所耗计算开销几近于0，可忽略不计。

3.文档添加：

当向数据集添加一份文档F_new时，数据上传方需要为F_new分配FID_new、生成用于更新请求的陷门并通过访问控制方法制定访问授权策略P_new，CA需要将待更新内容写入FS列表，所需计算量与数据集本身数据量无关。图10展示了添加一份文档的计算时间开销与数据集属性维度和数据量之间的关系，可见文档添加操作耗时不受数据集本身大小的影响，受属性维度的影响亦甚微，基本维持于0.2s附近。

基于IBS存储机制设计的对称可搜索加密方案IBS-SSE可由Java语言结合SQL语言完成代码实现。以目标存储文档为电子病历数据集FILE的情况为例，组成FILE的文档的结构示例如表1所示，可以以xml的文件格式呈现，其中是可共享内容，f代表病历内容，代表病历属性内容；是文档所有者的隐私身份信息，只有所有者本人和授权的数据使用者才能在特定的安全机制下进行访问。Α是FILE内所有可能的属性组合的集合，由Dim＝n+m共Dim维属性域构成且每个属性域均包含一个属性值。其中r_x代表范围类属性R_x的属性值，范围类属性通常指代诸如“年龄”、“日期”等属性值可按顺序排列的数值型属性；w_x则代表关键词类属性W_x的属性值，关键词类属性通常指代诸如“性别”、“职位”等字符型属性。F的属性维度可自由扩展，下文为简化表述，暂令F由三维属性域构成，则其中r为属性域R(表示“年龄”)的属性值，w₁和w₂分别为属性域W₁(表示“性别”)和属性域W₂(表示“疾病类型”)的属性值，此时card(Α)＝|R|×|W₁|×|W₂|。

表1

从数据访问者的身份与数据访问目的的角度考虑，在IBS-SSE.Trapdoor、IBS-SSE.Search等算法阶段将存在两种数据访问情境：令Situation-1表示数据访问者U_i为出于合法理由需要根据特定查询条件搜索数据的个人或机构而非数据所有者本人的情境，令Situation-2表示数据访问者U_i为数据所有者本人或被授权直接获取数据者的情境。IBS-SSE主要算法的具体实施方式如下：

IBS-SSE.Setup(λ)：

在系统建立阶段，CA以安全系数λ作为输入。

(1)利用Crypto++开源库为系统将用到的密码学原语生成密钥K_SSE＝K_IBS。

(2)根据已知用户集合创建用户列表UL，列表长度记为|UL|。UL中的第i个节点代表用户U_i＝＜UID_i,UN_i,BI_i,TS_i,ε_i＞，其中UID_i被设为U_i的用户ID，UN_i为U_i的用户名，BI_i包括了U_i的基本信息(包括姓名、年龄、地址、联系方式、工作等)，TS_i是在U_i每次生成并上传新文档的时间表，ε_i是属于U_i的随机因子。UID_i通过对U_i唯一的身份证件号码id_i作全域耐撞击哈希变换Η后与l串联生成，方式如下：

s_i←H(id_i)>

UID_i＝＜s_i||l＞(2)

s_i是id_i的转化形式(此处以长度为|s_i|的字符串表示)，l∈L是标识U_i用户身份类型的字符。

(3)将<UID_i,TS_i,ε_i>发送给用户U_i。

UID_i将作为用户在系统中的身份识别和加解密用户隐私身份数据的密钥，它只能由U_i本人持有(当然CA也需保存一份)。在实际应用中，UID_i可以通过扫描进行识别和使用，若条件允许，可利用指纹或虹膜等生物信息作为s_i来代替id_i生成UID_i，以此来加强安全性。

IBS-SSE.IndexGen(FILE，Α)：

索引生成算法将文档F的集合FILE与其所有可能的属性组合的集合Α作为输入，执行以下操作：

(1)为每一份文档F_j∈FILE按以下方式生成一个文档标识符FID_j：

$>{\mathrm{FID}}_j\leftarrow H\left(UID\right|\left|t\right)\oplus ϵ$>

其中UID是F_j所有者的用户ID，t是F_j的生成时间，ε是文档所有者专属的随机因子。同时，根据F_j所有者为其指定的访问权限，通过密文相关的用户身份访问控制方法生成访问策略P_j，P_j是一个32位的位串向量。

(2)为FILE初始化并建立索引文档集合IND和二维查询表T，算法3描述了建立过程：

对于任一创建一份索引文档I_i。将记为满足文档属性的所有文档标识符的集合。T＝{T_j|1≤j≤card(Α)}是一个将用于索引文档搜索的3列×card(Α)行的二维查询表集，每行元组均对应于一份索引文档I_i，可表示为其中包含I_i的标识符IID_i，经过保序变换后的第j个范围类属性域值以及记录由I_i所拆分而成的数据块在IBS中地址的字符串addr_i(初始化为空)。此处T简化为T＝{T}，其元组记为所有元组根据E_r的大小按升序排列。

(3)运行IBS.Initial(IND,T,K_IBS)以初始化IBS。

(4)将存入IBS的索引文档集合IND发送至CSP并将T保管于CA本地。由于在本方案中CSP只负责上传下载工作而不执行计算任务，因此CSP端可直接用诸如Dropbox等云存储应用实现。

IBS-SSE.Enc(FILE)：

加密阶段以文档集合FILE为输入。对任一文档按以下分区加密的方式进行加密：

$>{\mathrm{SE}}_{FID}\left(\stackrel{·}{F}\right)\to \stackrel{·}{C}$>

$>{\mathrm{SE}}_{UID}\left(\stackrel{··}{F}\right)\to \stackrel{··}{C}$>

后将发送并存储于CSP。

对可共享数据和身份隐私数据进行分区加密的方法为保护用户身份隐私并满足不同类型用户的访问需求奠定了基础。另外，此处使用了传统的对称加密算法AES来加密文档，还可以灵活地运用更复杂的加密机制(如BS)来寻求更高的安全性。

IBS-SSE.Trapdoor()：

(1)在Situation-1中，U_i应向CA提交搜索陷门其中描述了U_i对目标文档各属性域值的不同要求(即查询条件)，UID_i则表明了U_i身份。需要强调的是，为了确保对不同属性域的精确描述，的输入格式必须是固定的，但描述则可以十分灵活。具体来说，U_i可以为范围类属性指定一个数值或一个数值范围(例如将表示年龄的D_R设为“5”或“1～5”)，当数据使用者对属性域R_x的搜索条件为时，利用保序变换函数X对D_R作变换可得其加密形式可以为关键词类属性指定任意数目的关键词(例如将表示疾病类型的设为“感冒，发烧，咳嗽”或“低血糖”)，当数据使用者以z个关键词定义属性字段W_x时，利用全域伪随机函数Ψ对D_W进行加密可得其加密形式若对某个属性字段无特殊要求，允许属性值为空。若每个属性字段的值均为空，则目标文档为整个集合。

(2)在Situation-2中，数据所有者U_i可通过用户客户端本地信息获知目标文档的FID。具体来说，即利用UID_i、TS_i中的生成时间t与ε_i计算FID。

IBS-SSE.Search(Q,T,K_IBS)：

(1)在Situation-1中，CA将在收到来自U_i的搜索陷门Q后运行IBS.Access，用SQL进行查询，获取与Q中所描述搜索条件对应的索引文档并解密还原。接着，CA会通过访问控制方法对UID_i与索引文档中包含的所有(FID,P)s作访问授权匹配，并最终从CSP处请求返回匹配成功的FID所标识文档的密文数据块。

(2)在Situation-2中，U_i可直接根据FID向CSP请求返回目标文档的密文数据块。

IBS-SSE.Dec(C)：

解密算法以密文作为输入，U_i可通过获取F中的可共享部分。只有数据所有者与授权者可通过获取身份隐私部分。

IBS-SSE.AddUser(s',l',UN',BI',TS')：

在收到添加一位新用户的请求后，首先根据s'检查用户列表UL中是否已存在该用户。若无，CA则为新用户分配UID_|UL|+1＝<s'||l'>，并将U_|UL|+1＝<UID_|UL+1|,UN',BI',TS',ε'>挂入UL，|UL|＝|UL|+1。然后，告知新用户以<UID_|UL+1|,TS',ε'>。

IBS-SSE.AddDoc(F_new)：

(1)首先，数据上传方执行Enc算法并将加密后的F_new上传至CSP。同时，发送F_new的文档标识符、描述其属性与所有者身份的陷门和访问控制策略至CA端。

(2)CA需检查F_new的所有者是否已存在于用户列表UL中，若无，则转而先执行AddUser算法。

(3)CA适时调用算法以完成相关索引文档的更新。

本发明中相关参数符号的赋值说明如下表所示：