杜瑞忠　蔣浩宇　李明月

摘要： 傳統(tǒng)公鑰可搜索加密方案中，大多采用分布式雙陷門公鑰密碼系統(tǒng)分發(fā)密鑰，通過子集決策機制實現(xiàn)密文檢索，但是系統(tǒng)之間通信開銷較大。本文提出了1種新的可驗證的云邊端環(huán)境下的公鑰可搜索加密方案VSE－EPOMFC（Verifiable Searchable Encryption- Efficient Privacy－preserving Outsourced calculation framework with Multiple keys Filtering Computing， VSE－EPOMFC）。方案VSE－EPOMFC設計了1種基于部分同態(tài)加密的能在密文下計算的過濾算法篩選無意義任務來降低通信開銷。針對客戶端設備資源受限的缺點，采用閾值簽名機制，將客戶端簽名、驗證的任務委托給邊緣結(jié)點，輕量化了客戶端的驗證開銷與存儲開銷。仿真實驗結(jié)果表明，方案VSE－EPOMFC在任務集匹配度II的情況下通信時間節(jié)省了25.46%，在任務集匹配度I的情況下通信時間節(jié)省了62.21%。

關(guān)鍵詞：公鑰可搜索加密；可驗證；輕量化；云邊端

中圖分類號：中圖分類號TP309.7文獻標志碼：A文獻標識碼

Verifiable lightweight searchable encryption in cloud edge environment

DU? Ruizhong1，2，JIANG? Haoyu1，2，LI? Mingyue1，2

（1 School of Cyber Security and Computer， Hebei University， Baoding，Hebei 071002， China; 2 Hebei Key Laboratory

of Highly Trusted Information System， Baoding，Hebei 071002， China）

Abstract：? In the traditional public key searchable encryption schemes， the distributed two－trapdoor public key cryptosystem is mostly used to distribute the key， and the ciphertext retrieval is realized through the subset decision mechanism， but the communication overhead between systems is relatively large. This paper proposes a new verifiable public key searchable encryption scheme on cloud－edge －end environment （Verifiable Searchable Encryption Efficient Privacy－preserving Outsourced calculation framework with Multiple keys Filtering Computing， VSE－EPOMFC）. Scheme VSE－EPOMFC designs a filtering algorithm based on partial homomorphic encryption that can be calculated under ciphertext to filter meaningless tasks to reduce communication overhead. In view of the limitation of client device resources， the threshold signature mechanism is used to entrust the task of client signature and verification to the edge node， which lightens the verification and storage overhead of the client. The simulation results show that the communication time of VSE－EPOMFC is saved by 25.46% in the case of task set matching degree II and 62.21% in the case of task set matching degree I.

Key words： PEKS;verifiable;lightweight;cloud－edge－end environment

近些年，隨著物聯(lián)網(wǎng)和大數(shù)據(jù)的迅速發(fā)展，據(jù)GSMA預測，2025年全球物聯(lián)網(wǎng)終端連接數(shù)量將達到250億，物聯(lián)網(wǎng)設備數(shù)量將爆發(fā)式增長① https：//m.thepaper.cn/baijiahao_17826588。由于物聯(lián)網(wǎng)設備計算能力較弱，只能處理輕量級的任務，并且需要將復雜任務外包，因此逐漸形成了云邊端模型。在云邊端模型中，各方實體都是半可信的，邊緣節(jié)點能夠在數(shù)據(jù)所有者不知道的情況下竊取他們的信息并執(zhí)行惡意操作。為了保護數(shù)據(jù)隱私，數(shù)據(jù)持有人需要在敏感數(shù)據(jù)外包之前對其加密。一種方法是用戶可以下載全部數(shù)據(jù)并解密，但是這種方法下載了大量不必要的數(shù)據(jù)，顯然不具備可用性［2］。

為了解決上述問題，提出了云邊端環(huán)境下的可搜索加密方案，輕量化客戶端的存儲與計算開銷，解決了客戶端設備資源受限的問題。另一方面，由于半可信的云端可能返回不正確的搜索結(jié)果，設計基于可驗證的可搜索加密方案是近年來的另一個目標。

本文提出了可驗證的輕量化VSE－EPOMFC方案，設計了1種過濾算法來降低系統(tǒng)開銷。貢獻主要體現(xiàn)在以下3個方面：

（1） 引入了邊緣結(jié)點代替客戶端執(zhí)行計算簽名及驗證的任務，輕量化了客戶端驗證與存儲開銷。邊緣結(jié)點解決了客戶端計算、存儲資源匱乏的問題。

（2） 利用分布式雙陷門公鑰密碼系統(tǒng) （Distributed Two－Trapdoor Public－Key Cryptosystem，DT－PKC）、子集決策機制、部分同態(tài)加密3種技術(shù)，本研究設計了1種搜索前過濾搜索任務的算法，整個過程在密文下計算，保障用戶隱私，能在任務集有較多的無意義任務的情況下，減少系統(tǒng)的通信開銷。

（3） 仿真實驗評估了方案VSE－EPOMFC與SE－EPOM在搜索時的通信開銷，與方案CP－ABKS比較了客戶端的驗證開銷。實驗結(jié)果表明方案VSE－EPOMFC在搜索性能與驗證性能方面都有一定程度的提升。

對稱可搜索加密（Symmetric Searchable Encryption， SSE）計算速度快，但是存在嚴重的密鑰管理問題。為了解決以上問題，Boneh等［3］首先提出了基于公鑰的可搜索加密方案（Public Key Encryption with Keyword Search，PEKS），減少了多用戶場景下的密鑰數(shù)量。為了保證搜索結(jié)果的正確性，Zhang等［4］提出了1種可驗證的無證書的公鑰可搜索加密方案，解決了密鑰托管和證書管理問題。Liu等［5］設計了1種在多用戶環(huán)境下的可驗證的動態(tài)SSE方案，云服務器使用RSA累加器返回驗證信息給用戶。文獻［4-5］方案需要用戶或者數(shù)據(jù)持有人執(zhí)行一定的驗證操作，對于多用戶下資源受限的客戶端設備是1個挑戰(zhàn)。Chen等［6］在車載社交網(wǎng)絡的背景下，使用智能合約代替云服務器進行搜索和驗證，降低了客戶端的驗證開銷。從安全角度出發(fā)，Du等［7］通過引入?yún)^(qū)塊鏈實現(xiàn)了數(shù)據(jù)持有人與用戶之間的雙向認證，同時滿足前向和后向安全。Song等［8］通過利用重加密密碼系統(tǒng)和索引洗牌協(xié)議保護搜索模式和訪問模式。為了降低客戶端的壓力，Wang等［9］提出了1種基于工業(yè)物聯(lián)網(wǎng)環(huán)境下的輕量級PEKS方案，將復雜的任務委托給邊緣結(jié)點，消除了大部分方案由于雙線性配對運算帶來的沉重的計算開銷。He等［10］提出了1種新穎的魚骨鏈結(jié)構(gòu)，保證了客戶端的存儲開銷與關(guān)鍵字數(shù)量無關(guān)。

PEKS面臨KGA（Keyword Guess Attack）這一固有問題，主要原因是關(guān)鍵字空間遠遠小于密文空間，在實際搜索過程中，惡意用戶通常會選擇一些使用頻率較高的熱詞進行搜索。Chen等［11］提出了1種新的服務器輔助的PEKS方案SA－PEKS。使用輔助的服務器作為中介，數(shù)據(jù)持有人和用戶在生成可搜索密文和搜索陷門之前必須向關(guān)鍵字服務器（Keyword Server，KS）驗證身份并運行交互協(xié)議才能返回二次處理的可搜索密文、陷門。通過這種方法，將可搜索密文、陷門的生成過程變成了1種在線的方式，從而防止了惡意的內(nèi)部服務器的攻擊。Chen等［12］緊接著提出了1種雙服務器測試的DS－PEKS方案，與前者設計思路類似，使用前端服務器預處理并發(fā)送狀態(tài)信息、密文，后端服務器產(chǎn)生最終的陷門、可搜索密文并測試。2019年，Hwang等［13］提出了基于ElGamal密碼系統(tǒng)的無通道安全PEKS方案，同時防止了內(nèi)部、外部的攻擊。文獻［14］中，利用2個非共謀的服務器抵抗內(nèi)部KGA，免雙線性對運算的結(jié)構(gòu)輕量化了客戶端的開銷。

Huang等［15］構(gòu)建了1個具有多關(guān)鍵字搜索的PEKS方案PE－MKS，但是沒有支持恒定大小的搜索陷門、可搜索密文，它們的大小與關(guān)鍵字數(shù)量呈線性關(guān)系。Wu等［16］提出了1種多用戶環(huán)境下基于同態(tài)加密的可驗證的PEKS方案。對于現(xiàn)有的公鑰可搜索加密方案，構(gòu)建主要依賴于雙線性配對。但是，PEKS在客戶端的計算較為復雜［17］。因此，常見的設計輕量級PEKS方案的思路就是用某些操作替換昂貴的雙線性配對。我們還可以像Liu等［18］提出的方案一樣，設計1種在線、離線加密，將完整的過程劃分成2部分，離線部分可以預先計算，從而減少了復雜的客戶端加密開銷。2020年，Liu等［19］提出了在分布式系統(tǒng)中執(zhí)行搜索的多關(guān)鍵字PEKS方案，攻擊者想要執(zhí)行KGA需要獲取多個服務器的密鑰，因此方案SE－EPOM成功抵抗了來自內(nèi)部、外部攻擊者的攻擊。但是該方案在半可信云服務器環(huán)境下構(gòu)建，缺乏對搜索結(jié)果的驗證。此外，還存在系統(tǒng)之間通信開銷過大的問題。Zhang等［20］提出了1種雙向的公鑰可搜索加密方案。文獻［21-22］構(gòu)建了基于密文策略的可搜索加密方案，提供了細粒度的訪問控制，在文獻［23］中，客戶端需要計算額外的驗證過程，對于資源受限的設備是1個很大的挑戰(zhàn)。針對以上問題，本文提出了云邊端環(huán)境下可驗證的輕量化可搜索加密方案。

1 資料與方法

1.1 預備知識

1.1.1 DT－PKC

分布式雙陷門公鑰密碼系統(tǒng)（DT－PKC）可以將1個強私鑰SK=λ分成2部分，使得方案不僅支持弱私鑰ski解密，還可以通過分解強私鑰SKi=λi進行分布式解密，本文工作主要用到以下算法［24］：

1.2 模型構(gòu)建

1.2.1 系統(tǒng)模型

在方案VSE－EPOMFC中，系統(tǒng)由6部分實體組成，包括密鑰生成中心KGC（Key Generate Center， KGC）、多數(shù)據(jù)持有人MDO（Multi Data Owners， MDO）、邊緣結(jié)點EN（Edge Node， EN）、多用戶MDU（Multi Data Users， MDU）、云服務器CP（Cloud Platform， CP）和提供輔助計算服務的CSP（Cloud Service Provider， CSP）。圖1描述了系統(tǒng)模型，例如，企業(yè)將敏感數(shù)據(jù)外包給云服務器CP，方便授權(quán)的公司員工能夠隨時隨地訪問這些數(shù)據(jù)。在外包存儲到云服務器之前，應當選擇一部分結(jié)點作為管理人ENM （Edge Node Manger， ENM），為上傳的密文數(shù)據(jù)簽名，避免了以往方案中必須全部數(shù)據(jù)持有人同時在線簽名的限制。

（1）密鑰生成中心KGC負責產(chǎn)生并分發(fā)公共參數(shù)給多用戶MDU和多數(shù)據(jù)持有人MDO，分發(fā)部強私鑰給CP和CSP（實際生活中可以由政府等公信力強的機構(gòu)擔任），為邊緣結(jié)點管理人ENM產(chǎn)生密鑰對。

（2）多用戶MDU和多數(shù)據(jù)持有人MDO依靠從KGC產(chǎn)生的公共參數(shù)產(chǎn)生屬于自己的密鑰對，使用各自的公鑰產(chǎn)生可搜索密文SC和陷門TD，使用對稱密鑰加密文件，分別將加密文檔、可搜索密文和搜索陷門上傳至邊緣結(jié)點。

（3）邊緣結(jié)點主要由兩部分組成：代理邊緣結(jié)點ENM和普通邊緣結(jié)點EN。簽名由EN和ENM完成，ENM將多個邊緣結(jié)點產(chǎn)生的簽名進行整合，縮短了簽名長度。邊緣結(jié)點將加密文檔、可搜索密文和搜索陷門以及簽名上傳至CP。

（4）CP將加密文檔、可搜索密文、搜索陷門以及簽名在CSP備份。CP和CSP交互式的執(zhí)行子集決策機制、跨域安全計算協(xié)議，完成過濾和搜索，計算一個加密值。

（5）CP將加密值交給MDU。由MDU判斷對應的加密文檔是否屬于最終的搜索結(jié)果。MDU向CP申請獲取滿足條件的加密文檔。

（6）CSP收到MDU獲取加密文檔的請求之后，通過與ENM交互對相關(guān)加密文檔進行結(jié)果驗證，刪除其中被半可信云服務器增加的惡意文檔。CSP返回經(jīng)過搜索和驗證的加密文檔給MDU，MDU通過以上步驟獲取與感興趣關(guān)鍵字相關(guān)結(jié)果文檔。

1.2.2 威脅模型

在方案VSE－EPOMFC中，密鑰生成中心KGC被假設為是完全可信的，誠實的遵循協(xié)議去產(chǎn)生公共參數(shù)或者分發(fā)密鑰到各個實體。CP和CSP以及EN被假設為半可信的，即會誠實的遵循協(xié)議完成工作，但是會嘗試從加密的信息中推斷敏感信息。CP和CSP在過濾和搜索2個階段被假設為非共謀的2個實體。

多用戶MDU和多數(shù)據(jù)持有人MDO同樣是半可信的實體，會誠實的遵循協(xié)議完成工作。但是MDO可能會竊聽其他實體之間的通信，或者嘗試了解陷門信息。MDU可能會嘗試了解可搜索密文的信息或者由其他MDU上傳的陷門信息。

1.2.3 安全性定義

安全多方計算的安全定義

Kamara等［26］表示處在多方協(xié)議計算之間的共謀攻擊是1種有用信息的交換。這種有用信息指的是可信實體在整個協(xié)議計算過程中未規(guī)定過的輸入信息。只要多方參與者（敵手）能了解到這部分信息，那么共謀攻擊成立。方案SE－EPOMFC假設處在非共謀敵手攻擊模型下。

安全多方計算的安全性通過1種理想/現(xiàn)實世界模型來定義的。在當前模型中，必須首先設置集合P=（PMDO，PMDU，PCSP，PCP）表示各方執(zhí)行協(xié)議的實體對象，各方實體之間只能交互非協(xié)議信息。這里的各方實體主要包含4部分，包括MDO，MDU，還有負責過濾和搜索的CP和CSP。相應的會有敵手A=（AMDO，AMDU，ACSP，ACP）負責攻擊各個實體。

在現(xiàn)實世界中，執(zhí)行各種協(xié)議發(fā)生在各個實體P=（PMDO，PMDU，PCSP，PCP）之間，我們讓H∈P表示實體中完全可信的實體集合，讓J∈P-H表示實體中受到非共謀敵手攻擊并被破壞的實體集合。

再執(zhí)行過程的初始階段，P=（PMDO，PMDU，PCSP，PCP）中的實體PMDO或PMDU會收到輸入xMDO和xi，以及輔助輸入ZMDO和Zi，CP和CSP僅僅收到輔助輸入ZCP和ZCSP。當P是可信實體時，P∈H，outp是實體Pi的輸出。當P屬于被破壞的實體時，P∈I，outp輸出產(chǎn)生的是P執(zhí)行協(xié)議之后產(chǎn)生的新的輸出（被破壞的實體可能產(chǎn)生攻擊者偽造的輸出）。

某一部分實體Pi在現(xiàn)實世界中多方實體P=（PMDO，PMDU，PCSP，PCP）之間，同時存在敵手A=（AMDO，AMDU，ACSP，ACP）的情況下，執(zhí)行協(xié)議Π所產(chǎn)生的結(jié)果定義為：

IDEALPiΠ，，，z（k，x）={outp：P∈I}∪outpi。（1）

在理想世界中，所有的實體都會與完全可信的評估實體交互，在模擬器S=（SMDO，SMDU，SCSP，SCP）存在的情況下產(chǎn)生評估實體，我們用表示完全可信的評估實體。挑戰(zhàn)者會發(fā)送xi給。如果xi是⊥，那么返回⊥。否則，返回（x1，…，xi）給挑戰(zhàn)者。當P是可信實體時，P∈H，outp是完全可信實體返回給實體Pi的輸出。當P是屬于被破壞的實

密文不可區(qū)分性指的是上傳到CP和CSP的加密的可搜索密文不會泄露隱藏的關(guān)鍵字信息。同理，陷門隱私與密文不可區(qū)分性具有相似的概念，指的是產(chǎn)生的搜索陷門不會泄露隱藏的關(guān)鍵字信息。不可區(qū)分性游戲模型可以這樣定義：敵手選擇2個不同的關(guān)鍵字集發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機選擇一個計算可搜索密文并返回給敵手，此時，敵手嘗試猜測哪一個關(guān)鍵字集與挑戰(zhàn)者返回的密文對應。

假如不存在敵手A能在概率多項式時間內(nèi)從可搜索密文和搜索陷門中推斷出敏感的關(guān)鍵字信息，則關(guān)鍵字隱私能夠得到保障。定義的安全隱私游戲如下：

（1）初始化。通過輸入指定的k，挑戰(zhàn)者運行KeyGen算法產(chǎn)生SKCP，SKCSP，PKMDO，PKMDU，SKMDO，將SKCP，PKMDO，PKMDU發(fā)送給敵手A，私鑰SKCSP，SKMDO自己保留。

（2）挑戰(zhàn)。 敵手A選擇了兩對不同的關(guān)鍵字集合W0和W1，發(fā)送給挑戰(zhàn)者C。挑戰(zhàn)者從r∈0，1中隨機選擇一個值，運行算法Searchcp產(chǎn)生可搜索密文SC，發(fā)送給敵手A。

（1）初始化。通過輸入指定的k，挑戰(zhàn)者運行KeyGen算法產(chǎn)生SKCP，SKCSP，PKMDO，PKMDU，SKMDO，將SKCP，PKMDO，PKMDU發(fā)送給敵手A，私鑰SKCSP，SKMDO自己保留。

1.3 VSE－EPOMFC

本節(jié)從驗證輕量化、任務過濾2個小節(jié)簡單介紹了創(chuàng)新之處，首先將客戶端簽名和驗證的任務委托給邊緣結(jié)點降低客戶端的計算和存儲開銷，然后在搜索之前對任務進行過濾，篩選一部分不匹配的任務，降低系統(tǒng)之間的通信開銷。最后，具體方案構(gòu)造描述了算法細節(jié)。在表1中定義了論文使用的符號。

1.3.1 驗證輕量化

SE－EPOM通過引入通用關(guān)鍵字集W，將多關(guān)鍵字用二進制串形式加密，保證可搜索密文和陷門的大小與關(guān)鍵字數(shù)量無關(guān)。但是考慮到惡意的多數(shù)據(jù)持有人MDO、云服務器CP、CSP可能上傳錯誤的密文或者返回錯誤的搜索結(jié)果，通常是由MDO對密文進行簽名，MDU負責對搜索結(jié)果驗簽，此時客戶端將承擔計算密文、簽名、驗證簽名的任務，對于資源受限的客戶端設備，顯然是不可取的。因此，引入了邊緣結(jié)點代替MDO對密文執(zhí)行簽名，代替MDU驗證簽名，輕量化客戶端的驗證開銷。使用1種閾值簽名機制，先由邊緣結(jié)點EN1，EN2，…，ENi代替閾值數(shù)量的MDO對密文分別簽名，設置1個管理人ENM，根據(jù)多個簽名為每個文檔生成唯一的閾值簽名，縮短了簽名長度。

1.3.2 任務過濾

由于實際搜索過程中，需要用到大量的交互式算法，通信較為復雜，為了解決通信過程中由于大量不匹配的任務產(chǎn)生的不必要的通信開銷的問題，在子集決策機制的基礎上設計了1個過濾算法用于過濾完全不匹配的任務。

方案在搜索過程中用到了SE－EPOM中的子集決策機制，在密文的基礎上使用CP和CSP進行搜索。但是，當任務集中存在大量完全不匹配的加密二進制串時，方案SE－EPOM會產(chǎn)生多余的通信開銷。VSE－EPOMFC在搜索過程中增加了1個過濾算法，負責篩選完全不匹配的二進制串，如圖2所示。

只有當2個二進制串完全不匹配時，過濾算法生效。對密文進行計算，只能使用安全位加法和安全位乘法運算。為了便于理解，本文使用明文下的例子進行說明，實際情況下則需要在加密的二進制串上運行各種復雜的通信協(xié)議。過濾算法用于判斷兩個二進制串是否完全不匹配。首先當每個對應的加密位都不相同時，運用安全位乘法協(xié)議必定產(chǎn)生全為0的加密二進制串，接著使用安全位加法協(xié)議，對所有位累加，最后將結(jié)果交給多用戶MDU解密，如果結(jié)果為零表示2個二進制串必定完全不匹配，將其從任務集中刪除。

1.3.3 具體方案構(gòu)造

（1）初始化。 （SK，SK1，SK2，PP，H0，H1）←Setup（k）。

KGC首先執(zhí)行KeyGen得到強私鑰SK=λ，N=pq，s=-a2N（其中a∈Z*N2是隨機選取的）。然后KGC執(zhí)行SKeys對強私鑰λ進行拆分，得到2個部分強私鑰SK1=λ1，SK2=λ2。G和GT是2個大素數(shù)p階循環(huán)群，g是循環(huán)群G的生成元，e：G×G→GT是1個雙線性映射，選擇雙線性對參數(shù)BP={G，GT，e，p，g}，選擇2個抗碰撞哈希函數(shù)，H0：{0，1}*→Zp，H1：{0，1}*→G。最后，KGC將產(chǎn)生的參數(shù)PP={N，s，BP}，發(fā)送給多用戶MDU和多數(shù)據(jù)持有人MDO。將部分強私鑰SK1=λ1，SK2=λ2分發(fā)給CP和CSP，強私鑰λ秘密保存。

（2）生成密鑰。（pkMDU，skMDU，pkMDO，skMDO，pkm，skm）←KeyGen（SK，SK1，SK2，PP，ENi，ENM）。

MDU和MDO拿到公共參數(shù)PP=（N，s，BP）后執(zhí)行KeyGen產(chǎn)生屬于自己的密鑰對pkMDU，skMDU，pkMDO，skMDO。將ENM管理的邊緣結(jié)點小組設為EN=EN1，EN2，…，ENi，KGC會為ENM產(chǎn)生密鑰對（pkm=gb，skm=b），b∈Zp，管理人會輸出1個ξ-1次的多項式f（x）=cξ-1xξ-1+…+c1x+c0，這里cj∈Zp（j∈［1，ξ-1］），c0=b，i≤2ξ-1。管理人選擇i個滿足多項式的元素對{（x1，y1），（x2，y2），…，（xi，yi）}，y1，…，yi 值發(fā)送給剩余邊緣結(jié)點EN1，EN2，…，ENi用于簽名。

（3）加密并簽名。（Cm，SCm，τ）←Searchcp（Did，W，WT，pkMDO，pkm）。

執(zhí)行表2算法1，分別使用AES和DT－PKC計算加密文檔和可搜索密文，然后計算至少閾值數(shù)量的簽名，管理人ENM將全部的簽名整合成唯一閾值簽名，從而縮短了簽名長度。

如表3算法2所示，最后得到了2個所有位都被加密的二進制串SC′m，TD′m。在這2組子串中，使用SMD協(xié)議相乘得到ftimpkMDU，使用SAD協(xié)議對ftimpkMDU中的每一位進行累加，結(jié)果記為ftmpkMDU，交給用戶使用弱私鑰skMDU解密得到fmt，若fmt=0，則用戶返回“需要過濾”，否則返回“不需要過濾”。

執(zhí)行搜索需要獲取公鑰pkMDU，pkMDO，CP和CSP提供部分強私鑰SK1，SK2以及經(jīng)過過濾的可搜索密文SC′m和陷門TD′m，CP和CSP執(zhí)行表4算法3，用戶最終獲得fmpkMDU后使用弱私鑰skMDU解密。若結(jié)果輸出0，表示陷門與可搜索密文不匹配；若結(jié)果輸出1，表示陷門與可搜索密文匹配，用戶向CP申請獲取相關(guān)的文檔C*m。

2 結(jié)果與分析

2.1 安全性分析

本節(jié)是安全性證明，需要證明2個部分：首先，證明方案VSE－EPOMFC能被安全實現(xiàn)。然后證明如果方案能安全實現(xiàn)（各方之間的協(xié)議是安全的），那么方案滿足密文不可區(qū)分性以及陷門隱私性。

定理1 方案VSE－EPOMFC在滿足敵手A=（AMDO，AMDU，ACSP，ACP）存在的情況下能被安全的實現(xiàn)。

證明? SimMDO收到輸入x，通過執(zhí)行以下的算法模擬敵手AMDO：首先計算TpkMDO←Enc（T，pkMDO），將結(jié)果返回給AMDO。因為DP－PKC滿足語義安全（在VI－A定理1有詳細描述），所以敵手AMDO在現(xiàn)實世界和理想世界輸出的結(jié)果是難以區(qū)分的。

SimCP通過執(zhí)行以下算法模擬敵手ACP：首先隨機的從（0，…，2n-1）中選擇T^，t^，加密產(chǎn)生（T^pkMDO，t^pkMDU）←Enc（T^，t^，pkMDO，pkMDU），計算t^pkMDU，T^pkMDO，-T^pkMDO，2個加密二進制串中對應的位使用SMD協(xié)議相乘得到f^tipkMDU。使用SAD協(xié)議對f^tipkMDU中的每一位進行累加，結(jié)果記為f^tpkMDU。SMD和SAD的安全性在VI－C定理2中有詳細證明。

SimMDO與SimCP交互后確定過濾的任務，接下來使用與VI－C定理3證明過程相同的方法計算搜索過程中用到的加密中間值c^ipkMDU，d^ipkMDU，R^ipkMDU，f^ipkMDU。最后SimCP發(fā)送全部的加密中間值給ACP，如果ACP返回⊥，那么SimCP同樣返回⊥。因為DT－PKC是滿足語義安全的，MDO是誠實的，敵手ACP在現(xiàn)實世界和理想世界輸出的結(jié)果是難以區(qū)分的。

SimCSP通過執(zhí)行以下的算法模擬敵手ACSP：隨機選擇一些數(shù)字，使用與VI－C定理3證明過程相同的方法計算加密中間值。SimCSP發(fā)送全部的加密中間值給ACSP，如果ACSP返回⊥，那么SimCSP同樣返回⊥。因為DT－PKC是滿足語義安全的，MDO是誠實的，敵手ACP在理想世界和現(xiàn)實世界中輸出的結(jié)果是難以區(qū)分的。

因此，方案VSE－EPOMFC能被安全實現(xiàn)得到證明。

定理2 如果方案VSE－EPOMFC能在滿足敵手A=（AMDO，AMDU，ACSP，ACP）存在的情況下被安全的實現(xiàn)，那么該方案同時也滿足密文不可區(qū)分性和陷門隱私。

證明 假設方案VSE－EPOMFC不滿足密文不可區(qū)分性或者陷門隱私，那么該方案不能被安全的實現(xiàn)。

設置1個實體Z，它的目標是想方設法區(qū)分出現(xiàn)實世界和理想世界。

假設方案VSE－EPOMFC不滿足定義1中的密文不可區(qū)分性，即存在一個敵手B使得等式（1）中的優(yōu)勢不可忽略。實體Z會要求A或者S破壞PCP，以便PCP將從PMDO收到的消息傳輸給Z。在整個過程中，PCP對外表現(xiàn)誠實可信，敵手B從Z內(nèi)部執(zhí)行攻擊。如果B發(fā)送WT0，WT1∈W給挑戰(zhàn)者C，那么：

（1） Z輸入（Searchcp，sid，WT，b）給PMDO，b隨機的從0，1中選擇，sid表示文檔id。

（2） 在現(xiàn)實世界中，PMDO計算SC并發(fā)送SC給PCP，PCP發(fā)送給實體Z。

（3） 在理想世界中，MDO發(fā)送（Searchcp，sid，WT，b）給f，f發(fā)送|WT，b|給S。S計算SC′發(fā)送給Z。

當且僅當B輸出1時，Z輸出1。輸出1表示敵手B能區(qū)分出可搜索密文，即滿足挑戰(zhàn)者-敵手游戲。如果Z與協(xié)議∏交互，因為現(xiàn)實世界敵手A扮演ACP的角色，此時B模擬SC。如果Z與SCP交互，因為理想世界敵手S扮演SCP的角色，此時B模擬SC′。

根據(jù)我們的假設，存在1個敵手B，在現(xiàn)實世界中，它能以不可忽略的優(yōu)勢區(qū)分可搜索密文，輸出1。而在理想世界中，輸出1的概率為50%。顯然，將B作為子程序運行的實體Z可以將現(xiàn)實世界中PCP執(zhí)行的結(jié)果與理想世界中PCP執(zhí)行的結(jié)果區(qū)分開來。協(xié)議∏不能安全地實現(xiàn)VSE－EPOMEC得到證明。

假設方案VSE－EPOMFC不滿足定義2中的陷門不可區(qū)分性，即存在一個敵手B′使得等式（2）中的優(yōu)勢不可忽略。實體Z會要求A或者S破壞PCP，以便PCP將從PMDU收到的消息傳輸給Z。在整個過程中，PCP對外表現(xiàn)誠實可信，敵手B′從Z內(nèi)部執(zhí)行攻擊。如果B′發(fā)送Wt0，Wt1∈W給挑戰(zhàn)者，那么：

（1） Z輸入（Trapdoor，sid，Wt，b）給PMDU，b隨機的從0，1中選擇，sid表示文檔id。

（2） 在現(xiàn)實世界中，PMDU計算TD并發(fā)送TD給PCP，PCP發(fā)送給實體Z。

（3） 在理想世界中，MDU發(fā)送（Trapdoor，sid，Wt，b）給f，f發(fā)送|Wt，b|給S。S計算TD′發(fā)送給Z。

當且僅當B′輸出1時，Z輸出1。輸出1表示敵手B′能區(qū)分出搜索陷門，即滿足挑戰(zhàn)者-敵手游戲。如果Z與協(xié)議∏交互，因為現(xiàn)實世界敵手A扮演ACP的角色，此時B′模擬TD。如果Z與SCP交互，因為理想世界敵手S扮演SCP的角色，此時B′模擬TD′。

根據(jù)我們的假設，存在1個敵手B′，在現(xiàn)實世界中，它能以不可忽略的優(yōu)勢區(qū)分搜索陷門，輸出1。而在理想世界中，輸出1的概率為50%。顯然，將B′作為子程序運行的實體Z可以將現(xiàn)實世界中PCP執(zhí)行的結(jié)果與理想世界中PCP執(zhí)行的結(jié)果區(qū)分開來。證明協(xié)議∏不能安全地實現(xiàn)VSE－EPOMEC。綜上，方案VSE－EPOMFC同時滿足密文不可區(qū)分性和陷門隱私。

2.2 性能評估

2.2.1 理論評估

表5從性能和安全性2個方面出發(fā)，對不同方案實現(xiàn)的功能進行比較。其中MDU和MDO表示多用戶、多數(shù)據(jù)持有人，LW表示輕量化，MK表示多關(guān)鍵字，IKGA和OKGA分別表示內(nèi)部、外部關(guān)鍵字猜測攻擊，CS表示可搜索密文大小，TS表示陷門大小，V表示搜索結(jié)果可驗證。文獻［3］是最早提出的公鑰可搜索加密方案，支持單用戶上傳數(shù)據(jù)、多數(shù)據(jù)持有人查詢，它的可搜索密文以及陷門大小必須隨關(guān)鍵字數(shù)量|Wid|線性增長。在安全性方面，文獻［13］基于1種密碼系統(tǒng)，同時滿足了IKGA與OKGA，文獻［14］通過使用雙服務器抵抗IKGA，設計了免雙線性對的算法，輕量化了客戶端的開銷。文獻［19］實現(xiàn)了大部分功能，但是客戶端不具備驗證搜索結(jié)果這一功能。文獻［20］提出了1種支持雙向關(guān)鍵字搜索的PEKS方案，允許數(shù)據(jù)持有人檢索上傳的數(shù)據(jù)。文獻［23］支持輕量化和可驗證性，但是其可搜索密文長度與屬性數(shù)量|Ai|有關(guān)。方案VSE－EPOMFC讓邊緣結(jié)點代替客戶端實現(xiàn)簽名并且驗證搜索結(jié)果，輕量化了客戶端的存儲和計算開銷。

2.2.2 實驗評估

為了評估方案VSE－EPOMFC的實際性能，進行了實驗。本實驗使用python語言，通信過程使用socket編程建立TCP可靠連接。設置了2臺虛擬機，將KGC，CP和MDO部署在具有6GB RAM和Intel（R） Core（TM） i5－10400F 2.90GHz處理器的Ubantu 20.04操作系統(tǒng)上，同時ENM（包括EN），CSP和MDU部署在具有4GB RAM和Intel（R） Core（TM） i5－10400F 2.90GHz處理器的Ubantu 20.04操作系統(tǒng)上。為了與方案SE－EPOM對比，實驗設置80位安全級別，參數(shù)N選擇1024位長。

實驗主要選擇了2種參數(shù)，一種是任務集完全不匹配任務所占的比例（搜索任務完全不匹配意味著對應的2個二進制串中所有的位均不匹配），我們用匹配度IV，III，II，I表示。當任務集完全不匹配的任務數(shù)為0時，匹配度為IV，表示不存在完全不匹配的任務。當任務集中有25%的任務完全不匹配，匹配度為III，以此類推。另一種參數(shù)選擇關(guān)鍵字數(shù)量，分別為5、10、15、20。

圖3比較了方案PEBKS，方案SE－EPOM以及VSE－EPOMFC方案在不同匹配度條件下，執(zhí)行搜索的時間開銷。PEBKS方案在單個服務器場景下執(zhí)行搜索，所以搜索時間開銷遠遠小于多臺服務器環(huán)境下執(zhí)行搜索的方案。SE－EPOM沒有使用過濾算法，直接對任務集進行搜索，可以看出它的時間開銷在11s上下波動，不受匹配度變化的影響。而方案VSE－EPOMFC由于使用了過濾算法，在匹配度為IV和III的條件下，過濾算法產(chǎn)生的時間開銷更多，當匹配度在II以下時，過濾算法能顯著降低SE－EPOM的時間開銷。

圖4和圖5比較了方案LFGS，方案CP－ABKS，方案VSE－EPOMFC在客戶端產(chǎn)生的驗證時間開銷與驗證存儲開銷，方案VSE－EPOMFC將客戶端執(zhí)行簽名和驗證的任務委托給邊緣結(jié)點，因此在客戶端的開銷與關(guān)鍵字數(shù)量無關(guān)。驗證使用了閾值簽名機制，邊緣結(jié)點管理人ENM通過整合簽名縮短了簽名長度，也降低了驗證的時間開銷和存儲開銷。CP－ABKS同樣支持搜索結(jié)果驗證，但是需要用戶執(zhí)行部分解密和驗證，給客戶端的設備帶來了額外開銷。

LFGS方案能準確的驗證搜索結(jié)果，但是它需要用戶和數(shù)據(jù)持有人之間的交互，當返回大量搜索結(jié)果時，會產(chǎn)生更多通信開銷。此外，LFGS方案只能支持單關(guān)鍵字搜索，不能部署在多關(guān)鍵字設置中執(zhí)行搜索結(jié)果驗證。LGFS方案使用的搜索結(jié)果驗證機制主要依賴于本地存儲的文件-關(guān)鍵字哈希表，如圖6所示，當本地存儲的文件-關(guān)鍵字哈希表較大時，會產(chǎn)生很高的計算開銷，它的計算復雜度為O（|F||W|），而VSE－EPOMFC采用的搜索結(jié)果驗證機制與文件數(shù)量有關(guān)，計算復雜度為O（|F|）。

過濾算法節(jié)省時間需要任務集一半以上的任務不完全匹配，更適用于特殊的場景，比如在某個醫(yī)療系統(tǒng)中，需要對病人的隱私實現(xiàn)高度的保密，醫(yī)生只能了解其身體狀況，其余信息一無所知，只能使用少量關(guān)鍵字去查詢病人以獲取病例信息。在當前場景下，病人作為數(shù)據(jù)持有人上傳加密的病例信息、可搜索密文到云中心，醫(yī)生作為用戶，可以借助邊緣設備簽名并驗證搜索結(jié)果的正確性。病人的隱私信息保密程度越高，醫(yī)生搜索到完全不匹配任務的可能性越大，最終必定會產(chǎn)生大量不匹配任務。方案VSE－EPOMFC節(jié)省了醫(yī)生與病人的時間，使其不用執(zhí)行復雜的驗證。

3 討論與結(jié)論

本文設計了1個在云邊端環(huán)境下可驗證的輕量化可搜索加密方案，說明了其關(guān)于理想現(xiàn)實模型、關(guān)鍵字隱私模型的定義并給予證明。與先前的工作相比，輕量化客戶端復雜的簽名與驗證開銷。通過引入邊緣結(jié)點，借助邊緣結(jié)點的緩存，減少了主干網(wǎng)絡上的流量負載。設計了1種過濾算法來降低搜索帶來的通信開銷。實驗表明VSE－EPOMFC適用于任務集不完全匹配任務較多的情況。通過對比了幾種方案在離線關(guān)鍵字猜測攻擊、多關(guān)鍵字、多用戶、多數(shù)據(jù)持有人、可驗證性等方面的差異，表明了VSE－EPOMFC在整體的功能性、安全性、計算存儲開銷等方面具有一定的優(yōu)勢。未來工作考慮在當前方案基礎上增加動態(tài)更新功能，同時對動態(tài)更新中關(guān)鍵字泄露問題做進一步研究。

參考文獻（References）

［1］MAO Y， YOU C， ZHANG J， et al. A survey on mobile edge computing： the communication perspective［J］. IEEE Communications Surveys & Tutorials， 2017， 19（4）： 2322-2358.

［2］CUI M M， FEI Y M， LIU Y. A survey on secure deployment of mobile services in edge computing［J］. Security and Communication Networks， 2021（5）： 1-8.

［3］BONEH D， DI CRESCENZO G D， OSTROVSKY R， et al. Public key encryption with keyword search［C］//Advances in Cryptology－EUROCRYPT 2004： International Conference on the Theory and Applications of Cryptographic Techniques. Interlaken， Switzerland： Springer， 2004： 506-522.

［4］ZHANG L， JIANG F， TANG X. Verifiable conjunctive keyword search with certificateless searchable［C］//2021 IEEE 20th International Conference on Trust， Security and Privacy in Computing and Communications （TrustCom）. IEEE， 2021： 9-16.

［5］LIU X Q， YANG G M， MU Y， et al. Multi－user verifiable searchable symmetric encryption for cloud storage［J］. IEEE Transactions on Dependable and Secure Computing， 2020， 17（6）： 1322-1332.

［6］CHEN B， WU L， WANG H， et al. A blockchain－based searchable public－key encryption with forward and backward privacy for cloud－assisted vehicular social networks［J］. IEEE Transactions on Vehicular Technology， 2019， 69（6）： 5813-5825.

［7］DU R， WANG Y. Verifiable blockchain－based searchable encryption with forward and backward privacy［C］//2020 16th International Conference on Mobility， Sensing and Networking （MSN）. 2020： 630-635.

［8］SONG Q Y， LIU Z T， CAO J H， et al. SAP－SSE： Protecting search patterns and access patterns in searchable symmetric encryption［J］. IEEE Transactions on Information Forensics and Security， 2020， 16： 1795-1809.

［9］WANG W， XU P， LIU D L， et al. Lightweighted secure searching over public－key ciphertexts for edge－cloud－assisted industrial IoT devices［J］. IEEE Transactions on Industrial Informatics， 2020， 16（6）： 4221-4230.

［10］HE K， CHEN J， ZHOU Q X， et al. Secure dynamic searchable symmetric encryption with constant client storage cost［J］. IEEE Transactions on Information Forensics and Security， 2020， 16： 1538-1549.

［11］CHEN R M， MU Y， YANG G M， et al. Server－aided public key encryption with keyword search［J］. IEEE Transactions on Information Forensics and Security， 2016， 11（12）： 2833-2842.

［12］CHEN R M， MU Y， YANG G M， et al. Dual－server public－key encryption with keyword search for secure cloud storage［J］. IEEE Transactions on Information Forensics and Security， 2016， 11（4）： 789-798.

［13］HWANG M S， LEE C C， HSU S T. An ElGamal－like secure channel free public key encryption with keyword search scheme［J］. International Journal of Foundations of Computer Science， 2019， 30（2）： 255-273.

［14］CHEN B W， WU L B， ZEADALLY S， et al. Dual－server public－key authenticated encryption with keyword search［J］. IEEE Transactions on Cloud Computing， 2019， 10（1）： 322-333.

［15］HUANG K B， TSO R， CHEN Y C. Somewhat semantic secure public key encryption with filtered－equality－test in the standard model and its extension to searchable encryption［J］. Journal of Computer and System Sciences， 2017， 89： 400-409.

［16］WU D N， GAN Q Q， WANG X M. Verifiable public key encryption with keyword search based on homomorphic encryption in multi－user setting［J］. IEEE Access， 2018， 6： 42445-42453.

［17］SHAO J， CAO Z. CCA－secure proxy re－encryption without pairings［C］//Public Key Cryptography－PKC 2009： 12th International Conference on Practice and Theory in Public Key Cryptography， Irvine， CA， USA： Springer， 2009： 357-376.

［18］LIU W R， LIU J W， WU Q H， et al. Online/offline public－index predicate encryption for fine－grained mobile access control［C］//Computer Security－ESORICS 2016： 21st European Symposium on Research in Computer Security， Heraklion， Greece： Springer， 2016： 588-605.

［19］LIU X， YANG G， SUSILO W， et al. Privacy－preserving multi－keyword searchable encryption for distributed systems［J］. IEEE Transactions on Parallel and Distributed Systems， 2020， 32（3）： 561-574.

［20］ZHANG W， QIN B， DONG X， et al. Public－key encryption with bidirectional keyword search and its application to encrypted emails［J］. Computer Standards & Interfaces， 2021， 78： 103542.

［21］MIAO Y， MA J， LIU X， et al. Lightweight fine－grained search over encrypted data in fog computing［J］. IEEE Transactions on Services Computing， 2018， 12（5）： 772-785.

［22］CAO M S， WANG L H， QIN Z G， et al. A lightweight fine－grained search scheme over encrypted data in cloud－assisted wireless body area networks［J］. Wireless Communications and Mobile Computing， 2019， 2019： 9340808.

［23］MIAO Y， DENG R H， CHOO K K R， et al. Optimized verifiable fine－grained keyword search in dynamic multi－owner settings［J］. IEEE Transactions on Dependable and Secure Computing， 2019， 18（4）： 1804-1820.

［24］LIU X M， DENG R H， CHOO K K R， et al. An efficient privacy－preserving outsourced calculation toolkit with multiple keys［J］. IEEE Transactions on Information Forensics and Security， 2016， 11（11）： 2401-2414.

［25］SAMANTHULA B K， CHUN H， JIANG W. An efficient and probabilistic secure bit－decomposition［C］//Proceedings of the 8th ACM SIGSAC symposium on Information， computer and communications security， 2013： 541-546.

［26］KAMARA S， MOHASSEL P， RAYKOVA M. Outsourcing multi－party computation［J］. Cryptology ePrint Archive， 2011， 78： 103542.

（責任編輯：編輯郭蕓婕）

收稿日期：2023-02-23

基金項目：河北省重點研發(fā)計劃項目（22340701D），河北省自然科學基金項目（F2022201005）

作者簡介：杜瑞忠（1975—）男，教授，從事可信計算與信息安全方向的研究，e－mail：durz@hbu.edu.cn。

*通信作者：杜瑞忠（1975—）男，河北大學教授、碩士生導師，從事可信計算與信息安全方向的研究，