一种基于双线性映射的密文分享可搜索加密系统

Searchable Encryption System with Ciphertext Sharing Based on Bilinear Mapping

摘要

针对企业数据备份、云盘文件分享等云存储环境下安全准确高效的密文数据共享与搜索需求， 基于双线性映射方法设计一种支持密文索引分享的可搜索加密系统，采用计数器机制实现动态数据更新，通过重加密技术实现密文索引转换，数据拥有者可以使用分享票据实现细粒度的文件分享，数据使用者可以使用自己的私钥执行关键字搜索。在安全性证明方面，基于双线性（DBDH）假设难题证明方案的安全性，并对方案的复杂性进行分析。该方案在保持前向安全性的同时，实现细粒度的密文分享与搜索功能。

Abstract

To address the requirements for secure, accurate, and efficient ciphertext data sharing and searching in cloud storage environments for enterprise data backup and cloud file sharing, a searchable encryption system supporting ciphertext index sharing is proposed based on bilinear mapping. Dynamic data updates are achieved through a counter mechanism, while ciphertext index conversion is implemented via re-encryption techniques. Fine-grained file sharing is enabled for data owners through sharing tokens, and keyword searches can be executed by data users using their private keys. The scheme’s security is proven under the Decisional Bilinear Diffie-Hellman (DBDH) assumption, accompanied by a comprehensive complexity analysis. This solution ensures forward security while enabling fine-grained ciphertext sharing and searching capabilities.

Graphical abstract

关键词

云存储 / 可搜索对称加密 / 双线性映射 / 密文分享 / 重加密

Key words

cloud storage / searchable symmetric encryption / bilinear mapping / Ciphertext Sharing / re-encryption

在信息时代，由于本地数据规模的快速增长，越来越多的用户选择将数据上传到云端，以此减轻本地存储负担。云存储技术作为满足这一需求的核心手段，近几年来得到业界的广泛关注。然而，在大数据潮流下，云存储的大量应用也带来了另一个核心问题^[1]：如果企业或者用户直接将明文数据存储在云端，那么恶意服务器极有可能试图获取并破坏用户存储在云端的数据，侵犯用户的隐私。因此，基于安全性考虑，大部分用户和企业在将数据上传到云服务器前，通常使用密码学手段对明文数据进行加密，随后再将密文上传到云服务器进行存储，以此来保护数据的隐私性。可搜索加密技术^[2]的出现，实现了用户对云端密文数据的关键字检索功能。其基本原理^[3]是用户为指定的关键字生成搜索陷门并发送给服务器，服务器将搜索陷门和密文索引进行匹配，根据匹配结果返回相应密文数据。针对不同的应用场景，可搜索加密技术在密码体制上可以分为可搜索对称加密技术^[4]和公钥可搜索加密技术^[5]。其中，文献[6]于2012年首次正式提出了动态可搜索对称加密。

基于安全云存储技术，企业、组织和个人往往将大量重要敏感数据加密存储在云服务器中，加密数据的复制与分享成为云端数据使用全流程中的重要环节。这里列举两个典型场景：1）网盘文件分享。目前市面上百度网盘、腾讯微云等应用主要通过访问控制方式保护文件安全。此类应用提供了基于电子邮箱、分享链接等方式的文件转存功能，但上述转存工作通常在明文状态下进行，多数应用不支持对加密文件的分享和转存。对于隐形云和坚果云等数据加密存储的网盘类应用，由于未提供文件分享功能，用户想分享文件给其他用户，操作繁琐。2）商业数据备份。为了避免重要数据丢失、删除、损坏，企业通常会利用夜间或周末等用户数据低谷，使用数据复制技术对存储在服务器端的大规模重要数据进行备份。此举能够为企业提供有效的灾难恢复策略。此类云存储应用场景的关键是解决可搜索加密下的密文分享问题，从而实现安全、高效、准确的云端密文数据复制与分享。

针对此类问题，现有研究主要分为两类：1）基于密钥的分享。数据拥有者通过向数据使用者分享密钥，数据使用者可以在数据拥有者的加密数据库中进行关键字检索，即获得“查看”密文的能力。2013年，文献[7]提出了一种多密钥可搜索加密方案（Multi Key Searchable Encryption, MKSE），数据拥有者为每个文件使用单独的文件密钥进行加密，并通过转换密钥实现文件密钥与用户查询密钥的转换，向用户分享关键字搜索能力。由于MKSE需要使用预置密钥的方式为每个文件预先生成对应的转换密钥，因此存在冗余的密钥管理问题。之后的许多工作在MKSE方案的基础上进行了新的讨论，例如文献[8]提出了安全且可扩展的多方可搜索加密方案，文献[9]利用同态技术构造了通用的多密钥可搜索加密模型。2018年，文献[10]提出了一种针对MKSE的改进方案，在这个方案中，数据拥有者利用文件密钥加密数据，用户使用查询密钥生成关键字搜索陷门。与之前的MKSE相比，此方案在分享协议中额外增加了分享文件本身作为输入，以此可以提高分享的粒度。文献[11]提出了新的解决方案，使用混淆布隆过滤器对原方案进行了增强，使其满足结果的可验证性。文献[12]对MKSE方案中用户的分享和授权能力做了更严格的限定，实现了更高的分享安全等级。2）基于票据的分享。除了向数据使用者分享对密文索引的可搜索能力之外，数据拥有者还可以对可搜索密文索引进行分享和复制，数据使用者获得的是“使用”密文的能力。2023年，文献[13]提出了支持密文分享的关键字可搜索加密（Keyword Search Shareable Encryption, KS²E）。该工作首次提出了分享票据的概念，使用双向索引链表的方式构造可搜索密文索引结构，通过链式结构实现快速高效的密文分享和关键字检索。

针对以上问题，设计了一种支持密文索引分享的可搜索加密系统，基于双线性映射方法构造密文索引，采用基于票据的分享方式实现细粒度的文件分享，使被分享者保有使用自己的私钥对分享文件进行长期关键字检索的能力，之后基于双线性(Decisional Bilinear Diffie-Hellman, DBDH)数学难题规约证明了系统的安全性，最后对系统的计算复杂度和通信复杂度进行了分析。

1 基础知识及系统模型

1.1 双线性映射^[14]

设G和G_T 是两个阶为素数p的乘法循环群，g是群的一个生成元，若\widehat{e}满足以下3个条件：

1）双线性：对于任意的g,h\in G和a,b\in Z，运算\widehat{e}满足\widehat{e}\left(g^a,h^b\right)=\widehat{e}{\left(g,h\right)}^{ab}；

2）非退化性：存在g,h\in G，使得\widehat{e}\left(g,h\right)\ne {\mathrm{1}}_{GT}，其中{\mathrm{1}}_{GT}是群G_T 的生成元；

3）可计算性：对于任意的g,h\in G，都能够存在一个多项式时间的算法去计算\widehat{e}\left(g,h\right)\in G_T。

则称运算\widehat{e}:G\times G\to G_T是一个双线性映射。

1.2 DBDH假设难题^[15]

对于任意的概率多项式算法B,敌手都只有可以忽略不计的优势去解决DBDH假设,即区分\left(g,g^x,g^y,g^z,\widehat{e}{\left(g,g\right)}^{xyz}\right)和\left(g,g^x,g^y,g^z,\widehat{e}{\left(g,g\right)}^t\right),其中(x,y,z,t)是从整数群中随机选择的参数。那么该优势可以描述为

\begin{array}{l}{A}_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}=P[B(g,g^x,g^y,g^z,\widehat{e}{(g,g)}^{xyz})=\mathrm{1}]-\\ P[B(g,g^x,g^y,g^z,\widehat{e}{(g,g)}^t)=\mathrm{1}]\le \epsilon \end{array}（1）

式中，\epsilon表示一个可以忽略不计的概率值。

1.3 系统模型

密文分享可搜索加密系统模型按照功能划分，包含3类角色，分别是数据拥有者（Owner)、数据使用者（User）和服务器（Server），如图1所示。

3类角色各自完成以下工作：

1）数据拥有者：负责更新密文索引和生成分享票据。在更新时，数据拥有者负责对明文关键字和文件标识加密，并将加密后的密文索引上传到云端的密文数据库中；在分享文件时，数据拥有者根据文件标识生成分享票据，并传递给数据使用者。

2）服务器：负责存储和维护各个用户的密文数据库、进行密文索引的匹配和检索关键字。在分享文件时，服务器根据票据进行匹配，找到待分享文件对应的密文索引，并将密文索引从数据拥有者的密文数据库复制到数据使用者的密文数据库中；在检索关键字时，服务器根据用户提供的关键字检索陷门对密文索引进行匹配，返回关键字检索结果。

3）数据使用者：负责处理分享票据和关键字检索。在分享文件时，数据使用者从数据拥有者处获取分享票据，在进行一定处理后，将票据传递给服务器进行文件分享；在关键字检索时，数据使用者根据待搜索的关键字信息生成检索陷门，发送给服务器。此外，数据使用者也能更新自身的密文数据库和分享自己拥有的文件，扮演数据拥有者的角色。

2 方案设计

借鉴KS²E方案中基于票据的分享方法，使用分享票据，使被分享者保有使用私钥对分享文件进行长期关键字检索的能力。为确保系统无法使用之前的票据匹配到新的索引，设置了计数器用以生成用户的状态变量参数。同时，区别于KS²E双向索引链表的可搜索密文索引结构，利用双线性映射的计算性质，用来判断关键字检索陷门是否与密文索引匹配。该密文索引分享可搜索加密系统由以下5个核心协议构成：系统初始化、密文索引更新、分享票据生成、密文索引分享和关键字检索。如图2所示。

2.1 初始化协议Initiate

该协议由数据拥有者（Owner）、数据使用者（User）和服务器（Server）协作完成。数据拥有者、数据使用者分别单独执行Initiate协议,初始化主密钥和内部状态变量，并将密文数据库发送给服务器。

以数据拥有者端为例，初始化协议I(\lambda )执行步骤如下。

输入1个安全参数\lambda，初始化双线性映射系统B\leftarrow \left(p,G,G_T,\widehat{e},g,g_T\right)；初始化两个带随机种子的哈希函数，分别为H_{\mathrm{1}}:W\times {\{\mathrm{0},\mathrm{1}\}}^{\lambda }\to G和H_{\mathrm{2}}:I_{\mathrm{I}\mathrm{D}}\times {\{\mathrm{0},\mathrm{1}\}}^{\lambda }\to G；初始化伪随机函数F:{\{\mathrm{0},\mathrm{1}\}}^{\lambda }\times {\{\mathrm{0},\mathrm{1}\}}^{*}\to{\{\mathrm{0},\mathrm{1}\}}^{\lambda }；初始化主密钥K\stackrel{\$}{\leftarrow }{\{\mathrm{0},\mathrm{1}\}}^{\lambda }；初始化计数器变量c\leftarrow \mathrm{0}和内部状态变量T_W,T_{ID}\leftarrow \mathrm{\varnothing }；最后初始化空的密文数据库E_{\mathrm{O}}\leftarrow \mathrm{\varnothing }并上传至云服务器。

2.2 密文索引更新协议Update

该协议由数据拥有者和服务器共同参与完成。数据拥有者根据关键字—文件标识对(w,i)进行加密操作，生成可搜索密文索引C_{w,i}，并更新到自己的密文数据库E_{\mathrm{O}}中。

数据拥有者端执行密文索引更新协议U\left(K,\right.\left(w,i\right),c,\left.E_O\right)的执行步骤如下。

数据拥有者根据主密钥K和计数器变量计算加密密钥k_c\leftarrow F(K,c)；随后数据拥有者分别使用加密密钥k_c与关键字w和文件标识i计算生成子密文c\_t_{\mathrm{1}}\leftarrow H_{\mathrm{1}}(w,k_c)和子密文c\_t_{\mathrm{2}}\leftarrow H_{\mathrm{2}}(i,k_c)，利用双线性映射生成子密文c\_t_{\mathrm{3}}\leftarrow \widehat{e}{\left(H_{\mathrm{1}}\left(w,k_c\right),H_{\mathrm{2}}(i,k_c)\right)}^{k_c}；之后数据拥有者分别更新内部状态变量T_w[i]\leftarrow T_w[i]\bigcup c和T_w[w]\leftarrow T_w[w]\bigcup c，并将计数器值加1，即c\leftarrow c+\mathrm{1}；最后，数据拥有者将密文索引C_{w,i}\leftarrow (c\_t_{\mathrm{1}},c\_t_{\mathrm{2}},c\_t_{\mathrm{3}})发送给云服务器，云服务器完成对密文数据库的更新，即E_{\mathrm{O}}\leftarrow E_{\mathrm{O}}\bigcup C_{w,i}。

数据使用者和服务器使用相似的方法，完成对数据使用者密文数据库的更新，即E_{\mathrm{U}}\leftarrow E_{\mathrm{U}}\bigcup C_{w,i}。

根据双线性映射的运算性质，密文索引C_{w,i}的子密文之间存在以下对应关系：

\widehat{e}(c\_t_{\mathrm{1}},H_{\mathrm{2}}(i,k_c{)}^{k_c})=\widehat{e}(H_{\mathrm{1}}(w,k_c{)}^{k_c},c\_t_{\mathrm{2}})=c\_t_{\mathrm{3}}（2）

利用这种对应关系，可以完成文件分享票据和关键字检索票据的匹配。

2.3 分享票据生成协议Token

该协议由数据拥有者执行。数据拥有者根据待分享文件的文件标识，结合自己的主密钥和本地存储的内部状态，生成文件分享票据，并通过安全信道传递给数据使用者。

数据拥有者端执行分享票据生成协议T(K,c,i)的执行步骤如下。

数据拥有者首先初始化空集合T_i用于存放文件分享票据。随后根据待分享文件标识i，读取对应文件标识下的内部状态映射表内容T_w[i]。对于T_w[i]中的每一个元素i（i实际对应了数据拥有者在不同状态下的计数器变量c值），计算该状态下的加密密钥k_c\leftarrow F\left(K,i\right)和分享票据T\leftarrow \left(H_{\mathrm{2}}{\left(i,k_c\right)}^{k_c},H_{\mathrm{2}}\left(i,k_c\right),k_c\right)，并将分享票据T更新到票据集T_i中，即T_i\leftarrow T_i\bigcup T。最后，数据拥有者采用封装的方式，将票据集T_i通过安全信道发送至数据使用者。

2.4 密文索引匹配协议Match

该协议由数据使用者和服务器共同参与执行。数据使用者解封装收到的票据集，使用自己的主密钥生成文件匹配票据发送给服务器。服务器根据文件匹配票据，在数据拥有者的密文数据库中找到待分享文件对应的密文索引，重加密后更新到数据使用者的密文数据库中。

数据使用者和服务器间执行密文索引匹配协议M\left(T_i,c^{\text{'}},K^{\text{'}};E_O,E_U\right)的执行步骤如下。

数据使用者初始化空的集合M_i用于存储密文索引匹配票据，之后对票据集T_i进行解封装，并记其中的每个三元组为T\leftarrow (p_{\mathrm{1}},p_{\mathrm{2}},p_{\mathrm{3}})。对于每个三元组T，数据使用者使用自己的主密钥K^{\text{'}}和计数器值c^{\text{'}}，计算得到加密密钥k_c\text{'}\leftarrow F\left(K\text{'},c^{\text{'}}\right)，将二元组(c^{\text{'}},p_{\mathrm{3}})更新到映射表T_{\mathrm{u}\mathrm{I}\mathrm{D}}中，即T_{\mathrm{u}\mathrm{I}\mathrm{D}}\leftarrow T_{\mathrm{u}\mathrm{I}\mathrm{D}}\bigcup(c^{\text{'}},p_{\mathrm{3}})，并将二元组(p_{\mathrm{1}},{p_{\mathrm{2}}}^{k_c^{\text{'}}})更新到匹配票据集M_i中，即M_i\leftarrow M_i\bigcup (p_{\mathrm{1}},{p_{\mathrm{2}}}^{k_c^{\text{'}}})。完成之后，数据使用者将计数器值加1，即c\text{'}\leftarrow c\text{'}+\mathrm{1}。完成上述步骤后，数据使用者采用封装的方式，将匹配票据集M_i通过安全信道传递给服务器。

服务器对匹配票据集M_i解封装，并记其中的每一个二元组M为(d_{\mathrm{1}},d_{\mathrm{2}})。对于每一个二元组M，服务器读取数据拥有者密文数据库E_{\mathrm{O}}，若密文索引C_{w,i}\leftarrow \left(c\_t_{\mathrm{1}},c\_t_{\mathrm{2}},c\_t_{\mathrm{3}}\right)满足c\_t_{\mathrm{3}}=\widehat{e}\left(c\_t_{\mathrm{1}},d_{\mathrm{1}}\right)的等式关系，那么服务器就重加密计算c\_t_{\mathrm{3}}^{\text{'}}=\widehat{e}\left(c\_t_{\mathrm{1}},d_{\mathrm{2}}\right)，并保持c\_t_{\mathrm{1}}和c\_t_{\mathrm{2}}子密文不变，从而构造新的密文索引C_{w,i}^{\text{'}}\leftarrow \left(c\_t_{\mathrm{1}}^{\text{'}},c\_t_{\mathrm{2}}^{\text{'}},c\_t_{\mathrm{3}}^{\text{'}}\right)。服务器将重加密后得到的密文索引C_{w,i}^{\text{'}}复制到数据使用者的密文数据库E_{\mathrm{U}}中，即E_{\mathrm{U}}\leftarrow E_{\mathrm{U}}\bigcup C_{w,i}^{\text{'}}。数据使用者可以使用自己的密钥，对密文数据库中复制的密文索引进行关键字检索。

2.5 关键字检索协议Search

数据拥有者和数据使用者均可通过执行该协议进行关键字检索。以数据使用者为例，对于待检索关键字，数据使用者可恢复所有之前使用过的加密密钥，并生成检索陷门集。服务器读取数据使用者密文数据库中的密文索引，利用检索陷门对密文索引进行检索匹配，并将匹配结果返回给数据使用者。

以数据使用者为例，关键字检索协议S(K^{\text{'}},c^{\text{'}},w;E_{\mathrm{U}})的执行步骤如下。

数据使用者初始化空的集合S_w作为检索陷门集,并读取本地内部状态映射表T_{\mathrm{I}\mathrm{D}}和T_{\mathrm{u}\mathrm{I}\mathrm{D}}。对于映射表T_{\mathrm{I}\mathrm{D}}[w]中的每个元素t（t实际对应了数据使用者在不同状态下的计数器变量c^{\text{'}}值），数据使用者使用自己的主密钥K^{\text{'}}计算对应该状态下的加密密钥k_c^{\text{'}}\leftarrow F\left(K\text{'},t\right)（把计数器值t状态下计算得到的加密密钥记作k_{c-t}^{\text{'}}）,并计算值H_{\mathrm{1}}{\left(w,k_{c-t}\right)}^{k_{c-t}^{\text{'}}}更新到检索陷门集S_w中,即S_w\leftarrow S_w\bigcup H_{\mathrm{1}}{\left(w,k_{c-t}\right)}^{k_{c-t}^{\text{'}}}。类似的，对于映射表T_{\mathrm{u}\mathrm{I}\mathrm{D}}中的每个二元组，将其记作(s,k_{c-s})（s同样对应数据使用者在不同状态下的计数器变量c^{\text{'}}值），数据使用者使用自己的主密钥K\text{'}计算对应不同状态下的加密密钥k_c^{\text{'}}\leftarrow F(K\text{'},s)（把计数器值s状态下计算得到的加密密钥记作k_{c-s}^{\text{'}}），并将计算值H_{\mathrm{1}}{\left(w,k_{c-s}\right)}^{k_{c-s}^{\text{'}}}更新到检索陷门集S_w中，即S_w\leftarrow S_w\bigcup H_{\mathrm{1}}{\left(w,k_{c-s}\right)}^{k_{c-s}^{\text{'}}}。完成上述操作后，数据使用者将封装后的检索陷门集S_w通过安全信道发送给服务器。

服务器首先初始化空的集合R用于存放检索结果，之后服务器解封装检索陷门集S_w，对于其中每一个搜索陷门s_w，服务器读取数据使用者密文数据库E_{\mathrm{U}}中的密文索引C_{w,i}^{\text{'}}，执行计算并判断密文索引C_{w,i}^{\text{'}}和搜索陷门s_w之间是否满足等式关系\widehat{e}\left(s_w,c\_t_{\mathrm{2}}^{\text{'}}\right)=c\_t_{\mathrm{3}}^{\text{'}}。若满足，服务器将该密文索引C_{w,i}^{\text{'}}添加到检索结果集R中。最终，服务器将检索结果集R返回给数据使用者，完成关键字检索。

3 正确性、安全性及性能分析

3.1 正确性分析

方案的正确性可以评价为文件分享正确性和关键字检索正确性。

1）文件分享正确性。服务器能够使用匹配票据正确地匹配到待分享文件所对应的可搜索密文索引。在文件分享过程中，服务器对匹配票据集M_i解封装得到二元组\left(d_{\mathrm{1}},d_{\mathrm{2}}\right)，服务器读取数据拥有者密文数据库E_{\mathrm{O}}中的密文索引C_{w,i}\leftarrow \left(c\_t_{\mathrm{1}}\right.,c\_t_{\mathrm{2}},\left.c\_t_{\mathrm{3}}\right)，并计算\widehat{e}\left(c\_t_{\mathrm{1}},d_{\mathrm{1}}\right)。\widehat{e}(c\_t_{\mathrm{1}},d_{\mathrm{1}})计算为

\begin{array}{l}\widehat{e}(c\_t_{\mathrm{1}},d_{\mathrm{1}})=\widehat{e}(H_{\mathrm{1}}(w,k_c),H_{\mathrm{2}}(i,k_c{)}^{k_c})=\\ \widehat{e}(H_{\mathrm{1}}(w,k_c),H_{\mathrm{2}}(i,k_c{))}^{k_c}=c\_t_{\mathrm{3}}\end{array}（3）

当密文索引C_{w,i}中的c\_t_{\mathrm{1}}和c\_t_{\mathrm{3}}部分与匹配票据中的d_{\mathrm{1}}部分满足以上等式关系时，说明该密文索引C_{w,i}是由待分享文件对应的文件标识i所生成的，从而保证了文件分享的正确性。

2）关键字检索正确性。服务器可以使用检索陷门正确进行关键字检索。以数据使用者检索为例，在检索过程中，服务器对检索陷门集解封装，得到检索陷门s_w\leftarrow H_{\mathrm{1}}{\left(w,k_c\right)}^{k_c^{\text{'}}}，而后服务器读取数据使用者密文数据库E_{\mathrm{U}}中的可搜索密文索引C_{w,i}^{\text{'}}\leftarrow\left(c\_t_{\mathrm{1}}^{\text{'}},c\_t_{\mathrm{2}}^{\text{'}},c\_t_{\mathrm{3}}^{\text{'}}\right)，并计算\widehat{e}\left(s_w,c\_t_{\mathrm{2}}^{\text{'}}\right)。\widehat{e}\left(s_w,c\_t_{\mathrm{2}}^{\text{'}}\right)计算为

\begin{array}{l}\widehat{e}\left(s_w,c\_t_{\mathrm{2}}^{\text{'}}\right)=\widehat{e}\left(H_{\mathrm{1}}(w,k_c{)}^{k_c^{\text{'}}},H_{\mathrm{2}}(i,k_c)\right)=\\ \widehat{e}{\left(H_{\mathrm{1}}(w,k_c),H_{\mathrm{2}}(i,k_c)\right)}^{k_c^{\text{'}}}=\\ \widehat{e}\left(H_{\mathrm{1}}(w,k_c),H_{\mathrm{2}}(i,k_c{)}^{k_c^{\text{'}}}\right)=\widehat{e}\left(c\_t_{\mathrm{1}},d_{\mathrm{2}}\right)=\\ c\_t_{\mathrm{3}}^{\text{'}}\end{array}（4）

当密文索引C_{w,i}^{\text{'}}中的c\_t_{\mathrm{2}}^{\text{'}}和c\_t_{\mathrm{3}}^{\text{'}}部分与检索票据s_w满足以上等式关系时，说明生成该密文索引的关键字—文件标识对\left(w,i\right)包含了待检索的关键字w，从而保证了关键字检索的正确性。

3.2 安全性证明

将密文索引C_{w,i}中数据拥有者使用自己的主密钥、采用双线性映射方法计算得到的值，替换成从双线性映射值域空间G_T 中完全随机选择的字符串。那么敌手A能够准确区分真实密文和随机密文的优势，相当于敌手可以通过构造模拟算法B来解决公认的决策性双线性迪菲—赫尔曼假设难题。将敌手A区分真实密文和随机密文的优势表示为A_B^{\mathrm{W}\mathrm{i}\mathrm{n}}(\lambda )，将敌手A通过执行模拟算法B破解DBDH难题的优势表示为A_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}(\lambda )。分别使用符号O_T表示进行关键字检索陷门查询时访问的随机语言机，使用符号O_S表示进行分享票据查询时访问的随机预言机，使用符号O_C表示进行密文索引查询时访问的随机预言机。把带随机种子的哈希函数H_{\mathrm{1}}、H_{\mathrm{2}}分别模拟成随机预言机O_{H_{\mathrm{1}}}、O_{H_{\mathrm{2}}}。

给出模拟算法B的描述。算法B以一个DBDH假设的实例\left(G,G_T,\widehat{e},g,g^x,g^y,g^z,t,Z\right)作为输入，其中\left(x,y,z,t\right)是从整数群中随机选择的参数，参数Z的取值从Z=\widehat{e}{\left(g,g\right)}^{xyz}或者Z=\widehat{e}{\left(g,g\right)}^t中随机选择。之后设置两个随机硬币c\leftarrow \{\mathrm{0},\mathrm{1}\}和d\leftarrow\{\mathrm{0},\mathrm{1}\}，算法B会根据抛硬币的结果决定随机预言机O_{H_{\mathrm{1}}}和O_{H_{\mathrm{2}}}的取值，这里将每个硬币取值为0的概率分别表示为P\left[c=\mathrm{0}\right]=\delta、P\left[d=\mathrm{0}\right]=\theta。

敌手A将参加如下游戏：敌手A首先会查询随机预言机O_T，算法B会返回对应于所查询关键字w的模拟的关键字检索陷门；之后敌手A查询随机预言机O_S，算法会返回对应于查询文件标识i模拟的分享票据；接着敌手A还会对随机预言机O_C查询，算法B会返回对应于所查询\left(w,i\right)对的模拟密文索引。在完成对随机预言机的查询后，敌手A随机选择未查询过的挑战关键字w^{*}和挑战文件标识i^{*}，算法B会随机选择参数Z并计算挑战密文索引C_b^{*}\leftarrow (c\_t_{\mathrm{1}}^{*},c\_t_{\mathrm{2}}^{*},c\_t_{\mathrm{3}}^{*})，并将挑战密文索引C_b^{*}返回给敌手A。敌手A根据接收的挑战密文索引C_b^{*}，输出一比特值b\text{'}\mathrm{ϵ}\{\mathrm{0},\mathrm{1}\}作为对算法B选用的参数值Z的猜测。若b^{\text{'}}=b，则敌手A赢得游戏。

下面讨论敌手A能够解决DBDH难题并赢得游戏的概率。记算法B在上述游戏中不发生中止为事件\overline{r}，事件\overline{r}发生的概率用P\left[\overline{r}\right]来表示，敌手A解决DBDH难题并赢得游戏的优势可以表示为A_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}(\lambda )。

在算法B执行过程中，存在两种情况会使算法B执行中止，这里分别用事件r_{\mathrm{1}}和事件r_{\mathrm{2}}来表示这两种情形。

对于第1种情形，当敌手A在查询随机预言机O_T、O_S和O_C时，若随机硬币的数值满足c=\mathrm{0}或d=\mathrm{0}时，会导致算法B执行中断，这里记事件r_{\mathrm{1}}不发生为事件\overline{r_{\mathrm{1}}}，因此事件\overline{r_{\mathrm{1}}}发生的概率可以计算为

P[\overline{r_{\mathrm{1}}}]={\left(\mathrm{1}-\delta \right)}^{q_T+q_C}\cdot {(\mathrm{1}-\theta )}^{q_S+q_C}

式中，q_T、q_S和q_C分别表示查询随机预言机O_T、O_S和O_C的次数。

对于第2种情形，当算法B在计算挑战密文索引时，当随机硬币的取值满足c=\mathrm{1}或d=\mathrm{1}时，会导致算法B执行中断，这里把不发生r_{\mathrm{2}}记为事件\overline{r_{\mathrm{2}}}，因此事件\overline{r_{\mathrm{2}}}发生的概率可以计算为

P[\overline{r_{\mathrm{2}}}]=\theta \cdot \delta

综合上述两种情形，记算法B不发生执行中断为事件\overline{r}，因此事件\overline{r}发生的概率可以计算为

P[\overline{r}]=\delta {\left(\mathrm{1}-\delta \right)}^{q_T+q_C}\cdot \theta {(\mathrm{1}-\theta )}^{q_S+q_C}

当\delta和\theta的取值分别为\delta =\frac{\mathrm{1}}{\mathrm{1}+q_T+q_C}和\theta =\frac{\mathrm{1}}{\mathrm{1}+q_S+q_C}时，此时事件\overline{r}发生的概率可以计算为

P[\overline{r}]\approx \frac{\mathrm{1}}{{\mathrm{e}}^{\mathrm{2}}(\mathrm{1}+q_T+q_C)(\mathrm{1}+q_S+q_C)}（5）

式中，e为自然常数。

因此，将敌手A区分真实密文和随机密文的优势A_B^{\mathrm{W}\mathrm{i}\mathrm{n}}(\lambda )规约到敌手通过执行模拟算法破解DBDH难题的优势A_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}(\lambda )上，即：

A_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}(\lambda )=\frac{\mathrm{1}}{{\mathrm{e}}^{\mathrm{2}}\left(\mathrm{1}+q_T+q_C\right)\left(\mathrm{1}+q_S+q_C\right)}\cdot A_B^{\mathrm{W}\mathrm{i}\mathrm{n}}(\lambda )（6）

由于DBDH假设难题是公认在多项式时间内难以破解的，那么敌手A能够破解DBDH难题的优势自然也是可以忽略不计的。因此，敌手A区分真实密文和随机密文的优势A_B^{\mathrm{W}\mathrm{i}\mathrm{n}}(\lambda )可以表示为

A_B^{\mathrm{W}\mathrm{i}\mathrm{n}}(\lambda )={\mathrm{e}}^{\mathrm{2}}\left(\mathrm{1}+q_T+q_C\right)\left(\mathrm{1}+q_S+q_C\right)\cdot A_B^{\mathrm{D}\mathrm{B}\mathrm{D}\mathrm{H}}(\lambda )（7）

因此，敌手A区分真实密文和随机密文的优势也是可以忽略不计的。

证明完毕。

3.3 性能分析

3.3.1 计算复杂度

本方案的计算开销主要集中于双线性映射运算和模幂运算。在初始化阶段，主要完成双线性映射系统基本参数、哈希函数及伪随机函数的初始化，计算复杂度为O（1）；在密文索引更新阶段，对于每个关键字—文件标识对\left(w,i\right)，数据拥有者使用伪随机函数计算加密密钥k_c\leftarrow F(K,c)，而后分别使用哈希函数、双线性映射和模幂运算方法依次计算得到c\_t_{\mathrm{1}}\leftarrow H_{\mathrm{1}}(w,k_c)、c\_t_{\mathrm{2}}\leftarrow H_{\mathrm{2}}(i,k_c)和c\_t_{\mathrm{3}}\leftarrow\widehat{e}{\left(H_{\mathrm{1}}\left(w,k_c\right),H_{\mathrm{2}}\left(i,k_c\right)\right)}^{k_c}，在此阶段，假设密文数据库更新了n个关键字—文件标识对\left(w,i\right)，那么数据拥有者共计进行n次模幂运算、n次双线性运算、2n次哈希运算和n次伪随机函数运算；在分享票据生成阶段，对于每个待分享文件i，数据拥有者分别使用伪随机函数生成分享密钥k_c\leftarrow F\left(K,i\right)、使用哈希函数和模幂运算生成分享票据T\leftarrow \left(H_{\mathrm{2}}{\left(i,k_c\right)}^{k_c}\right.,\left.H_{\mathrm{2}}\left(i,k_c\right),k_c\right)，而后得到分享票据集T_i，假设数据拥有者分享的m个文件包含n_a 个关键字—文件标识对，则共计进行n_a 次模幂运算；在密文索引匹配阶段，对于数据使用者，其使用伪随机函数计算加密密钥k_c^{\text{'}}\leftarrow F\left(K\text{'},c^{\text{'}}\right)、使用模幂运算将二元组\left(p_{\mathrm{1}},{p_{\mathrm{2}}}^{k_c^{\text{'}}}\right)更新匹配票据集M_i中，共计进行n_a 次模幂运算。对于服务器，其使用双线性映射计算c\_t_{\mathrm{3}}=\widehat{e}(c\_t_{\mathrm{1}},d_{\mathrm{1}})并进行密文索引匹配，对于匹配到的密文索引，重加密计算c\_t_{\mathrm{3}}\text{'}=\widehat{e}(c\_t_{\mathrm{1}},d_{\mathrm{2}})，构造新的密文索引，共计进行（n+1）×n_a 次双线性映射运算；在关键字检索阶段，数据使用者使用哈希函数和模幂运算生成检索陷门集S_w，服务器使用双线性映射计算\widehat{e}\left(s_w,\right.\left.c\_t_{\mathrm{2}}^{\text{'}}\right)与密文数据库E_{\mathrm{U}}中的密文索引C_{w,i}^{\text{'}}进行检索匹配，假设数据使用者密文数据库中包含关键字w的关键字—文件标识对\left(w,i\right)数量为n_b，那么数据使用者共计执行n_b 次模幂运算，服务器共计执行n×n_b 次双线性映射运算。

3.3.2 通信复杂度

对于分享和检索操作，需要数据拥有者与数据使用者之间进行票据传输，此过程通信量取决于分享文件或检索关键字对应关键字—文件标识对\left(w,i\right)的数量n，通信复杂度为O（n）。对于服务器与数据使用者之间的通信，服务器需要在收到检索票据后，返回对于每个检索关键字的检索结果，通信复杂度为O（n）。

4 结束语

针对聚焦云存储场景下云端加密数据在复制和分享过程中存在的困境，基于双线性映射、计数器和重加密技术，设计了一种支持密文索引分享的可搜索加密系统。该系统实现了文件标识粒度的文件分享和关键字粒度的密文索引检索，并基于DBDH假设难题证明了方案的安全性。在之后的方案改进中，可以考虑在密文索引结构设计上进行优化，对于双线性映射可能带来的巨大计算开销^[16]，也可以考虑使用更轻量的运算方法生成密文。

参考文献

[1] 张玉清，王晓菲，刘雪峰，等.云计算环境安全综述［J］.软件学报，2016，27（6）：1328-1348.

[2] 李颖，马春光.可搜索加密研究进展综述［J］.网络与信息安全学报，2018，4（7）：13-21.

[3] 徐鹏，金海.可搜索加密的研究进展［J］.网络与信息安全学报，2016，2（10）：8-16.

[4] SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data［C］∥Proceeding of the 2000 IEEE Symposium on Security and Privacy. Piscataway， USA： IEEE， 2000：44-55.

[5] BONEH D， DI CRESCENZO G， OSTROVSKY R， et al. Public key encryption with keyword search［C］∥Proceeding of the Advances in Cryptology-EUROCRYPT 2004. Berlin， Germany： Springer， 2004：506-522.

[6] KAMARA S， PAPAMANTHOU C， ROEDER T. Dynamic searchable symmetric encryption［C］∥Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York， USA： ACM， 2012：965-976.

[7] POPA R A， ZEIDOVICH N. Multi-key searchable encryption［EB/OL］. （2013-08-17） ［2024-08-10］.

[8] TANG Q. Nothing is for free： security in searching shared and encrypted data［J］. IEEE Transactions on Information Forensics and Security， 2014，9（11）：1943-1952.

[9] YANG J， FU C， SHEN N， et al. General multi-key searchable encryption［C］∥Proceedings of the 2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops. Piscataway， USA： IEEE， 2015：89-95.

[10] HAMLIN A， SHELAT A， WEISS M， et al. Multi-key searchable encryption， revisited［M］∥Public-Key Cryptography-PKC 2018. Cham， Switzerland： Springer， 2018：95-124.

[11] SU Y P， WANG J F， WANG Y L， et al. Efficient verifiable multi-key searchable encryption in cloud computing［J］. IEEE Access， 2019，7：141352-141362.

[12] HAHN C， YOON H， HUR J. Multi-key similar data search on encrypted storage with secure pay-per-query［J］. IEEE Transactions on Information Forensics and Security， 2023，18：1169-1181.

[13] WANG W， LIU D L， XU P， et al. Keyword search shareable encryption for fast and secure data replication［J］. IEEE Transactions on Information Forensics and Security， 2023，18：5537-5552.

[14] 魏福山，黄根勋，高峰修.基于双线性映射的门限短签名方案［J］.信息工程大学学报，2008，9（1）：24-26；61.

[15] BONEH D， BOYEN X. Efficient selective-ID secure identity-based encryption without random oracles［M］∥Advances in Cryptology： EUROCRYPT 2004. Berlin， Germany： Springer， 2004：223-238.

[16] 赵昌安，张方国.双线性对有效计算研究进展［J］.软件学报，2009，20（11）：3001-3009.