高效的可驗(yàn)證無證書可搜索加密方案

崔新華，田有亮，張起嘉

（1.公共大數(shù)據(jù)國家重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025；2.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；3.貴州師范大學(xué)經(jīng)濟(jì)與管理學(xué)院，貴州 貴陽 550025；4.貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025）

0 引言

隨著云計(jì)算技術(shù)的快速發(fā)展，為了滿足用戶日益增長的需求，互聯(lián)網(wǎng)設(shè)備產(chǎn)生的數(shù)據(jù)量飛速增長。越來越多的企業(yè)與個人選擇將數(shù)據(jù)存放在云服務(wù)器中，以緩解本地存儲帶來的壓力。然而，當(dāng)數(shù)據(jù)被上傳至云服務(wù)器后，數(shù)據(jù)擁有者便失去了對數(shù)據(jù)的控制。特別是當(dāng)數(shù)據(jù)中包含敏感信息時，數(shù)據(jù)擁有者難以對敏感信息提供安全保護(hù)。為了避免云服務(wù)器侵犯敏感數(shù)據(jù)的隱私性，需要將文件加密后再上傳。然而，加密會導(dǎo)致數(shù)據(jù)之間的關(guān)聯(lián)性被破壞，給文件檢索帶來了困難。為了解決云服務(wù)器對密文實(shí)現(xiàn)高效檢索的問題，可搜索加密[1]成為最受研究者關(guān)注的方法之一。

現(xiàn)有的可搜索加密方案中，公鑰可搜索加密（PEKS）[2-3]相比于對稱可搜索加密（SSE,symmetric searchable encryption）[4-5]更適用于云存儲環(huán)境中的文件共享等場景，因此成為一個重要的研究熱點(diǎn)。PEKS 引入了非對稱的搜索陷門，以關(guān)鍵詞密文與搜索陷門能否匹配作為搜索成功的判斷依據(jù)。具體來說，數(shù)據(jù)擁有者首先需要依次對準(zhǔn)備上傳的文件提取關(guān)鍵詞，然后利用文件接收者的公鑰計(jì)算生成關(guān)鍵詞密文。接下來，數(shù)據(jù)擁有者將數(shù)據(jù)文件加密，再將文件密文與關(guān)鍵詞密文相連接，形成密文索引并一同上傳至云服務(wù)器中進(jìn)行存儲。數(shù)據(jù)用戶在對目標(biāo)文件發(fā)起搜索前，首先需要確定目標(biāo)文件的關(guān)鍵詞，并使用私鑰生成搜索陷門，然后作為搜索請求發(fā)送給云服務(wù)器。云服務(wù)器接收到搜索請求后，對密文索引進(jìn)行匹配測試，最后將匹配到的密文作為搜索結(jié)果返回給數(shù)據(jù)用戶。在此期間，不可信的云服務(wù)器雖然執(zhí)行存儲與匹配任務(wù)，卻無法得知任何關(guān)于數(shù)據(jù)文件的信息。

然而，在現(xiàn)實(shí)環(huán)境中云服務(wù)器可能會因?yàn)榻?jīng)濟(jì)利益或黑客攻擊等因素，惡意地發(fā)動選擇性轉(zhuǎn)發(fā)攻擊[6]，即只返回部分搜索結(jié)果給用戶。而在目前大多數(shù)的PEKS 方案中，用戶缺乏搜索結(jié)果的驗(yàn)證機(jī)制，無法檢測返回的搜索結(jié)果是否完整或是否已經(jīng)被惡意篡改。為了抵抗惡意云服務(wù)的攻擊，可驗(yàn)證性[7-9]為用戶提供了搜索結(jié)果的審查機(jī)制，成為研究目標(biāo)之一。Sun 等[10]提出了一種可驗(yàn)證的多關(guān)鍵詞可搜索加密方案。該方案采用基于樹的數(shù)據(jù)結(jié)構(gòu)作為索引，以實(shí)現(xiàn)搜索結(jié)果的完整性驗(yàn)證。Wang 等[11]結(jié)合布隆過濾器（BF,Bloom filter）、Merkle 哈希樹（MHT,Merkle hash tree）等數(shù)據(jù)結(jié)構(gòu)，提出了一種外包數(shù)據(jù)庫的審計(jì)協(xié)議。然而，該協(xié)議只能實(shí)現(xiàn)靜態(tài)審計(jì)，無法適用于云計(jì)算中的動態(tài)更新場景。隨后，大量支持動態(tài)更新的可驗(yàn)證的可搜索加密方案被提出[6,12-13]。然而，這些方案在更新過程中帶來的計(jì)算開銷與通信開銷較大，有待進(jìn)一步降低。因此，對搜索結(jié)果實(shí)現(xiàn)高效驗(yàn)證與密文的高效更新仍是亟待解決的難題。

大多數(shù)PEKS 方案都是基于證書或基于身份的公鑰密碼，存在證書管理以及密鑰托管問題。為了解決該問題，Peng 等[14]提出了第一個基于無證書的公鑰可搜索加密（CLPEKS,certificateless public key encryption with keyword search）方案，該方案將無證書的公鑰密碼引入PEKS 中，為傳統(tǒng)的PEKS 方案提升了抗惡意用戶與半誠實(shí)的密鑰生成中心的安全性。此后，大量的研究人員對基于無證書的PEKS 方案進(jìn)行了研究[15-18]。Zheng 等[19]提出了一個不需要用戶執(zhí)行對運(yùn)算的無證書可搜索加密方案，該方案顯著降低了用戶的計(jì)算量，提升了方案的實(shí)用性。Miao 等[20]實(shí)現(xiàn)了一種基于無證書的可驗(yàn)證的多關(guān)鍵詞可搜索加密方案，該方案不僅基于Zheng 等[19]方案實(shí)現(xiàn)了無證書加密，還將云審計(jì)與可搜索加密相結(jié)合，采用可信的第三方審計(jì)服務(wù)器協(xié)助用戶對搜索結(jié)果進(jìn)行驗(yàn)證。田有亮等[21]在Miao 等[20]方案的基礎(chǔ)上提出了一種基于改進(jìn)Merkle 樹認(rèn)證方法的可驗(yàn)證多關(guān)鍵詞可搜索加密方案，與之前的方案相比，該方案將驗(yàn)證過程中的計(jì)算開銷由經(jīng)典MHT 的O(n)降低到O(logn)，實(shí)現(xiàn)了高效驗(yàn)證與更新。然而，經(jīng)過本文分析，該方案存在明顯的安全性缺陷，無法達(dá)到文中聲稱的安全要求。張鍵紅等[6]提出了一種高效、可驗(yàn)證的多關(guān)鍵詞搜索加密方案，該方案不僅能夠支持多關(guān)鍵詞搜索，還實(shí)現(xiàn)了搜索模式的隱私性和文件的前向安全。

為了實(shí)現(xiàn)安全高效可驗(yàn)證的密文檢索，同時滿足無證書公鑰加密環(huán)境中的安全性，本文提出了一種高效的可驗(yàn)證無證書可搜索加密方案。本文的主要貢獻(xiàn)如下。

1) 首先，對文獻(xiàn)[21]方案進(jìn)行了安全性分析，指出了其既不能滿足密文的選擇明文攻擊的不可區(qū)分（IND-CPA）安全，也不能滿足適用于可搜索加密的選擇關(guān)鍵詞攻擊的不可區(qū)分（IND-CKA）安全。然后，給出了2 種具體的攻擊，即外部攻擊者發(fā)動的密文猜測攻擊，以及惡意用戶發(fā)動的在線關(guān)鍵詞猜測攻擊。

2) 提出了一種高效的基于無證書的可搜索加密方案。在隨機(jī)預(yù)言機(jī)模型下，基于判定性線性（DLIN,decisional linear）假設(shè)與計(jì)算性DH（co-CDH,co-computational Diffie-Hellman）假設(shè)，證明了所提方案滿足選擇關(guān)鍵詞攻擊下的不可區(qū)分性與簽名的不可偽造性。

3) 通過結(jié)合改進(jìn)的MHT 與無證書簽名，實(shí)現(xiàn)了高效可驗(yàn)證性與高效動態(tài)更新，通過實(shí)驗(yàn)與其他現(xiàn)有主流方案進(jìn)行對比，分析表明了所提方案在計(jì)算效率方面與通信效率方面均優(yōu)于其他相關(guān)方案，具有更高的實(shí)用價值。

1 基礎(chǔ)知識

本節(jié)首先介紹了雙線性對的概念和本文用到困難假設(shè)，然后給出了無證書可搜索加密方案的形式化定義和相關(guān)的安全模型。

1.1 雙線性對

設(shè)λ為安全參數(shù)，p為與λ相關(guān)的大素?cái)?shù)，G1、G2和GT為3 個階為p的乘法循環(huán)群。

定義1雙線性映射。若映射e:G1×G2→GT滿足以下3 個條件，則該映射為一個雙線性映射。

1) 雙線性：對于任意元素g1∈G1,g2∈G2和a,b∈Zp，均有

2) 非退化性：至少存在元素g1∈G1和g2∈G2，滿足e(g1,g2) ≠ 1。

3) 可計(jì)算性：對于任意元素g1∈G1和g2∈G2，均有多項(xiàng)式時間算法計(jì)算e(g1,g2)。

根據(jù)群G1與G2的不同關(guān)系，雙線性映射可分為2 類。若G1=G2，則該雙線性映射為Type-1 類型；若G1≠G2，且G1與G2之間存在一個同構(gòu)映射?，使?(G2)→G1，則該雙線性映射為Type-2 類型。

1.2 困難假設(shè)

1.3 Merkle 哈希樹

經(jīng)典Merkle 哈希樹是一種二叉樹數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)分成若干個塊，然后對每個塊計(jì)算哈希值，作為葉子節(jié)點(diǎn)。輸入相鄰的2 個葉子節(jié)點(diǎn)的哈希值，再計(jì)算生成一個新的哈希值，作為這2 個葉子節(jié)點(diǎn)的父節(jié)點(diǎn)。遞歸進(jìn)行該操作，直到得到一個根節(jié)點(diǎn)，它可以確保所有節(jié)點(diǎn)的完整性，因此可以作為整個數(shù)據(jù)的哈希值。Garg 等[22]提出了一種基于相對索引和時間戳的Merkle 哈希樹，通過修改搜索算法實(shí)現(xiàn)了高效動態(tài)更新。

改進(jìn)Merkle 樹的每個節(jié)點(diǎn)包括2 個信息：一個是數(shù)據(jù)塊的哈希值，另一個是相對索引。與節(jié)點(diǎn)T關(guān)聯(lián)的相對索引是指屬于T的子樹的葉子節(jié)點(diǎn)的數(shù)量，葉子節(jié)點(diǎn)的索引值為1。例如，如果T的左右節(jié)點(diǎn)分別為hLeft和hRight且相對索引為iLeft和iRight，則T的哈希值為H(hLeft,hRight)，索引值為左右節(jié)點(diǎn)的相對索引之和 (iLeft+iRight)。根節(jié)點(diǎn)hRoot的生成方式為hRoot=H(hLeft,hRight,dt)，其中，時間戳dt表示Merkle 樹創(chuàng)建的時間，根節(jié)點(diǎn)只對樹中任意數(shù)據(jù)塊做出修改而更新，且只有在有效時間內(nèi)才能通過驗(yàn)證，因此能夠保證數(shù)據(jù)的有效性。

1.4 形式化定義

如圖1 所示，無證書可搜索加密系統(tǒng)模型中包含4 個不同的實(shí)體：密鑰生成中心（KGC,key generation center）、數(shù)據(jù)擁有者（DO,data owner）、數(shù)據(jù)用戶（DU,data user）以及云服務(wù)器（CSP,cloud service provider）。

圖1 系統(tǒng)模型

1) 密鑰生成中心。KGC 為一個半誠實(shí)的實(shí)體，負(fù)責(zé)根據(jù)安全參數(shù)生成系統(tǒng)主密鑰與系統(tǒng)公開參數(shù)，以及為每個數(shù)據(jù)擁有者與用戶生成部分私鑰。KGC 會對密文中包含的信息產(chǎn)生好奇，能夠利用已知的系統(tǒng)主密鑰等關(guān)鍵信息發(fā)動猜測攻擊，以及勾結(jié)云服務(wù)器偽造驗(yàn)證信息。

2) 數(shù)據(jù)擁有者。數(shù)據(jù)擁有者為一個誠實(shí)的實(shí)體，負(fù)責(zé)生成自己的公私鑰，并使用私鑰生成驗(yàn)證信息；還負(fù)責(zé)使用用戶的公鑰生成關(guān)鍵詞密文，創(chuàng)建密文索引，最后將密文文件、密文索引與驗(yàn)證信息一同上傳至云服務(wù)器中。除此之外，數(shù)據(jù)擁有者還能夠?qū)γ芪倪M(jìn)行修改、添加、刪除等更新操作。

3) 數(shù)據(jù)用戶。數(shù)據(jù)用戶為一個可能存在惡意的實(shí)體，但不與其他實(shí)體相互勾結(jié)。數(shù)據(jù)用戶負(fù)責(zé)向云服務(wù)器提出搜索請求，以及收到結(jié)果后對結(jié)果進(jìn)行驗(yàn)證。惡意用戶可能偽裝成合法用戶偽造搜索陷門，也可能對驗(yàn)證信息發(fā)動偽造攻擊。

4) 云服務(wù)器。云服務(wù)器為一個半誠實(shí)的實(shí)體，負(fù)責(zé)存儲數(shù)據(jù)擁有者上傳的信息、幫助數(shù)據(jù)用戶執(zhí)行搜索、協(xié)助數(shù)據(jù)擁有者完成密文更新操作。在操作過程中，云服務(wù)器可能會對密文中包含的信息產(chǎn)生好奇。

定義4可驗(yàn)證的無證書可搜索加密方案。可驗(yàn)證的無證書可搜索加密方案通常包括以下7 個多項(xiàng)式時間算法。

1) Setup(λ)。該算法由KGC 執(zhí)行。輸入安全參數(shù)λ，生成系統(tǒng)主密鑰msk，發(fā)布系統(tǒng)公開參數(shù)params。

2) ParKeyGen(params,msk,ID)。該算法由KGC 執(zhí)行。輸入系統(tǒng)主密鑰msk、系統(tǒng)公開參數(shù)params 以及用戶ID，生成用戶的部分私鑰psk。

3) KeyGen(params,psk,ID)。該算法由用戶執(zhí)行。輸入部分私鑰psk、系統(tǒng)公開參數(shù)params 以及用戶ID，生成用戶的私鑰skU與公鑰pkU。

4) Encrypt(params,w,Files,pkU,skO,ID)。該算法由數(shù)據(jù)擁有者執(zhí)行。輸入系統(tǒng)公開參數(shù)params、數(shù)據(jù)擁有者私鑰skO以及數(shù)據(jù)文件Files，生成驗(yàn)證信息v。然后輸入用戶公鑰pkU與關(guān)鍵詞w，生成關(guān)鍵詞密文CT。

5) Trapdoor(params,w,skU)。該算法由數(shù)據(jù)用戶執(zhí)行。輸入系統(tǒng)公開參數(shù)params、私鑰skU、關(guān)鍵詞w，生成搜索陷門T。

6) Search(T,CT)。該算法由CSP 執(zhí)行。輸入搜索陷門T和關(guān)鍵詞密文CT，由CSP 計(jì)算是否匹配，若匹配成功，則將文件密文以及相應(yīng)的驗(yàn)證信息返回給用戶。

7) Verify(params,v,pkO,Files)。該算法由數(shù)據(jù)用戶執(zhí)行。輸入系統(tǒng)公開參數(shù)params、數(shù)據(jù)擁有者公鑰pkO、驗(yàn)證信息v以及解密文件Files，輸出驗(yàn)證結(jié)果1（成功）或0（失?。?。

1.5 安全模型

無證書可搜索加密考慮2 種類型的敵手：Type-1類型的敵手AI代表惡意用戶，無法得知系統(tǒng)主密鑰msk，但可以發(fā)動公鑰替換攻擊，偽裝成一個合法用戶偽造搜索陷門或簽名；Type-2 類型的敵手AII代表誠實(shí)且好奇的KGC，能夠掌握系統(tǒng)主密鑰msk，以及掌握每個用戶的部分私鑰psk，但無法得知用戶私鑰，也無法偽裝成其他用戶。

本文通過以下4 個挑戰(zhàn)者C與敵手AI、AII之間的安全游戲來定義方案的安全模型，其中，Game1與Game2 為針對密文的IND-CKA 游戲，Game3 與Game4 為針對簽名的EUF-CMA 游戲。

Game1此處的敵手為AI。

1) 初始化。挑戰(zhàn)者C運(yùn)行Setup 算法，設(shè)置公共參數(shù)。然后設(shè)置系統(tǒng)主密鑰，計(jì)算系統(tǒng)公鑰。最后將生成的系統(tǒng)公共參數(shù)與公鑰發(fā)送給敵手AI。

2) 哈希詢問。敵手AI在該階段對2 個隨機(jī)預(yù)言機(jī)分別進(jìn)行多項(xiàng)式有限次的詢問，挑戰(zhàn)者C維護(hù)2 個初始為空的列表，用來記錄每次詢問。

3) 階段1。在該階段，敵手AI向挑戰(zhàn)者C進(jìn)行多項(xiàng)式有界次適應(yīng)性詢問，內(nèi)容包含以下4 項(xiàng)。

①ParKeyGen 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID。當(dāng)ID 與挑戰(zhàn)者身份相同時，中止游戲；否則，挑戰(zhàn)者C在收到ID 后，查詢哈希列表并計(jì)算部分私鑰psk，返回給敵手。

②KeyGen 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID。當(dāng)ID 與挑戰(zhàn)者身份相同時，中止游戲；否則，挑戰(zhàn)者C執(zhí)行ParKeyGen 算法，然后計(jì)算公私鑰對(sk,pk)，并返回給敵手。

③Replace-KeyGen 詢問。挑戰(zhàn)者C首先建立一個初始為空的列表。敵手AI隨機(jī)生成一個公鑰pk'。隨后向挑戰(zhàn)者C發(fā)送想要替換的身份ID 與替換公鑰pk'，挑戰(zhàn)者C將身份ID 對應(yīng)的公鑰pk 使用pk'替換，并將其存儲在列表中。

④Trapdoor 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID 與一個關(guān)鍵詞w。挑戰(zhàn)者C首先對于ID 執(zhí)行ParKeyGen 詢問與KeyGen 詢問，然后計(jì)算Trapdoor 并返回給敵手AI。

4) 挑戰(zhàn)。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID與2 個長度相同的關(guān)鍵詞w0,w1。ID 與w0,w1曾經(jīng)被詢問過，則中止游戲；否則，挑戰(zhàn)者C隨機(jī)拋出一枚硬幣b={0,1}，計(jì)算關(guān)于ID 與wb的密文，返回給敵手。

5) 階段2。與階段1 相同，唯一的限制是敵手AI不能詢問關(guān)于挑戰(zhàn)密文的關(guān)鍵詞，也不能詢問挑戰(zhàn)者的私鑰與部分私鑰。

6) 猜測。敵手AI輸出一個比特b'={0,1}，若b'=b，則敵手獲勝。

定義5對于多項(xiàng)式時間內(nèi)的敵手AI，贏得IND-CKA 游戲的優(yōu)勢為

Game2此處的敵手為AII。Game2 與Game1相似，區(qū)別是不需要執(zhí)行 ParKeyGen 詢問與Replace-KeyGen 詢問，且Setup 階段需要發(fā)送系統(tǒng)密鑰給敵手AII。

Game3此處的敵手為AI。

1) 初始化。挑戰(zhàn)者C運(yùn)行Setup 算法，設(shè)置公共參數(shù)。然后設(shè)置系統(tǒng)主密鑰，計(jì)算系統(tǒng)公鑰。最后將生成的系統(tǒng)公共參數(shù)與公鑰發(fā)送給敵手AI。

2) 哈希詢問。敵手AI在該階段對2 個隨機(jī)預(yù)言機(jī)分別進(jìn)行多項(xiàng)式有限次的詢問，挑戰(zhàn)者C維護(hù)2 個初始為空的列表，用來記錄的每次詢問。

3) 詢問階段。在該階段，敵手AI向挑戰(zhàn)者C進(jìn)行多項(xiàng)式有界次適應(yīng)性詢問，內(nèi)容包含以下4 項(xiàng)。

①ParKeyGen 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID。當(dāng)ID 與挑戰(zhàn)者身份相同時，中止游戲；否則，挑戰(zhàn)者C在收到ID 后，查詢哈希列表并計(jì)算部分私鑰psk，返回給敵手。

②KeyGen 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID。當(dāng)ID 與挑戰(zhàn)者身份相同時，中止游戲；否則，挑戰(zhàn)者C執(zhí)行ParKeyGen 算法，然后計(jì)算公私鑰對(sk,pk)，并返回給敵手。

③Replace-KeyGen 詢問。挑戰(zhàn)者C首先建立一個初始為空的列表。敵手AI隨機(jī)生成一個公鑰pk'。隨后向挑戰(zhàn)者C發(fā)送想要替換的身份ID 與替換公鑰pk'，挑戰(zhàn)者C將身份ID 對應(yīng)的公鑰pk 使用pk'替換，并將其存儲在列表中。

④Signature 詢問。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID 與一個消息m。挑戰(zhàn)者C首先對ID 執(zhí)行ParKeyGen 詢問與KeyGen 詢問，然后計(jì)算簽名并返回給敵手AI。

4) 偽造。敵手AI向挑戰(zhàn)者C發(fā)送一個身份ID、一個關(guān)于ID 的公鑰、一個消息m*以及對應(yīng)的簽名σ*。若ID 與消息m*的簽名曾經(jīng)被詢問過，則中止游戲；否則，敵手AI贏得該游戲。

定義6對于多項(xiàng)式時間內(nèi)的敵手AI，贏得EUF-CMA 游戲的優(yōu)勢為

Game4此處的敵手為AII。Game4 與Game3相似，區(qū)別是不需要執(zhí)行 ParKeyGen 詢問與Replace-KeyGen 詢問，且Setup 階段需要發(fā)送系統(tǒng)密鑰給敵手AII。

2 對文獻(xiàn)[21]方案的安全性分析

本節(jié)首先簡要回顧文獻(xiàn)[21]中的方案，然后指出其不能滿足密文不可區(qū)分性，并給出2 種具體的攻擊過程。

2.1 對文獻(xiàn)[21]中方案的描述

由于篇幅限制，本節(jié)只簡要描述其Setup、ParKeyGen、KeyGen、Encryption、Trapdoor Generation以及Search 算法。方案的詳細(xì)設(shè)計(jì)請參考文獻(xiàn)[21]。

6) Search。服務(wù)器收到搜索用戶發(fā)來的Tw后，計(jì)算并驗(yàn)證式(1)是否成立。

若式(1)成立，則返回相應(yīng)的密文給搜索用戶；否則，匹配失敗，終止搜索。

2.2 針對IND-CKA 的攻擊

本節(jié)通過分析證明文獻(xiàn)[21]方案無法達(dá)到其聲稱的IND-CKA 安全。

2) 根據(jù)挑戰(zhàn)階段中接收到的挑戰(zhàn)密文，驗(yàn)證式(2)是否成立。

因此，敵手攻擊成功，同時證明該方案不滿足可搜索加密的IND-CKA 安全。

2.3 針對密文機(jī)密性的關(guān)鍵詞猜測攻擊

本節(jié)通過分析證明文獻(xiàn)[21]方案無法實(shí)現(xiàn)密文的機(jī)密性。具體來說，誠實(shí)且好奇的云服務(wù)器能夠?qū)Υ鎯Φ年P(guān)鍵詞密文發(fā)動關(guān)鍵詞猜測攻擊。詳細(xì)過程如下。

對于一個包含關(guān)鍵詞集W={w1,…,wn}的密文CT，有

誠實(shí)且好奇的云服務(wù)器首先計(jì)算

假設(shè)猜測的關(guān)鍵詞集為W*，則云服務(wù)器計(jì)算

最后，驗(yàn)證式(4)是否成立。

當(dāng)W*=W時，則有

由于現(xiàn)實(shí)世界中的關(guān)鍵詞的明文空間有限，攻擊者可以通過對所有可能的關(guān)鍵詞集W*進(jìn)行有限次窮舉，對式(3)進(jìn)行大量計(jì)算，得到的分別使用式(4)進(jìn)行對比，便可在多項(xiàng)式時間內(nèi)成功猜測出密文CT 中所包含的關(guān)鍵詞明文信息。

因此，該方案不滿足關(guān)鍵詞密文的機(jī)密性。

3 所提方案

下面給出本文提出的高效的可驗(yàn)證無證書可搜索加密方案。

3.1 系統(tǒng)初始化

最后，KGC 保留系統(tǒng)主密鑰msk={x,y}，公開系統(tǒng)公共參數(shù)

3.2 部分私鑰生成

給定身份ID，通過執(zhí)行該算法，KGC 分別生成數(shù)據(jù)用戶與數(shù)據(jù)擁有者的部分私鑰，具體步驟如下。

1) 對于數(shù)據(jù)用戶，輸入 (msk,IDU,params)，其中，IDU為長度為lID的比特串，表示用戶的身份。KGC 隨機(jī)選擇t∈Zp，并計(jì)算

2) 對于數(shù)據(jù)擁有者，輸入 (msk,IDO,params)，其中，IDO為數(shù)據(jù)擁有者的身份。KGC 隨機(jī)選擇t′∈Zp，并計(jì)算

然后將2 個部分私鑰 pskU=(pskU,1,pskU,2)與pskO=(pskO,1,pskO,2)通過安全信道分別發(fā)送給數(shù)據(jù)用戶與數(shù)據(jù)擁有者。

3.3 公私鑰生成

3.4 密文生成

首先，數(shù)據(jù)擁有者對數(shù)據(jù)文件進(jìn)行提取關(guān)鍵詞處理。對于包含相同關(guān)鍵詞集W={w1,…,wn}的文件fi，數(shù)據(jù)擁有者使用對稱加密算法（如SM4）對其進(jìn)行加密處理，生成數(shù)據(jù)文件密文c={c1,…,cq}。

其次，計(jì)算每個密文ci的哈希值hi，再將每個文件的哈希值作為葉子節(jié)點(diǎn)，每個葉子節(jié)點(diǎn)作為哈希函數(shù)H3的輸入，迭代生成MHT。其中，根節(jié)點(diǎn)為一個n位長的序列。由左右葉子節(jié)點(diǎn)與系統(tǒng)時間戳dt共同計(jì)算生成。系統(tǒng)時間戳dt表示一個有效時間段（如一天、一周或一個月），若時間段有效，則系統(tǒng)生成的時間戳相同。數(shù)據(jù)擁有者輸入自己的身份IDO、私鑰skO、公鑰p kO，生成根節(jié)點(diǎn)的簽名

最后，數(shù)據(jù)擁有者將{CW,v,c} 一同上傳至云服務(wù)器中進(jìn)行存儲，其中，CW=(C1,C2,C3)。

3.5 陷門生成

3.6 密文搜索

云服務(wù)器收到用戶發(fā)送的搜索陷門Tw'后，將其與存儲的關(guān)鍵詞密文Cw進(jìn)行匹配，計(jì)算并判斷式(6)是否成立。

若式(6)成立，則說明關(guān)鍵詞密文與陷門匹配一致，將數(shù)據(jù)文件密文c={c1,…,cq}以及相應(yīng)的驗(yàn)證信息v=(hRoot,σ1,σ2)返回給用戶。

3.7 結(jié)果驗(yàn)證

3.8 動態(tài)更新

當(dāng)數(shù)據(jù)擁有者希望對存儲在云服務(wù)器上的文件進(jìn)行修改或添加時，首先向服務(wù)器認(rèn)證自己的身份。當(dāng)身份驗(yàn)證通過后，通過以下方式對文件進(jìn)行更新。

圖2 原始密文MHT

圖3 數(shù)據(jù)添加過程

圖4 數(shù)據(jù)刪除過程

4 方案分析

本節(jié)針對所提方案的正確性與安全性給出了具體的證明。

4.1 正確性分析

在搜索階段，為了保證方案中的云服務(wù)器能夠嚴(yán)格地對關(guān)鍵詞密文與搜索陷門進(jìn)行匹配，對于式(6)，有

在結(jié)果驗(yàn)證階段，為了保證搜索結(jié)果的正確性與完備性，對于式(7)，有

方案的正確性證畢。

4.2 安全性分析

本節(jié)通過定理1～定理3，證明了所提方案在CDH 假設(shè)與DLIN 假設(shè)下能夠抵抗無證書環(huán)境中Type-1 與Type-2 這2 種類型的敵手的攻擊，實(shí)現(xiàn)選擇關(guān)鍵詞攻擊下的IND-CKA 安全，并且滿足簽名的EUF-CMA 安全。

定理1若DLIN 問題是困難的，則所提方案在隨機(jī)預(yù)言機(jī)模型下能夠滿足IND-CKA 安全。

階段1。在該階段，敵手AI向B進(jìn)行多項(xiàng)式有界次適應(yīng)性詢問，內(nèi)容包含以下4 項(xiàng)。

最后將pskj返回給敵手。該pskj于敵手視角中為合法部分私鑰。由于一個合法psk 需要滿足以下關(guān)系

敵手在收到pskj后，可以利用已知信息對pskj進(jìn)行如下驗(yàn)證

猜測。敵手AI輸出一個比特 {0,1}b′=。若b′=b，則敵手在該游戲獲勝，同時B輸出b*。

當(dāng)敵手AI在游戲中獲勝時，若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

1) 敵手AI沒有在 ParKeyGen 詢問與PrivateKey 詢問階段向B發(fā)送過身份IDi*。

2) 敵手AI沒有在陷門詢問階段向B同時發(fā)送過身份IDi*與σi=1的消息Mj*。

3) 敵手AI在挑戰(zhàn)階段必須發(fā)送的是身份IDi*與σi=1的消息Mj*。

則B在以上條件下利用AI的攻擊成功解決DLIN 問題的優(yōu)勢為

引理1 證畢。

引理2在隨機(jī)預(yù)言機(jī)模型下，若存在一個Type-2 類型的敵手AII，能夠以不可忽略的優(yōu)勢ε攻破所提方案的IND-CKA 安全性，則能夠構(gòu)造一個算法B，利用敵手A的能力以不可忽略的優(yōu)勢求解DLIN 問題。

證明引理2 的證明與引理1 采用的思路相似，區(qū)別是Type-2 類型的敵手AII能夠得知系統(tǒng)主密鑰msk，因此需要將DLIN 問題的元素隱藏在用戶公鑰pkj中，而非系統(tǒng)公鑰中。為節(jié)省篇幅，此處不再展開詳細(xì)證明。

需要注意的是，Type-2 類型的敵手AII不能進(jìn)行replace-public-key 詢問。由于Type-2 類型的敵手擁有msk，因此也不需要進(jìn)行ParKeyGen 詢問。在挑戰(zhàn)階段，限制AII不能得知目標(biāo)身份的私鑰

定理2若co-CDH 問題是困難的，則所提方案在隨機(jī)預(yù)言機(jī)模型下能夠滿足EUF-CMA 安全。

引理3在隨機(jī)預(yù)言機(jī)模型下，若存在一個Type-1 類型的敵手AI，能夠以不可忽略的優(yōu)勢ε攻破所提方案的EUF-CMA 安全性，則能夠構(gòu)造一個算法B，利用敵手AI的能力以不可忽略的優(yōu)勢求解co-CDH 問題。

若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

引理3 證畢。

若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

1) 敵手AII沒有在PrivateKey 詢問階段向B發(fā)送過身份IDi*。

2) 敵手AII沒有在簽名詢問階段向B同時發(fā)送過身份IDi*與消息Mj*。

3) 敵手AII在偽造階段必須發(fā)送的是關(guān)于身份IDi*與消息Mj*的簽名。則B在以上條件下利用AII偽造的簽名成功解決co-CDH 問題的概率為

引理4 證畢。

5 性能分析

為了展示所提方案在效率方面的優(yōu)勢，本節(jié)對其與4 種對比方案進(jìn)行了理論性能分析，4 種對比方案分別為高被引的文獻(xiàn)[19]、文獻(xiàn)[20]、文獻(xiàn)[21]以及最新的文獻(xiàn)[6]。最后，將所提方案與4 種對比方案進(jìn)行了實(shí)現(xiàn)，通過實(shí)驗(yàn)對比，驗(yàn)證了理論分析的結(jié)果。參數(shù)含義如表1 所示。

表1 參數(shù)含義

5.1 理論分析

在通信開銷方面，文獻(xiàn)[19]在密文生成階段的通信開銷為4 096 bit，且不提供可驗(yàn)證性。文獻(xiàn)[6]在密文階段的通信開銷為7 168 bit，其中驗(yàn)證信息為2 048 bit。文獻(xiàn)[20]在密文生成階段的通信開銷為5 120 bit，其中包含的關(guān)鍵詞密文為4 096 bit，驗(yàn)證信息為1 024 bit。由于基于相同的思想，文獻(xiàn)[21]在密文生成階段的通信開銷同樣為5 120 bit。而所提方案在該階段僅需生成密文為2 226 bit 長度、驗(yàn)證信息為1 272 bit 長度的無證書簽名。由于所提方案采用的群滿足Type-2 類型的雙線性對，因此在滿足相同的安全等級的同時，群中元素的長度要短于另外3 種方案中的群元素。通過比較可知，所提方案在密文生成階段的通信開銷明顯低于其他對比方案。

在用戶執(zhí)行的陷門生成階段，文獻(xiàn)[19]、文獻(xiàn)[21]、文獻(xiàn)[20]、文獻(xiàn)[6]的通信開銷分別為4 096 bit、4 096 bit、5 120 bit、2 048 bit，而所提方案僅需1 590 bit，明顯優(yōu)于這4 種方案。表2 展示了幾種方案的通信開銷。

表2 通信開銷

表3 展示了幾種方案的計(jì)算開銷。為便于展示，省略了耗時較短的乘法運(yùn)算與整數(shù)群哈希運(yùn)算，僅展示對計(jì)算開銷影響較大的7 種運(yùn)算（如表1 所示）。由表3 可知，所提方案在涉及計(jì)算資源受限的終端用戶的密鑰生成、密文生成階段的計(jì)算效率顯著高于其他方案，在陷門生成階段的計(jì)算效率雖與文獻(xiàn)[6]持平，但明顯高于其他方案。在涉及數(shù)據(jù)擁有者與云服務(wù)器的密文搜索階段與結(jié)果階段的計(jì)算開銷也低于其他4 種方案。

表3 計(jì)算開銷

5.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)設(shè)備為樹莓派4B，處理器為四核ARM Cortex-A72，內(nèi)存為2 GB，操作系統(tǒng)為Raspberry Pi OS。使用C 語言作為編程語言，調(diào)用PBC 密碼庫實(shí)現(xiàn)群元素運(yùn)算。本文實(shí)驗(yàn)采用PBC 庫推薦的Type-A 曲線實(shí)現(xiàn)滿足對稱雙線性映射的群，群中所有元素均采樣自Type-A 曲線上的點(diǎn)，用于構(gòu)建文獻(xiàn)[19]、文獻(xiàn)[20]、文獻(xiàn)[21]、文獻(xiàn)[6]方案中的實(shí)驗(yàn)。同時，為了達(dá)到與Type-A 曲線近似的安全位數(shù)，實(shí)驗(yàn)采用了D159 曲線實(shí)現(xiàn)滿足所提方案的非對稱雙線性映射的群G1、G2。同理，G1、G2群中的元素均由D159 曲線上的點(diǎn)構(gòu)成。實(shí)驗(yàn)設(shè)置在G、G1、G2群中元素的安全性一致的條件下（即攻擊者破解離散對數(shù)問題的代價相同），從構(gòu)建的群中選取參數(shù)，實(shí)現(xiàn)方案中的算法與功能，衡量不同方案的時間開銷。Type-A 曲線與D159曲線的詳細(xì)實(shí)驗(yàn)參數(shù)與樹莓派運(yùn)行benchmark 的時間如表4 所示。

表4 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)分別模擬實(shí)現(xiàn)了KGC 的初始化與部分私鑰生成算法、數(shù)據(jù)擁有者執(zhí)行的密鑰生成算法與加密算法、云服務(wù)器執(zhí)行的搜索算法以及用戶執(zhí)行的密鑰生成算法與陷門算法。實(shí)驗(yàn)中各算法執(zhí)行100 次，然后記錄各方案的單次運(yùn)行平均耗時。

在關(guān)鍵詞密文生成階段，4 種對比方案為了實(shí)現(xiàn)關(guān)鍵詞不可區(qū)分性，分別采用了9 次、11 次、11 次、8 次群G中的指數(shù)運(yùn)算，且文獻(xiàn)[20]中包含了1 次map to point 運(yùn)算、文獻(xiàn)[6]中包含了1 次map to point運(yùn)算和2 次對運(yùn)算。而所提方案實(shí)現(xiàn)相同的安全特性僅需4 次G1群中的指數(shù)運(yùn)算和1 次map to point運(yùn)算。根據(jù)圖5 中的實(shí)驗(yàn)結(jié)果可知，所提方案的計(jì)算開銷為 49.403 ms，分別低于文獻(xiàn)[19]的60.534 ms、文獻(xiàn)[20]的88.266 ms、文獻(xiàn)[21]的73.986 ms 和文獻(xiàn)[6]的86.390 ms。對比實(shí)驗(yàn)結(jié)果表明，所提方案在密文生成算法上的計(jì)算效率優(yōu)于其他4 種方案。

圖5 關(guān)鍵詞密文生成階段的計(jì)算開銷

終端用戶負(fù)責(zé)執(zhí)行陷門生成算法，其計(jì)算開銷如圖6 所示。4 種對比方案在該階段為了生成與密文相匹配的陷門，同時保障陷門內(nèi)關(guān)鍵詞的機(jī)密性，文獻(xiàn)[19]、文獻(xiàn)[20]和文獻(xiàn)[21]均需要用戶執(zhí)行10 次群G中的指數(shù)運(yùn)算，計(jì)算開銷較大。由于文獻(xiàn)[6]優(yōu)化了陷門生成算法，僅需執(zhí)行3 次群G中的指數(shù)運(yùn)算，大幅降低了計(jì)算量。在所提方案中，用戶需要執(zhí)行1 次G1群中的指數(shù)運(yùn)算和3 次G2群中的指數(shù)運(yùn)算。然而，由表4 可知，所提方案采用了帶有Type-2 類型pairing 特性的曲線，其G2群中的指數(shù)運(yùn)算開銷要顯著低于其他方案的指數(shù)運(yùn)算開銷，因此計(jì)算效率依然優(yōu)于文獻(xiàn)[6]。由圖6 可知，所提方案的計(jì)算效率不僅優(yōu)于文獻(xiàn)[6]，更較文獻(xiàn)[19]、文獻(xiàn)[20]、文獻(xiàn)[21]提升了77.68%，具有明顯優(yōu)勢。

圖6 陷門生成階段的計(jì)算開銷

用戶總負(fù)載記錄了在方案實(shí)現(xiàn)的全部過程中用戶端花費(fèi)的全部計(jì)算開銷。文獻(xiàn)[19]由于不支持搜索結(jié)果的公開驗(yàn)證性，因此用戶總計(jì)算開銷低于文獻(xiàn)[20]、文獻(xiàn)[21]、文獻(xiàn)[6]。而文獻(xiàn)[20]、文獻(xiàn)[21]的算法設(shè)計(jì)導(dǎo)致2 種方案中用戶的計(jì)算開銷（如表3所示）相近。文獻(xiàn)[6]雖然優(yōu)化了陷門生成算法和驗(yàn)證算法，其密文生成算法涉及了多種耗時的運(yùn)算，但計(jì)算效率仍低于所提方案。由圖7 可知，所提方案不僅實(shí)現(xiàn)了搜索結(jié)果的公開驗(yàn)證性，還采用了更少的指數(shù)運(yùn)算次數(shù)，以及計(jì)算開銷更低的曲線，因此效率顯著高于其他方案，更能適用于如智能手機(jī)等資源有限的終端設(shè)備，具有較高的實(shí)用價值。

圖7 用戶總負(fù)載

6 結(jié)束語

本文首先對可驗(yàn)證的無證書可搜索加密進(jìn)行了研究，指出了文獻(xiàn)[21]方案存在安全缺陷，無法抵抗惡意用戶的猜測攻擊。然后，結(jié)合無證書加密、無證書簽名與改進(jìn)的Merkle Tree 方法，提出了一種高效的可驗(yàn)證無證書可搜索加密方案。與現(xiàn)有的無證書可搜索加密方案相比，所提方案既實(shí)現(xiàn)了搜索結(jié)果的可驗(yàn)證性，又能滿足無證書場景中的安全性，同時，所提方案具有更高的計(jì)算效率與更小的通信開銷，在結(jié)合云計(jì)算的實(shí)際應(yīng)用場景中具備更強(qiáng)的實(shí)用性。