基于区块链的多关键词模糊搜索加密方案_闫玺玺.pdf

基于区块链的多关键词模糊搜索加密方案闫玺玺冯苏伟*汤永利尹沛(河南理工大学软件学院焦作454003)摘要：针对1对多数据密文共享中多关键词模糊匹配和用户公平性问题，该文提出一种基于区块链的多关键词模糊搜索加密方案。该文提出一种R-HashMap索引结构，通过使用对偶编码函数和位置敏感哈希函数来构建安全索引，并采用K最近邻算法来加密索引，通过计算欧式距离度量查询关键词向量与索引节点之间的相似性，实现多关键词模糊密文搜索。该文除了消除预定义词典和降低存储开销外，还在不增加搜索复杂度的前提下实现对安全索引的更新。此外，将以太坊区块链技术与可搜索加密方案相结合避免了恶意服务器对数据的篡改，使用智能合约作为可信第三方进行检索工作，不仅可以防止云服务器内部的关键词猜测攻击，还可以解决检索结果不正确的问题。通过安全性证明分析，该文不但满足自适应选择关键词语义安全性，还可以保护用户隐私和数据安全。将该文与其他方案进行实验对比，证明该文在保证精确度的前提下，时间开销上具有更好的效率优势。关键词：加密方案；多关键词；模糊搜索；可验证；以太坊智能合约中图分类号：TN918;TP309.2文献标识码：A文章编号：1009-5896(2023)04-1346-10DOI:10.11999/JEIT220207Multi-keyword Fuzzy Search Encryption SchemeBased on BlockchainYANXixiFENGSuweiTANGYongliYINPei(Software College,Henan Polytechnic University,Jiaozuo 454003,China)Abstract:Consideringtheproblemofmulti-keywordfuzzymatchinganduserfairnessinone-to-manydataciphertextsharing,amulti-keywordfuzzysearchencryptionschemebasedonblockchainisproposed.AnR-HashMapindexstructureisproposed.Thesecureindexisconstructedbyusingpairscodingfunctionandpositionsensitivehashfunction,andtheK-nearestneighboralgorithmisusedtoencrypttheindex.ThesimilaritybetweenthequerykeywordvectorandtheindexnodeiscalculatedbyEuclidiandistancemeasure,andthemulti-keywordfuzzyciphertextsearchisrealized.Inadditiontoeliminatingthepre-defineddictionaryandreducingthestorageoverhead,thisschemealsorealizestheupdateofthesecurityindexwithoutincreasingthesearchcomplexity.Inaddition,thecombinationofEthereumblockchaintechnologyandsearchableencryptionschemeavoidsdatatamperingbymaliciousservers,andtheuseofsmartcontractsastrustedthirdpartiesforretrievalworkcannotonlypreventkeywordguessingattackswithincloudservers,butalsosolvetheproblemofincorrectretrievalresults.Throughsecurityproofanalysis,theproposedschemenotonlysatisfiesthesemanticsecurityofadaptivekeywordselection,butalsocanprotectuserprivacyanddatasecurity.Theexperimentalcomparisonbetweenthisprogramandotherschemesprovesthattheprogramhasbetterefficiencyintermsoftimeandcostwhileensuringaccuracy.Key words:Encryptionscheme;Multi-keyword;Fuzzysearch;Verifiable;Ethereumsmartcontract收稿日期：2022-03-01；改回日期：2022-05-24；网络出版：2022-06-01*通信作者：冯苏伟BeiY基金项目：河南省高校基本科研业务费专项资金(NSFRF210312)，河南省青年人才托举工程项目(2021HYTP008)FoundationItems:TheFundamentalResearchFundsfortheUniversitiesofHenanProvince(NSFRF210312),TheYouthTalentSupportProgramofHenanAssociationforScienceandTechnology(2021HYTP008)第45卷第4期电子与信息学报Vol.45No.42023年4月JournalofElectronics&InformationTechnologyApr.20231 引言云存储的出现降低了用户的存储开销和管理开销，给人们带来了极大的便利。因此，许多个人或者企业习惯将自己的隐私数据部分或者全部存储在云服务器中，然而，实际生活中的云服务器往往是不可信的。所以，保护用户的隐私显得尤为重要。为了提高用户的隐私性，数据往往是通过加密的方式存储到云服务器，但这又带来了如何快速检索数据的问题。所以，可搜索加密1(SearchableEn-cryption,SE)应运而生，它是一种能够支持用户在密文上进行检索而不泄露用户隐私信息的技术。近年来，研究人员针对加密数据提出了一系列的思路和方法。2000年，Song等人1首次实现了对称可搜索加密技术。由于他们的开创性工作，引发了后续众多研究人员对外包数据的安全和隐私问题的研究，其中，模糊搜索方案因其能处理拼写错误或拼写相近的关键词而备受关注。Li等人2首次形式化了加密云数据上模糊关键词搜索问题，并设计了一种基于通配符的安全索引构建方案，该方案首先构造一个基于通配符的模糊关键词集，模糊集中的每个元素都被加密，搜索时，用户首先生成相同的加密模糊关键词集，然后云服务器找到对应的关键词，最后返回对应的文件。后续，Wang等人3在文献2的基础上进行了改进，提出了一种基于关键词的索引树结构的模糊关键词搜索的可搜索加密方案，提高了搜索效率。但上述方案都必须预定义一个词典，时间和存储开销比较大，且只支持单关键词搜索。目前，大多数模糊搜索方案在索引结构和功能上进行了拓展和创新。Kuzu等人4首次提出了一种基于Jaccard距离的模糊搜索方案。Wang等人5首次提出了基于布隆过滤器(BloomFilter,BF)和局部敏感哈希技术(Locality-SensitiveHashing,LSH)的多关键词模糊搜索加密方案，消除了预定义词典。后来，Fu等人6为了提高检索效率和精度，提出了一种改进的数据结构。然而，以上方案缺点就在于生成索引时初始化数据结构的规模较大，匹配算法不能很好地满足用户的检索需求，不支持方案的验证，保障不了用户的公平性。区块链被认为是一个可以帮助实体建立信任关系的系统，即使它们以前彼此不信任。随着区块链的发展7，将区块链与可搜索加密方案结合在一起实现可验证性可以有效解决第三方实体可不可信的问题，由于这种特性使其在可搜索加密方案中广受欢迎。例如，Li等人8提出了一个可搜索加密方案的区块链模型，并设计了一个自适应性加密方案。Yang等人9利用智能合约构建了一个多关键词可搜索加密方案，但是该方案不支持动态更新。文献10构建了一种细粒度的安全云端数据存储与删除方案，实现了细粒度访问控制，解决了第三方可信的问题和保证了结果的正确性，但该方案不支持结果优化且用户开销较大。因此，针对上述方案存在的安全性、效率和功能局限等问题，本文提出一种基于区块链的多关键词模糊搜索加密方案。利用区块链的不可篡改、透明性、可追溯性的特点11来保护用户的私有数据不会遭到泄露；同时采用R-HashMap的索引结构和安全K最近邻12算法(K-NearestNeighbor,KNN)来保障用户能够高效进行搜索、更新。本文的创新点如下：(1)引入区块链机制，将安全索引存储在区块链中、文件密文上传到云服务器，确保检索结果的正确性；借助区块链的不可篡改性来确保结果的正确性和用户的公平性，对文件进行编号，防止云服务器错误下发数据或者伪造搜索结果。(2)提出一种新的高效索引结构R-HashMap，以提高可搜索加密的效率；使用安全KNN算法测量不同关键字的欧式距离，通过设立阈值，可以满足模糊搜索；利用top-k算法对检索结果进行优化，可以更好地满足用户的查询需求。(3)安全性分析证实了方案满足自适应选择关键词语义安全和用户公平性。性能对比和实验分析表明，本方案在保证搜索精准度的前提下，提高了索引生成阶段、陷门生成阶段、模糊搜索阶段的效率，尤其索引生成阶段的效率相对提高1倍。2 预备知识R-HashMap索引结构O(log2n)HashMap是Java开发中的一个集合类13，它的底层数据结构主要由数组+链表+红黑树组成，虽然底层原理很复杂，但却能够高效地实现插入、删除、搜索等操作，时间复杂度为。p-stable LSHllCi(Li,vi,i)HashMap保留了数组和链表的特点，所以，本方案充分利用了这种结构的特点，通过函数14将相似的向量映射到R-HashMap数据结构的同一个桶中，不同的关键词映射到不同的桶中，然后根据桶中的关键词构成一个链表，最后得到安全高效的R-HashMap索引。如图1所示，它跟HashMap存储数据是相似的，不同之处就在于本文是采用随机投影算法，随机选取 个LSH函数和 个随机数进行一系列的计算得到哈希值，而HashMap仅采用哈希函数得到哈希值。本方案索引中的每个Node包含一个向量形式的关键字、哈希结果和文档信息，定义为。第4期闫玺玺等：基于区块链的多关键词模糊搜索加密方案13473 算法与安全模型定义3.1 模型系统模型如图2所示，主要包含4个实体，分别是数据拥有者(DataOwner,DO)、云服务器(CloudServer,CS)、智能合约15(SmartContract,SC)、授权用户(AuthorizedUser,AU)。DO首先对明文数据进行加密，接着为关键词构建安全索引，将安全索引和打包密文集合上传至SC，数据密文上传到CS。AU利用ID在DO端注册，DO选择自己信赖的用户(包括自己)，并为其生成陷门。AU将陷门提交给SC执行搜索操作，同时向CS发送密文请求。SC将陷门与索引进行匹配，然后将结果下发给CS和用户。CS搜索完成后，将结果发送给AU。AU得到结果后验证是否是合法文件，最后进行解密。3.2 算法定义本方案主要包括以下算法：KeyGen(1)skK：系统初始化算法。该算法输入安全参数，输出用户密钥sk和对称密钥。BuildIndex(sk,i,W)IiW：DO输入密钥sk，文档标识符 以及文件对应的关键词集合，输出安全索引I，接着将安全索引I提交给SC。Enc(i,Fi,K)(CT,N)FiKCi：由DO执行。DO首先将明文文档用对称密钥进行加密得到密文。iKN=Ni|i=1,2,.NiCiHiN