区块链上支持多关键字检索的可搜索加密方案 *

牛淑芬，王金风，王伯彬，陈敬民，杜小妮

(1.西北师范大学计算机科学与工程学院，甘肃 兰州730070；2.西北师范大学数学与统计学院，甘肃 兰州730070)

1 引言

为了保护数据的隐私，在将数据上传到云服务器之前，需要对数据进行加密。为了解决密文上的检索问题，Song等人[1]提出了对称可搜索加密SSE(Symmetric Search Encryption)方案，该方案实现了基于密文的搜索功能，但需要对所有的文档进行扫描，所以效率比较低。 为了提高对密文的搜索效率，Goh[2]根据关键字建立安全索引，云服务器通过匹配陷门和索引返回用户所需要的密文文档。Boneh等人[3]提出了带关键字的公钥可搜索加密PEKS(Public key Encryption with Keyword Search)方案，公钥可搜索加密方案利用公钥加密，仅有相应私钥的用户才能搜索加密数据，公钥可搜索加密方案更适合多用户的数据共享领域。

在某些应用场景中，用户需要通过更多的关键词来缩小搜索范围，获得更加精确的搜索结果。Golle等人[4]在GSW-1中最早提出了多关键词检索MKSE(Multi-Keyword Searchable Encryption)方案，在该方案中关键字陷门的大小与加密文档的数量成线性关系。Kerschbaum[5]提出了非结构化文本的多关键词可搜索加密方案，但每次搜索针对的是文件中的所有关键词，而不是有选择地进行。为了提高检索结果的准确性，Cao等人[6]提出了可以捜索多个关键字的密文排序搜索方案，采用匹配的方式衡量了关键字与密文文件的相关度，返回满足用户搜索条件的密文范围。Zhang等人[7]提出的方案实现了分离关键字搜索，Ballard等人[8]提出的连接关键字的可搜索加密方案实现了多关键字搜索的扩展功能。宋衍等人[9]提出了多关键字任意连接的可搜索加密方案，提高了多关键字搜索的灵活性。Xia等人[10]提出了支持动态更新的多关键词排序搜索方案，通过采用贪婪深度优先搜索算法提高检索结果的准确性。杨旸等人[11]提出了能实现数据隐私保护的多关键词语义排序搜索方案，该方案不仅提高了数据搜索效率，而且返回了更能满足用户需求的搜索结果。Li等人[12]提出了在电子邮件系统中支持指定服务器身份验证的可搜索加密方案，通过对电子邮件发件人在加密时对邮件进行身份验证，加强了方案的安全性。

2008年，Nakamoto[13]提出了一个不涉及第三方交易记录的比特币平台。区块链[14]是一个基于比特币协议维护不可篡改的数据记录列表。区块链本质上是一个P2P网络系统中的分布式数据库[15]，区块链上的每一个区块是使用密码学的相关技术而产生的数据块，交易创建后将被广播到区块链系统中；交易被矿工[16]验证有效后将被记录到临时区块；矿工使用工作量证明机制[17]计算出区块后将此区块向全网广播，再将区块链接在区块链上。区块链上的交易是公开透明且不可更改的。

在基于云存储的可搜索加密方案中[18,19]，云服务器是半诚实的，即服务器可以任意改变搜索结果或不执行搜索任务。在理想情况下，如果服务器未返回搜索结果或返回错误结果给用户时，用户希望服务器能受到经济处罚，以降低其可信度，用户也能赎回自己承诺的手续费。通过引入区块链技术[20,21]可以实现这一要求，而现有的方案[22,23]无法精确返回搜索结果，因此本文提出了区块链上的多关键字可搜索加密方案。根据存储数据的大小将其分为轻量级数据和重量级数据，本方案主要是针对轻量级数据的存储及检索作了描述，即嵌入一笔交易的数据可以存储在一个区块上，如果是重量级数据，需要对数据做分割处理后再将其以交易的形式存储在区块链上。

2 系统模型和安全模型

2.1 系统模型

区块链上的可搜索加密主要有数据拥有者V、数据使用者U、搜索者Q和矿工M共4个参与者。假设数据拥有者有n个文档D1,D2,…,Dn，为了保护文档的隐私，数据拥有者将文档加密成密文C1,C2,…,Cn，并将其以交易TX=(TX1,TX2,…,TXn)的形式上传到区块链上。为了提高文档的搜索效率，数据拥有者V生成文档对应的索引I并将索引嵌入交易Inx中，再将索引交易上传到区块链上。当数据使用者要检索包含目标关键字W′的文档时，数据使用者需要构造一笔包含关键字陷门TW′和索引交易Inx的查询交易ask，再将查询交易广播到区块链网络中，由矿工将合法有效的交易上传到区块链上。通过搜索者Q返回包含陷门信息的交易get，数据使用者U在交易get中获得密文Ci(1≤i≤n)，U将密文在本地用私钥k解密，系统模型如图1所示。

Figure 1 System model图1 系统模型

2.2 方案形式化定义

(1)param←SetUp(1λ)：输入安全系数λ，输出系统参数param。

(2)k←KeyGen(param)：输入系统参数param，输出用户密钥k。

(3)(TX,Inx)←Enc(k,D,W)：数据拥有者运行该算法，对文档集D={D1,…,Dn}和关键字W加密，并生成关键字索引I，将密文Ci(1≤i≤n)以交易TX的形式，索引I以交易Inx的形式上传到区块链上，将交易Inx广播到P2P的区块链网络。

(4)TW′←Trapdoor(k,W′)：由数据使用者生成关键字搜索令牌，输入密钥k和目标关键字集W′ =(w′1,w′2,…,w′m}，输出陷门TW′。

(5)(withdraw/get)←Search(TW′,Inxi)：由数据使用者U和搜索者Q运行的确定性算法，数据使用者U构建一笔包含TW′和Inx的交易ask，当数据使用者U执行该算法时，输出交易withdraw，若搜索者Q执行该算法，则输出交易get。

(6)D←Dec(k,get)：数据使用者U运行该算法，输入密钥k和交易get，输出解密文档D，数据使用者U从区块链上获得交易get并从该交易里获得密文，然后对其用k解密。

2.3 安全模型

3 区块链上多关键字的可搜索加密方案

区块链上的多关键字可搜索加密主要有数据拥有者V、数据使用者U、搜索者Q和矿工M共4个参与者，方案的详细过程描述如下：

(2)KeyGen(k)：假设每一个用户X有一个秘密指数aX，其中0≤aX≤q-1，对应的公开值为bX=gaX，bX被包含在X的证书里并被可信的权威机构TA签名。

③U计算出会话密钥k=SVaUbVrU，其中U从Cert(V)中获得了bV值。

④V计算会话密钥k=SUaVbUrV，其中Di从Cert(U)中获得了bU值。在会话结束时，V和U计算出相同的会话密钥k=grVaU+rUaV。

(3)Enc(k,D,W)：数据拥有者V执行该算法，输入密钥k、文档集D={D1,D2,…,Dn}和关键字集W={w1,w2,…,wn}，其中，wi={wi1,wi2,…,wim}，数据拥有者V按如下步骤构造密文交易TXi(1≤i≤n)和索引交易Inxi(1≤i≤n)：

①将文档Di加密为密文Ci=Enck(Di)(1≤i≤n)。

③为了存储密文Ci(1≤i≤n)和索引结构Is，V需要找到n+1个值di$且交易接受者是V的未花费交易输出UTXi(1≤i≤n+1)来构造交易TXi(1≤i≤n)和交易Inxi,1≤i≤n，将密文Ci和索引结构Is分别嵌入交易TXi和交易Inxi中，将其存储在区块上,再由矿工将其链接到区块链上。关键字索引结构如图2所示。

Figure 2 Keyword index structure图2 关键字索引结构

(4)Trapdoor(k,W′)：授权数据使用者U执行该算法生成关键字陷门，输入密钥k和要检索的关键字集W′，数据使用者U按如下步骤构建交易ask：

②U可以指定任意用户进行搜索，假设该搜索者是Q。

③U需要找到值d$且交易接受者为U的一笔未花费交易Tq，U用Tq计算交易ask的主体。

④U将(TW,Inx)嵌入交易ask的外部脚本中，对该交易进行签名后向全网广播。

(5)Search(TW,Inx)：由Q来执行该搜索算法，如果Q想获取交易ask中的服务费，Q需要构造交易get。交易构造如下所示：

②Q以ask作为输入计算交易get的主体，Q将密文(C1,C2,…,Cn)嵌入交易get中，Q对交易get签名并向全区块链网络广播，再由M将收集的交易写入区块链，若get未出现在区块链上，U构造交易withdraw来追回交易ask中的费用d$。区块链上的搜索过程如图3所示。

Figure 3 Search process on blockchain图3 区块链上搜索过程

(6)Dec(k,get)：U执行该算法，如果交易get出现在区块链上，U从区块链上获得交易get，U再读取嵌入交易get中的密文Ci，并使用密钥k解密密文Ci，获得明文文档Deck(Ci)=Di。

4 安全性和效率分析

4.1 安全性证明

定理1如果f是多项式时间安全的伪随机函数，H1是抗碰撞的哈希函数，Enc和Dec是PPT安全的对称加解密算法，那么基于区块链的多关键字对称可搜索加密方案Π=(SetUp,KeyGen,Enc,Trapdoor,Search,Dec)是IND-CKA安全的。

(3)模拟陷门TXTW。

(4)模拟交易ask。

使用模拟器S模拟交易ask，如果敌手Α想获得模拟交易ask*中的手续费，当qt=0时，S需要将关键字密文返回给Α。当qt≥1时，S将询问的关键字密文返回给Α，Ciwq是关于关键字wq的访问密文，如果想得到这笔服务费，他必须建立一个新的不同的区块链，这违反了区块链上的不可逆性，又因为f是伪随机函数，因此敌手Α创建的交易S无法获得交易ask中的服务费。

□

4.2 效率分析

4.2.1 理论分析

本节将区块链上的可搜索加密方案与其他方案在性能和计算效率方面做了详细的比较，如表1和表2所示，其中“√”表示是，“×”表示否，E和P分别为循环群中的双线性对运算时间和指数运算时间，n′为每个文档的关键字个数，m为用户搜索的关键字的数量,H表示哈希运算时间，|D|表示文档的大小，|TX|表示交易的大小，r表示包含某关键字的文档检索数量。

Table 1 Performance comparison among different schmems

如表1所示，在支持关键字搜索方面，文献[9]方案和本文方案实现了多关键字搜索的功能，文献[12,22,23]支持密文上的单关键字搜索功能。在采用加密算法方面，文献[22]方案和本文方案采用对称加密算法，实现了数据的快速加密，文献[9,12,23]方案使用公钥加密算法解决了数据加密过程中的密钥传输问题，但公钥加密算法加密速度慢。在数据存储平台方面，文献[9,12]方案采用云存储服务器,但云存储服务器是半诚实且好奇的，搜索过程中不具有公平性，文献[22,23]方案和本文方案采用区块链技术，为存储平台解决了搜索者的公平性问题。

如表2所示，在关键字加密计算量上，本文方案计算开销大于文献[12,23]方案，但本文方案实现了多关键字的数据加密功能，本文方案比文献[9]方案多1次指数运算；在陷门计算量上，本文方案在满足多关键字搜索的同时只进行了1次指数运算，因此具有较高的计算优势，文献[23]方案只用了4个哈希函数但其支持单关键字的检索，文献[9,12]方案的计算开销均大于本文方案的；在搜索运算量上，在支持多关键字检索的同时本文方案的计算开销小于文献[9]方案的，大于文献[12,23]方案的，文献[12,23]方案使用公钥加密算法实现了密文上的单关键字检索功能，因此文献[12,23]方案的计算开销要小于本文方案的；在通信量计算上，文献[9,12]方案的通信量大小与文档的大小及包含关键字的文档检索数量的乘积呈线性关系，文献[23]方案和文本方案是基于区块链技术存储的，因此通信量与区块上交易的大小有关，文献[23]方案基于联盟链存储，因此通信量大小是8|TX|，本文方案是基于公开链存储的，区块上每一笔交易需要6次确认才能记录到区块链上，通信量是6|TX|，选择存储区块链的类型不同所需要的通信计算量也不同。

Table 2 Efficiency comparison among different schemes

本文提出的方案既实现了区块链上的多关键字检索功能，又实现了较高的陷门生成率，同时也满足搜索效率与关键字数量成线性关系。此外，在本文方案中，存储在区块链上的数据是分布式存储且不可篡改的，具有安全性更高的加密和陷门生成方式，并且用户能够使用区块链技术实现真正的数据共享。

4.2.2 数值实验分析

本节通过对文献[9]方案和本文方案进行数值模拟来分析方案的实际性能。在Linux 系统上使用PBC(Pairing-Based Cryptography)库，基于C语言实现文献[9]方案和本文方案，数值模拟环境参数配置如表3所示。

Table 3 Simulation environment configuration parameters

本文方案和文献[9]方案都实现了密文上多关键字的检索功能。在数值模拟实验中，索引生成、陷门生成和搜索过程均使用相同的关键字，增加关键字数量，统计在不同数量关键字下各个过程的计算开销。关键字的个数设置为100，200，300，400，500，600，700，800，900，1 000。本次实验结果采用运行程序100次的平均值，本文方案与文献[9]方案的实验结果如图4～图6所示。

Figure 4 Time of index generation图4 索引生成时间

Figure 5 Time of trapdoor generation图5 陷门生成时间

Figure 6 Retrieval time图6 检索时间

如图4所示，在索引生成阶段，本文方案与文献[9]方案的索引生成时间均与关键字的个数呈线性增长关系，本文方案的索引生成时间略高于文献[9]方案的,本文方案的关键字加密过程比文献[9]的多进行1次指数运算，但本文方案实现了区块链上的数据存储及检索功能，具有更高的安全性。

如图5所示，在陷门生成阶段，文献[9]方案陷门生成时间与关键字的个数呈线性增长关系，而本文方案关键字的增加不会影响陷门生成的时间，且本文方案中的陷门生成时间略低于文献[9]方案的，本文方案具有较高的陷门生成效率。

如图6所示，在数据检索阶段，本文方案与文献[9]方案的检索时间与关键字的个数呈线性增长关系，文献[9]方案的检索时间随关键字数量的增加速度比本文方案的要快，在不考虑密文存储平台的情况下，在支持多关键字搜索的同时，本文方案的检索效率要明显优于文献[9]方案的。

5 结束语

本文针对目前可搜索加密方案中云服务器诚实且好奇的特点和单关键字搜索效率低的问题，提出了区块链上多关键字的可搜索加密方案。在该方案中，每个参与的节点都是平等的，且无需指定关键字的位置，搜索者Q在交易中给数据使用者U返回正确的文档时需遍历文件中的所有关键字，Q将搜索到符合条件的所有文档以交易的形式返回给用户，提供更精确的检索服务。用户将所有的数据以交易的形式存储在区块链上，但区块的大小是有限的，因此虚拟链的使用将会是一个重点。