摘 要：

針對傳統(tǒng)對稱可搜索加密方案靈活性和安全性不足的問題，提出了一種自適應(yīng)安全的區(qū)塊鏈模糊多關(guān)鍵詞可搜索加密方案。首先，使用局部敏感哈希模糊處理關(guān)鍵詞，并為各文件生成雙布隆過濾器存儲和隱藏關(guān)鍵詞，再以其為葉子節(jié)點結(jié)合基于圖的關(guān)鍵詞劃分算法構(gòu)造索引樹，從而實現(xiàn)亞線性模糊多關(guān)鍵詞搜索；其次，將默克爾哈希樹與自適應(yīng)多集累加器結(jié)合，用于驗證搜索結(jié)果的正確性和完整性；此外，聯(lián)盟鏈共識選舉輪換產(chǎn)生授權(quán)節(jié)點管理加密密鑰，鏈上部署智能合約執(zhí)行添加和搜索交易，并提出以全局時間作為共識中間參考的存儲優(yōu)化機(jī)制，從而使得搜索安全可信并減少鏈上存儲開銷；最后，安全分析證明方案可抵抗自適應(yīng)選擇關(guān)鍵詞攻擊，仿真實驗證明方案可實現(xiàn)亞線性多關(guān)鍵詞搜索，具有實際應(yīng)用價值。

關(guān)鍵詞：模糊多關(guān)鍵詞；自適應(yīng)安全；可搜索加密；區(qū)塊鏈

中圖分類號：TP309"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號：1001-3695（2024）12-004-3553-10

doi： 10.19734/j.issn.1001-3695.2024.03.0107

Adaptive secure fuzzy multi-keyword searchable encryption scheme based on blockchain

Zhai Shepinga， b， Zhang Ruitinga， Yang Ruia， Liu Jiayitenga

（a.School of Computer Science amp; Technology， b.Shaanxi Key Laboratory of Network Data Analysis amp; Intelligent Processing， Xi’an University of Posts amp; Telecommunications， Xi’an 710121， China）

Abstract：

Aiming at the lack of flexibility and security of traditional symmetric searchable encryption schemes， this paper proposed an adaptive and secure blockchain fuzzy multi-keyword searchable encryption scheme. Firstly， it utilized the local sensitive hash to fuzzily process the keywords， and generated a double bloom filter for each file to store and hide the keywords. Then， it constructed the index tree with the leaf nodes integrated with the graph-based keyword partitioning algorithm， so as to realize the sub-linear fuzzy multi-keyword search. Secondly， it combined Merkle hash tree with adaptive multi-set accumulator to validate the correctness and completeness of search results. In addition， it implemented an alliance chain consensus election mechanism to rotate and designate authorized nodes for managing encryption keys， deployed smart contracts on the blockchain to automate addition and search transactions， and proposed a storage optimization mechanism with global time as the consensus intermediate reference to enhance search security and reliability， and reduce on-chain storage overhead. Finally， the security analysis proves that the scheme can resist the adaptive keyword attack， and the simulation experiment proves that the scheme can realize sub-linear multi-keyword search， which has practical application value.

Key words：fuzzy multi-keyword; adaptive security; searchable encryption; blockchain

0 引言

隨著全球信息化與數(shù)據(jù)共享程度越來越高，云計算的普及有效節(jié)約了成本并增強(qiáng)了共享靈活性，因此數(shù)據(jù)外包越來越普遍。然而，云服務(wù)提供商通常為半誠實的第三方，極易泄露外包數(shù)據(jù)的隱私。為了增強(qiáng)數(shù)據(jù)的隱私性，可以對外包數(shù)據(jù)加密，但是加密會阻礙數(shù)據(jù)的搜索和共享。對稱可搜索加密（symmetric searchable encryption，SSE）［1］為基于關(guān)鍵詞的密文搜索提供了一種有效的解決方案。此外，為了解決用戶實際關(guān)鍵詞搜索過程中可能存在的拼寫錯誤、形式類似等問題，已有方案基于傳統(tǒng)SSE實現(xiàn)了模糊單或多關(guān)鍵詞密文搜索。Zhang等人［2］在加密數(shù)據(jù)上實現(xiàn)了模糊單關(guān)鍵詞可排序搜索，但會額外返回許多不相關(guān)的搜索結(jié)果，并且相比于單關(guān)鍵詞，模糊多關(guān)鍵詞搜索可以更貼切地描述用戶真實需求。吳曦等人［3］采用布隆過濾器和局部敏感哈希實現(xiàn)了模糊匹配；魏國富等人［4］在模糊搜索的基礎(chǔ)上，引入詞頻-逆向文件頻率（term frequency-inverse document frequency，TF-IDF）實現(xiàn)了搜索結(jié)果排序。Liu等人［5］利用編輯距離實現(xiàn)了一種基于通配符的模糊多關(guān)鍵詞搜索，同時支持聯(lián)結(jié)詞（AND和OR）語義搜索，但是以上方案的搜索復(fù)雜度會隨著文件數(shù)量呈線性增長。為提升搜索效率，Chen等人［6］設(shè)計了兩階段索引結(jié)構(gòu)，Zhong等人［7］構(gòu)建了平衡二叉樹。然而，現(xiàn)有的模糊多關(guān)鍵詞搜索方案仍然存在一定的安全隱患。

已有使用安全K近鄰（secure K nearest neighbor，KNN）技術(shù)的模糊多關(guān)鍵詞搜索方案［8～10］無法抵抗已知明文攻擊（known-plaintext attack，KPA），更不可能抵抗自適應(yīng)選擇關(guān)鍵詞攻擊（adaptively chosen-keyword attack，IND-CKA2）。在安全KNN中，數(shù)據(jù)向量p和搜索請求向量q會被分別加密為索引和陷門，如果存在N個明-密文對的搜索請求，那么將會暴露最多包含N個未知數(shù)的數(shù)據(jù)向量；如果利用信號處理理論，甚至在純密文攻擊中也能推斷出數(shù)據(jù)向量。然而，一旦數(shù)據(jù)向量被暴露，相應(yīng)外包數(shù)據(jù)的隱私性就無法保證。為了解決這一問題，文獻(xiàn)［11～13］將屬性基加密與可搜索加密結(jié)合，方案實現(xiàn)了抵抗KPA，但是只支持關(guān)鍵詞的精確搜索并且無法保證謂詞隱私。Liu等人［14］提出了滿足IND-CKA2安全的方案，但是主要支持單關(guān)鍵詞搜索。因此，如何設(shè)計可搜索加密方案實現(xiàn)可抵抗IND-CKA2的模糊多關(guān)鍵詞搜索，同時一定程度上提升搜索效率是當(dāng)前研究有待解決的問題。

除了數(shù)據(jù)和謂詞隱私安全之外，搜索還應(yīng)保證結(jié)果的正確性和完整性。在實際應(yīng)用中，由于經(jīng)濟(jì)利益、硬件錯誤、黑客攻擊等原因，半誠實的云服務(wù)商可能會不實搜索或在已被竄改的數(shù)據(jù)上執(zhí)行搜索，從而返回虛假或缺失的搜索結(jié)果。因此，為保護(hù)用戶利益，需要驗證結(jié)果。在正確性驗證方面，文獻(xiàn)［14］使用RSA累加器對搜索結(jié)果生成證明，計算開銷極大；張曉均等人［15］使用消息認(rèn)證碼（message authentication code，MAC）技術(shù)對每個索引進(jìn)行認(rèn)證，用于快速匹配測試密文和搜索陷門；Tong等人［16］根據(jù)默克爾哈希樹（Merkle hash tree，MHT）提出了一種基于已驗證樹的索引結(jié)構(gòu)。對于正確性和完整性驗證，Xu等人［17］將MHT與多集累加器結(jié)合，但只支持明文檢索，其完整性驗證無效。此外，驗證機(jī)制的設(shè)計依賴于索引結(jié)構(gòu)。盛祺天［18］使用RSA累加器對索引結(jié)構(gòu)進(jìn)行認(rèn)證，計算開銷巨大，不適用于樹結(jié)構(gòu)；Shao等人［19］采用密鑰哈希MAC和基數(shù)樹支持高效的可驗證模糊多關(guān)鍵詞搜索，但以上方案都無法實現(xiàn)IND-CKA2安全。因此，第二個值得研究的問題是如何為可搜索加密方案的索引結(jié)構(gòu)設(shè)計一種驗證機(jī)制，用于保證搜索結(jié)果的正確性和完整性。

針對云服務(wù)商不誠實行為導(dǎo)致的搜索問題，雖然驗證機(jī)制可以有效增強(qiáng)搜索結(jié)果的正確性和完整性，但是利用可信的第三方執(zhí)行搜索可以進(jìn)一步減少惡意行為的發(fā)生，還可以約束用戶否認(rèn)搜索等不誠實操作，減少無效搜索。區(qū)塊鏈?zhǔn)且环N分布式賬本技術(shù)［20］，礦工節(jié)點在新區(qū)塊內(nèi)打包歷史交易，使得鏈上操作可溯源；通過共識機(jī)制約束、經(jīng)濟(jì)激勵增加節(jié)點的誠實行為獲益，從而減少惡意操作；使用條件觸發(fā)自動執(zhí)行的智能合約編程實現(xiàn)擴(kuò)展應(yīng)用，降低惡意第三方的參與風(fēng)險，故使用區(qū)塊鏈取代傳統(tǒng)第三方執(zhí)行可信搜索成為新的研究方向。林祿濱等人［21］針對現(xiàn)有方案中存在過度依賴中心化服務(wù)器的問題，提出面向醫(yī)療系統(tǒng)的區(qū)塊鏈的可搜索加密方案，通過部署智能合約實現(xiàn)高效的模糊多關(guān)鍵詞搜索，從而確保醫(yī)生收到的結(jié)果正確可信，但是方案僅針對醫(yī)療系統(tǒng)，不具有應(yīng)用普遍性。Chakraborty等人［22］針對遠(yuǎn)程數(shù)據(jù)存儲隱私問題，為以太坊開發(fā)了一個智能合約用于協(xié)助數(shù)據(jù)用戶和云服務(wù)器之間的交互，并提出了一種區(qū)塊鏈輔助的加密數(shù)據(jù)模糊搜索方案BSMFS，但是不可抵抗IND-CKA2。閆璽璽等人［23］提出了一種基于區(qū)塊鏈的多關(guān)鍵詞模糊搜索加密方案，使用對偶編碼和局部敏感哈希構(gòu)建安全索引，并通過計算歐氏距離度量關(guān)鍵詞向量的相似性，從而實現(xiàn)一對多密文共享中的多關(guān)鍵詞模糊搜索；此外，由以太坊中智能合約作為可信第三方完成搜索操作，解決用戶公平性問題，但是方案使用無法抵抗KPA的KNN技術(shù)，因此存在安全隱患。上述方案和現(xiàn)有大多方案都是基于對稱加密機(jī)制，數(shù)據(jù)使用者直接向數(shù)據(jù)擁有者發(fā)出搜索請求，需要數(shù)據(jù)擁有者持續(xù)處于在線狀態(tài)并處理大量請求，很難滿足實際需求。此外，現(xiàn)有方案還存在以下問題：首先，大多區(qū)塊鏈與SSE結(jié)合的解決方案中，數(shù)據(jù)收發(fā)雙方使用安全信道傳輸對稱密鑰或由傳統(tǒng)中心授權(quán)機(jī)構(gòu)分發(fā)密鑰，存在密鑰泄露和單點崩潰的風(fēng)險；其次，難竄改是區(qū)塊鏈的特性之一，數(shù)據(jù)存儲不可逆必然產(chǎn)生巨大的存儲開銷，會對密文搜索解決方案的性能產(chǎn)生影響。因此，如何結(jié)合區(qū)塊鏈設(shè)計方案的整體模型與搜索流程，使方案具有廣泛應(yīng)用價值并保證第三方可信搜索和密鑰安全性，同時減輕區(qū)塊鏈的存儲負(fù)擔(dān)是當(dāng)前的研究熱點之一。

針對現(xiàn)有方案中存在的問題，本文的主要研究如下：

a）設(shè)計了一種自適應(yīng)安全的模糊多關(guān)鍵詞可搜索加密方案。基于傳統(tǒng)對稱可搜索加密方案，在索引構(gòu)建過程中，結(jié)合局部敏感哈希和雙布隆過濾器，實現(xiàn)多關(guān)鍵詞模糊處理；以文件的雙布隆過濾器作為葉子節(jié)點構(gòu)建平衡二叉索引樹，實現(xiàn)亞線性搜索；使用基于圖的關(guān)鍵詞劃分算法優(yōu)化索引樹構(gòu)建，進(jìn)一步提升搜索效率。

b）基于方案的索引樹結(jié)構(gòu)設(shè)計了一種搜索結(jié)果的驗證機(jī)制。在索引樹構(gòu)建過程中，使用自適應(yīng)多集累加器對沒有作為搜索結(jié)果返回的文件和相應(yīng)的搜索關(guān)鍵詞生成不匹配證明，確保有效結(jié)果沒有缺失；通過默克爾哈希樹和根節(jié)點摘要的數(shù)字簽名，確保存儲在索引樹中的內(nèi)容不被竄改。

c）結(jié)合區(qū)塊鏈設(shè)計了模型和搜索流程并提出了存儲優(yōu)化機(jī)制。使用智能合約設(shè)計聯(lián)盟鏈中的添加和搜索交易，實現(xiàn)搜索公平可溯源；通過共識選舉授權(quán)節(jié)點輪換管理并分發(fā)密鑰，降低密鑰泄露和單點崩潰風(fēng)險；利用全局時間作為全網(wǎng)達(dá)成共識的中間參考，使得節(jié)點可從中間塊進(jìn)行公平驗證，無須處理過期交易，有效降低了存儲開銷。

1 預(yù)備知識

1.1 雙布隆過濾器

雙布隆過濾器（twin Bloom filter，TBF）是基于布隆過濾器（Bloom filter，BF）擴(kuò)展得到的一種數(shù)據(jù)結(jié)構(gòu)［24］，即TBF是一個有N個雙胞胎的位數(shù)組BTBF，每個雙胞胎是兩個存儲相反位的單元?？梢允褂眠@種結(jié)構(gòu)同時存儲和屏蔽關(guān)鍵詞信息，算法表示為TBF=（Setup，Init，Insert，Check）：

2.4 存儲優(yōu)化機(jī)制

區(qū)塊鏈?zhǔn)且环N激勵驅(qū)動的去中心化存儲服務(wù)，聯(lián)盟鏈?zhǔn)枪?jié)點加入需要授權(quán)許可的區(qū)塊鏈，可信程度更高。在本方案中，聯(lián)盟鏈節(jié)點由于提供索引樹存儲和關(guān)鍵詞搜索服務(wù)而獲得獎勵，具體是采用智能合約來實現(xiàn)服務(wù)的承包和獎勵。發(fā)布的智能合約包含租賃節(jié)點服務(wù)信息，例如預(yù)設(shè)的服務(wù)期限等。此外，可以編程并附加以下功能：a）預(yù)存功能，客戶可以將加密貨幣的單位存入合約；b）添加費(fèi)用功能，為每個添加索引樹的操作發(fā)送回預(yù)定義數(shù)量的加密貨幣；c）搜索費(fèi)用功能，為完成每個關(guān)鍵詞搜索請求的操作發(fā)送回預(yù)定義數(shù)量的加密貨幣；d）終止功能，節(jié)點可以了解該智能合約的租賃服務(wù)期限是否已經(jīng)結(jié)束。特別地，如果達(dá)到服務(wù)持續(xù)時間，智能合約將提取合約持有的全部資產(chǎn)。

現(xiàn)有的區(qū)塊鏈系統(tǒng)都是以僅添加的方式實現(xiàn)，比如Bitcoin、Ethereum等。只要區(qū)塊鏈運(yùn)行，記錄的交易就會留在鏈上。然而，在本文方案中，雖然添加索引的交易和搜索請求的交易記錄在鏈上，但如果設(shè)定的服務(wù)過期，它們將不會再次被使用，所以將它們持續(xù)保存在鏈上，將不可避免地帶來巨大的存儲開銷。為了解決這個問題，本文加入?yún)^(qū)塊鏈優(yōu)化機(jī)制，即利用全局時間作為聯(lián)盟鏈全網(wǎng)達(dá)成共識的中間參考。因此，礦工節(jié)點可以從中間塊而不是從一開始就對聯(lián)盟鏈進(jìn)行公平驗證，不需要處理過期的交易。

通常區(qū)塊鏈結(jié)構(gòu)包括帶有時間戳的智能合約和由節(jié)點生成的交易，節(jié)點可以使用全局時間作為參考來檢查智能合約是否處于活躍狀態(tài)。在如圖4所示的優(yōu)化機(jī)制中，全局認(rèn)可的聯(lián)盟鏈?zhǔn)菑谋粯?biāo)記為當(dāng)前可信區(qū)塊的第一個活躍的智能合約中被驗證和訪問的。一旦智能合約達(dá)到設(shè)定的服務(wù)持續(xù)時間，它就會過期，然后下一個活躍的智能合約將被標(biāo)記為當(dāng)前可信區(qū)塊。為了在不影響安全性的前提下節(jié)省區(qū)塊鏈的本地存儲成本，在當(dāng)前可信區(qū)塊之前記錄的交易和智能合約將被公開發(fā)布到每個可信的聯(lián)盟鏈節(jié)點都可以訪問的位置，例如指定的網(wǎng)站或聯(lián)盟鏈共享的云服務(wù)器存儲，類似的技術(shù)在基于區(qū)塊鏈的域名服務(wù)（domain name service，DNS）中也有使用［26］。

舉例說明如圖4所示的優(yōu)化機(jī)制，用戶Alice在日期8～10號維護(hù)一個智能合約，在日期9號用戶Bob建立了一個日期為9～11號的智能合約。然后，Alice和Bob的所有交易將在Bob的智能合約（從日期9號開始）之后被記錄。當(dāng)日期轉(zhuǎn)變?yōu)?0號時，Alice的智能合約將會到期，而Bob的合約仍然是有效的，因此它被選為當(dāng)前的可信區(qū)塊。在此之后，從日期8～9號的全部交易都將過期并被公開發(fā)布。

定理3 如果區(qū)塊鏈不可竄改，基于區(qū)塊鏈的模糊多關(guān)鍵詞可搜索加密方案是公平的。

證明 首先，如果DR是惡意的，那么區(qū)塊鏈不會接受此次交易，CS也無法獲得搜索結(jié)果。在此過程中，DR將受到懲罰，同時服務(wù)器接收不到任何信息。其次，如果CS是惡意的，它會返回錯誤或竄改的搜索結(jié)果，那么它將無法獲得交易中的服務(wù)費(fèi)，同時它將損失自己的押金并受到懲罰。然而，如果DR和CS都誠實地執(zhí)行合約規(guī)則，那么它們將可以分別獲得正確且完整的搜索結(jié)果和相應(yīng)的服務(wù)費(fèi)。此外，由于DR預(yù)先為自己的搜索請求設(shè)置一個時間限制Tlim，若當(dāng)前時間T≥Tlim，將退還DR的押金并結(jié)束交易。結(jié)合以上分析可知，將模糊多關(guān)鍵詞可搜索加密方案與區(qū)塊鏈技術(shù)相結(jié)合，可以實現(xiàn)公平性。

3.2 功能性分析

將本文方案與相關(guān)文獻(xiàn)［13～15，19，23］提出的模糊關(guān)鍵詞搜索方案之間進(jìn)行功能性比較，結(jié)果如表1所示。與大多數(shù)方案相比：

a）本方案使用LSH將拼寫無論正誤的關(guān)鍵詞哈希為同一桶值，再將桶值存儲并隱藏在TBF中生成文件索引，從而實現(xiàn)自適應(yīng)安全的模糊搜索；再使用索引作為葉子節(jié)點構(gòu)建平衡二叉索引樹，以實現(xiàn)亞線性搜索復(fù)雜度。此外，方案可基于GKP算法構(gòu)建索引樹，從而進(jìn)一步提升效率。然而，文獻(xiàn)［13，15，19，23］不能實現(xiàn)該性能。

b）本方案使用MSA為未返回的文件和相應(yīng)的搜索關(guān)鍵詞生成不匹配的證明，確保沒有缺失有效結(jié)果；同時，使用MHT對存儲在樹中每個節(jié)點的內(nèi)容進(jìn)行散列，確保索引樹中的內(nèi)容不被竄改，并使用數(shù)字簽名防止根摘要被竄改，從而實現(xiàn)對搜索結(jié)果的完整性和正確性驗證。然而，文獻(xiàn)［13～15］不能實現(xiàn)該性能。

c）本方案基于區(qū)塊鏈實現(xiàn)可信搜索，通過共識選舉動態(tài)產(chǎn)生授權(quán)節(jié)點，生成并分發(fā)密鑰，取代傳統(tǒng)密鑰信道傳輸和中心化授權(quán)中心；在節(jié)點上部署智能合約，完成鏈上添加索引樹和搜索的操作；并提出優(yōu)化機(jī)制，利用全局時間作為區(qū)塊鏈全網(wǎng)達(dá)成共識的中間參考，使得節(jié)點可以從中間區(qū)塊進(jìn)行公平驗證而不需要處理過期的交易，從而有效降低了區(qū)塊鏈的存儲開銷。然而，文獻(xiàn)［13～15，19］不能實現(xiàn)該性能。

分析表2可知，本方案使用優(yōu)化機(jī)制前與文獻(xiàn)［28］存儲開銷類似，但略高于文獻(xiàn)［23］。因為本方案使用TBF，相比傳統(tǒng)BF增加了一部分存儲開銷，但是可以有效隱藏索引信息。雖然本方案將索引與密文數(shù)據(jù)分離，在使用優(yōu)化機(jī)制后，存儲開銷與文獻(xiàn)［23］相當(dāng)，但是對于海量數(shù)據(jù)仍然負(fù)擔(dān)較重，因此本方案更適用于輕量級密文數(shù)據(jù)搜索。

3.4 實驗分析

本文在12th Gen Intel CoreTM i7-12700H 2.30 GHz CPU的Ubuntu 16.04服務(wù)器上，基于開源項目Hyperledger Fabric搭建了一個聯(lián)盟鏈，并部署智能合約執(zhí)行添加和搜索操作。方案由Java語言實現(xiàn)，使用jPBC密碼庫對本方案和其他對比方案進(jìn)行仿真，使用Java中的AES加密工具類實現(xiàn)文件加密。從NSF（National Science Foundation，美國國家科學(xué)基金會）研究獎勵摘要1990—2003年的數(shù)據(jù)集中隨機(jī)選擇3 000篇論文作為測試數(shù)據(jù)集，然后從中提取1 000個關(guān)鍵詞，提取關(guān)鍵詞的平均數(shù)約為56。設(shè)計用于存儲每個文件的TBF的長度N=800，哈希消息驗證碼HMAC的數(shù)量為k=10，TBF的平均假陽性概率小于（1－e－|W|×k/N）k=（1－e－|56|×10/800）10≈0.1%。由于文獻(xiàn)［14，23］和本文方案類似，所以一起進(jìn)行實驗對比。

通常關(guān)鍵詞拼寫錯誤可以概括為拼錯字母、缺少字母、多余字母和顛倒字母順序四種形式。文獻(xiàn)［25］已測試得到在多余字母的形式下，uni-gram、bi-gram和three-gram的精確率相似；其余三種形式下，uni-gram的精確率都更高，因此本文選用uni-gram表示關(guān)鍵詞。在效率測試中，指定HMAC和H1、H2、H作為SHA1，并且將LSH的個數(shù)設(shè)置為3。圖5分別顯示了不同方案在BulidIndex階段時間隨文件數(shù)量m、關(guān)鍵詞個數(shù)|Δ|和TBF長度N的變化情況。

由圖5（a）可知，這些方案構(gòu)建索引的時間隨著文件數(shù)量的增加而增加，并且本方案的索引樹構(gòu)建時間相比驗證時間增長更快，但是其總索引生成時間遠(yuǎn)小于文獻(xiàn)［14］，因為該方案需要計算素數(shù)約800 m。根據(jù)圖5（b）可以得到，本方案的索引樹構(gòu)建時間不隨關(guān)鍵詞數(shù)量增加而變化，但驗證時間隨著關(guān)鍵詞數(shù)量增加而增加，因為使用MSA.Accumulator生成累積值的時間會隨關(guān)鍵詞數(shù)量增多而增長；文獻(xiàn)［14］的驗證時間也隨關(guān)鍵詞數(shù)量增加而增加，并且遠(yuǎn)遠(yuǎn)大于本方案的總索引生成時間。在圖5（c）中，本方案的索引樹構(gòu)建時間和驗證時間都隨著TBF長度的增加而增加，因為TBF越長，加密索引的計算成本越高，但是本方案的索引樹構(gòu)建由DO完成，所以索引生成時間并不影響區(qū)塊鏈的搜索效率。

由于方案實現(xiàn)的是模糊多關(guān)鍵詞搜索，所以實驗首先測試在多關(guān)鍵詞下不同方案的陷門生成時間，如圖6所示。由圖6可知，本方案的陷門生成時間隨搜索關(guān)鍵詞數(shù)量呈現(xiàn)線性增加，但是本方案相比文獻(xiàn)［23］的陷門生成時間更長，因為本方案除了將關(guān)鍵詞轉(zhuǎn)換成桶字符串再進(jìn)行加密之外，還需要計算生成該關(guān)鍵詞的標(biāo)簽用于搜索，最終生成搜索陷門和標(biāo)簽集合，所以時間相對較長，但是生成搜索陷門是由DR完成的，所以陷門生成時間并不影響區(qū)塊鏈的搜索效率。

為測試本方案模糊多關(guān)鍵詞的搜索性能，本文以不同方案在搜索關(guān)鍵詞數(shù)量增加條件下的搜索時間變化趨勢為對比，如圖7所示。在search階段，本文選擇3 000篇論文作為測試數(shù)據(jù)集，并從中提取1 000個關(guān)鍵詞。由圖7可知，三個方案的搜索時間基本上都隨著搜索關(guān)鍵詞量的增加而增加，但是搜索關(guān)鍵詞的數(shù)量對本方案的單純搜索時間影響不大，可實現(xiàn)亞線性搜索復(fù)雜度。此外，由于本方案的搜索時間是由單純搜索時間和證明生成時間兩部分組成，而文獻(xiàn)［14，23］都只是包含單純搜索時間，所以本方案的實際搜索時間相比其他兩個方案較長，但是搜索階段的證明生成是為了實現(xiàn)本方案對于搜索結(jié)果的完整性和正確性驗證，可以增強(qiáng)方案安全性。

根據(jù)2.2節(jié)方案詳細(xì)設(shè)計可知，本文搜索過程中需要為驗證結(jié)果生成證明，因此生成錯誤匹配證明會極大損耗搜索時間，降低搜索效率。為了證明本方案使用GKP算法可以有效提升搜索效率，同時測試文件數(shù)量變化對于搜索時間的影響，本文對比了在文件數(shù)量m改變時，本方案加入GKP（GKP-T）和未加入GKP（GKP-F）產(chǎn)生的錯誤匹配證明的數(shù)量proofw，如表3所示。

由表3可知，在10次搜索中，本方案GKP-T產(chǎn)生的錯配證明數(shù)量明顯少于GKP-F。此外，為了更進(jìn)一步證明本方案加入GKP算法后有效提升了搜索效率，本文在不同文件數(shù)量下測試了加入GKP算法前后的搜索時間，如圖8所示。

圖8顯示了10次搜索的平均搜索時間，明顯可以看到GKP-T的搜索時間小于GKP-F，綜合表3分析可知：a）本方案使用GKP算法的搜索效率更高；b）文件數(shù)量越大，使用GKP提升方案的搜索效率越明顯?；贕KP算法對本方案搜索性能的優(yōu)化，本文再次對比了三個方案搜索時間隨文件數(shù)量增加的變化趨勢，如圖9所示。其中，每個文件提取9個關(guān)鍵詞，查詢關(guān)鍵詞設(shè)為3個。

由圖9可知，三個方案的搜索時間基本是隨文件數(shù)量增加呈線性增長。類似于圖7的對比，雖然GKP減少了錯誤匹配證明的數(shù)量，但是本方案的證明生成時間仍然相對較長，因此實際搜索效率相比其他兩個方案存在一定劣勢。然而，在實際應(yīng)用中，毫秒級別的搜索時間差距在可搜索加密方案中是可以忽略的。因為搜索過程是基于聯(lián)盟鏈部署智能合約完成的，而驗證是為了增強(qiáng)搜索結(jié)果的可信程度，解決傳統(tǒng)方案中第三方不實搜索問題。因此，本方案在結(jié)合區(qū)塊鏈的醫(yī)療、身份信息等安全性需求高但實時性要求不高的應(yīng)用領(lǐng)域仍具有實用價值。

此外，本方案是在聯(lián)盟鏈上部署智能合約執(zhí)行添加和搜索操作，而智能合約的執(zhí)行性能指標(biāo)之一是響應(yīng)時間。Hyperledger Caliper 是一個專為Hyperledger平臺設(shè)計的區(qū)塊鏈性能基準(zhǔn)測試工具，它支持測量從提交事務(wù)到事務(wù)被確認(rèn)所需的時間等關(guān)鍵性能指標(biāo)。因此，為測試智能合約執(zhí)行搜索交易的響應(yīng)時間，本文部署并執(zhí)行不同搜索關(guān)鍵詞數(shù)量的搜索智能合約，運(yùn)行Caliper測試腳本記錄每次交易的提交時間和確認(rèn)時間，最終計算響應(yīng)時間為確認(rèn)時間與提交時間的差值，得到的測試結(jié)果如圖10所示。

根據(jù)測試結(jié)果圖10可知，本方案執(zhí)行搜索操作的智能合約響應(yīng)時間隨著搜索關(guān)鍵詞數(shù)量的增加而增加?；谥悄芎霞s執(zhí)行的響應(yīng)時間會受到數(shù)據(jù)量、復(fù)雜計算等因素影響的特性，結(jié)合搜索階段方案設(shè)計和圖7的不同搜索關(guān)鍵詞數(shù)量的搜索時間測試結(jié)果分析，本方案為實現(xiàn)安全性搜索和搜索結(jié)果驗證犧牲了一定的搜索性能，但是毫秒級時間損耗在安全需求較高且實時性需求不高的應(yīng)用（如醫(yī)療領(lǐng)域、政府部門）中是可接受的。同樣，本方案可進(jìn)一步研究繼續(xù)提升搜索效率。

本方案設(shè)計的重點之一是搜索結(jié)果的驗證，因此同樣需要考慮驗證時間對方案的影響，設(shè)計通過文件數(shù)量變化測試不同方案驗證時間，對比結(jié)果如圖11所示。由圖11可知，本方案的驗證時間隨文件數(shù)量增加而增加，因為文件數(shù)量越多，根摘要計算時間就越長，每次摘要計算時間隨著TBF長度的增加而增加。此外，與MHT驗證相比，錯誤匹配驗證所需的時間非常少，這表明完整性驗證對總驗證成本的影響很小。文獻(xiàn)［19］的驗證時間少于本方案，但索引、陷門生成和單純搜索時間較長，因此本方案相比文獻(xiàn)［14］也有一定優(yōu)勢。

結(jié)束語

本文結(jié)合區(qū)塊鏈提出了一種自適應(yīng)安全的模糊多關(guān)鍵詞可搜索加密方案，實現(xiàn)了亞線性搜索并支持驗證搜索結(jié)果的正確性和完整性。針對現(xiàn)有對稱可搜索加密方案搜索靈活性、安全性不足的問題，首先，使用局部敏感哈希將拼寫無論正誤的關(guān)鍵詞映射為桶字符串，實現(xiàn)模糊處理；其次，設(shè)計雙布隆過濾器存儲和隱藏每個文件的多個關(guān)鍵詞哈希值，再以其為葉子節(jié)點設(shè)計索引樹構(gòu)建算法生成用于搜索和驗證的索引結(jié)構(gòu)；接著，結(jié)合Merkel哈希樹和自適應(yīng)多集累加器驗證索引樹，并為驗證后的根摘要生成數(shù)字簽名，從而實現(xiàn)可驗證結(jié)果且自適應(yīng)安全的模糊多關(guān)鍵詞搜索。為進(jìn)一步優(yōu)化搜索效率，在索引樹構(gòu)建算法中加入基于圖的劃分算法，實現(xiàn)亞線性搜索。針對半誠實云服務(wù)器在密文上的不實搜索問題，本文結(jié)合區(qū)塊鏈設(shè)計方案模型和搜索流程，設(shè)定由聯(lián)盟鏈共識選舉授權(quán)節(jié)點輪換管理加密密鑰，并在鏈上發(fā)布添加和搜索交易，由智能合約自動執(zhí)行搜索過程，從而增強(qiáng)搜索可信度、降低密鑰泄露風(fēng)險。此外，方案將索引與密文分離，減輕區(qū)塊鏈存儲負(fù)擔(dān)，并為進(jìn)一步減少存儲開銷提出了優(yōu)化機(jī)制。最后，安全證明和性能分析表明，方案能夠抵抗自適應(yīng)選擇關(guān)鍵詞攻擊，實現(xiàn)高效的模糊多關(guān)鍵詞搜索和結(jié)果驗證，并可以一定程度降低區(qū)塊鏈的存儲開銷。然而，在實驗測試中，本方案為驗證搜索結(jié)果的正確性和完整性，需要在搜索過程中為搜索結(jié)果生成證明信息，存在一定的時間損耗。因此，本方案難以支持實時性需求高的海量數(shù)據(jù)模糊搜索，更加適用于對安全性要求高的輕量級密文搜索。下一步將繼續(xù)深入提升搜索性能，使方案的應(yīng)用范圍更廣泛。

參考文獻(xiàn)：

［1］Song D X， Wagner D， Perrig A. Practical techniques for searches on encrypted data ［C］// Proc of IEEE Symposium on Security and Privacy. Piscataway，NJ： IEEE Press， 2000： 44-55.

［2］Zhang Hua， Zhao Shaohua， Guo Ziqing， et al. Scalable fuzzy keyword ranked search over encrypted data on hybrid clouds ［J］. IEEE Trans on Cloud Computing， 2023， 11 （1）： 308-323.

［3］吳曦， 俞能海， 張衛(wèi)明. 一種基于BloomFilter的改進(jìn)型加密文本模糊搜索機(jī)制研究 ［J］. 控制與決策， 2019， 34（1）： 97-104. （Wu Xi， Yu Nenghai， Zhang Weiming. Research on an improved fuzzy search mechanism for encrypted text based on BloomFilter ［J］. Control and Decision， 2019， 34（1）： 97-104.）

［4］魏國富， 葛新瑞， 于佳. 支持?jǐn)?shù)據(jù)去重的可驗證模糊多關(guān)鍵詞搜索方案 ［J］. 密碼學(xué)報， 2019， 6（5）： 615-626. （Wei Guofu， Ge Xinrui， Yu Jia. A verifiable fuzzy multi-keyword search scheme supporting data de-duplication ［J］. Acta Cryptologica Sinica， 2019， 6（5）： 615-626.）

［5］Liu Qin， Peng Yu， Pei Shuyu， et al. Prime inner product encoding for effective wildcard-based multi-keyword fuzzy search ［J］. IEEE Trans on Services Computing， 2022， 15（4）： 1799-812.

［6］Chen Jing， He Kun， Deng Lan， et al. EliMFS： achieving efficient， leakage-resilient， and multi-keyword fuzzy search on encrypted cloud data ［J］. IEEE Trans on Services Computing， 2020， 13（6）： 1072-1085.

［7］Zhong Hong， Li Zhanfei， Cui Jie， et al. Efficient dynamic multi-keyword fuzzy search over encrypted cloud data ［J］. Journal of Network and Computer Applications， 2020， 149： 102469.

［8］吳楚欣. 多用戶場景下的多關(guān)鍵字可搜索加密方案的研究與改進(jìn) ［D］. 深圳：深圳大學(xué)， 2020. （Wu Chuxin. Research and improvement of multi-keyword searchable encryption scheme in multi-user scenario ［D］. Shenzhen： Shenzhen University， 2020.）

［9］黃保華， 趙統(tǒng)， 雷素梅， 等. 基于語義的模糊關(guān)鍵詞排序可搜索加密方案 ［J］. 廣西大學(xué)學(xué)報：自然科學(xué)版， 2023， 48（5）： 1167-1180. （Huang Baohua， Zhao Tong， Lei Sumei， et al. Semantic based fuzzy keyword sorting searchable encryption scheme ［J］. Journal of Guangxi University：Natural Science Edition， 2023， 48（5）： 1167-1180.）

［10］王玉璇. 基于連接關(guān)鍵字的可驗證密文排序檢索研究 ［D］. 西安：西安電子科技大學(xué)， 2023. （Wang Yuxuan. Research on verifiable ciphertext sorting retrieval based on link keywords ［D］. Xi’an： Xidian University， 2023.）

［11］王正， 曹素珍， 趙曉， 等. 云邊協(xié)同下可排序的屬性基可搜索加密方案 ［J］. 計算機(jī)工程， 2023， 49（12）： 121-128. （Wang Zheng， Cao Suzhen， Zhao Xiao， et al. Searchable attribute base encryption scheme under cloud edge collaboration ［J］. Computer Engineering， 2019， 49（12）： 121-128.）

［12］周藝華， 李美奇， 扈新宇， 等. 云環(huán)境下基于屬性策略隱藏的細(xì)粒度高效可搜索加密方案 ［J］. 計算機(jī)科學(xué)， 2023， 50（7）： 339-346. （Zhou Yihua， Li Meiqi， Hu Xinyu， et al. A fine-grained efficient searchable encryption scheme based on attribute policy hiding in cloud environment ［J］. Computer Science， 2023， 50（7）： 339-346.）

［13］薛慶水， 時雪磊， 王俊華， 等. 基于屬性加密的個人醫(yī)療數(shù)據(jù)共享方案 ［J］. 計算機(jī)應(yīng)用研究， 2023， 40（2）： 589-594，600. （Xue Qingshui， Shi Xuelei， Wang Junhua， et al. Personal medical data sharing scheme based on attribute encryption［J］. Application Research of Computers， 2019， 40（2）： 589-594，600.）

［14］Liu Qin， Tian Yue， Wu Jie， et al. Enabling verifiable and dynamic ranked search over outsourced data ［J］. IEEE Trans on Services Computing， 2019， 15（1）： 69-82.

［15］張曉均， 劉慶， 鄭爽， 等. 支持隱私保護(hù)的可驗證云端數(shù)據(jù)分享方案 ［J］. 計算機(jī)工程， 2023， 49（3）： 49-57. （Zhang Xiaojun， Liu Qing， Zheng Shuang， et al. Verifiable cloud data sharing Scheme supporting privacy protection ［J］. Computer Engineering， 2019， 49（3）： 49-57.）

［16］Tong Qiuyun， Miao Yinbin， Liu Ximeng， et al. VPSL： verifiable privacy-preserving data search for cloud-assisted Internet of Things［J］. IEEE Trans on Cloud Computing， 2020， 10（4）： 2964-2976.

［17］Xu Cheng， Zhang Ce， Xu Jianliang. vChain： enabling verifiable Boolean range queries over blockchain databases ［C］// Proc of International Conference on Management of Data. New York： ACM Press， 2019： 141-158.

［18］盛祺天. 高效可驗證的連接關(guān)鍵詞密文檢索技術(shù)研究 ［D］. 西安：西安電子科技大學(xué)， 2022. （Sheng Qitian. Research on efficient and verifiable link keyword ciphertext retrieval technology ［D］. Xi’an：Xidian University， 2022.）

［19］Shao Jun， Lu Rongxing， Guan Yunguo， et al. Achieve efficient and verifiable conjunctive and fuzzy queries over encrypted data in cloud ［J］. IEEE Trans on Services Computing， 2019， 15（1）： 124-137.

［20］楊亞濤， 蔡居良， 張筱薇， 等. 基于SM9算法可證明安全的區(qū)塊鏈隱私保護(hù)方案 ［J］. 軟件學(xué)報， 2019， 30（6）： 1692-1704. （Yang Yatao， Cai Juliang， Zhang Xiaowei， et al. A provable security blockchain privacy protection scheme based on SM9 algorithm ［J］. Journal of Software， 2019， 30（6）： 1692-1704.）

［21］林祿濱， 張桂鵬， 李彥峰， 等. 面向醫(yī)療系統(tǒng)的區(qū)塊鏈的可搜索加密方案 ［J/OL］. 小型微型計算機(jī)系統(tǒng).（2023-02-09） ［2024-01-25］. http：//kns. cnki. net/kcms/detail/21. 1106. tp. 20230209. 1121. 021. html. （Lin Lubin， Zhang Guipeng， Li Yanfeng， et al. Health system oriented block chain searchable encryption scheme ［J/OL］. Small Microcomputer System.（2023-02-09） ［2024-01-25］. http：//kns. cnki. net/kcms/detail/21. 1106. tp. 20230209. 1121. 021. html.）

［22］Chakraborty P S， Chandrawanshi M S， Kumar P， et al. BSMFS： blockchain assisted secure multi-keyword fuzzy search over encrypted data ［C］// Proc of IEEE International Conference on Blockchain. Piscataway， NJ： IEEE Press， 2022： 216-221.

［23］閆璽璽， 馮蘇偉， 湯永利， 等. 基于區(qū)塊鏈的多關(guān)鍵詞模糊搜索加密方案 ［J］. 電子與信息學(xué)報， 2023， 45（4）： 1346-1355. （Yan Xixi， Feng Suwei， Tang Yongli， et al. Multi-keyword fuzzy search encryption scheme based on blockchain ［J］. Journal of Electronics and Information Technology， 2023， 45（4）： 1346-1355.）

［24］Li Rui， Liu A X. Adaptively secure conjunctive query processing over encrypted data for cloud computing ［C］// Proc of the 33rd IEEE International Conference on Data Engineering. Piscataway，NJ： IEEE Press， 2017： 697-708.

［25］Tong Qiuyun， Miao Yinbin， Weng Jian， et al. Verifiable fuzzy multi-keyword search over encrypted data with adaptive security ［J］. IEEE Trans on Knowledge and Data Engineering， 2022， 35（5）： 5386-5399.

［26］Ali M， Nelson J， Shea R， et al. Blockstack： a global naming and sto-rage system secured by blockchains ［C］// Proc of USENIX Annual Technical Conference. ［S.l.］：USENIX Association， 2016： 181-194.

［27］Merkle R C. A certified digital signature ［C］// Advances in Crypto-logy—CRYPTO’89. New York： Springer， 2007： 218-238.

［28］Cai Chengjun， Yuan Xingliang， Wang Cong. Towards trustworthy and private keyword search in encrypted decentralized storage ［C］// Proc of IEEE International Conference on Communications. Piscataway， NJ： IEEE Press， 2017： 1-7.