龐曉瓊，王云婷，陳文俊，2，姜 攀，高亞楠

（1.中北大學(xué) 大數(shù)據(jù)學(xué)院，太原 030051；2.中國(guó)人民銀行 太原中心支行，太原 030001）

0 引言

隨著云計(jì)算的飛速發(fā)展，越來(lái)越多的用戶(hù)將大量數(shù)據(jù)遷移到云平臺(tái)，以節(jié)省本地存儲(chǔ)成本；同時(shí)云平臺(tái)也為遠(yuǎn)程存儲(chǔ)和計(jì)算提供即時(shí)服務(wù)，方便用戶(hù)隨時(shí)隨地進(jìn)行數(shù)據(jù)訪問(wèn)和使用［1］。但由于用戶(hù)失去了對(duì)數(shù)據(jù)的控制，如何保障數(shù)據(jù)隱私安全成為關(guān)鍵問(wèn)題。為保護(hù)敏感數(shù)據(jù)的隱私性，數(shù)據(jù)需要在用戶(hù)上傳至云服務(wù)器（Cloud Service Provider，CSP）前進(jìn)行加密處理［2］；然而數(shù)據(jù)加密使基于明文的關(guān)鍵詞檢索技術(shù)無(wú)法使用?？伤阉骷用芗夹g(shù)［3］的提出不僅能實(shí)現(xiàn)對(duì)加密數(shù)據(jù)的檢索，同時(shí)亦能保障數(shù)據(jù)隱私安全。

在可搜索加密技術(shù)中，通常假設(shè)CSP 是誠(chéng)實(shí)且好奇的實(shí)體。然而在實(shí)際中，為獲取服務(wù)費(fèi)的同時(shí)節(jié)省計(jì)算資源，CSP 可能會(huì)不誠(chéng)實(shí)地執(zhí)行搜索操作并向用戶(hù)發(fā)送不正確或不完整的搜索結(jié)果［4］。在先付費(fèi)后使用的模式中，即使出現(xiàn)上述不誠(chéng)實(shí)的情況，用戶(hù)也必須先向CSP 支付服務(wù)費(fèi)；而在先使用后付費(fèi)的模式中，可能存在不誠(chéng)實(shí)的用戶(hù)收到正確的結(jié)果拒絕支付服務(wù)費(fèi)的情況。此外，數(shù)據(jù)擁有者（Data Owner，DO）向CSP 提供的數(shù)據(jù)的價(jià)值也需要被考慮在交易中，即數(shù)據(jù)使用者（Data User，DU）進(jìn)行交易時(shí)應(yīng)向數(shù)據(jù)擁有者支付所提供數(shù)據(jù)的消息費(fèi)［5］。為了解決以上公平問(wèn)題，傳統(tǒng)解決方案往往會(huì)依賴(lài)一個(gè)可信的第三方；但由于第三方?jīng)]有能力直接驗(yàn)證檢索結(jié)果的正確性和完整性，當(dāng)發(fā)生交易糾紛時(shí)，第三方機(jī)構(gòu)需要花費(fèi)大量時(shí)間解決糾紛，公平支付無(wú)法直接保證，交易過(guò)程中產(chǎn)生的不誠(chéng)實(shí)行為得不到懲罰。另一方面，第三方機(jī)構(gòu)、CSP 及用戶(hù)之間發(fā)生交互時(shí)，用戶(hù)在第三方機(jī)構(gòu)上的個(gè)人隱私信息也有被泄露的風(fēng)險(xiǎn)。

從以上分析可知，需要一種有效的方法來(lái)解決傳統(tǒng)可搜索加密方案中的公平支付問(wèn)題。隨著比特幣［6］的問(wèn)世，區(qū)塊鏈作為其底層技術(shù)能夠?yàn)榻鉀Q這一問(wèn)題提供支持。區(qū)塊鏈具有去中心化和不可篡改等特性，能夠很好地與云計(jì)算結(jié)合；區(qū)塊鏈上的智能合約［7］可以直接寫(xiě)入代碼并自動(dòng)執(zhí)行，不受任何集中機(jī)構(gòu)的控制。因此，區(qū)塊鏈和智能合約適合在可搜索加密方案中執(zhí)行驗(yàn)證操作并實(shí)現(xiàn)公平支付。

在區(qū)塊鏈智能合約與可搜索加密方案相結(jié)合的進(jìn)程中，人們利用區(qū)塊鏈智能合約執(zhí)行檢索結(jié)果的驗(yàn)證和實(shí)現(xiàn)公平支付。此外，還有一些方案采用智能合約取代CSP 執(zhí)行搜索操作，在執(zhí)行過(guò)程中區(qū)塊鏈智能合約需進(jìn)行多筆事務(wù)交易，儲(chǔ)存占用空間較多的索引以及執(zhí)行復(fù)雜搜索操作，可擴(kuò)展性低、費(fèi)用高且時(shí)間耗費(fèi)大；并且費(fèi)用成本和時(shí)間成本會(huì)隨著智能合約所執(zhí)行操作的復(fù)雜性增加而增加。因此，有必要考慮在保證實(shí)現(xiàn)結(jié)果驗(yàn)證和公平支付的基礎(chǔ)上，降低智能合約所執(zhí)行操作的復(fù)雜性以降低時(shí)間與費(fèi)用成本的開(kāi)銷(xiāo)，提高效率，同時(shí)拓展方案功能，對(duì)用戶(hù)更友好。

此外，在實(shí)際應(yīng)用中，僅支持單關(guān)鍵詞檢索的方案往往不能滿(mǎn)足用戶(hù)需求。例如，為了獲得更精確的搜索結(jié)果，用戶(hù)檢索時(shí)一般會(huì)輸入多個(gè)關(guān)鍵詞，并希望返回與輸入關(guān)鍵詞最相關(guān)的前k個(gè)文檔［8］。因此，有必要考慮在結(jié)合區(qū)塊鏈技術(shù)保證實(shí)現(xiàn)結(jié)果驗(yàn)證和公平支付的基礎(chǔ)上，設(shè)計(jì)一個(gè)檢索功能更豐富的可搜索加密方案。

為降低實(shí)現(xiàn)結(jié)果驗(yàn)證和公平支付產(chǎn)生的時(shí)間和費(fèi)用成本，本文方案將CSP 強(qiáng)大高效的檢索能力與區(qū)塊鏈智能合約自動(dòng)執(zhí)行合約內(nèi)容的優(yōu)勢(shì)相結(jié)合，實(shí)現(xiàn)了對(duì)密文的排序檢索、檢索結(jié)果的驗(yàn)證以及數(shù)據(jù)擁有者、CSP 和數(shù)據(jù)使用者之間的公平支付。本文方案采用CSP 存儲(chǔ)加密索引樹(shù)和執(zhí)行搜索操作，數(shù)據(jù)擁有者在生成加密索引樹(shù)的同時(shí)，構(gòu)建包含驗(yàn)證證明的查找表并將其存儲(chǔ)在云端；在執(zhí)行搜索操作時(shí)，CSP 通過(guò)驗(yàn)證令牌查找相應(yīng)的驗(yàn)證證明，再將該驗(yàn)證證明發(fā)送給智能合約以輔助其完成檢索結(jié)果的驗(yàn)證和公平支付，這種方式可有效降低智能合約執(zhí)行操作的復(fù)雜性，節(jié)約費(fèi)用和時(shí)間成本，提高驗(yàn)證效率；同時(shí)，為了解決關(guān)鍵詞檢索中功能過(guò)于局限的問(wèn)題，本文方案將向量空間模型與詞頻逆文檔頻率（Term Frequency-Inverse Document Frequency，TF-IDF）結(jié)合，構(gòu)建平衡二叉樹(shù)的索引結(jié)構(gòu)，在保證檢索效率的基礎(chǔ)上，支持多關(guān)鍵詞檢索的動(dòng)態(tài)更新和檢索結(jié)果的可排序，提升方案的用戶(hù)友好性。

1 相關(guān)工作

可搜索加密技術(shù)是一種允許用戶(hù)對(duì)密文數(shù)據(jù)進(jìn)行檢索的密碼原語(yǔ)，利用云服務(wù)器的強(qiáng)大計(jì)算資源進(jìn)行關(guān)鍵詞檢索，其核心思想在于使用戶(hù)具有在密文域上進(jìn)行關(guān)鍵詞搜索的能力。2000 年，Song 等［3］首次提出了可搜索加密的思想，解決了在云平臺(tái)上搜索加密數(shù)據(jù)的問(wèn)題，隨后云存儲(chǔ)技術(shù)下的可搜索加密成為了研究熱點(diǎn)。近幾年，許多可搜索加密工作致力于豐富其功能，陸續(xù)提出了多關(guān)鍵詞搜索［8-11］、動(dòng)態(tài)加密搜索［12-15］、模糊關(guān)鍵詞搜索［16-19］和可驗(yàn)證的加密搜索［20-23］等方案。這些方案通常假設(shè)云服務(wù)器會(huì)誠(chéng)實(shí)地執(zhí)行任務(wù)，然而云服務(wù)器往往并不是完全可信的，它可能為節(jié)省計(jì)算資源或者騙取服務(wù)費(fèi)，在收到服務(wù)費(fèi)后返回不正確或不完整的結(jié)果；同時(shí)，即使用戶(hù)收到正確的搜索結(jié)果，如果用戶(hù)聲稱(chēng)搜索結(jié)果不正確，也可能惡意拒絕支付服務(wù)費(fèi)。以上情況導(dǎo)致了服務(wù)-支付不公平現(xiàn)象，導(dǎo)致用戶(hù)和云服務(wù)器之間互不信任。為解決上述問(wèn)題，傳統(tǒng)方案通常考慮由可信第三方機(jī)構(gòu)進(jìn)行監(jiān)管與仲裁。

區(qū)塊鏈自問(wèn)世以來(lái)，受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，它能夠在不引入第三方機(jī)構(gòu)的情況下實(shí)現(xiàn)公平支付。因此，人們積極嘗試將區(qū)塊鏈與可搜索加密技術(shù)結(jié)合，以解決傳統(tǒng)方案的問(wèn)題。文獻(xiàn)［24］提出一種基于云存儲(chǔ)的可信賴(lài)關(guān)鍵詞搜索方案，利用比特幣區(qū)塊鏈技術(shù)和哈希函數(shù)在沒(méi)有第三方的情況下實(shí)現(xiàn)搜索費(fèi)用的公平支付。該方案建立基于數(shù)字簽名的安全索引，保證了用戶(hù)端檢索結(jié)果的正確性，同時(shí)也實(shí)現(xiàn)了服務(wù)器端對(duì)加密數(shù)據(jù)有效性的驗(yàn)證；但是該方案在用戶(hù)端驗(yàn)證結(jié)果正確性的過(guò)程中需要進(jìn)行大量簽名驗(yàn)證計(jì)算，用戶(hù)開(kāi)銷(xiāo)較大。文獻(xiàn)［25］設(shè)計(jì)了一個(gè)基于比特幣區(qū)塊鏈的公平對(duì)稱(chēng)可搜索加密方案，通過(guò)區(qū)塊鏈自動(dòng)驗(yàn)證檢索結(jié)果，保證了用戶(hù)和云服務(wù)器之間交易的公平性；但是該方案每次需要執(zhí)行6 筆交易才能獲取檢索結(jié)果，同時(shí)通過(guò)比特幣腳本實(shí)現(xiàn)檢索結(jié)果的驗(yàn)證，其交易周期過(guò)長(zhǎng)從而導(dǎo)致時(shí)間成本較高。文獻(xiàn)［24-25］方案均由云服務(wù)器執(zhí)行檢索操作，基于比特幣區(qū)塊鏈對(duì)檢索結(jié)果進(jìn)行驗(yàn)證以實(shí)現(xiàn)多方之間的公平支付；然而由于比特幣智能合約并不是圖靈完備的，其功能較為局限、交易過(guò)程復(fù)雜、交易周期長(zhǎng)且效率不高。文獻(xiàn)［26］在分布式存儲(chǔ)網(wǎng)絡(luò)中實(shí)現(xiàn)了支持動(dòng)態(tài)高效的關(guān)鍵詞檢索，利用智能合約在以太坊區(qū)塊鏈上記錄加密搜索日志，并設(shè)計(jì)了一個(gè)協(xié)議來(lái)處理爭(zhēng)議和發(fā)放傭金，以便在客戶(hù)端與服務(wù)器之間進(jìn)行公平搜索。該方案由分布式存儲(chǔ)網(wǎng)絡(luò)中的簽約服務(wù)節(jié)點(diǎn)執(zhí)行檢索操作，將可搜索索引和檢索結(jié)果的元數(shù)據(jù)作為證據(jù)錨定在區(qū)塊鏈上，再由分布式存儲(chǔ)網(wǎng)絡(luò)中仲裁者分片上的仲裁節(jié)點(diǎn)檢查檢索結(jié)果的正確性并基于以太坊智能合約實(shí)現(xiàn)公平支付；當(dāng)數(shù)據(jù)用戶(hù)申請(qǐng)仲裁時(shí)，需要每個(gè)仲裁節(jié)點(diǎn)重新且獨(dú)立地執(zhí)行搜索算法，根據(jù)重新生成的搜索結(jié)果判斷客戶(hù)端發(fā)出的判斷請(qǐng)求（即停止支付請(qǐng)求）是否有效，然后將這些單獨(dú)的仲裁結(jié)果匯聚到仲裁智能合約中來(lái)作出最終決定；如果仲裁者分片中大于2/3 數(shù)量的節(jié)點(diǎn)接受判斷結(jié)果，限時(shí)支付將被暫停；可以看出，該仲裁過(guò)程會(huì)浪費(fèi)大量的計(jì)算資源。文獻(xiàn)［27］提出了一個(gè)基于區(qū)塊鏈的支持復(fù)雜邏輯表達(dá)式查詢(xún)的可搜索加密方案，該方案利用以太坊智能合約保證了檢索結(jié)果的正確性，能夠在沒(méi)有任何驗(yàn)證機(jī)制的情況下實(shí)現(xiàn)公平支付。文獻(xiàn)［28］提出了一種基于區(qū)塊鏈的支持細(xì)粒度訪問(wèn)控制的分布式存儲(chǔ)系統(tǒng)，該系統(tǒng)使用以太坊智能合約實(shí)現(xiàn)了密文狀態(tài)下的關(guān)鍵詞搜索功能，解決了傳統(tǒng)云存儲(chǔ)系統(tǒng)中云服務(wù)器可能無(wú)法返回所有檢索結(jié)果或返回錯(cuò)誤結(jié)果的問(wèn)題。文獻(xiàn)［29］設(shè)計(jì)了一種基于區(qū)塊鏈且支持驗(yàn)證的屬性基搜索加密方案，該方案基于以太坊智能合約設(shè)計(jì)搜索合約與驗(yàn)證合約，在不需要本地額外驗(yàn)證的情況下實(shí)現(xiàn)了支持多關(guān)鍵詞檢索的公平支付。文獻(xiàn)［27-29］方案均是由區(qū)塊鏈存儲(chǔ)加密索引和檢索結(jié)果，并基于以太坊智能合約執(zhí)行搜索操作以及實(shí)現(xiàn)公平支付；然而區(qū)塊鏈的存儲(chǔ)容量受到存儲(chǔ)空間最小的節(jié)點(diǎn)的限制，復(fù)雜的加密索引需要分片處理后才能存儲(chǔ)進(jìn)區(qū)塊鏈交易中，并且這些交易必須逐個(gè)上傳，會(huì)消耗大量的時(shí)間；此外，智能合約執(zhí)行操作時(shí)會(huì)消耗一定的費(fèi)用，方案中由智能合約執(zhí)行復(fù)雜性高的搜索操作和驗(yàn)證操作，執(zhí)行時(shí)需要進(jìn)行大量計(jì)算，亦會(huì)導(dǎo)致費(fèi)用成本增加。因此文獻(xiàn)［27-29］方案都存在可擴(kuò)展性低、時(shí)間成本和費(fèi)用成本高的問(wèn)題。另外，文獻(xiàn)［24-28］方案都僅支持單關(guān)鍵詞檢索，均未考慮對(duì)檢索結(jié)果進(jìn)行相關(guān)性排序，功能上不夠靈活，用戶(hù)友好性不高。

因此，本文提出了一種基于以太坊區(qū)塊鏈的公平可驗(yàn)證的多關(guān)鍵詞密文排序檢索方案。利用云服務(wù)器高效的檢索能力與以太坊智能合約自動(dòng)執(zhí)行的特點(diǎn)，由云服務(wù)器來(lái)存儲(chǔ)加密索引樹(shù)與查找表；同時(shí)執(zhí)行搜索算法，可有效降低智能合約執(zhí)行操作的復(fù)雜性，從而降低消耗的時(shí)間成本和費(fèi)用成本；由以太坊智能合約實(shí)現(xiàn)結(jié)果的驗(yàn)證過(guò)程，不但保證檢索結(jié)果的正確性和完整性，完成數(shù)據(jù)擁有者、云服務(wù)器和數(shù)據(jù)使用者之間的公平支付，而且可以有效減少費(fèi)用開(kāi)銷(xiāo)并提高驗(yàn)證效率。此外，本文采用平衡二叉樹(shù)為索引，在保證檢索效率的基礎(chǔ)上，實(shí)現(xiàn)了多關(guān)鍵詞檢索的動(dòng)態(tài)更新以及檢索結(jié)果可排序，提升了方案的靈活性和用戶(hù)友好性。

2 預(yù)備知識(shí)

2.1 符號(hào)定義

DC={d1，d2，…，dm}，表示m個(gè)明文文檔的集合。

C={c1，c2，…，cm}，表示存儲(chǔ)在云服務(wù)器的密文文檔集合。

DW={w1，w2，…，wn}，表示關(guān)鍵詞字典。

Tr 為未加密的索引樹(shù)，ETr 為對(duì)Tr 的加密形式。

Du為索引向量，它的維數(shù)等于字典DW的基數(shù)，u為索引樹(shù)節(jié)點(diǎn)；Iu為Du的加密形式。

T 為查找表，W為查詢(xún)關(guān)鍵詞集，Q為查詢(xún)關(guān)鍵詞集W的查詢(xún)向量，為Q的加密形式。

TD 為搜索令牌，token為驗(yàn)證令牌。

μVK為消息認(rèn)證碼，VK為驗(yàn)證密鑰。

ek為文檔加密密鑰。

proof為搜索結(jié)果的驗(yàn)證證明。

FIDk(W)，Ck(W)，DCk(W)分別為按照相關(guān)性分?jǐn)?shù)排序的前k個(gè)文檔的標(biāo)識(shí)符集合、密文文檔集合和明文文檔集合。

2.2 向量空間模型和相關(guān)性分?jǐn)?shù)

向量空間模型與TF-IDF 規(guī)則廣泛應(yīng)用于明文信息檢索，可有效支持多關(guān)鍵詞排序檢索。在TF-IDF 規(guī)則中，詞頻（Term Frequency，TF）是關(guān)鍵詞在文檔中出現(xiàn)的頻率，逆文檔頻率（Inverse Document Frequency，IDF）是通過(guò)文檔集合的總數(shù)除以包含該關(guān)鍵詞的文檔數(shù)量得到。在向量空間模型中，?di∈DC，均能用一個(gè)|DW|× 1 維的文檔索引向量Du表示，Du中每一位的值對(duì)應(yīng)DW中相應(yīng)關(guān)鍵詞的歸一化TF 值，若關(guān)鍵詞在文檔di中并未出現(xiàn)，則將Du對(duì)應(yīng)位設(shè)置為0；用戶(hù)搜索請(qǐng)求也能用一個(gè)|DW|× 1 維的查詢(xún)向量Q表示，所查詢(xún)關(guān)鍵詞在Q的對(duì)應(yīng)位為文檔集合中查詢(xún)關(guān)鍵詞的歸一化IDF 值，其他設(shè)置為0。通過(guò)計(jì)算向量Du和向量Q的內(nèi)積可以量化文檔di和查詢(xún)之間的相關(guān)性。

以下是相關(guān)性評(píng)估函數(shù)中使用的符號(hào)：

2.3 未加密可搜索索引樹(shù)構(gòu)建

本文方案中的搜索索引樹(shù)為平衡二叉樹(shù)。給定文檔集合DC={d1，d2，…，dm}，每個(gè)文檔di對(duì)應(yīng)于索引樹(shù)中的一個(gè)葉子節(jié)點(diǎn)，如果有m個(gè)文檔，則需要自下而上構(gòu)造一個(gè)具有m個(gè)葉子節(jié)點(diǎn)的搜索索引樹(shù)。將索引樹(shù)節(jié)點(diǎn)u的數(shù)據(jù)結(jié)構(gòu)定義為{ID，F(xiàn)ID，Du，Prl，Prr}，其中：ID表示節(jié)點(diǎn)編號(hào)，Du表示n維向量，Prl和Prr分別表示指向u的左、右孩子的指針。對(duì)于文檔di的葉子節(jié)點(diǎn)，F(xiàn)ID表示文檔di的標(biāo)識(shí)符，Du表示文檔di的索引向量。對(duì)于內(nèi)部節(jié)點(diǎn)，Du的每一位則由其孩子節(jié)點(diǎn)中向量對(duì)應(yīng)位的值計(jì)算得到，假設(shè)內(nèi)部節(jié)點(diǎn)u的左右孩子節(jié)點(diǎn)分別為l和r，如果Dl[i]=0(i=1，2，…，n)且Dr[i]=0，則Du[i]=0；否則，Du[i]=1。內(nèi)部節(jié)點(diǎn)中，F(xiàn)ID設(shè)置為空。

通過(guò)BuildIndexTree(DC)算法構(gòu)造索引樹(shù)，算法如下所示。

算法1 BuildIndexTree(DC)。

1）對(duì)于文檔合集中的每個(gè)文檔di，生成對(duì)應(yīng)的葉子節(jié)點(diǎn)，過(guò)程如下：

①為di生成一個(gè)唯一的標(biāo)識(shí)符，并將這個(gè)標(biāo)識(shí)符設(shè)置為這個(gè)葉子節(jié)點(diǎn)的FID。

②根據(jù)關(guān)鍵詞字典DW={w1，w2，…，wn}生成索引向量Du，其中Du的維數(shù)為關(guān)鍵詞字典的基數(shù)，每個(gè)維度Du[i]為文檔di中wi的歸一化的TF 值。

2）生成搜索索引樹(shù)Tr，其葉子節(jié)點(diǎn)為上一步生成的m個(gè)節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)u的FID和Du的初始設(shè)置為空。

3）對(duì)于每個(gè)內(nèi)部節(jié)點(diǎn)u，根據(jù)其左右孩子節(jié)點(diǎn)中向量對(duì)應(yīng)位的值計(jì)算Du。

4）輸出搜索索引樹(shù)Tr。

在實(shí)際方案中，采用安全K近鄰技術(shù)［30］加密上述可搜索索引樹(shù)Tr 中的葉子節(jié)點(diǎn)向量Du和查詢(xún)向量Q。

3 本文方案

3.1 方案框架

本文方案包括數(shù)據(jù)擁有者（DO）、數(shù)據(jù)使用者（DU）、云服務(wù)器（CSP）以及區(qū)塊鏈和智能合約四個(gè)實(shí)體。

1）數(shù)據(jù)擁有者（DO）。

DO 生成密鑰，授予搜索權(quán)限并通過(guò)安全信道傳遞用于檢索的秘密信息給DU；加密明文文檔、構(gòu)建加密索引樹(shù)和查找表，并存儲(chǔ)到CSP；部署用于公平支付的FairPayment 智能合約以收取信息費(fèi)；生成動(dòng)態(tài)更新信息。

2）數(shù)據(jù)使用者（DU）。

DU 由DO 授予搜索權(quán)限，生成搜索和驗(yàn)證令牌并使用FairPayment 智能合約將搜索請(qǐng)求和令牌提交給CSP。若檢索結(jié)果驗(yàn)證通過(guò)，則向CSP 支付服務(wù)費(fèi)，向DO 支付消息費(fèi)；否則不支付任何費(fèi)用。

3）云服務(wù)器（CSP）。

CSP 為DO 存儲(chǔ)密文文檔、加密索引樹(shù)和查找表；為DU提供搜索服務(wù)并收取服務(wù)費(fèi)；向FairPayment 智能合約支付押金并上傳檢索結(jié)果和驗(yàn)證證明；根據(jù)接收到的信息更新存儲(chǔ)內(nèi)容。

4）區(qū)塊鏈和智能合約。

區(qū)塊鏈存儲(chǔ)DU 上傳至FairPayment 智能合約的搜索和驗(yàn)證令牌以及CSP 上傳的檢索結(jié)果和驗(yàn)證證明；FairPayment智能合約驗(yàn)證檢索結(jié)果的正確性和完整性，實(shí)現(xiàn)預(yù)定義比例的費(fèi)用公平支付，將檢索結(jié)果返回給DU。

方案框架如圖1 所示。

圖1 本文方案框架Fig.1 Framework of proposed scheme

具體步驟如下：

步驟1 DO 生成安全密鑰SK、文檔加密密鑰ek和驗(yàn)證密鑰VK，然后從明文文檔集合DC中提取關(guān)鍵詞字典DW，生成加密索引樹(shù)ETr 和查找表T。DO 利用ek對(duì)DC進(jìn)行加密得到密文文檔集合C，然后將ETr、T 和C外包給CSP。

步驟2 DO 部署用于公平支付的FairPayment 智能合約，并將驗(yàn)證密鑰VK記錄在用于公平支付的智能合約中。

步驟3 DO 記錄智能合約地址和合約應(yīng)用程序二進(jìn)制接口（Application Binary Interface，ABI）。

步驟4 DU 向DO 請(qǐng)求搜索權(quán)限。

步驟6 DU 生成多關(guān)鍵詞搜索令牌TD 和驗(yàn)證令牌token，并將其發(fā)送到區(qū)塊鏈以觸發(fā)智能合約。在請(qǐng)求之前，要求DU 在智能合約中存入足夠的搜索費(fèi)用（包括消息費(fèi)和服務(wù)費(fèi)）。

步驟7 如果DU 被驗(yàn)證為授權(quán)用戶(hù)，并且存放了足夠的搜索費(fèi)用，則智能合約將自動(dòng)在區(qū)塊鏈廣播TD 和token，CSP 將接收到它們。

步驟8 CSP 根據(jù)TD 和token分別對(duì)ETr 和T 執(zhí)行檢索操作，得到相應(yīng)的檢索結(jié)果和驗(yàn)證證明。CSP 支付一定的押金后，將檢索結(jié)果和驗(yàn)證證明返回給智能合約進(jìn)行驗(yàn)證。

步驟9 FairPayment 智能合約利用VK驗(yàn)證檢索結(jié)果的正確性和完整性。如果驗(yàn)證通過(guò)，智能合約將自動(dòng)使用DU的搜索費(fèi)用向DO 支付信息費(fèi)，向CSP 支付服務(wù)費(fèi)（根據(jù)預(yù)定義的分配比例）并返回CSP 的押金；否則，DU 的搜索費(fèi)用與CSP 的押金都將被支付給DU。

步驟10 步驟9 中的正確性和完整性驗(yàn)證通過(guò)后，智能合約將檢索結(jié)果發(fā)送給DU。

步驟11 DU 從CSP 收到密文文檔集合Ck(W)后，對(duì)加密文檔進(jìn)行解密。

步驟12 在實(shí)際應(yīng)用中，DO 可以動(dòng)態(tài)地添加、刪除或修改文檔，重新生成新的加密索引樹(shù)ETr′、查找表T′和加密文檔合集C′，以實(shí)現(xiàn)動(dòng)態(tài)更新。

3.2 方案實(shí)現(xiàn)

本文方案包含8 個(gè)子算法（Setup，Enc，GenTrapdoor，Search，Verify，Decrypt，GenYpdatlnto，Update），具體過(guò)程如下：

1）Setup(1λ) →(SK，ek，VK)。

該算法由DO 執(zhí)行。給定安全參數(shù)λ，定義偽隨機(jī)函數(shù)消息認(rèn)證碼（Message Authentication Code，MAC）函數(shù)μVK：{0，1}λ×{0，1}*→{0，1}l，其中：fl是文檔標(biāo)識(shí)符的長(zhǎng)度，l是標(biāo)準(zhǔn)MAC 函數(shù)的輸出長(zhǎng)度；密鑰K1，K2，VK∈R{0，1}λ。DO 生成安全密鑰SK={S，M1，M2，K1，K2}，其中：S是一個(gè)n維二進(jìn)制的拆分指示向量；M1，M2是兩個(gè)n×n階可逆矩陣，用于加密拆分后的向量；n為關(guān)鍵詞字典的基數(shù)。DO 生成用來(lái)加密文檔集合的文檔加密密鑰ek∈REK，EK為對(duì)稱(chēng)密鑰空間。上述過(guò)程如3.1 節(jié)步驟1 所示。

2）Enc(DC，DW，SK，ek，VK) →(ETr，T，C)。

該算法由DO 執(zhí)行。給定一個(gè)明文文檔集合DC={d1，d2，…，dm}，DO 首先掃描文檔集合，提取出關(guān)鍵詞字典DW={w1，w2，…，wn}，然后執(zhí)行兩個(gè)子算法GenIndex 和FileEnc 分別生成加密索引樹(shù)ETr、查找表T 和密文文檔集合C。

①GenIndex(DC，SK，VK) →(ETr，T)。

a）DO 使用算法BuildIndexTree(DC)構(gòu)建未加密的索引樹(shù)Tr。

b）構(gòu)建加密索引樹(shù)ETr。

c）構(gòu)建查找表T。

DO 利用K1和VK構(gòu)建包含驗(yàn)證證明的查找表T，T 是結(jié)構(gòu)，其中key字段包含偽隨機(jī)函數(shù)的輸出，proof字段用于存儲(chǔ)多關(guān)鍵詞排序搜索結(jié)果的驗(yàn)證證明。

對(duì)每個(gè)查詢(xún)關(guān)鍵詞集W，利用關(guān)鍵詞歸一化后的TF 值和歸一化后的IDF 值，計(jì)算相關(guān)性分?jǐn)?shù)，得到按照相關(guān)性分?jǐn)?shù)降序排序的結(jié)果ResultList(RScore，F(xiàn)ID)，其中：RScore表示查詢(xún)關(guān)鍵詞集合W與文檔的相關(guān)性分?jǐn)?shù)，F(xiàn)ID表示文檔標(biāo)識(shí)符。ResultList()根據(jù)RScore進(jìn)行降序排序，包含查詢(xún)關(guān)鍵詞集W的文檔的標(biāo)識(shí)符集合被表示為FID(W)=，F(xiàn)ID(W)中的FID按照RScore降序排序。

表1 查找表TTab.1 Lookup table T

②FileEnc(DC，ek) →C。

DO 利用ek對(duì)DC進(jìn)行加密，得到密文文檔集合C={c1，c2，…，cm}。

DO 將{ETr，T，C}外包給CSP。然后DO 在Ethereum 部署了一個(gè)FairPayment 智能合約，將驗(yàn)證密鑰VK作為私有參數(shù)嵌入到合約之中（用Solidity 編碼），其中VK只有DO 知道。合約負(fù)責(zé)注冊(cè)授權(quán)用戶(hù)，檢查請(qǐng)求搜索服務(wù)的每個(gè)用戶(hù)賬戶(hù)的有效性，記錄和廣播令牌以及驗(yàn)證來(lái)自CSP 的搜索結(jié)果，并且最終實(shí)現(xiàn)公平支付。DO 記錄智能合約的地址和合約ABI。上述過(guò)程如3.1 節(jié)步驟1～3 所示。

3）GenTrapdoor(W，SK) →(TD，token)。

該算法由DU 執(zhí)行。當(dāng)用戶(hù)賬戶(hù)第一次請(qǐng)求搜索服務(wù)時(shí)，應(yīng)該首先向DO 請(qǐng)求搜索權(quán)限。如果請(qǐng)求被允許，DO 通過(guò)安全信道將授予DU。

①生成搜索令牌TD。

a）DU 根據(jù)其查詢(xún)關(guān)鍵詞集W和，生成n維查詢(xún)向量Q。如果wi∈W，Q[i]存儲(chǔ)wi的歸一化IDF 值；否則，Q[i]被設(shè)置為0。

②生成驗(yàn)證令牌token。

DU 利用W和偽隨機(jī)函數(shù)生成驗(yàn)證令牌token=

DU 將足夠的搜索費(fèi)用存入FairPayment 智能合約的存款池（與DU 的賬戶(hù)相關(guān)聯(lián)），將TD 和token上傳到合約，智能合約將自動(dòng)在區(qū)塊鏈廣播TD 和token，CSP 將接收到它們。上述過(guò)程如3.1 節(jié)步驟4～7 所示。

4）Search(TD，ETr，T，token) →(FIDk(W)，proof)。

該算法由CSP 執(zhí)行。FairPayment 智能合約收到token后，檢查DU 是否為授權(quán)用戶(hù)，如果DU 被授權(quán)，合約將通知CSP 執(zhí)行以下檢索操作。

①檢索得到相應(yīng)文檔標(biāo)識(shí)符集合FIDk(W)。

CSP 收到用戶(hù)搜索令牌TD 后，對(duì)加密索引樹(shù)ETr 進(jìn)行檢索。從樹(shù)的根節(jié)點(diǎn)開(kāi)始，當(dāng)?shù)竭_(dá)一個(gè)內(nèi)部節(jié)點(diǎn)u時(shí)，對(duì)于TuW中的每一項(xiàng)如果至少存在一個(gè)at使得，則以相同步驟繼續(xù)檢索u的左右孩子。當(dāng)檢索到達(dá)某個(gè)葉子節(jié)點(diǎn)時(shí)，計(jì)算葉子節(jié)點(diǎn)中的Iu和的內(nèi)積作為相關(guān)性分?jǐn)?shù)。最后對(duì)相關(guān)性分?jǐn)?shù)進(jìn)行降序排序得到最相關(guān)的前k個(gè)文檔標(biāo)識(shí)符集合FIDk(W)。Iu和內(nèi)積計(jì)算的具體過(guò)程如下：

②檢索得到相應(yīng)驗(yàn)證證明proof。

CSP 根據(jù)從智能合約收到的驗(yàn)證令牌token，在查找表T中查找到相應(yīng)的proof，T[token]=proof。

CSP 檢索過(guò)程見(jiàn)算法2。

算法2 Search（ETr 的根節(jié)點(diǎn)u，TD，T，token）。

CSP 向合約支付一定的押金，再發(fā)送FIDk(W)和proof向其求證。上述過(guò)程如3.1 節(jié)步驟8 所示。

5）Verify(VK，proof，F(xiàn)IDk(W)，token) →1/0。

該算法由FairPayment 智能合約執(zhí)行，合約對(duì)CSP 的查詢(xún)結(jié)果FIDk(W)的正確性和完整性進(jìn)行驗(yàn)證。假設(shè)從CSP 接收的驗(yàn)證證明是proof，合約利用從DU 接收的token，計(jì)算proof′=μVK(token‖F(xiàn)IDk(W))并驗(yàn)證等式證明proof′=proof是否成立。如果等式成立，則認(rèn)為CSP 返回的檢索結(jié)果正確且完整，合約將按照預(yù)定義的分配比例將DU 的搜索費(fèi)用從存款池中轉(zhuǎn)移給DO 和CSP（分別作為消息費(fèi)和服務(wù)費(fèi)），將CSP 的押金返回，并將FIDk(W)發(fā)送給DU。否則，合約將會(huì)退回DU 的搜索費(fèi)并將CSP 的押金轉(zhuǎn)給DU 作為補(bǔ)償。上述過(guò)程如3.1 節(jié)步驟9～10 所示。

FairPayment 智能合約驗(yàn)證檢索結(jié)果并完成公平支付過(guò)程見(jiàn)算法Verify（）。其中，msg.sender表示消息或交易的發(fā)送方，msg.value表示交易的金額，deposit是DU 搜索費(fèi)用金額，cspdeposit為CSP 押金金額。設(shè)定deposit=2cspdeposit。

算法3 Verify（proof，token，F(xiàn)IDk(W)，VK）。

該算法由DU 執(zhí)行。DU 根據(jù)智能合約返回的FIDk(W)收到正確的密文文檔集合Ck(W)后，利用ek解密Ck(W)，得到相應(yīng)的明文文檔集合DCk(W)，DCk(W)=Dec(ek，Ck(W))。上述過(guò)程如3.1 節(jié)步驟11 所示。

7）GenUpdatlnto(SK，ek，VK，P，updtype，doc) →(T′，EI′，Cdoc)。

該算法由DO 執(zhí)行，當(dāng)DO 插入或刪除標(biāo)識(shí)符為doc的文檔ddoc時(shí)，需要更新加密索引樹(shù)和查找表，生成更新信息{T′，EI′，Cdoc}發(fā)送給CSP，此過(guò)程如3.1 節(jié)步驟12 所示。在該算法中，updtype∈{Del，Ins}表示更新類(lèi)型為刪除或插入；P表示在更新期間需要修改的樹(shù)節(jié)點(diǎn)組成的集合，一般為從更新的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)。具體地：

①當(dāng)updtype為Del 時(shí)，DO 查找文檔標(biāo)識(shí)符doc對(duì)應(yīng)的葉子節(jié)點(diǎn)并將其刪除，然后遵循索引樹(shù)構(gòu)造規(guī)則對(duì)P中節(jié)點(diǎn)的向量Du依次進(jìn)行修改，生成新的節(jié)點(diǎn)集合P′。接著通過(guò)偽隨機(jī)函數(shù)對(duì)P′中內(nèi)部節(jié)點(diǎn)的向量Du加密，得到加密后的更新信息EI′，再生成更新后的查找表T′。DO 將{T′，EI′，null}提交給CSP。

②當(dāng)updtype為Ins 時(shí)，DO 首先對(duì)文檔ddoc進(jìn)行加密得到Cdoc，并且生成一個(gè)新的葉子節(jié)點(diǎn)，然后依據(jù)平衡二叉樹(shù)的插入規(guī)則，在不破壞搜索索引樹(shù)平衡結(jié)構(gòu)的情況下更新索引樹(shù)，更新時(shí)必須保證原先的葉子節(jié)點(diǎn)仍為葉子節(jié)點(diǎn)。接著更新從新葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的節(jié)點(diǎn)得到P′。最后對(duì)新葉子節(jié)點(diǎn)和P′中內(nèi)部節(jié)點(diǎn)的向量Du加密得到EI′，再生成更新后的查找表T′。DO 將{T′，EI′，Cdoc}提交給CSP。

在更新查找表T 時(shí)，無(wú)論updtype是Del 還是Ins，DO 能夠根據(jù)文檔ddoc中所包含的關(guān)鍵詞，迅速定位到查找表T 中包含有這些關(guān)鍵詞的key字段。如果updtype為Del，DO 首先判斷相應(yīng)proof字段中doc是否屬于FIDk(W)，若doc?FIDk(W)，則相應(yīng)proof字段保持不變；若doc∈FIDk(W)，則需要重新計(jì)算相應(yīng)的proof字段，生成更新后查找表T′。如果updtype為Ins，對(duì)于與文檔ddoc相關(guān)的key字段所對(duì)應(yīng)查詢(xún)關(guān)鍵詞集合W，DO 計(jì)算文檔ddoc與這些W的相關(guān)性分?jǐn)?shù)：若ddoc不屬于最相關(guān)的前k個(gè)文檔，則相應(yīng)proof字段保持不變；若ddoc屬于最相關(guān)的前k個(gè)文檔，則得到新的FIDk(W)，DO 重新計(jì)算相應(yīng)proof字段，生成更新后查找表T′。

8）Update(C，ETr，T′，EI′，updtype，Cdoc) →(ETr′，T′，C′)。

CSP 收到DO 的更新信息{T′，EI′，Cdoc}后，根據(jù)EI′中的節(jié)點(diǎn)編號(hào)ID在索引樹(shù)ETr 中找到對(duì)應(yīng)的路徑，用EI′中的更新信息替換該路徑中對(duì)應(yīng)節(jié)點(diǎn)的信息，得到更新后的加密索引樹(shù)ETr′與更新后的查找表T′。如果updtype為Del，則CSP從C中刪除相應(yīng)加密文檔Cdoc；如果updtype為Ins，CSP 將Cdoc插入原有的C中，得到更新后的密文文檔集合C′。

4 安全性分析

4.1 文檔的隱私性

明文文檔集合被發(fā)送到CSP 之前，DO 會(huì)對(duì)其進(jìn)行加密處理，并且會(huì)在對(duì)DU 進(jìn)行授權(quán)認(rèn)證后，通過(guò)安全信道將密鑰傳遞給已授權(quán)認(rèn)證的DU。因此只有DO 和已授權(quán)認(rèn)證的DU 才能得到明文文檔，未授權(quán)認(rèn)證的DU 和CSP 是無(wú)法對(duì)密文文檔進(jìn)行解密的；而且本文方案中對(duì)于文檔的檢索、更新和驗(yàn)證操作都是基于文檔標(biāo)識(shí)符的，不需要訪問(wèn)文檔內(nèi)容，因此文檔隱私性得到了保證。

4.2 加密索引樹(shù)、查找表和搜索令牌的機(jī)密性

生成加密索引樹(shù)ETr 時(shí)，采用安全K近鄰算法對(duì)未加密索引樹(shù)Tr 的葉子節(jié)點(diǎn)的索引向量Du進(jìn)行加密。由于該算法具有不確定性，即使對(duì)于擁有相同關(guān)鍵詞集合的兩個(gè)文檔，其加密后得到的向量Iu也不相同；對(duì)于加密索引樹(shù)中內(nèi)部節(jié)點(diǎn)創(chuàng)建的哈希表φu，采用偽隨機(jī)函數(shù)和將關(guān)鍵詞及內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)位置的向量進(jìn)行加密隱藏，CSP 在未擁有偽隨機(jī)函數(shù)密鑰的情況下，不能推斷出內(nèi)部節(jié)點(diǎn)向量Du。構(gòu)建查找表T 時(shí)，采用偽隨機(jī)函數(shù)和MAC 函數(shù)μVK分別對(duì)查詢(xún)關(guān)鍵詞集W和文檔標(biāo)識(shí)符集合FIDk(W)加密，生成相應(yīng)字段key和proof，在CSP 未擁有密鑰K1和VK的情況下，不能推斷出查詢(xún)關(guān)鍵詞集W和文檔標(biāo)識(shí)符集合FIDk(W)。

4.3 查詢(xún)的無(wú)關(guān)聯(lián)性

本文方案對(duì)查詢(xún)向量Q采用二進(jìn)制向量隨機(jī)拆分進(jìn)行不確定性加密，即使對(duì)前后兩次相同的搜索請(qǐng)求，所生成的加密查詢(xún)向量也是不同的，從這個(gè)角度考慮保證了查詢(xún)的無(wú)關(guān)聯(lián)性。然而，當(dāng)搜索請(qǐng)求相同時(shí)，生成的TuW卻是相同的，搜索執(zhí)行時(shí)訪問(wèn)的節(jié)點(diǎn)和最終得出的加密文檔也都是相同的；此外，相同的搜索請(qǐng)求即使被加密成了不同的向量，計(jì)算得到的相關(guān)性分?jǐn)?shù)也是相同的?；谝陨蟽牲c(diǎn)，僅在CSP能夠關(guān)聯(lián)相同搜索請(qǐng)求的情況下，在已知密文模型下會(huì)泄露檢索模式或訪問(wèn)模式。

4.4 檢索的公平性

本文方案中，DU 首先把搜索費(fèi)用存入FairPayment 智能合約的存款池，CSP 在執(zhí)行檢索任務(wù)后，向合約支付一定的押金并返回相關(guān)檢索結(jié)果，合約自動(dòng)驗(yàn)證檢索結(jié)果是否正確完整。若驗(yàn)證通過(guò)，合約按照預(yù)定義的分配比例將DU 支付的搜索費(fèi)用從存款池中轉(zhuǎn)移給DU 和CSP（分別作為消息費(fèi)和服務(wù)費(fèi)），將CSP 的押金返回，并將搜索結(jié)果發(fā)送給DU；否則，退回DU 的搜索費(fèi)并將CSP 的押金轉(zhuǎn)給DU 作為補(bǔ)償。所以，CSP 為了獲取服務(wù)費(fèi)并且不被扣除押金，將會(huì)返回正確的檢索結(jié)果；同時(shí)，DU 不能惡意拒絕支付費(fèi)用，智能合約會(huì)根據(jù)預(yù)設(shè)的條件自動(dòng)執(zhí)行協(xié)議，保證了檢索的公平與可信。

5 性能分析

本文方案使用Python 實(shí)現(xiàn)可搜索加密算法，其中偽隨機(jī)函數(shù)采用HMAC-MD5 模擬，MAC 函數(shù)采用HMAC-SHA256。以太坊的仿真實(shí)驗(yàn)在以太坊虛擬機(jī)（Ethereum Virtual Machine，EVM）上進(jìn)行，使用Solidity 語(yǔ)言構(gòu)建了以太坊智能合約。計(jì)算機(jī)硬件配置為Inter Core i5 7300HQ@2.50 GHz 處理器、RAM 16 GB、SSD 512 GB、操作系統(tǒng)為Ubuntu 18.04LTS。

5.1 關(guān)鍵算法性能分析

DO 索引生成階段GenIndex 算法的計(jì)算開(kāi)銷(xiāo)包括加密索引樹(shù)的構(gòu)建和查找表的構(gòu)建，CSP 檢索階段Search 算法的計(jì)算開(kāi)銷(xiāo)包括加密索引樹(shù)的檢索和查找表的定位，以下對(duì)GenIndex 和Search 的計(jì)算開(kāi)銷(xiāo)進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中使用的數(shù)據(jù)集源自文獻(xiàn)［31］，數(shù)據(jù)包含20 個(gè)類(lèi)別，共9 804 篇文檔，本文選用5 000 篇文檔作為測(cè)試數(shù)據(jù)。

為觀 察DO 執(zhí)行GenIndex 以及CSP 執(zhí)行Search 的計(jì)算開(kāi)銷(xiāo)與文檔數(shù)量的關(guān)系，在實(shí)驗(yàn)1 中設(shè)置文檔數(shù)量為500～5 000（步長(zhǎng)500），實(shí)驗(yàn)結(jié)果如圖2 所示。從圖2（a）可以看出，GenIndex 的時(shí)間隨著文檔數(shù)量的增加基本呈線性增長(zhǎng)，特別地，當(dāng)測(cè)試文檔數(shù)為500、5 000 時(shí)，GenIndex 的時(shí)間分別為221.655 s、2 012.544 s。需要說(shuō)明的是，該項(xiàng)操作可在離線狀態(tài)下執(zhí)行，消耗的時(shí)間成本是可接受的。

如圖2（b）所示，可以看出，Search 的時(shí)間隨著文檔數(shù)量的增加基本呈對(duì)數(shù)增長(zhǎng)，在目前實(shí)驗(yàn)文檔數(shù)下，Search 的時(shí)間均小于1 s，時(shí)間成本是可接受的。特別地，當(dāng)測(cè)試文檔數(shù)為500、5 000 時(shí)，Search 的時(shí)間分別為7.5 ms 和50.2 ms。

圖2 GenIndex、Search的文檔數(shù)量與計(jì)算開(kāi)銷(xiāo)的關(guān)系Fig.2 Relationships between computational cost and number of documents of GenIndex，Search

5.2 智能合約性能分析

以太坊區(qū)塊鏈在以太坊虛擬機(jī)中實(shí)現(xiàn)智能合約，以太坊虛擬機(jī)中的每一步操作都會(huì)產(chǎn)生一定的消耗，用gas 來(lái)計(jì)算，每項(xiàng)操作的特定gas 消耗值被稱(chēng)為gas used，單位gas 的價(jià)格（用以太幣計(jì)算）為gas price，實(shí)際的交易成本為二者的乘積，實(shí)驗(yàn)于2021 年7 月25 日進(jìn)行，ETH 的價(jià)格是1 ether=2175 USD，gas price=1 Gwei，1 Gwei=109wei=10-9ether。

本文方案的智能合約部署在Ropsten 測(cè)試網(wǎng)絡(luò)中，各個(gè)實(shí)體對(duì)應(yīng)的賬戶(hù)、合約地址見(jiàn)表2。

表2 各實(shí)體對(duì)應(yīng)的地址Tab.2 Address corresponding to each entity

實(shí)驗(yàn)測(cè)試了FairPayment 智能合約中各項(xiàng)功能的花費(fèi)，結(jié)果如表3 所示。其中，DU 獲取檢索結(jié)果getSearchResults沒(méi)有成本，這是因?yàn)間etSearchResults 只執(zhí)行讀取操作獲取結(jié)果。表3 結(jié)果表明本文方案能夠以可接受的開(kāi)銷(xiāo)實(shí)現(xiàn)結(jié)果驗(yàn)證和公平支付。

表3 智能合約花費(fèi)測(cè)試Tab.3 Smart contract cost test

5.3 功能比較

將現(xiàn)有的基于區(qū)塊鏈的可搜索加密方案與本文方案分別從區(qū)塊鏈技術(shù)、執(zhí)行搜索算法的平臺(tái)、是否在區(qū)塊鏈上存儲(chǔ)加密索引、是否支持訪問(wèn)控制、是否支持多關(guān)鍵詞檢索以及是否支持檢索結(jié)果可排序6 個(gè)方面進(jìn)行對(duì)比分析，對(duì)比結(jié)果如表4 所示。

從表4 可以看出，文獻(xiàn)［24-25］方案都是由云服務(wù)器執(zhí)行搜索算法，基于比特幣實(shí)現(xiàn)公平支付；然而由于比特幣智能合約不是圖靈完備的，致使交易過(guò)程復(fù)雜以及交易周期長(zhǎng)，即使并未在區(qū)塊鏈上存儲(chǔ)加密索引也導(dǎo)致區(qū)塊鏈開(kāi)銷(xiāo)高。在基于以太坊的可搜索加密方案中，文獻(xiàn)［26］方案由分布式存儲(chǔ)網(wǎng)絡(luò)中的簽約服務(wù)節(jié)點(diǎn)執(zhí)行搜索算法，由分布式存儲(chǔ)網(wǎng)絡(luò)中的仲裁節(jié)點(diǎn)檢查結(jié)果的正確性，并基于以太坊智能合約實(shí)現(xiàn)公平支付；然而由區(qū)塊鏈存儲(chǔ)復(fù)雜且占用空間較多的索引導(dǎo)致區(qū)塊鏈開(kāi)銷(xiāo)增加。文獻(xiàn)［27-29］方案都是基于以太坊智能合約執(zhí)行搜索算法以及實(shí)現(xiàn)公平支付；但是由于區(qū)塊鏈存儲(chǔ)復(fù)雜且占用空間較多的索引會(huì)消耗大量時(shí)間并且智能合約執(zhí)行復(fù)雜的搜索算法亦會(huì)使費(fèi)用成本增加，兩者均導(dǎo)致區(qū)塊鏈開(kāi)銷(xiāo)升高。本文方案由云服務(wù)器存儲(chǔ)加密索引樹(shù)和查找表，同時(shí)執(zhí)行搜索算法，基于以太坊智能合約實(shí)現(xiàn)公平支付，有效降低智能合約執(zhí)行操作的復(fù)雜性，從而降低區(qū)塊鏈開(kāi)銷(xiāo)；此外，在訪問(wèn)控制、多關(guān)鍵詞檢索和檢索結(jié)果可排序方面，僅本文方案同時(shí)支持此三項(xiàng)功能。綜上分析，在以上功能方面，相較于對(duì)比方案，本文方案考慮較為全面。

表4 基于區(qū)塊鏈的可搜索加密方案的功能對(duì)比分析Tab.4 Functional comparison and analysis of searchable encryption schemes based on blockchain

5.4 計(jì)算開(kāi)銷(xiāo)對(duì)比

將本文方案與相關(guān)對(duì)比方案在索引、搜索、驗(yàn)證方面的計(jì)算開(kāi)銷(xiāo)進(jìn)行對(duì)比，結(jié)果如表5 所示。其中E0和E1分別表示兩個(gè)不同乘法循環(huán)群上的指數(shù)運(yùn)算，MM表示模乘運(yùn)算，H 表示散列運(yùn)算，F(xiàn)表示偽隨機(jī)函數(shù)運(yùn)算，V表示MAC函數(shù)運(yùn)算，L表示構(gòu)建每個(gè)內(nèi)部節(jié)點(diǎn)的操作，X 表示n維向量間點(diǎn)積運(yùn)算，E和D分別表示加密和解密操作，M表示取模運(yùn)算。SIG表示簽名算法，包含簽名和驗(yàn)證2 個(gè)過(guò)程；“—”表示不參與此項(xiàng)操作。g表示條件表達(dá)式的記錄條數(shù)，IA表示與門(mén)訪問(wèn)策略的下標(biāo)，Y 表示樹(shù)型訪問(wèn)策略的葉子節(jié)點(diǎn)個(gè)數(shù)，j表示返回密文文件個(gè)數(shù)，a表示滿(mǎn)足條件表達(dá)式的文檔標(biāo)識(shí)符被分割成的份數(shù)，b表示數(shù)據(jù)使用者預(yù)測(cè)步數(shù)，t為W中的關(guān)鍵詞數(shù)量，n為關(guān)鍵詞字典DW的大小，Z為查找表中記錄數(shù)量，θ為包含查詢(xún)關(guān)鍵詞的文檔數(shù)量，現(xiàn)實(shí)場(chǎng)景中，θ遠(yuǎn)小于文檔集合基數(shù)m。

表5 基于區(qū)塊鏈的可搜索加密方案的計(jì)算開(kāi)銷(xiāo)對(duì)比分析Tab.5 Computational cost comparison and analysis of searchable encryption schemes based on blockchain

索引生成階段，文獻(xiàn)［24］方案需要在關(guān)鍵詞字典和包含關(guān)鍵詞的文檔集合上進(jìn)行1 次偽隨機(jī)函數(shù)運(yùn)算、1 次散列運(yùn)算、1 次簽名算法運(yùn)算。文獻(xiàn)［25］方案需要在關(guān)鍵詞字典和包含關(guān)鍵詞的文檔集合上進(jìn)行3 次偽隨機(jī)函數(shù)運(yùn)算、1 次加密操作、1 次散列運(yùn)算。文獻(xiàn)［26］方案需要在文檔的ID 和添加標(biāo)記集合上分別進(jìn)行1 次散列運(yùn)算，在明文文檔合集上進(jìn)行1 次加密操作，在關(guān)鍵詞字典上進(jìn)行1 次偽隨機(jī)函數(shù)運(yùn)算。文獻(xiàn)［27］方案的數(shù)據(jù)擁有者需要進(jìn)行a次耗時(shí)的模乘運(yùn)算，還要進(jìn)行2(a+1)g次偽隨機(jī)函數(shù)運(yùn)算。文獻(xiàn)［28-29］方案的數(shù)據(jù)擁有者都需要進(jìn)行耗時(shí)的指數(shù)和模乘運(yùn)算，同時(shí)，文獻(xiàn)［28］方案需要在每個(gè)關(guān)鍵詞上進(jìn)行2 次偽隨機(jī)函數(shù)運(yùn)算，文獻(xiàn)［29］方案進(jìn)行1 次偽隨機(jī)函數(shù)運(yùn)算。本文方案采用平衡二叉樹(shù)作為索引，檢索效率高，內(nèi)部節(jié)點(diǎn)的構(gòu)建需進(jìn)行m-1 次，每個(gè)內(nèi)部節(jié)點(diǎn)的加密需要對(duì)其向量中的每一位進(jìn)行1 次對(duì)稱(chēng)加密運(yùn)算，每個(gè)葉子節(jié)點(diǎn)向量由安全K近鄰算法進(jìn)行加密，需進(jìn)行兩次n×n矩陣與n維向量的乘法運(yùn)算；構(gòu)建一個(gè)與加密索引樹(shù)相匹配的查找表，需要進(jìn)行Z次偽隨機(jī)函數(shù)運(yùn)算和Z次MAC 函數(shù)運(yùn)算。

搜索階段，文獻(xiàn)［26］方案對(duì)發(fā)布列表和文摘索引分別進(jìn)行O(Z)次比較，再進(jìn)行m次散列運(yùn)算搜索。文獻(xiàn)［27］方案需要進(jìn)行b次耗時(shí)的模乘運(yùn)算，還要進(jìn)行2b次偽隨機(jī)函數(shù)運(yùn)算。文獻(xiàn)［28-29］方案生成鍵值對(duì)的查找表作為索引，具有O(Z)的搜索效率。文獻(xiàn)［26-29］方案均在區(qū)塊鏈上存儲(chǔ)加密索引和執(zhí)行搜索算法，致使區(qū)塊鏈開(kāi)銷(xiāo)高，既占用存儲(chǔ)空間，效率也低。而文獻(xiàn)［24-25］方案與本文方案都采用CSP進(jìn)行搜索，CSP 存儲(chǔ)密文文檔和加密索引，能減小區(qū)塊鏈開(kāi)銷(xiāo)，提高檢索效率。本文方案對(duì)內(nèi)部節(jié)點(diǎn)進(jìn)行tθ(lbm-1)次解密運(yùn)算，在最壞情況下，需做2θ次兩個(gè)n維向量間的點(diǎn)積運(yùn)算和θ次取模運(yùn)算，根據(jù)DU 的token在查找表中定位相應(yīng)的proof，需要進(jìn)行O(Z)次比較操作。

驗(yàn)證結(jié)果的正確性階段，文獻(xiàn)［24］方案移除審計(jì)機(jī)構(gòu)，但需要用戶(hù)在本地進(jìn)行m次散列運(yùn)算和m次簽名算法運(yùn)算，隨著文檔數(shù)量的增加，驗(yàn)證時(shí)間增加。文獻(xiàn)［25］方案僅需要進(jìn)行4 次散列運(yùn)算，但過(guò)程中需要涉及到比特幣腳本上的6筆交易，驗(yàn)證時(shí)間長(zhǎng)、效率低。文獻(xiàn)［26］方案需要分布式存儲(chǔ)平臺(tái)中仲裁者分片上的每個(gè)仲裁節(jié)點(diǎn)對(duì)用戶(hù)端獲得的添加標(biāo)記集合進(jìn)行j次散列運(yùn)算，再重新執(zhí)行搜索操作進(jìn)行m次散列運(yùn)算以驗(yàn)證檢索結(jié)果，計(jì)算開(kāi)銷(xiāo)大。文獻(xiàn)［29］方案和本文方案采用智能合約進(jìn)行搜索結(jié)果的驗(yàn)證，文獻(xiàn)［29］方案需要進(jìn)行j！次散列運(yùn)算，本文方案僅需要進(jìn)行1 次MAC 函數(shù)運(yùn)算，判斷MAC 函數(shù)運(yùn)算后值是否正確，完成驗(yàn)證。

綜上所述，相較于其他具有驗(yàn)證功能的對(duì)比方案，本文方案在驗(yàn)證階段的計(jì)算開(kāi)銷(xiāo)是最低的。這是由于本文方案采用CSP 存儲(chǔ)密文文檔和加密索引、并執(zhí)行搜索算法，而智能合約僅需執(zhí)行驗(yàn)證和公平支付操作，使得其計(jì)算開(kāi)銷(xiāo)低；但是這也導(dǎo)致CSP 的存儲(chǔ)開(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)有所增加，但從搜索階段計(jì)算開(kāi)銷(xiāo)的分析和Search 算法的實(shí)驗(yàn)結(jié)果可以看出，CSP 搜索階段的計(jì)算開(kāi)銷(xiāo)也是可以接受的。

6 結(jié)語(yǔ)

本文提出了一種基于以太坊區(qū)塊鏈的支持驗(yàn)證與公平支付的多關(guān)鍵詞排序檢索方案，實(shí)現(xiàn)了檢索結(jié)果的驗(yàn)證、交易三方間的公平支付以及對(duì)密文的多關(guān)鍵詞排序檢索。為了實(shí)現(xiàn)檢索結(jié)果的可驗(yàn)證與公平支付，同時(shí)降低時(shí)間和費(fèi)用成本，方案設(shè)計(jì)由云服務(wù)器存儲(chǔ)加密索引樹(shù)和查找表、并執(zhí)行搜索操作；由以太坊智能合約完成檢索結(jié)果的驗(yàn)證與公平支付，有效降低了智能合約執(zhí)行操作的復(fù)雜性，減少了時(shí)間和費(fèi)用開(kāi)銷(xiāo)，提高了驗(yàn)證效率；此外，方案以平衡二叉樹(shù)為索引，在保證檢索效率的同時(shí)，實(shí)現(xiàn)了多關(guān)鍵詞檢索、檢索結(jié)果可排序和動(dòng)態(tài)更新功能，提升了方案的靈活性和用戶(hù)友好性。最后對(duì)方案的安全性和性能進(jìn)行了分析，并對(duì)方案進(jìn)行了仿真實(shí)驗(yàn)。性能分析及實(shí)驗(yàn)結(jié)果表明本文方案具有可行性與實(shí)用性。功能對(duì)比結(jié)果表明，相較于現(xiàn)有的基于區(qū)塊鏈的可搜索加密方案，本文方案在功能方面考慮更為全面。此外，本文方案的驗(yàn)證過(guò)程是針對(duì)所有檢索結(jié)果進(jìn)行的，有進(jìn)一步優(yōu)化的空間。未來(lái)研究針對(duì)特定交易的驗(yàn)證策略，以更好地滿(mǎn)足用戶(hù)需求，同時(shí)降低時(shí)間成本和費(fèi)用成本。