高效的可验证无证书可搜索加密方案.pdf

2023 年 8 月 Journal on Communications August 2023 第 44 卷第 8 期 通 信 学 报 Vol.44 No.8高效的可验证无证书可搜索加密方案 崔新华1,2,3，田有亮1,2,4，张起嘉1,2（1.公共大数据国家重点实验室，贵州 贵阳 550025；2.贵州大学计算机科学与技术学院，贵州 贵阳 550025；3.贵州师范大学经济与管理学院，贵州 贵阳 550025；4.贵州大学密码学与数据安全研究所，贵州 贵阳 550025）摘 要：在云计算环境中，可搜索加密方案是一种实现数据隐私保护和关键词搜索的有效方法。目前，现有方案不仅难以实现高效验证与动态更新，同时也存在证书管理和密钥分配问题。为了解决上述问题，近期有相关学者提出了一种基于改进 Merkle-Tree 认证方法的可验证多关键词搜索方案，然而经过安全性分析，该方案不能满足密文的不可区分性。通过改进，提出了一种新的高效的可验证无证书可搜索加密方案。分析表明，所提方案不仅能够满足无证书环境下的密文不可区分性与签名的不可伪造性，还实现了更高的计算效率与更小的通信开销，更能适用于资源有限的终端设备。关键词：无证书加密；可搜索加密；可验证性；动态更新 中图分类号：TP309 文献标志码：A DOI:10.11959/j.issn.1000436x.2023156 Efficient certificateless searchable encryption scheme with verifiability CUI Xinhua1,2,3,TIAN Youliang1,2,4,ZHANG Qijia1,2 1.State Key Laboratory of Public Big Data,Guiyang 550025,China 2.College of Computer Science and Technology,Guizhou University,Guiyang 550025,China 3.College of Economics and Management,Guizhou Normal University,Guiyang 550025,China 4.Institute of Cryptography&Data Security,Guizhou University,Guiyang 550025,China Abstract:Searchable encryption offers an effective way to achieve data privacy protection and keyword search in cloud computing environments.Currently,the existing schemes not only lack dynamic update and efficient verification me-chanism,but also suffer from the certificate management burden and key escrow issue.To address these issues,a verifia-ble multi-keyword searchable encryption scheme based on improved Merkle-Tree had been proposed recently.However,through cryptoanalysis,that scheme could not achieve the indistinguishability.With improvement,an efficient able certi-ficateless searchable encryption scheme with verifiability was proposed.Rigorous analysis show that the proposed scheme not only supports the indistinguishability and the unforgeability,but also enjoys higher computing efficiency and lower communication cost,which is more suitable for terminal devices with limited resources.Keywords:certificateless encryption,searchable encryption,verifiability,dynamic updating 收稿日期：20230317；修回日期：20230606 通信作者：田有亮， 基金项目：国家重点研发计划基金资助项目（No.2021YFB3101100）；国家自然科学基金资助项目（No.U1836205,No.62272123）；贵州省高层次创新型人才基金资助项目（黔科合平台人才20206008）；贵阳市科技计划基金资助项目（筑科合20211-5,筑科合20222-4）；贵州省科技计划基金资助项目（黔科合平台人才20205017,黔科合支撑2022一般 065）Foundation Items:The National Key Research and Development Program of China(No.2021YFB3101100),The National Natu-ral Science Foundation of China(No.U1836205,No.62272123),Project of High-level Innovative Talents of Guizhou Province(No.20206008),Science and Technology Program of Guiyang(No.20211-5,No.20222-4),Science and Technology Programof Guizhou Province(No.20205017,No.2022065)62 通 信 学 报 第 44 卷 0 引言 随着云计算技术的快速发展，为了满足用户日益增长的需求，互联网设备产生的数据量飞速增长。越来越多的企业与个人选择将数据存放在云服务器中，以缓解本地存储带来的压力。然而，当数据被上传至云服务器后，数据拥有者便失去了对数据的控制。特别是当数据中包含敏感信息时，数据拥有者难以对敏感信息提供安全保护。为了避免云服务器侵犯敏感数据的隐私性，需要将文件加密后再上传。然而，加密会导致数据之间的关联性被破坏，给文件检索带来了困难。为了解决云服务器对密文实现高效检索的问题，可搜索加密1成为最受研究者关注的方法之一。现有的可搜索加密方案中，公钥可搜索加密（PEKS）2-3相比于对称可搜索加密（SSE,symmetric searchable encryption）4-5更适用于云存储环境中的文件共享等场景，因此成为一个重要的研究热点。PEKS 引入了非对称的搜索陷门，以关键词密文与搜索陷门能否匹配作为搜索成功的判断依据。具体来说，数据拥有者首先需要依次对准备上传的文件提取关键词，然后利用文件接收者的公钥计算生成关键词密文。接下来，数据拥有者将数据文件加密，再将文件密文与关键词密文相连接，形成密文索引并一同上传至云服务器中进行存储。数据用户在对目标文件发起搜索前，首先需要确定目标文件的关键词，并使用私钥生成搜索陷门，然后作为搜索请求发送给云服务器。云服务器接收到搜索请求后，对密文索引进行匹配测试，最后将匹配到的密文作为搜索结果返回给数据用户。在此期间，不可信的云服务器虽然执行存储与匹配任务，却无法得知任何关于数据文件的信息。然而，在现实环境中云服务器可能会因为经济利益或黑客攻击等因素，恶意地发动选择性转发攻击6，即只返回部分搜索结果给用户。而在目前大多数的 PEKS 方案中，用户缺乏搜索结果的验证机制，无法检测返回的搜索结果是否完整或是否已经被恶意篡改。为了抵抗恶意云服务的攻击，可验证性7-9为用户提供了搜索结果的审查机制，成为研究目标之一。Sun 等10提出了一种可验证的多关键词可搜索加密方案。该方案采用基于树的数据结构作为索引，以实现搜索结果的完整性验证。Wang 等11结合布隆过滤器（BF,Bloom filter）、Merkle 哈希树（MHT,Merkle hash tree）等数据结构，提出了一种外包数据库的审计协议。然而，该协议只能实现静态审计，无法适用于云计算中的动态更新场景。随后，大量支持动态更新的可验证的可搜索加密方案被提出6,12-13。然而，这些方案在更新过程中带来的计算开销与通信开销较大，有待进一步降低。因此，对搜索结果实现高效验证与密文的高效更新仍是亟待解决的难题。大多数 PEKS 方案都是基于证书或基于身份的公钥密码，存在证书管理以及密钥托管问题。为了解决该问题，Peng 等14提出了第一个基于无证书的公钥可搜索加密（CLPEKS,certificateless public key encryption with keyword search）方案，该方案将无证书的公钥密码引入 PEKS 中，为传统的 PEKS 方案提升了抗恶意用户与半诚实的密钥生成中心的安全性。此后，大量的研究人员对基于无证书的 PEKS 方案进行了研究15-18。Zheng 等19提出了一个不需要用户执行对运算的无证书可搜索加密方案，该方案显著降低了用户的计算量，提升了方案的实用性。Miao 等20实现了一种基于无证书的可验证的多关键词可搜索加密方案，该方案不仅基于 Zheng 等19方案实现了无证书加密，还将云审计与可搜索加密相结合，采用可信的第三方审计服务器协助用户对搜索结果进行验证。田有亮等21在 Miao 等20方案的基础上提出了一种基于改进 Merkle 树认证方法的可验证多关键词可搜索加密方案，与之前的方案相比，该方案将验证过程中的计算开销由经典 MHT 的 O(n)降低到 O(logn)，实现了高效验证与更新。然而，经过本文分析，该方案存在明显的安全性缺陷，无法达到文中声称的安全要求。张键红等6提出了一种高效、可验证的多关键词搜索加密方案，该方案不仅能够支持多关键词搜索，还实现了搜索模式的隐私性和文件的前向安全。为了实现安全高效可验证的密文检索，同时满足无证书公钥加密环境中的安全性，本文提出了一种高效的可验证无证书可搜索加密方案。本文的主要贡献如下。1)首先，对文献21方案进行了安全性分析，指出了其既不能满足密文的选择明文攻击的不可区分（IND-CPA）安全，也不能满足适用于可搜索加密的选择关键词攻击的不可区分（IND-CKA）安全。然后，给出了 2 种具体的攻击，即外部攻第 8 期 崔新华等：高效的可验证无证书可搜索加密方案 63 击者发动的密文猜测攻击，以及恶意用户发动的在线关键词猜测攻击。2)提出了一种高效的基于无证书的可搜索加密方案。在随机预言机模型下，基于判定性线性（DLIN,decisional linear）假设与计算性DH（co-CDH,co-computational Diffie-Hellman）假设，证明了所提方案满足选择关键词攻击下的不可区分性与签名的不可伪造性。3)通过结合改进的 MHT 与无证书签名，实现了高效可验证性与高效动态更新，通过实验与其他现有主流方案进行对比，分析表明了所提方案在计算效率方面与通信效率方面均优于其他相关方案，具有更高的实用价值。1 基础知识 本节首先介绍了双线性对的概念和本文用到困难假设，然后给出了无证书可搜索加密方案的形式化定义和相关的安全模型。1.1 双线性对 设为安全参数，p 为与相关的大素数，12GG、和TG为 3 个阶为p的乘法循环群。定义1 双线性映射。若映射12:Te GGG满足以下3个条件，则该映射为一个双线性映射。1)双线性：对于任意元素1122,gG gG和,pa bZ，均有1212(,)(,)ababe gge g g。2)非退化性：至少存在元素11gG和22gG，满足12(,)1e g g。3)可计算性：对于任意元素11gG和22gG，均有多项式时间算法计算12(,)e g g。根据群1G与2G的不同关系，双线性映射可分为2类。若12GG，则该双线性映射为Type-1类型；若12GG，且1G与2G之间存在一个同构映射，使21()GG，则该双线性映射为Type-2类型。1.2 困难假设 定义 2 co-CDH假设。给定四元组 12(,g g 1ag22212,)bgGG，其中,pa bZ未知，对于任意的多项式时间算法A，计算得出1abg的优势是可忽略的，数学形式表示为 co-CDH12121Adv()Pr(,)ababAA g gggg 定义 3 DLIN假设。给定六元组(,u v w,cv,)dwZ，其中,pc dZ未知，且1(,)cu v v ZG，2(,)dw wG。对于任意的多项式时间算法A，判定c dZu是否成立的优势是可忽略的，数学形式表示为 DLINAdv()Pr(,)1Pr(,)1cdc dAcdA u v w v wuA u v w v wZ 1.3 Merkle 哈希树 经典Merkle哈希树是一种二叉树数据结构，将数据分成若干个块，然后对每个块计算哈希值，作为叶子节点。输入相邻的2个叶子节点的哈希值，再计算生成一个新的哈希值，作为这2个叶子节点的父节点。递归进行该操作，直到得到一个根节点，它可以确保所有节点的完整性，因此可以作为整个数据的哈希值。Garg等22提出了一种基于相对索引和时间戳的Merkle哈希树，通过修改搜索算法实现了高效动态更新。改进Merkle树的每个节点包括2个信息：一个是数据块的哈希值，另一个是相对索引。与节点T关联的相对索引是指属于T的子树的叶子节点的数量，叶子节点的索引值为1。例如，如果T的左右节点分别为Lefth和Righth且相对索引为Lefti和Righti，则T的哈希值为LeftRight(,)H hh，索引值为左右节点的相对索引之和LeftRight()ii。根节点Rooth的生成方式为RootLeftRight(,)thH hhd，其中，时间戳td表示Merkle树创建的时间，根节点只对树中任意数据块做出修改而更新，且只有在有效时间内才能通过验证，因此能够保证数据的有效性。1.4 形式化定义 如图1所示，无证书可搜索加密系统模型中包含4个不同的实体：密钥生成中心（KGC,key generation center）、数据拥有者（DO,data owner）、数据用户（DU,data user）以及云服务器（CSP,cloud service provider）。图 1 系统模型 64 通 信 学 报 第 44 卷 1)密钥生成中心。KGC为一个半诚实的实体，负责根据安全参数生成系统主密钥与系统公开参数，以及为每个数据拥有者与用户生成部分私钥。KGC会对密文中包含的信息产生好奇，能够利用已知的系统主密钥等关键信息发动猜测攻击，以及勾结云服务器伪造验证信息。2)数据拥有者。数据拥有者为一个诚实的实体，负责生成自己的公私钥，并使用私钥生成验证信息；还负责使用用户的公钥生成关键词密文，创建密文索引，最后将密文文件、密文索引与验证信息一同上传至云服务器中。除此之外，数据拥有者还能够对密文进行修改、添加、删除等更新操作。3)数据用户。数据用户为一个可能存在恶意的实体，但不与其他实体相互勾结。数据用户负责向云服务器提出搜索请求，以及收到结果后对结果进行验证。恶意用户可能伪装成合法用户伪造搜索陷门，也可能对验证信息发动伪造攻击。4)云服务器。云服务器为一个半诚实的实体，负责存储数据拥有者上传的信息、帮助数据用户执行搜索、协助数据拥有者完成密文更新操作。在操作过程中，云服务器可能会对密文中包含的信息产生好奇。定义 4 可验证的无证书可搜索加密方案。可验证的无证书可搜索加密方案通常包括以下7个多项式时间算法。1)Setup()。该算法由KGC执行。输入安全参数，生成系统主密钥msk，发布系统公开参数params。2)ParKeyGen(params,msk,ID)。该 算 法 由KGC执行。输入系统主密钥msk、系统公开参数params以及用户ID，生成用户的部分私钥psk。3)KeyGen(params,psk,ID)。该算法由用户执行。输入部分私钥psk、系统公开参数params以及用户ID，生成用户的私钥Usk与公钥Upk。4)UOEncrypt(params,Files,pk,sk,ID)w。该算法由数据拥有者执行。输入系统公开参数params、数据拥有者私钥Osk以及数据文件Files，生成验证信息v。然后输入用户公钥Upk与关键词w，生成关键词密文CT。5)UTrapdoor(params,sk)w。该算法由数据用户执行。输入系统公开参数params、私钥Usk、关键词w，生成搜索陷门T。6)Search(,CT)T。该算法由CSP执行。输入搜索陷门T和关键词密文CT，由CSP计算是否匹配，若匹配成功，则将文件密文以及相应的验证信息返回给用户。7)OVerify(params,pk,Files)v。该算法由数据用户执行。输入系统公开参数params、数据拥有者公钥Opk、验证信息v以及解密文件Files，输出验证结果1（成功）或0（失败）。1.5 安全模型 无证书可搜索加密考虑2种类型的敌手：Type-1类型的敌手IA代表恶意用户，无法得知系统主密钥msk，但可以发动公钥替换攻击，伪装成一个合法用户伪造搜索陷门或签名；Type-2类型的敌手IIA代表诚实且好奇的KGC，能够掌握系统主密钥msk，以及掌握每个用户的部分私钥psk，但无法得知用户私钥，也无法伪装成其他用户。本文通过以下4个挑战者C与敌手IA、IIA之间的安全游戏来定义方案的安全模型，其中，Game1与Game2为针对密文的IND-CKA游戏，Game3与Game4为针对签名的EUF-CMA游戏。Game1 此处的敌手为IA。1)初始化。挑战者C运行Setup算法，设置公共参数。然后设置系统主密钥，计算系统公钥。最后将生成的系统公共参数与公钥发送给敌手IA。2)哈希询问。敌手IA在该阶段对2个随机预言机分别进行多项式有限次的询问，挑战者C维护2个初始为空的列表，用来记录每次询问。3)阶段1。在该阶段，敌手IA向挑战者C进行多项式有界次适应性询问，内容包含以下4项。ParKeyGen询问。敌手IA向挑战者C发送一个身份ID。当ID与挑战者身份相同时，中止游戏；否则，挑战者C在收到ID后，查询哈希列表并计算部分私钥psk，返回给敌手。KeyGen询问。敌手IA向挑战者C发送一个身份ID。当ID与挑战者身份相同时，中止游戏；否则，挑战者C执行ParKeyGen算法，然后计算公私钥对(sk,pk)，并返回给敌手。Replace-KeyGen询问。挑战者C首先建立一个初始为空的列表。敌手IA随机生成一个公钥pk。随后向挑战者C发送想要替换的身份ID与替换公钥pk，挑战者C将身份ID对应的公钥pk使用pk替换，并将其存储在列表中。Trapdoor询问。敌手AI向挑战者C发送一个第 8 期 崔新华等：高效的可验证无证书可搜索加密方案 65 身份ID与一个关键词w。挑战者C首先对于ID执行ParKeyGen询问与KeyGen询问，然后计算Trapdoor并返回给敌手IA。4)挑战。敌手IA向挑战者C发送一个身份ID与2个长度相同的关键词01,w w。ID与01,w w曾经被询问过，则中止游戏；否则，挑战者C随机抛出一枚硬币0,1b，计算关于ID与bw的密文，返回给敌手。5)阶段2。与阶段1相同，唯一的限制是敌手IA不能询问关于挑战密文的关键词，也不能询问挑战者的私钥与部分私钥。6)猜测。敌手IA输出一个比特0,1b，若 bb，则敌手获胜。定义 5 对于多项式时间内的敌手IA，赢得IND-CKA游戏的优势为 IIND-CKA1Adv()Pr 2Abb Game2 此处的敌手为IIA。Game2与Game1相似，区别是不需要执行ParKeyGen询问与Replace-KeyGen询问，且Setup阶段需要发送系统密钥给敌手IIA。Game3 此处的敌手为IA。1)初始化。挑战者C运行Setup算法，设置公共参数。然后设置系统主密钥，计算系统公钥。最后将生成的系统公共参数与公钥发送给敌手IA。2)哈希询问。敌手IA在该阶段对2个随机预言机分别进行多项式有限次的询问，挑战者C维护2个初始为空的列表，用来记录的每次询问。3)询问阶段。在该阶段，敌手IA向挑战者C进行多项式有界次适应性询问，内容包含以下4项。ParKeyGen询问。敌手IA向挑战者C发送一个身份ID。当ID与挑战者身份相同时，中止游戏；否则，挑战者C在收到ID后，查询哈希列表并计算部分私钥psk，返回给敌手。KeyGen询问。敌手IA向挑战者C发送一个身份ID。当ID与挑战者身份相同时，中止游戏；否则，挑战者C执行ParKeyGen算法，然后计算公私钥对(sk,pk)，并返回给敌手。Replace-KeyGen询问。挑战者C首先建立一个初始为空的列表。敌手IA随机生成一个公钥pk。随后向挑战者C发送想要替换的身份ID与替换公钥pk，挑战者C将身份ID对应的公钥pk使用pk替换，并将其存储在列表中。Signature询问。敌手IA向挑战者C发送一个身份ID与一个消息m。挑战者C首先对ID执行ParKeyGen询问与KeyGen询问，然后计算签名并返回给敌手IA。4)伪造。敌手IA向挑战者C发送一个身份ID、一个关于ID的公钥、一个消息m*以及对应的签名*。若ID与消息m*的签名曾经被询问过，则中止游戏；否则，敌手IA赢得该游戏。定义 6 对于多项式时间内的敌手IA，赢得EUF-CMA游戏的优势为 IEUF CMAAdv()PrVer(*,*,ID,pk)1Am Game4 此处的敌手为IIA。Game4与Game3相似，区别是不需要执行ParKeyGen询问与Replace-KeyGen询问，且Setup阶段需要发送系统密钥给敌手IIA。2 对文献21方案的安全性分析 本节首先简要回顾文献21中的方案，然后指出其不能满足密文不可区分性，并给出2种具体的攻击过程。2.1 对文献21中方案的描述 由于篇幅限制，本节只简要描述其Setup、ParKeyGen、KeyGen、Encryption、Trapdoor Generation以及Search算法。方案的详细设计请参考文献21。1)Setup。输入安全参数，选定一个双线性映射:Te GGG，其中，G是阶为素数p的一个乘法循环群，g是群G的生成元。KGC首先选择2个随机元素*,px yZ作为系统主密钥，计算,xygg并作 为 系 统 公 钥。选 择n+1个 随 机 元 素1,nu uuG，然 后 定 义 一 个 哈 希 函 数ID11(ID)iniiHuu，其中1IDID,ID n。选择一个哈希函数*00,1pHZ：。最后，保留系统主密钥msk,x y，公开系统公共参数 011param,xyng HH u uugg 2)ParKeyGen。给定用户身份ID，KGC随机选择*ptZ，为用户生成部分私钥 1psk,(ID)txtgg H 3)KeyGen。用户随机选择*,px yZ，计算用户 公 钥pk,xygg，并 保 留 用 户 私 钥66 通 信 学 报 第 44 卷 skpsk,x y。4)Encryption。给定文件对应的关键词集1,nWww，以及搜索用户的身份ID，数据拥有者随机选择*12,pr rZ，并计算关键词密文CT 11rCg 0112()()()2yHW rx xrrCgg 23rCg 241(ID)rCH 5)Trapdoor Generation。给定搜索关键词集1,nWww，搜索用户随机选择*psZ，并计算搜索陷门Tw 1tsTg ()21(ID)x x stsTgH 3sTg 0()()4syHWx xTgg 6)Search。服务器收到搜索用户发来的Tw后，计算并验证式(1)是否成立。32231441(,)(,)(,)(,)e C Te C Te C Te C T(1)若式(1)成立，则返回相应的密文给搜索用户；否则，匹配失败，终止搜索。2.2 针对 IND-CKA 的攻击 本节通过分析证明文献21方案无法达到其声称的IND-CKA安全。在IND-CKA安全游戏中，敌手在挑战阶段向挑战者发送2个长度相等的关键词集*0W和*1W，挑战者随机选择0,1b，生成相应的关键词密文*CTb，并发送给敌手。而敌手在收到关键词密文后，不需要知道用户私钥便可以区分出其中的关键词信息，进而得出正确的b。敌手通过伪造生成合法的搜索陷门，与挑战密文进行匹配，实现对挑战关键词的区分。具体操作如下。1)随机选择*psZ，利用公开的系统参数与用户公钥，生成*1W相关的伪造陷门*1wT 1sTg ()21(ID)x x ssTgH 31TT *01()()4syHWx xTgg 2)根据挑战阶段中接收到的挑战密文，验证式(2)是否成立。*322314*41(,)(,)(,)(,)e C Te C Te C Te C T(2)显然，若式(2)成立，则密文中包含的关键词集为*1W；若式(2)不成立，则密文中包含的关键词集为*0W。因此，敌手攻击成功，同时证明该方案不满足可搜索加密的IND-CKA安全。2.3 针对密文机密性的关键词猜测攻击 本节通过分析证明文献21方案无法实现密文的机密性。具体来说，诚实且好奇的云服务器能够对存储的关键词密文发动关键词猜测攻击。详细过程如下。对于一个包含关键词集1,nWww的密文CT，有 11rCg 0112()()()2yHW rx xrrCgg 23rCg 241(ID)rCH 诚实且好奇的云服务器首先计算 011212()()()(,)(,)yHW rx xrre Cge ggg 然后，利用给定的系统公钥,xygg以及用户公钥xg，计算 21331(,)(,)xxye g gC Ce gC 假设猜测的关键词集为*W，则云服务器计算 *0*()23HWW (3)最后，验证式(4)是否成立。*1W(4)当*WW时，则有 0*0012101210121()23()131()()()()()()()()()1(,)(,)(,)(,)(,)(,)(,)HWWHWxxyHWrrrx xyyHWx xrrryHWx xrrre g gC C e gCe gge gge gg e gge ggg (5)第 8 期 崔新华等：高效的可验证无证书可搜索加密方案 67 由于现实世界中的关键词的明文空间有限，攻击者可以通过对所有可能的关键词集*W进行有限次穷举，对式(3)进行大量计算，得到的*W分别使用式(4)进行对比，便可在多项式时间内成功猜测出密文CT中所包含的关键词明文信息。因此，该方案不满足关键词密文的机密性。3 所提方案 下面给出本文提出的高效的可验证无证书可搜索加密方案。3.1 系统初始化 给定安全参数，KGC首先生成一个Type-2类型的双线性映射12:Te GGG，其中12,G G均是阶为素数p的乘法循环群，1g为1G群的生成元，2g为2G群的生成元。KGC选择2个随机元素*,px yZ作为系统主密钥，并计算112,xyyggg作为系统公钥。然后，KGC选择如下5个哈希函数。dateIDIDkw12231*415:0,10,10,10,1,:0,1,:0,1,:0,1,:0,1lnnnlllpHHG HGHG HZ 最后，KGC保留系统主密钥msk,x y，公开系统公共参数 1212345112params,xyyg gH HHHHggg 3.2 部分私钥生成 给定身份ID，通过执行该算法，KGC分别生成数据用户与数据拥有者的部分私钥，具体步骤如下。1)对于数据用户，输入U(msk,ID,params)，其中，UID为长度为IDl的比特串，表示用户的身份。KGC随机选择ptZ，并计算 U,11psktg,U,222Upsk(ID)xtg H 2)对于数据拥有者，输入O(msk,ID,params)，其中，OID为数据拥有者的身份。KGC随机选择ptZ，并计算 O,12psktg,O,213Opsk(ID)xtg H 然后将2个部分私钥UU,1U,2psk(psk,psk)与OO,1O,2psk(psk,psk)通过安全信道分别发送给数据用户与数据拥有者。3.3 公私钥生成 在收到部分私钥后，数据用户随机选择一个*pxZ，然后计算1xg。则数据用户的公私钥为U1pkxg，UUskpsk,x。同时，数据拥有者随机选择一个*pyZ，计算生 成 数 据 拥 有 者 的 公 私 钥O2pkyg，OOskpsk,y。3.4 密文生成 首先，数据拥有者对数据文件进行提取关键词处理。对于包含相同关键词集1,nWww的文件if，数据拥有者使用对称加密算法（如SM4）对其进行加密处理，生成数据文件密文1,qccc。其次，计算每个密文ic的哈希值ih，再将每个文件的哈希值作为叶子节点，每个叶子节点作为哈希函数3H的输入，迭代生成MHT。其中，根节点Root1LeftRight(|)thH hhd为一个n位长的序列。由左右叶子节点与系统时间戳td共同计算生成。系统时间戳td表示一个有效时间段（如一天、一周或一个月），若时间段有效，则系统生成的时间戳相同。数据拥有者输入自己的身份OID、私钥Osk、公钥Opk，生成根节点的签名 1O,1psk 2O,24O2Rootpsk(ID,)yytHghd 并将Root12(,)vh 作为搜索结果的验证信息。然后，给定系统公钥11,xygg以及数据用户的UID与公钥1xg，数据拥有者随机选择*prZ，对关键词iwW计算生成关键词密文wC 11rCg 5()()211()yHwx x yrCgg 32U(ID)rCH 最后，数据拥有者将,WCv c一同上传至云服务器中进行存储，其中，123(,)WCC C C。3.5 陷门生成 数据用户想要在云服务器中搜索感兴趣的文件，首先需要输入特定的关键词wW，然后随机选择一个元素*psZ，计算生成搜索陷门wT 11tsTg 5()()222U2(ID)yHwx x ytsTgHg 32sTg 最后，将搜索陷门wT提交给云服务器。68 通 信 学 报 第 44 卷 3.6 密文搜索 云服务器收到用户发送的搜索陷门wT后，将其与存储的关键词密文wC进行匹配，计算并判断式(6)是否成立。132312(,)(,)(,)e T C e C Te C T(6)若式(6)成立，则说明关键词密文与陷门匹配一致，将数据文件密文1,qccc以及相应的验证信息Root12(,)vh 返回给用户。3.7 结果验证 数据用户收到返回的搜索结果后，出于对云服务器的不信任，需要对搜索结果进行验证 首先，将数据文件密文1,qccc作为输入，依次计算哈希值1,qhh。然后，将得到的哈希值1,qhh作为叶子节点重建MHT，同时输入系统生成的时间戳td，得到根节点Root1LeftRight(,)thH hhd。最后，输入Rooth、数据拥有者的公钥与系统公钥，验证签名?22123O1O(,)(,)(ID),)(,pk)xege gg e He(7)其中，4OORoot(ID,pk,)tHhd。若式(7)成立，则通过验证，同时证明搜索结果满足正确性与完备性。3.8 动态更新 当数据拥有者希望对存储在云服务器上的文件进行修改或添加时，首先向服务器认证自己的身份。当身份验证通过后，通过以下方式对文件进行更新。1)数据修改。数据拥有者向云服务器发送修改令牌(,)itX i c d，其中，X表示修改操作，i表示待修改的文件所处的位置信息，ic表示更新后的文件，td表示系统时间戳。云服务器收到修改令牌后，执行以下操作，原始密文MHT如图2所示。首先，使用ic替换原来的文件。其次，计算ic的哈希值，并根据文件的位置信息对原有的MHT中对应的路径上的节点进行更新。最后，输入更新后的MHT以及td，计算新的根节点Root1LeftRight(|)thH hhd，并将Rooth与MHT发送给数据拥有者。数据拥有者根据收到的MHT对云服务器进行挑战，挑战内容包括验证文件的哈希值，以及文件是否被正确更新。通过挑战后，数据拥有者计算Rooth的签名，生成新的验证信息Root(,Sig)vh，并发送给云服务器。云服务器使用收到的Root(,Sig)vh替换原有的验证信息。图 2 原始密文 MHT 2)数据添加。数据拥有者向云服务器发送文件令牌(,)itI i c d，其中，I表示插入操作，i表示想要将文件插入的位置信息，ic表示想要插入的文件，td表示系统时间戳。云服务器收到插入令牌后，执行以下操作（如图3所示）。首先，在MHT中找到位置i的对应的叶子节点，复制该节点的哈希值。将该节点作为父节点，使用该哈希值生成右叶子节点。然后，计算待插入文件ic的哈希值，并作为原位置i节点的左叶子节点。接下来，根据新生成的两个叶子节点计算生成哈希值，并替换原有的父节点，依次类推，计算并替换该路径上除根节点外的全部节点的值，得到更新后的MHT。最后，输入td与得到的MHT，计算Root1LeftRight(|)thH hhd，并将Rooth与MHT发送给数据拥有者。数据拥有者根据收到的MHT对云服务器进行挑战。通过挑战后，数据拥有者计算生成新的验证信息Root(,Sig)vh，并 发 送 给 云 服 务 器。云 服 务 器 使 用 收 到 的Root(,Sig)vh替换原有的验证信息，然后将文件ic插入指定位置。图 3 数据添加过程 3)数据删除。数据拥有者向云服务器发送文件令牌(,)tD i d，其中，D表示插入操作，i表示待删除的文件的位置信息，td表示系统时间戳。云服务器收到删除指令后，执行以下操作（如图4所示）。首先，删除位置i对应的文件。其次，在MHT中找到位置i对应叶子节点，以及相同父节点下的另一个叶子节点i。使用节点i的值替换父节点的第 8 期 崔新华等：高效的可验证无证书可搜索加密方案 69 值，并将叶子节点i删除。计算并替换该路径上除根节点外的全部节点的值，得到更新后的MHT。最后，输入td与得到的MHT，计算新的根节点Rooth，并将Rooth与MHT发送给数据拥有者。数据拥有者根据收到的MHT对云服务器进行挑战。通过挑战后，数据拥有者计算生成新的验证信息Root(,Sig)vh，并发送给云服务器。云服务器使用收到的Root(,Sig)vh替换原有的验证信息。图 4 数据删除过程 4 方案分析 本节针对所提方案的正确性与安全性给出了具体的证明。4.1 正确性分析 在搜索阶段，为了保证方案中的云服务器能够严格地对关键词密文与搜索陷门进行匹配，对于式(6)，有 551323()()12112()1212Left(,)(,)(,(ID)(,)(,(ID)(,)yHw rtsrx x y rssr x x yyHwtsre T C e C Te gHe ggge g He g g 5512()()1222()1212Right(,)(,(ID)(,(ID)(,)yHwrx xytssr x x yyHwtsre C Te ggHge g He g g 当wT与wC中包含的关键词相同时，即ww，则有132312(,)(,)(,)e T C e C Te C T，因此式(6)成立。在结果验证阶段，为了保证搜索结果的正确性与完备性，对于式(7)，有 22O,2213O2123O22123O1O(,)(psk,)(ID),)(,)(ID),)(,)(,)(ID),)(,pk)yxtyxtyxegege g Hge gg e Hg e