面向資源受限用戶的高效動(dòng)態(tài)數(shù)據(jù)審計(jì)方案

李秀艷，劉明曦，史聞博，董國(guó)芳*

（1.云南民族大學(xué)電氣信息工程學(xué)院，昆明 650500；2.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110819；3.東北大學(xué)秦皇島分校計(jì)算機(jī)與通信工程學(xué)院，河北秦皇島 066004）

（*通信作者電子郵箱dongguofang1@163.com）

0 引言

近年來(lái)隨著物聯(lián)網(wǎng)設(shè)備呈現(xiàn)爆炸式的指數(shù)增長(zhǎng)，促使這些用戶設(shè)備將其數(shù)據(jù)存儲(chǔ)在云端來(lái)解決用戶存儲(chǔ)容量不足的問(wèn)題。云存儲(chǔ)為用戶提供便捷的外包服務(wù)，它也是推動(dòng)物聯(lián)網(wǎng)的基礎(chǔ)平臺(tái)［1］，在物聯(lián)網(wǎng)中大部分設(shè)備通常為輕量級(jí)設(shè)備，如智能儀器儀表（Intelligent Meter，IM）、智能手機(jī)、平板電腦、可穿戴設(shè)備等［2-3］。隨著海量設(shè)備接入云端進(jìn)行交互，這些受限設(shè)備的應(yīng)用越來(lái)越廣泛［4］。例如遠(yuǎn)程測(cè)控系統(tǒng)一般以用戶端和工作站相結(jié)合的方式實(shí)現(xiàn)數(shù)據(jù)的自動(dòng)測(cè)量及存儲(chǔ)。用戶端可以通過(guò)遠(yuǎn)程控制IM 來(lái)獲取測(cè)量數(shù)據(jù)［5］，并將結(jié)果實(shí)時(shí)更新反饋到網(wǎng)絡(luò)中，由于IM 可以作為網(wǎng)絡(luò)中獨(dú)立的節(jié)點(diǎn)存在，能采用就近原則與本地線纜進(jìn)行網(wǎng)絡(luò)連接，這樣可以保證數(shù)據(jù)的實(shí)時(shí)傳輸。但由于設(shè)備本身存儲(chǔ)和計(jì)算能力有限，需要通過(guò)網(wǎng)絡(luò)將實(shí)時(shí)數(shù)據(jù)存儲(chǔ)在云服務(wù)器中，用戶再通過(guò)云服務(wù)器來(lái)獲取所需的數(shù)據(jù)信息；并且不同的用戶可以在同一時(shí)間對(duì)同一進(jìn)程數(shù)據(jù)信息進(jìn)行有效監(jiān)測(cè)。為了給這類(lèi)受限設(shè)備提供合適的存儲(chǔ)和安全保護(hù)，面向資源受限用戶設(shè)備審計(jì)應(yīng)運(yùn)而生，并成為密碼學(xué)領(lǐng)域的一個(gè)研究熱點(diǎn)。

隨著物聯(lián)網(wǎng)的進(jìn)一步發(fā)展，網(wǎng)絡(luò)技術(shù)、云計(jì)算等日新月異。大多數(shù)終端用戶設(shè)備，如IM 為資源受限設(shè)備，其處理能力、通信能力及存儲(chǔ)能力都非常有限［6-8］。為了使用戶從沉重的高運(yùn)算負(fù)擔(dān)中解脫出來(lái)，用戶數(shù)據(jù)外包得到快速發(fā)展，特別針對(duì)資源受限的用戶，外包數(shù)據(jù)可以將用戶繁重的計(jì)算任務(wù)外包給云服務(wù)提供商（Cloud Service Provider，CSP），并由CSP來(lái)向用戶提供各種數(shù)據(jù)庫(kù)服務(wù)，從而降低用戶維護(hù)數(shù)據(jù)的成本［9］。但同時(shí)用戶數(shù)據(jù)存儲(chǔ)在半誠(chéng)信的CSP 中，失去了對(duì)數(shù)據(jù)的直接控制，CSP 可能會(huì)由于軟/硬件故障或?yàn)榱俗陨砝娴葐?wèn)題，返回不正確或不完整的檢索結(jié)果給用戶，并且當(dāng)上述問(wèn)題發(fā)生時(shí)，CSP 可能還會(huì)隱瞞用戶，讓用戶以為數(shù)據(jù)依然被正確地存儲(chǔ)在CSP 上，由此為確保訪問(wèn)信息的正確性和完整性，需要用戶定期執(zhí)行數(shù)據(jù)完整性驗(yàn)證［10］。此外為減輕用戶的計(jì)算負(fù)擔(dān)，可以通過(guò)引入代理來(lái)幫助用戶在云存儲(chǔ)審計(jì)方案中處理數(shù)據(jù)［11-12］。遠(yuǎn)程存儲(chǔ)的數(shù)據(jù)不僅可以被訪問(wèn)，還應(yīng)被用戶端更新，如數(shù)據(jù)的修改、刪除、插入等操作［13］。為保證現(xiàn)場(chǎng)測(cè)試實(shí)時(shí)數(shù)據(jù)的及時(shí)更新，以及用戶從云服務(wù)器端可以實(shí)時(shí)獲取更新信息來(lái)準(zhǔn)確掌握監(jiān)測(cè)數(shù)據(jù)的動(dòng)態(tài)情況，需實(shí)現(xiàn)數(shù)據(jù)的高效動(dòng)態(tài)操作請(qǐng)求。在遠(yuǎn)程測(cè)控場(chǎng)景下，數(shù)據(jù)信息需要進(jìn)行保密，以防數(shù)據(jù)泄露導(dǎo)致利益損失；同時(shí)審計(jì)的安全性也應(yīng)該被滿足。

本文使用高效且安全的輕量級(jí)算法來(lái)構(gòu)建一個(gè)適合輕量級(jí)設(shè)備自身特點(diǎn)，且綜合考慮高效性、安全性的審計(jì)方案，主要工作如下：

1）基于新穎的計(jì)數(shù)布隆過(guò)濾器（Novel Counting Bloom Filter，NCBF）和多棵Merkle 哈希樹(shù)（Multi-Merkle Hash Tree，M-MHT）技術(shù)提出一個(gè)高效且安全的數(shù)據(jù)結(jié)構(gòu)NCBF-MMHT。其中：NCBF 用來(lái)支持?jǐn)?shù)據(jù)的快速查找，實(shí)現(xiàn)審計(jì)高效性；M-MHT用來(lái)存儲(chǔ)數(shù)據(jù)及確保數(shù)據(jù)的安全性。

2）提出一個(gè)針對(duì)資源受限用戶設(shè)備的輕量級(jí)審計(jì)方案，對(duì)審計(jì)各實(shí)體采用不同的分配操作。首先引入代理幫助用戶處理復(fù)雜的高運(yùn)算過(guò)程；其次審計(jì)驗(yàn)證通過(guò)云服務(wù)器端返回的數(shù)據(jù)證據(jù)響應(yīng)和代理端發(fā)送的標(biāo)簽證據(jù)來(lái)共同驗(yàn)證數(shù)據(jù)存儲(chǔ)的完整性，并從協(xié)議上來(lái)實(shí)現(xiàn)對(duì)資源受限用戶的輕量級(jí)審計(jì)。

3）通過(guò)安全分析和性能評(píng)估驗(yàn)證了本文方案的高效性與安全性，該方案能夠保證審計(jì)結(jié)果的正確性和完整性。

1 相關(guān)工作

物聯(lián)網(wǎng)和云計(jì)算領(lǐng)域的研究已成為熱門(mén)，而數(shù)據(jù)完整性驗(yàn)證一直是外包物聯(lián)網(wǎng)數(shù)據(jù)中一個(gè)非常重要的問(wèn)題［3］。關(guān)于數(shù)據(jù)完整性驗(yàn)證的研究大致可分為隱私安全、動(dòng)態(tài)更新和輕量級(jí)審計(jì)三個(gè)方面。

在2016 年，Botta 等［14］和Diíaz 等［15］提出了物聯(lián)網(wǎng)和云計(jì)算集成想法，并討論了關(guān)于物聯(lián)網(wǎng)設(shè)備中存在海量數(shù)據(jù)急需外包到云服務(wù)器中進(jìn)行處理的問(wèn)題。為了保證數(shù)據(jù)的完整性，Ateniese 等［16］于2007 年首先提出了可證明數(shù)據(jù)擁有的概念，利用同態(tài)認(rèn)證技術(shù)和隨機(jī)樣本技術(shù)來(lái)驗(yàn)證云中的數(shù)據(jù)的完整性。同年，Juels 等［17］提出了數(shù)據(jù)可檢索性的概念，并利用點(diǎn)檢和糾錯(cuò)編碼技術(shù)設(shè)計(jì)了具體方案，這也是提出審計(jì)協(xié)議的開(kāi)端。為了保證數(shù)據(jù)持有的公正性，Wang等［18］引入了第三方審計(jì)員（Third Party Auditor，TPA）。為了保護(hù)數(shù)據(jù)隱私，Wang 等［19］在2011 年使用同態(tài)加密技術(shù)解決數(shù)據(jù)隱私問(wèn)題。到2013 年，Wang 等［20］又提出采用隨機(jī)掩碼技術(shù)來(lái)保護(hù)數(shù)據(jù)隱私的審計(jì)方案。同年，Yang 等［21］提出了一種基于配對(duì)加密的新方案來(lái)解決數(shù)據(jù)隱私問(wèn)題，還利用數(shù)據(jù)碎片技術(shù)將每個(gè)數(shù)據(jù)塊分割成扇區(qū)，減少了數(shù)據(jù)標(biāo)簽的數(shù)量，提高了審計(jì)性能。2016 年，Li 等［22］提出了一種基于零知識(shí)證明的隱私保護(hù)遠(yuǎn)程數(shù)據(jù)完整性審計(jì)方案。

為了支持?jǐn)?shù)據(jù)的動(dòng)態(tài)操作，Wang等［19］提出采用Merkle哈希樹(shù)（Merkle Hash Tree，MHT）為數(shù)據(jù)結(jié)構(gòu)的審計(jì)方案，該方案能支持塊級(jí)的全數(shù)據(jù)動(dòng)態(tài)操作。Zhu 等［23］提出了一種新的基于片段結(jié)構(gòu)和索引哈希表（Index Hash Table，IHT）的審計(jì)方案。Liu 等［24］設(shè)計(jì)了一種基于MHT 高效細(xì)粒度更新的動(dòng)態(tài)數(shù)據(jù)完整性審計(jì)方案，該方案支持對(duì)可變大小的文件塊進(jìn)行公共審計(jì)。Tian 等［25］提出了一種利用動(dòng)態(tài)哈希表（Dynamic Hash Table，DHT）來(lái)支持?jǐn)?shù)據(jù)動(dòng)態(tài)更新的云存儲(chǔ)審計(jì)方案。Yu 等［26］利用密鑰更新技術(shù)解決了云存儲(chǔ)審計(jì)中的密鑰暴露問(wèn)題。Shen 等［27］提出了一個(gè)基于位置數(shù)組雙向鏈接信息表（Location Array-Doubly Linked Info Table，LA-DLIT）的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)公共審計(jì)協(xié)議，該協(xié)議采用全局和無(wú)塊抽樣驗(yàn)證方式，可以減少審計(jì)的計(jì)算和通信開(kāi)銷(xiāo)。

為了減輕用戶的計(jì)算負(fù)擔(dān)，提出了多種輕量級(jí)云存儲(chǔ)審計(jì)方案。Li 等［28］提出了基于在線/離線簽名的低端設(shè)備云存儲(chǔ)審計(jì)方案，但用戶仍然需要在聯(lián)機(jī)階段執(zhí)行數(shù)據(jù)簽名的計(jì)算。為了解決這個(gè)問(wèn)題，Wang等［29］提出了一種基于身份的云存儲(chǔ)審計(jì)方案，引入代理來(lái)幫助用戶生成數(shù)據(jù)簽名。在此方案中，用戶不需要消耗計(jì)算資源來(lái)生成數(shù)據(jù)簽名。Shen 等［30］設(shè)計(jì)了一種輕量級(jí)的云存儲(chǔ)數(shù)據(jù)完整性審計(jì)方案，通過(guò)引入第三方媒介（Third Party Media，TPM）來(lái)代表用戶處理數(shù)據(jù)。Zhang 等［31］提出了采用模糊不區(qū)分公共審計(jì)方案，該方案在TPA 上進(jìn)行輕量級(jí)計(jì)算，并將大部分計(jì)算委托給CSP。Rabaninejad 等［32］提出了具有抗共謀性的數(shù)據(jù)審計(jì)方案，該方案在實(shí)時(shí)在線階段為用戶端提供輕量級(jí)的計(jì)算成本，用戶將數(shù)據(jù)簽名生成任務(wù)委托給一個(gè)專用代理，并提供身份數(shù)據(jù)隱私和抗共謀用戶撤銷(xiāo)。

2 問(wèn)題描述與預(yù)備知識(shí)

2.1 系統(tǒng)模型

如圖1 所示，本文考慮外包數(shù)據(jù)可驗(yàn)證場(chǎng)景，設(shè)計(jì)的方案由資源受限用戶（Resource-constrained User，RU）、私鑰生成器（Private Key Generator，PKG）、誠(chéng)實(shí)代理人（Honest Proxy，HP）、第三方審計(jì)員（TPA）和云服務(wù)器（CSP）五個(gè)實(shí)體組成：1）RU是數(shù)據(jù)所有者，有將用戶個(gè)體數(shù)據(jù)存儲(chǔ)在云服務(wù)器上的需求。與TPA 和CSP 相比，用戶端設(shè)備的計(jì)算能力更低。同時(shí)，用戶的數(shù)據(jù)量很大，超出了用戶的存儲(chǔ)能力，需要通過(guò)CSP 為用戶提供數(shù)據(jù)存儲(chǔ)服務(wù)。2）PKG 是誠(chéng)信的私鑰分發(fā)中心，通過(guò)獲取用戶和代理人身份信息，然后返回用戶私鑰和代理私鑰。3）HP 是誠(chéng)信實(shí)體，有一定的存儲(chǔ)和計(jì)算能力，負(fù)責(zé)幫助用戶上傳數(shù)據(jù)、生成簽名及動(dòng)態(tài)更新操作。4）TPA 是第三方可信組織，它代表用戶執(zhí)行云存儲(chǔ)審計(jì)，可以定期檢查云服務(wù)器上用戶數(shù)據(jù)的完整性；而且對(duì)數(shù)據(jù)存在誠(chéng)實(shí)好奇性，審計(jì)中需要保護(hù)數(shù)據(jù)隱私。5）CSP 是負(fù)責(zé)為用戶提供云存儲(chǔ)服務(wù)的半誠(chéng)信實(shí)體，存儲(chǔ)能力和計(jì)算能力強(qiáng)，但由于利益問(wèn)題會(huì)存在共謀、泄露隱私等現(xiàn)象。

圖1 系統(tǒng)模型Fig.1 System model

系統(tǒng)模型為資源受限用戶設(shè)備實(shí)現(xiàn)輕量級(jí)審計(jì)方案，該方案的審計(jì)過(guò)程可描述如下：

1）初始化階段：RU對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單的文件分塊和數(shù)據(jù)致盲處理后將數(shù)據(jù)上傳給HP，并刪除本地?cái)?shù)據(jù)。

2）數(shù)據(jù)上傳階段：HP 收到數(shù)據(jù)后為數(shù)據(jù)生成標(biāo)簽證據(jù)，接著使用布隆過(guò)濾器（Bloom Filter，BF）對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)分配，并指定到相應(yīng)MHT 上，然后采用MHT 來(lái)對(duì)已分配數(shù)據(jù)進(jìn)行存儲(chǔ)，這樣可以大大提升數(shù)據(jù)驗(yàn)證的查找速度。操作完成后HP將收到數(shù)據(jù)發(fā)送給CSP，由CSP存儲(chǔ)用戶數(shù)據(jù)。

3）審計(jì)階段：當(dāng)RU 有審計(jì)需求時(shí)，首先向TPA 提出審計(jì)請(qǐng)求，接著由TPA 向CSP發(fā)送審計(jì)挑戰(zhàn)，并通過(guò)CSP返回的數(shù)據(jù)證據(jù)響應(yīng)和HP發(fā)送的標(biāo)簽證據(jù)來(lái)驗(yàn)證數(shù)據(jù)存儲(chǔ)的完整性。

4）動(dòng)態(tài)更新階段：RU 提出動(dòng)態(tài)請(qǐng)求，并將動(dòng)態(tài)請(qǐng)求和動(dòng)態(tài)數(shù)據(jù)發(fā)送給HP；HP 生成新數(shù)據(jù)標(biāo)識(shí)后，更新特定的數(shù)據(jù)結(jié)構(gòu)；然后由HP 將動(dòng)態(tài)請(qǐng)求和動(dòng)態(tài)數(shù)據(jù)發(fā)送給CSP，CSP 收到后將動(dòng)態(tài)請(qǐng)求放入工作記錄表中，并更新數(shù)據(jù)。

2.2 威脅模型

在威脅模型中，假設(shè)TPA 是誠(chéng)實(shí)但好奇的實(shí)體，CSP 是半誠(chéng)實(shí)云服務(wù)器，在此情況下，云服務(wù)器可能向用戶返回不正確或不完整的驗(yàn)證結(jié)果；或者由于利益關(guān)系出現(xiàn)與其他實(shí)體內(nèi)部勾結(jié)泄露用戶數(shù)據(jù)，導(dǎo)致用戶端的經(jīng)濟(jì)損失。因此在存儲(chǔ)和審計(jì)過(guò)程中，在各實(shí)體未知用戶真實(shí)數(shù)據(jù)的情況下，需要幫助用戶處理數(shù)據(jù)，安全的審計(jì)框架和數(shù)據(jù)結(jié)構(gòu)是不可或缺的。

本文主要考慮兩種類(lèi)型的攻擊：

1）內(nèi)部攻擊：內(nèi)部敵手主要是半誠(chéng)信的云服務(wù)器，在動(dòng)態(tài)更新過(guò)程中，為了自身利益，不按照用戶要求來(lái)更新數(shù)據(jù)塊，試圖返回不正當(dāng)?shù)臋z索結(jié)果達(dá)到欺騙用戶的目的。

2）共謀攻擊：主要是半誠(chéng)實(shí)云服務(wù)器和誠(chéng)實(shí)好奇的第三方審計(jì)員合謀獲取用戶隱私數(shù)據(jù)信息，從中謀取利益。

2.3 設(shè)計(jì)目標(biāo)

本文方案的目的是實(shí)現(xiàn)高效和安全的外包數(shù)據(jù)檢索驗(yàn)證，基于圖1模型，本文設(shè)計(jì)實(shí)現(xiàn)以下安全目標(biāo)：

1）公共審計(jì)：用戶可以將審計(jì)任務(wù)委托給任何可信的第三方機(jī)構(gòu)來(lái)執(zhí)行。在可信第三方機(jī)構(gòu)執(zhí)行完審計(jì)任務(wù)后，只需將審計(jì)結(jié)果反饋給用戶即可。

2）輕量級(jí)：方案支持資源受限用戶的審計(jì)請(qǐng)求。即對(duì)用戶運(yùn)算能力和存儲(chǔ)能力有限、無(wú)法完成確保數(shù)據(jù)安全的簽名操作以及數(shù)據(jù)存儲(chǔ)，需要用戶以外的系統(tǒng)成員設(shè)備來(lái)負(fù)責(zé)完成。

3）動(dòng)態(tài)操作效率：用戶對(duì)云服務(wù)器存儲(chǔ)數(shù)據(jù)的動(dòng)態(tài)需求主要是進(jìn)行插入、修改和刪除，對(duì)于資源受限用戶來(lái)說(shuō)，這些動(dòng)態(tài)更新的效率將直接影響用戶對(duì)云端的存儲(chǔ)需求，因?yàn)橛脩舻挠?jì)算能力非常有限，動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的檢索時(shí)間復(fù)雜度直接關(guān)系到審計(jì)的執(zhí)行效率，高效的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)才能滿足資源受限用戶的實(shí)現(xiàn)需求。

4）低延遲、計(jì)算開(kāi)銷(xiāo)?。和ㄐ砰_(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)小，整個(gè)審計(jì)過(guò)程時(shí)延低，在用戶請(qǐng)求動(dòng)態(tài)操作和審計(jì)操作流期間，可以避免用戶和TPA 多次與數(shù)據(jù)結(jié)構(gòu)進(jìn)行交互，快速獲知操作結(jié)果。檢索和更新速度越快，審計(jì)越高效，用戶的經(jīng)濟(jì)損失也就越小。

5）數(shù)據(jù)隱私安全：用戶在數(shù)據(jù)上傳、動(dòng)態(tài)更新和審計(jì)過(guò)程中，需要其他各實(shí)體在未獲取真實(shí)數(shù)據(jù)信息情況下，幫助用戶處理這些數(shù)據(jù)，確保用戶數(shù)據(jù)信息的安全；而且由于用戶不直接檢查數(shù)據(jù)的完整性，同時(shí)也需確保將正確的審計(jì)結(jié)果反饋給用戶。

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

2.4.1 雙線性映射對(duì)

雙線性映射對(duì)［28］定義如下：存在G1、G2和GT是p階素?cái)?shù)乘法循環(huán)群，G1和G2分別是g1和g2的生成元，則雙線性對(duì)e：G1×G2→GT具有以下幾個(gè)性質(zhì)：

1）雙 線 性 性：對(duì)?u∈G1，?v∈G2和a，b∈Zp，有e(ua，vb)=e(u，v)ab成立。

2）可計(jì)算性：對(duì)?u∈G1和?v∈G2，存在有效的算法能夠計(jì)算e(u，v)。

3）非退化性：對(duì)任意的g1和g2，存在e(g1，g2)≠1。

2.4.2 離散對(duì)數(shù)問(wèn)題

對(duì)給定素?cái)?shù)p階的有限循環(huán)群G，其生成元g和任意元素h∈G，計(jì)算a∈Zp值是很困難的，使得h=ga。換句話說(shuō)，對(duì)于任意一個(gè)概率多項(xiàng)式時(shí)間對(duì)手A，解決離散對(duì)數(shù)（Discrete Logarithm，DL）問(wèn)題［33］的概率可忽略，即為：

2.4.3 計(jì)算Diffie-Hellman密鑰交換算法問(wèn)題

令G為一素?cái)?shù)階p的循環(huán)群，對(duì)a隨機(jī)選取一個(gè)生成元g和隨機(jī)數(shù)a，b∈Zp，給定(g，ga，gb)∈G，計(jì)算其值gab是很困難的。也就是說(shuō)，對(duì)于任意一個(gè)概率多項(xiàng)式時(shí)間對(duì)手A，解決計(jì)算Diffie-Hellman（Computational Diffie-Hellman，CDH）密鑰交換算法問(wèn)題［34］的概率可以忽略不計(jì)，即為：

2.4.4 布隆過(guò)濾器

布隆過(guò)濾器（BF）［34］是一個(gè)對(duì)元素集合實(shí)現(xiàn)查詢驗(yàn)證且存儲(chǔ)高效的數(shù)據(jù)結(jié)構(gòu)，不僅可以表示元素所在的集合，還可以支持?jǐn)?shù)據(jù)的動(dòng)態(tài)操作和查詢，優(yōu)勢(shì)在于可以在時(shí)間復(fù)雜度為O(1)內(nèi)有效地實(shí)現(xiàn)用戶的查詢請(qǐng)求。BF以實(shí)現(xiàn)n個(gè)元素的集合S查詢，假設(shè)由長(zhǎng)度為m的數(shù)組RBF表示，集合可表示為S={s1，s2，…，sn}，將元素通過(guò)k個(gè)相互獨(dú)立的哈希函數(shù)H={h1，h2，…，hk} 映射到數(shù)組RBF中去，每個(gè)哈希函數(shù)的范圍都是{1，2，…，m}，可表示為hi：{0，1}*→[1，m]，其中i∈[1，k]對(duì)于每個(gè)元素si∈S，把RBF中相應(yīng)位置h1(si)，h2(si)，…，hk(si)都設(shè)置為1。

2.4.5 多棵Merkle哈希樹(shù)

M-MHT 是一種認(rèn)證的二叉樹(shù)結(jié)構(gòu)［35］，主要用來(lái)完成數(shù)據(jù)完整性驗(yàn)證，目的是有效且安全地證明一組元素是否被損壞和更改。M-MHT 頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，根節(jié)點(diǎn)的身份驗(yàn)證提供了所有葉節(jié)點(diǎn)的完整性保證。M-MHT 根節(jié)點(diǎn)可以通過(guò)用戶進(jìn)行簽名，并將其存儲(chǔ)在服務(wù)器上，這也是它能保證數(shù)據(jù)安全性的主要原因。假設(shè)描述8 個(gè)葉節(jié)點(diǎn)的M-MHT，可設(shè)數(shù)據(jù)集S={s1，s2，…，s8}，h(i)=h(si)(i∈[1，8])。假設(shè)用戶需驗(yàn)證數(shù)據(jù)塊s3的完整性，則需要返回s3的哈希值h(s3)和相關(guān)輔助信息AI(s3)：{h1，2，h(s4)，h5，8}，通過(guò)驗(yàn)證根節(jié)點(diǎn)的真實(shí)性，所有塊都被自動(dòng)認(rèn)證，以此方式來(lái)驗(yàn)證數(shù)據(jù)的完整性并確保存儲(chǔ)的安全性。

3 本文方案

本章首先介紹一個(gè)高效和安全的數(shù)據(jù)結(jié)構(gòu)來(lái)保證輕量級(jí)審計(jì)方案的實(shí)現(xiàn)，以及作為協(xié)議的基礎(chǔ)建設(shè)；然后詳細(xì)介紹了資源受限用戶外包數(shù)據(jù)可驗(yàn)證審計(jì)方案。表1 給出了本文方案中使用的符號(hào)定義。

表1 本文方案中的符號(hào)定義Tab.1 Symbol definition for the proposed scheme

3.1 數(shù)據(jù)結(jié)構(gòu)

為了讓資源受限用戶實(shí)現(xiàn)對(duì)外包數(shù)據(jù)的檢索驗(yàn)證，其核心是需要提出一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)支持整個(gè)審計(jì)過(guò)程的完成；而且由于用戶數(shù)據(jù)的實(shí)時(shí)更新，該數(shù)據(jù)結(jié)構(gòu)還需支持?jǐn)?shù)據(jù)動(dòng)態(tài)功能。因此本文方案提出了一個(gè)高效和安全的新型數(shù)據(jù)結(jié)構(gòu)，以滿足用戶對(duì)數(shù)據(jù)處理的實(shí)時(shí)需求。該數(shù)據(jù)結(jié)構(gòu)主要是滿足兩方面的性能需求：首先該結(jié)構(gòu)是高效的，檢索速度快，計(jì)算開(kāi)銷(xiāo)小，可以使整個(gè)審計(jì)過(guò)程的時(shí)延很低，減少用戶的經(jīng)濟(jì)損失；其次該結(jié)構(gòu)是安全的，可以保證存儲(chǔ)數(shù)據(jù)的安全性。

3.1.1 數(shù)據(jù)結(jié)構(gòu)描述

標(biāo)準(zhǔn)的布隆過(guò)濾器只允許對(duì)元素進(jìn)行插入和搜索查詢操作，不支持元素的刪除操作，一但存儲(chǔ)到BF中，就不能刪除數(shù)據(jù)記錄。為了解決這一缺陷，F(xiàn)an 等［36］提出了計(jì)數(shù)布隆濾波器（Counting Bloom Filter，CBF）。CBF 用計(jì)數(shù)器數(shù)組替換BF中的位數(shù)組，也就是說(shuō)，每個(gè)比特位位置都是一個(gè)小計(jì)數(shù)器，它允許對(duì)CBF 執(zhí)行插入、修改和刪除操作。但采用傳統(tǒng)CBF還不能滿足數(shù)據(jù)結(jié)構(gòu)的高效性，本文在CBF 結(jié)構(gòu)基礎(chǔ)上提出NCBF 結(jié)構(gòu)，NCBF 除了支持?jǐn)?shù)據(jù)動(dòng)態(tài)操作，還可以與存儲(chǔ)數(shù)據(jù)位置相關(guān)聯(lián)，能極大提升數(shù)據(jù)動(dòng)態(tài)處理和對(duì)數(shù)據(jù)查找驗(yàn)證的效率。設(shè)定一個(gè)由m個(gè)計(jì)數(shù)器組成的NCBF，用RNCBF表示，讓U是一個(gè)大集合，其子集S={s1，s2，…，sn} ?U，隨機(jī)選擇k個(gè)相互獨(dú)立的哈希函數(shù)H={h1，h2，…，hk}，對(duì)于每個(gè)元素si∈U，使用k個(gè)哈希函數(shù)將其映射到RNCBF的k個(gè)位置上，當(dāng)元素插入或刪除時(shí)，在對(duì)應(yīng)的計(jì)數(shù)器上加1 或減1；修改操作采用先刪除再插入的方式來(lái)實(shí)現(xiàn)。接著還需構(gòu)造一個(gè)函數(shù)f：U→[1，M]，M∈Z，其中M是M-MHT 的總數(shù)量。該函數(shù)的目的是能快速訪問(wèn)數(shù)據(jù)存儲(chǔ)在哪一棵M-MHT的數(shù)據(jù)結(jié)構(gòu)中，且最壞函數(shù)f求值的時(shí)間復(fù)雜度為O(1)。為解決這個(gè)問(wèn)題，采用了創(chuàng)建最小完美哈希函數(shù)的思想。將搜索函數(shù)f分為映射和查找兩個(gè)階段：首先將集合S映射到一個(gè)隨機(jī)圖G(V，E)上，其中V是一個(gè)頂點(diǎn)集，且，讓兩個(gè)相互獨(dú)立的哈希函數(shù)滿足(h1，h2)：U→V和另一個(gè)獨(dú)立的哈希函數(shù)滿足h3：U→ZMZ；E是圖的邊集，E={(h1(si)，h2(si))，si∈S，|E|=n=|S|}。接著查找G(V，E)中滿足的哈希函數(shù)(h1，h2)，若查找到的(h1，h2)哈希函數(shù)使得G(V，E)是循環(huán)的，則重新更換兩個(gè)新的且獨(dú)立的，直到通過(guò)迭代查找到一個(gè)非循環(huán)圖G(V，E)。這樣得到的哈希函數(shù)就是完美的，它將訪問(wèn)次數(shù)減少到只有1 次，即實(shí)現(xiàn)時(shí)間復(fù)雜度為O(1)，并且節(jié)省空間。最后尋找一個(gè)函數(shù)g：V→ZMZ，使其對(duì)于每一個(gè)元素si∈S，讓 等 式f(si) ≡g(h1(si))+g(h2(si))+h3(si)(modM)成立。該等式的計(jì)算結(jié)果f(si)指向數(shù)據(jù)元素si的存儲(chǔ)位置。

相比哈希表、索引表等數(shù)據(jù)結(jié)構(gòu)，NCBF 結(jié)構(gòu)在存儲(chǔ)空間和占用時(shí)間方面有較大優(yōu)勢(shì)，NCBF的數(shù)據(jù)存儲(chǔ)和動(dòng)態(tài)更新都能在O(1)內(nèi)完成，這極大提高了數(shù)據(jù)查找驗(yàn)證的效率。但由于NCBF 并沒(méi)有存儲(chǔ)數(shù)據(jù)元素本身，因此還需要一個(gè)安全的結(jié)構(gòu)來(lái)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)，本文方案采用M-MHT結(jié)構(gòu)來(lái)實(shí)現(xiàn)這一功能。M-MHT 是一個(gè)可以降低大型數(shù)據(jù)結(jié)構(gòu)成本的二叉樹(shù)結(jié)構(gòu)，其中每個(gè)非葉子節(jié)點(diǎn)都為其子節(jié)點(diǎn)的哈希值。每一棵樹(shù)的頂部有一個(gè)根節(jié)點(diǎn)，每個(gè)根節(jié)點(diǎn)都可以通過(guò)用戶直接進(jìn)行簽名存儲(chǔ)，使得結(jié)構(gòu)本身可以確保數(shù)據(jù)存儲(chǔ)的安全性。在本文方案中，令計(jì)算結(jié)果f(si)=Mj(Mj∈[1，M])，該結(jié)果指向數(shù)據(jù)對(duì)應(yīng)的M-MHT 上，即可以跳過(guò)無(wú)關(guān)的M-MHT，直接跳轉(zhuǎn)到所需信息的M-MHT上進(jìn)行提取驗(yàn)證，這樣可以大大減少數(shù)據(jù)在M-MHT上的搜索時(shí)間，因此該數(shù)據(jù)結(jié)構(gòu)方案是高效可行的。

本文方案采用NCBF 來(lái)提高數(shù)據(jù)檢索的效率。NCBF 結(jié)構(gòu)數(shù)據(jù)插入和檢索時(shí)間復(fù)雜度都為O(1)；而且可以將數(shù)據(jù)元素和存儲(chǔ)位置相關(guān)聯(lián)，跳過(guò)無(wú)關(guān)的存儲(chǔ)位置信息，直接跳轉(zhuǎn)到相關(guān)聯(lián)的存儲(chǔ)位置，顯著減少搜索時(shí)延，從而實(shí)現(xiàn)高效存儲(chǔ)和驗(yàn)證過(guò)程。但只滿足高效性還不能達(dá)到整個(gè)審計(jì)過(guò)程的預(yù)期，因?yàn)镹CBF 本身不是用來(lái)存儲(chǔ)數(shù)據(jù)的，它主要是對(duì)數(shù)據(jù)存放位置進(jìn)行指示，還需要一個(gè)結(jié)構(gòu)來(lái)存放數(shù)據(jù)；其次它存在假陽(yáng)性問(wèn)題，可能會(huì)出現(xiàn)誤判，把沒(méi)有存儲(chǔ)的數(shù)據(jù)信息返回為存儲(chǔ)在結(jié)構(gòu)中，該問(wèn)題可能會(huì)引發(fā)敵手的攻擊，通過(guò)欺騙用戶來(lái)獲取更多利益，會(huì)對(duì)審計(jì)過(guò)程造成安全隱患。因此為了數(shù)據(jù)存儲(chǔ)和驗(yàn)證的安全性，本文方案引入了M-MHT，因?yàn)镸-MHT結(jié)構(gòu)的根節(jié)點(diǎn)可以通過(guò)用戶來(lái)進(jìn)行簽名存儲(chǔ)在代理上，當(dāng)想要驗(yàn)證某條數(shù)據(jù)記錄時(shí)，用戶通過(guò)重新計(jì)算M-MHT根節(jié)點(diǎn)的簽名來(lái)完成，這樣可以確保數(shù)據(jù)的安全性。本文方案的數(shù)據(jù)結(jié)構(gòu)是將NCBF 結(jié)構(gòu)和M-MHT 結(jié)構(gòu)進(jìn)行結(jié)合得到，稱為NCBF-M-MHT，如圖2所示。

圖2 NCBF-M-MHT數(shù)據(jù)結(jié)構(gòu)示意圖Fig.2 Schematic diagram of NCBF-M-MHT data structure

3.1.2 動(dòng)態(tài)操作

本文方案的數(shù)據(jù)結(jié)構(gòu)除了數(shù)據(jù)檢索驗(yàn)證外，還支持用戶數(shù)據(jù)的實(shí)時(shí)更新操作，主要包括用戶數(shù)據(jù)的插入、修改和刪除操作。

1）數(shù)據(jù)插入是將新的數(shù)據(jù)塊插入到整個(gè)存儲(chǔ)服務(wù)器的某些指定位置。假如用戶想插入兩個(gè)數(shù)據(jù)塊I={x，y}，首先根據(jù)選取的k個(gè)哈希函數(shù)將數(shù)據(jù)塊散列到NCBF 中，在NCBF 中對(duì)數(shù)據(jù)塊信息進(jìn)行更新，在相應(yīng)位置增加1，接著對(duì)數(shù)據(jù)塊標(biāo)簽信息進(jìn)行存儲(chǔ)，采用最小完美哈希函數(shù)的思想，將數(shù)據(jù)塊與M-MHT 存儲(chǔ)的位置相關(guān)聯(lián)。對(duì)于數(shù)據(jù)塊x，關(guān)聯(lián)結(jié)果F(x)=Mj代表數(shù)據(jù)塊的標(biāo)簽信息存儲(chǔ)到第Mj棵MHT 上；同樣，對(duì)于數(shù)據(jù)塊y，關(guān)聯(lián)結(jié)果F(y)=Mj+1代表數(shù)據(jù)塊的標(biāo)簽信息存儲(chǔ)到第Mj+1棵MHT 上，最后根據(jù)MHT 更新規(guī)則更新后生成一個(gè)新的根節(jié)點(diǎn)。插入結(jié)構(gòu)如圖3所示。

圖3 數(shù)據(jù)插入示意圖Fig.3 Schematic diagram of data insertion

2）數(shù)據(jù)刪除是從存儲(chǔ)服務(wù)器中移除數(shù)據(jù)信息，具體操作和插入操作相似，在NCBF 中是對(duì)相應(yīng)位置減去1，通過(guò)關(guān)聯(lián)后，在MHT中把標(biāo)簽信息刪除，刪除操作如圖4所示。

3）修改操作是將已存儲(chǔ)在服務(wù)器中的某些數(shù)據(jù)信息進(jìn)行更正，具體操作和插入及刪除一致，先對(duì)原有數(shù)據(jù)進(jìn)行刪除操作后，再把新的數(shù)據(jù)進(jìn)行插入來(lái)完成。

3.2 設(shè)計(jì)協(xié)議

資源受限用戶設(shè)備實(shí)現(xiàn)輕量級(jí)審計(jì)方案的協(xié)議由數(shù)據(jù)上傳、審計(jì)驗(yàn)證和數(shù)據(jù)更新三個(gè)階段構(gòu)成，具體可由ParaSetup、RUDataBlind、HPSignGen、CSPStorage、ChalGen、ProofGen、ProofVerify、DataUpdate 這八個(gè)算法來(lái)進(jìn)行描述。審計(jì)協(xié)議如圖5所示。

1）ParaSetup：由PKG 來(lái)分發(fā)密鑰。G1、G2和GT是p階素?cái)?shù)乘法循環(huán)群，p為素?cái)?shù)乘法循環(huán)群的階數(shù)，g是G1的生成元，雙線性對(duì)為e：G1×G2→GT。全局參數(shù)GP={g，y，H，e，μ，pk}，其中H：{0，1}*→G1為哈希函數(shù)，y=ga，α∈Zp，μ是G1中隨機(jī)產(chǎn)生的生成元，私鑰sk={α，ssk}，(ssk，pk)為隨機(jī)非對(duì)稱加密密鑰對(duì)。接著PKG 分別為RU 和HP生成私鑰RUID和HPID。

圖4 數(shù)據(jù)刪除示意圖Fig.4 Schematic diagram of data deletion

a）數(shù)據(jù)塊插入：若RU想在數(shù)據(jù)塊mi之后插入數(shù)據(jù)塊mi*，則由RU 將插入的數(shù)據(jù)塊信息發(fā)送給HP，其中I代表操作類(lèi)型為插入，i為插入數(shù)據(jù)塊的位置。HP 在收到DI后計(jì)算它的數(shù)據(jù)簽名，接著在數(shù)據(jù)結(jié)構(gòu)中對(duì)NCBF 進(jìn)行計(jì)數(shù)增加，并在MHT 中增加新的節(jié)點(diǎn)信息，最后把DI發(fā)送給CSP，CSP驗(yàn)證后在mi之后存儲(chǔ)該數(shù)據(jù)塊。

b）數(shù)據(jù)塊修改：若RU 想將數(shù)據(jù)塊mi修改為mi*，則首先發(fā)送修改的數(shù)據(jù)塊信息DM={M，i，mi*} 給HP，其中M 代表操作類(lèi)型為修改，i為修改數(shù)據(jù)塊的位置。HP 在收到DM后重新計(jì)算它的數(shù)據(jù)簽名，接著在數(shù)據(jù)結(jié)構(gòu)中對(duì)NCBF 進(jìn)行計(jì)數(shù)更新，并修改相應(yīng)MHT 節(jié)點(diǎn)信息，最后把DM發(fā)送給CSP，CSP驗(yàn)證后將數(shù)據(jù)塊mi進(jìn)行修改并存儲(chǔ)。

c）數(shù)據(jù)塊刪除：若RU 想刪除數(shù)據(jù)塊mi，則首先發(fā)送需要?jiǎng)h除的數(shù)據(jù)塊信息DD={D，i，mi} 給HP，其中D代表操作類(lèi)型為刪除，i為刪除數(shù)據(jù)塊的位置。接著HP 在數(shù)據(jù)結(jié)構(gòu)中減少NCBF 的計(jì)數(shù)，并在MHT 中刪除相關(guān)節(jié)點(diǎn)信息，最后把DD發(fā)送給CSP，CSP驗(yàn)證后將數(shù)據(jù)塊mi刪除。

圖5 審計(jì)協(xié)議示意圖Fig.5 Schematic diagram of audit protocol

4 安全分析

本章利用博弈假設(shè)的方法，首先證明審計(jì)的可靠性和動(dòng)態(tài)操作的有效性，然后用雙線性對(duì)的知識(shí)來(lái)證明審計(jì)的正確性；接著考慮到CSP半誠(chéng)信和TPA誠(chéng)實(shí)好奇問(wèn)題，在數(shù)據(jù)上傳和審計(jì)過(guò)程中需要確保數(shù)據(jù)的隱私保護(hù)；最后針對(duì)本文方案的特殊場(chǎng)景存在的攻擊方式進(jìn)行安全分析。

定理1審計(jì)可靠性。審計(jì)挑戰(zhàn)的數(shù)據(jù)塊只有真正存儲(chǔ)在CSP中，才能通過(guò)TPA驗(yàn)證，否則不能通過(guò)驗(yàn)證。

定理2動(dòng)態(tài)操作有效性。在動(dòng)態(tài)操作過(guò)程中，半誠(chéng)實(shí)的CSP 必須按動(dòng)態(tài)請(qǐng)求的要求來(lái)執(zhí)行，不可能采用篡改或假裝執(zhí)行動(dòng)態(tài)請(qǐng)求的方式來(lái)通過(guò)TPA的驗(yàn)證。

定理3審計(jì)正確性。只有CSP生成的數(shù)據(jù)證據(jù)和HP生成的標(biāo)簽證據(jù)同時(shí)有效才能通過(guò)TPA驗(yàn)證。

從式（6）可以看出，若LPHP或DPCSP無(wú)效，則不能通過(guò)上述等式驗(yàn)證。因此只有標(biāo)簽證據(jù)LPHP和數(shù)據(jù)證據(jù)DPCSP對(duì)應(yīng)且同時(shí)有效，才能通過(guò)TPA驗(yàn)證。

5 性能評(píng)估

本章主要從理論和實(shí)驗(yàn)兩個(gè)方面對(duì)方案的計(jì)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)進(jìn)行分析。首先從理論方面分析了協(xié)議的計(jì)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)；接著通過(guò)搭建實(shí)驗(yàn)環(huán)境，模擬輕量級(jí)審計(jì)協(xié)議及構(gòu)建動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)過(guò)程來(lái)評(píng)估本文方案的開(kāi)銷(xiāo)；最后將本文方案使用的協(xié)議與其他方案進(jìn)行對(duì)比，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

5.1 理論分析

5.1.1 計(jì)算開(kāi)銷(xiāo)

此外將本文方案與Tian 等提出的基于DHT 的審計(jì)方案（簡(jiǎn)記為DHT Audit）［25］、Shen等提出的基于LA-DLIT的審計(jì)方案（簡(jiǎn)記為L(zhǎng)A-DLIT Audit）［27］和Wang 等提出的基于MHT 的審計(jì)方案（簡(jiǎn)記為MHT Audit）［19］在計(jì)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)兩個(gè)方面進(jìn)行了分析比較，結(jié)果如表3、4所示。

由表3可以看出，本文方案在RU端的數(shù)據(jù)計(jì)算階段、CSP證明階段和TPA驗(yàn)證階段中與其他三個(gè)方案相比有顯著的優(yōu)勢(shì)，因?yàn)楸疚姆桨竿ㄟ^(guò)引入HP 明顯減少了RU 的計(jì)算量，并對(duì)審計(jì)各實(shí)體分配不同的操作流程，實(shí)現(xiàn)了針對(duì)RU 的輕量級(jí)審計(jì)。在數(shù)據(jù)上傳生成簽名階段，本文方案比DHT Audit有顯著改進(jìn)，因?yàn)樵隍?yàn)證過(guò)程中TPA無(wú)須生成驗(yàn)證證明，而是分配到HP和CSP進(jìn)行；本文方案只需做兩次配對(duì)就能完成驗(yàn)證，計(jì)算開(kāi)銷(xiāo)比LA-DLIT Audit和MHT Audit的低。

5.1.2 通信開(kāi)銷(xiāo)

通信開(kāi)銷(xiāo)主要針對(duì)的是驗(yàn)證階段和數(shù)據(jù)動(dòng)態(tài)更新兩個(gè)過(guò)程，由于各數(shù)據(jù)結(jié)構(gòu)不同，以及存儲(chǔ)位置不同，導(dǎo)致它們的通信開(kāi)銷(xiāo)也不同，具體情況如表4 所示。與LA-DLIT Audit 和MHT Audit 相比，本文方案的通信成本有顯著的優(yōu)勢(shì)。因?yàn)長(zhǎng)A-DLIT Audit 和MHT Audit 將數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在CSP 端，這比起DHT Audit 將結(jié)構(gòu)存儲(chǔ)在TPA 上和本方案將結(jié)構(gòu)存儲(chǔ)在HP 上，需要更高的通信成本；與DHT Audit 相比，本文方案的優(yōu)勢(shì)并不明顯，因?yàn)镈HT Audit 的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在TPA 上可以減少計(jì)算成本和通信開(kāi)銷(xiāo)。

表2 本文方案計(jì)算開(kāi)銷(xiāo)Tab.2 Computational cost of the proposed scheme

表3 不同方案計(jì)算開(kāi)銷(xiāo)對(duì)比Tab.3 Comparison of computational cost of different schemes

表4 不同方案通信開(kāi)銷(xiāo)對(duì)比Tab.4 Comparison of communication cost of different schemes

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

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)評(píng)估NCBF-M-MHT 審計(jì)的時(shí)間開(kāi)銷(xiāo)與動(dòng)態(tài)更新操作時(shí)間開(kāi)銷(xiāo)，對(duì)上述的計(jì)算開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)進(jìn)行驗(yàn)證，并將其與DHT-Audit、LA-DLIT 和MHT-Audit 進(jìn)行比較。實(shí)驗(yàn)在配置為Intel Core i5-9300H CPU，8 GB 內(nèi)存的筆記本電腦上進(jìn)行，并搭建Linux 虛擬機(jī)，使用C 語(yǔ)言構(gòu)建算法。實(shí)現(xiàn)的算法基于密碼學(xué)庫(kù)（Pairing-Based Cryptography，PBC），庫(kù)版本為0.5.14 進(jìn)行加密。采用MNT d159 橢圓曲線，它有一個(gè)160 位的組順序，因此實(shí)驗(yàn)中p是一個(gè)160 位長(zhǎng)度的素?cái)?shù)，密鑰參數(shù)長(zhǎng)度設(shè)置為80 位，選用SH3-keccak256 作為安全哈希函數(shù)，共采用10 000 個(gè)數(shù)據(jù)塊進(jìn)行上傳，400～5 000 個(gè)挑戰(zhàn)數(shù)據(jù)塊來(lái)驗(yàn)證數(shù)據(jù)完整性。

5.2.1 初始化階段的時(shí)間開(kāi)銷(xiāo)

為實(shí)現(xiàn)數(shù)據(jù)的可驗(yàn)證性，用戶在初始化階段需要對(duì)上傳數(shù)據(jù)進(jìn)行一些相關(guān)操作后才能將數(shù)據(jù)發(fā)送到云端進(jìn)行存儲(chǔ)，并可將本地的數(shù)據(jù)副本刪除。該過(guò)程共處理5 000個(gè)數(shù)據(jù)塊，觀察數(shù)據(jù)塊從500增加到5 000間隔為500的性能曲線，如圖6所示。與對(duì)比方案相比，本文方案中輕量級(jí)用戶端RU 無(wú)須為數(shù)據(jù)塊簽名花費(fèi)大量開(kāi)銷(xiāo)，只需對(duì)數(shù)據(jù)塊進(jìn)行簡(jiǎn)單的致盲處理，所以本文方案針對(duì)輕量級(jí)用戶有明顯優(yōu)勢(shì)。在數(shù)據(jù)塊上傳過(guò)程中，需要代理HP 為數(shù)據(jù)塊生成簽名，如圖7所示，相比其他方案，DHT Audit 需要額外的n個(gè)哈希操作和配對(duì)操作，所需的開(kāi)銷(xiāo)最大，而本文方案與LA-DLIT Audit 和MHT Audit的開(kāi)銷(xiāo)無(wú)明顯差異，而且本文方案少了一次哈希和冪操作，所以花費(fèi)開(kāi)銷(xiāo)比LA-DLIT Audit和MHT Audit要低。

5.2.2 證明驗(yàn)證階段時(shí)間開(kāi)銷(xiāo)

圖8 顯示了CSP 證明階段的開(kāi)銷(xiāo)，CSP 在收到挑戰(zhàn)請(qǐng)求后，為該挑戰(zhàn)返回一個(gè)響應(yīng)所需的時(shí)間成本。該過(guò)程總共處理3 000 個(gè)數(shù)據(jù)塊，挑戰(zhàn)的數(shù)據(jù)塊數(shù)從600 增加到1 500，間隔為100，由于本文方案對(duì)各審計(jì)實(shí)體分配不同的操作流程，在CSP證明階段只需完成c個(gè)累乘和累加的操作，所以時(shí)間開(kāi)銷(xiāo)較低，相較對(duì)比方案有明顯的優(yōu)勢(shì)。圖9 顯示了TPA 驗(yàn)證階段的時(shí)間開(kāi)銷(xiāo)，TPA 對(duì)返回的數(shù)據(jù)證明和標(biāo)簽證明進(jìn)行驗(yàn)證所產(chǎn)生的時(shí)間成本。該過(guò)程共處理10 000 個(gè)數(shù)據(jù)塊，挑戰(zhàn)的數(shù)據(jù)塊數(shù)從500 增加到5 000，間隔為500，該TPA 驗(yàn)證過(guò)程中，本文方案需要更少的冪運(yùn)算、哈希和配對(duì)操作，因此相比其他方案有更低的計(jì)算開(kāi)銷(xiāo)。

圖6 RU時(shí)間開(kāi)銷(xiāo)Fig.6 Time cost of RU

圖7 數(shù)據(jù)上傳開(kāi)銷(xiāo)Fig.7 Cost of data uploading

5.2.3 數(shù)據(jù)更新階段計(jì)算開(kāi)銷(xiāo)

圖10 展示了對(duì)數(shù)據(jù)更新的插入、修改和刪除三個(gè)動(dòng)態(tài)操作的時(shí)間開(kāi)銷(xiāo)，該過(guò)程處理更新數(shù)據(jù)塊從20增至200，間隔為20。本文方案采用NCBF-M-MHT 數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)據(jù)塊的插入和查找時(shí)間復(fù)雜度為O(1)；DHT Audit采用一個(gè)動(dòng)態(tài)哈希表的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)驗(yàn)證的復(fù)雜度為O(n)，需要花費(fèi)的時(shí)間開(kāi)銷(xiāo)較大；LA-DLIT Audit 采用一個(gè)位置數(shù)組雙向鏈接信息表構(gòu)成數(shù)據(jù)結(jié)構(gòu)，雖然可以減小時(shí)間開(kāi)銷(xiāo)，但無(wú)法抵御內(nèi)部攻擊；MHT Audit 采用一棵MHT 結(jié)構(gòu)，對(duì)數(shù)據(jù)塊的更新時(shí)間復(fù)雜度為O(logn)，但是隨著數(shù)據(jù)塊數(shù)增多，樹(shù)的深度增加，查找花費(fèi)時(shí)間開(kāi)銷(xiāo)較大。相比其他方案，本文采用的NCBF-M-MHT 數(shù)據(jù)結(jié)構(gòu)性能更優(yōu)，時(shí)間開(kāi)銷(xiāo)更低。

圖8 CSP證明開(kāi)銷(xiāo)Fig.8 Cost of CSP certification

圖9 TPA驗(yàn)證開(kāi)銷(xiāo)Fig.9 Cost of TPA validation

圖10 動(dòng)態(tài)更新開(kāi)銷(xiāo)Fig.10 Cost of dynamic updating

6 結(jié)語(yǔ)

本文提出了一個(gè)面向資源受限用戶的輕量級(jí)審計(jì)方案。為了解決云數(shù)據(jù)完整性驗(yàn)證中存在的用戶輕量級(jí)運(yùn)算、數(shù)據(jù)隱私安全性和動(dòng)態(tài)操作效率問(wèn)題，首先引入誠(chéng)信代理幫助用戶進(jìn)行復(fù)雜的簽名操作，用戶端只需對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單的致盲處理。其次為了滿足動(dòng)態(tài)需求，提出NCBF-M-MHT 數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)支持?jǐn)?shù)據(jù)的插入、修改和刪除操作。其中NCBF 可在O(1)時(shí)間內(nèi)實(shí)現(xiàn)數(shù)據(jù)的插入和查找等操作；再結(jié)合M-MHT 對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)及通過(guò)用戶對(duì)根節(jié)點(diǎn)簽名來(lái)保證數(shù)據(jù)的安全性。接著為實(shí)現(xiàn)審計(jì)的正確性和完整性驗(yàn)證，通過(guò)對(duì)云服務(wù)器端返回的數(shù)據(jù)證據(jù)響應(yīng)和代理端發(fā)送的標(biāo)簽證據(jù)來(lái)共同驗(yàn)證數(shù)據(jù)。性能分析與實(shí)驗(yàn)對(duì)比結(jié)果表明，本文方案是高效和安全的，且具有更低的時(shí)間開(kāi)銷(xiāo)。

總的來(lái)說(shuō)，本文方案對(duì)于資源受限用戶實(shí)現(xiàn)云數(shù)據(jù)完整性驗(yàn)證有一定的積極作用。但目前本文方案還只探討了單個(gè)資源受限用戶的數(shù)據(jù)完整性驗(yàn)證，如何高效且安全地實(shí)現(xiàn)多個(gè)輕量級(jí)用戶間云數(shù)據(jù)共享審計(jì)驗(yàn)證將是下一步的研究方向。