面向資源受限用戶的高效動態數據審計方案

李秀艷，劉明曦，史聞博，董國芳*

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

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

0 引言

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

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

本文使用高效且安全的輕量級算法來構建一個適合輕量級設備自身特點，且綜合考慮高效性、安全性的審計方案，主要工作如下：

1）基于新穎的計數布隆過濾器（Novel Counting Bloom Filter，NCBF）和多棵Merkle 哈希樹（Multi-Merkle Hash Tree，M-MHT）技術提出一個高效且安全的數據結構NCBF-MMHT。其中：NCBF 用來支持數據的快速查找，實現審計高效性；M-MHT用來存儲數據及確保數據的安全性。

2）提出一個針對資源受限用戶設備的輕量級審計方案，對審計各實體采用不同的分配操作。首先引入代理幫助用戶處理復雜的高運算過程；其次審計驗證通過云服務器端返回的數據證據響應和代理端發送的標簽證據來共同驗證數據存儲的完整性，并從協議上來實現對資源受限用戶的輕量級審計。

3）通過安全分析和性能評估驗證了本文方案的高效性與安全性，該方案能夠保證審計結果的正確性和完整性。

1 相關工作

物聯網和云計算領域的研究已成為熱門，而數據完整性驗證一直是外包物聯網數據中一個非常重要的問題［3］。關于數據完整性驗證的研究大致可分為隱私安全、動態更新和輕量級審計三個方面。

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

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

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

2 問題描述與預備知識

2.1 系統模型

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

圖1 系統模型Fig.1 System model

系統模型為資源受限用戶設備實現輕量級審計方案，該方案的審計過程可描述如下：

1）初始化階段：RU對數據進行簡單的文件分塊和數據致盲處理后將數據上傳給HP，并刪除本地數據。

2）數據上傳階段：HP 收到數據后為數據生成標簽證據，接著使用布隆過濾器（Bloom Filter，BF）對數據進行存儲分配，并指定到相應MHT 上，然后采用MHT 來對已分配數據進行存儲，這樣可以大大提升數據驗證的查找速度。操作完成后HP將收到數據發送給CSP，由CSP存儲用戶數據。

3）審計階段：當RU 有審計需求時，首先向TPA 提出審計請求，接著由TPA 向CSP發送審計挑戰，并通過CSP返回的數據證據響應和HP發送的標簽證據來驗證數據存儲的完整性。

4）動態更新階段：RU 提出動態請求，并將動態請求和動態數據發送給HP；HP 生成新數據標識后，更新特定的數據結構；然后由HP 將動態請求和動態數據發送給CSP，CSP 收到后將動態請求放入工作記錄表中，并更新數據。

2.2 威脅模型

在威脅模型中，假設TPA 是誠實但好奇的實體，CSP 是半誠實云服務器，在此情況下，云服務器可能向用戶返回不正確或不完整的驗證結果；或者由于利益關系出現與其他實體內部勾結泄露用戶數據，導致用戶端的經濟損失。因此在存儲和審計過程中，在各實體未知用戶真實數據的情況下，需要幫助用戶處理數據，安全的審計框架和數據結構是不可或缺的。

本文主要考慮兩種類型的攻擊：

1）內部攻擊：內部敵手主要是半誠信的云服務器，在動態更新過程中，為了自身利益，不按照用戶要求來更新數據塊，試圖返回不正當的檢索結果達到欺騙用戶的目的。

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

2.3 設計目標

本文方案的目的是實現高效和安全的外包數據檢索驗證，基于圖1模型，本文設計實現以下安全目標：

1）公共審計：用戶可以將審計任務委托給任何可信的第三方機構來執行。在可信第三方機構執行完審計任務后，只需將審計結果反饋給用戶即可。

2）輕量級：方案支持資源受限用戶的審計請求。即對用戶運算能力和存儲能力有限、無法完成確保數據安全的簽名操作以及數據存儲，需要用戶以外的系統成員設備來負責完成。

3）動態操作效率：用戶對云服務器存儲數據的動態需求主要是進行插入、修改和刪除，對于資源受限用戶來說，這些動態更新的效率將直接影響用戶對云端的存儲需求，因為用戶的計算能力非常有限，動態數據結構的檢索時間復雜度直接關系到審計的執行效率，高效的動態數據結構才能滿足資源受限用戶的實現需求。

4）低延遲、計算開銷?。和ㄐ砰_銷和計算開銷小，整個審計過程時延低，在用戶請求動態操作和審計操作流期間，可以避免用戶和TPA 多次與數據結構進行交互，快速獲知操作結果。檢索和更新速度越快，審計越高效，用戶的經濟損失也就越小。

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

2.4 預備知識

2.4.1 雙線性映射對

雙線性映射對［28］定義如下：存在G1、G2和GT是p階素數乘法循環群，G1和G2分別是g1和g2的生成元，則雙線性對e：G1×G2→GT具有以下幾個性質：

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

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

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

2.4.2 離散對數問題

對給定素數p階的有限循環群G，其生成元g和任意元素h∈G，計算a∈Zp值是很困難的，使得h=ga。換句話說，對于任意一個概率多項式時間對手A，解決離散對數（Discrete Logarithm，DL）問題［33］的概率可忽略，即為：

2.4.3 計算Diffie-Hellman密鑰交換算法問題

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

2.4.4 布隆過濾器

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

2.4.5 多棵Merkle哈希樹

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

3 本文方案

本章首先介紹一個高效和安全的數據結構來保證輕量級審計方案的實現，以及作為協議的基礎建設；然后詳細介紹了資源受限用戶外包數據可驗證審計方案。表1 給出了本文方案中使用的符號定義。

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

3.1 數據結構

為了讓資源受限用戶實現對外包數據的檢索驗證，其核心是需要提出一個數據結構來支持整個審計過程的完成；而且由于用戶數據的實時更新，該數據結構還需支持數據動態功能。因此本文方案提出了一個高效和安全的新型數據結構，以滿足用戶對數據處理的實時需求。該數據結構主要是滿足兩方面的性能需求：首先該結構是高效的，檢索速度快，計算開銷小，可以使整個審計過程的時延很低，減少用戶的經濟損失；其次該結構是安全的，可以保證存儲數據的安全性。

3.1.1 數據結構描述

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

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

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

圖2 NCBF-M-MHT數據結構示意圖Fig.2 Schematic diagram of NCBF-M-MHT data structure

3.1.2 動態操作

本文方案的數據結構除了數據檢索驗證外，還支持用戶數據的實時更新操作，主要包括用戶數據的插入、修改和刪除操作。

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

圖3 數據插入示意圖Fig.3 Schematic diagram of data insertion

2）數據刪除是從存儲服務器中移除數據信息，具體操作和插入操作相似，在NCBF 中是對相應位置減去1，通過關聯后，在MHT中把標簽信息刪除，刪除操作如圖4所示。

3）修改操作是將已存儲在服務器中的某些數據信息進行更正，具體操作和插入及刪除一致，先對原有數據進行刪除操作后，再把新的數據進行插入來完成。

3.2 設計協議

資源受限用戶設備實現輕量級審計方案的協議由數據上傳、審計驗證和數據更新三個階段構成，具體可由ParaSetup、RUDataBlind、HPSignGen、CSPStorage、ChalGen、ProofGen、ProofVerify、DataUpdate 這八個算法來進行描述。審計協議如圖5所示。

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

圖4 數據刪除示意圖Fig.4 Schematic diagram of data deletion

a）數據塊插入：若RU想在數據塊mi之后插入數據塊mi*，則由RU 將插入的數據塊信息發送給HP，其中I代表操作類型為插入，i為插入數據塊的位置。HP 在收到DI后計算它的數據簽名，接著在數據結構中對NCBF 進行計數增加，并在MHT 中增加新的節點信息，最后把DI發送給CSP，CSP驗證后在mi之后存儲該數據塊。

b）數據塊修改：若RU 想將數據塊mi修改為mi*，則首先發送修改的數據塊信息DM={M，i，mi*} 給HP，其中M 代表操作類型為修改，i為修改數據塊的位置。HP 在收到DM后重新計算它的數據簽名，接著在數據結構中對NCBF 進行計數更新，并修改相應MHT 節點信息，最后把DM發送給CSP，CSP驗證后將數據塊mi進行修改并存儲。

c）數據塊刪除：若RU 想刪除數據塊mi，則首先發送需要刪除的數據塊信息DD={D，i，mi} 給HP，其中D代表操作類型為刪除，i為刪除數據塊的位置。接著HP 在數據結構中減少NCBF 的計數，并在MHT 中刪除相關節點信息，最后把DD發送給CSP，CSP驗證后將數據塊mi刪除。

圖5 審計協議示意圖Fig.5 Schematic diagram of audit protocol

4 安全分析

本章利用博弈假設的方法，首先證明審計的可靠性和動態操作的有效性，然后用雙線性對的知識來證明審計的正確性；接著考慮到CSP半誠信和TPA誠實好奇問題，在數據上傳和審計過程中需要確保數據的隱私保護；最后針對本文方案的特殊場景存在的攻擊方式進行安全分析。

定理1審計可靠性。審計挑戰的數據塊只有真正存儲在CSP中，才能通過TPA驗證，否則不能通過驗證。

定理2動態操作有效性。在動態操作過程中，半誠實的CSP 必須按動態請求的要求來執行，不可能采用篡改或假裝執行動態請求的方式來通過TPA的驗證。

定理3審計正確性。只有CSP生成的數據證據和HP生成的標簽證據同時有效才能通過TPA驗證。

從式（6）可以看出，若LPHP或DPCSP無效，則不能通過上述等式驗證。因此只有標簽證據LPHP和數據證據DPCSP對應且同時有效，才能通過TPA驗證。

5 性能評估

本章主要從理論和實驗兩個方面對方案的計算開銷和通信開銷進行分析。首先從理論方面分析了協議的計算開銷和通信開銷；接著通過搭建實驗環境，模擬輕量級審計協議及構建動態數據結構過程來評估本文方案的開銷；最后將本文方案使用的協議與其他方案進行對比，并對實驗結果進行分析。

5.1 理論分析

5.1.1 計算開銷

此外將本文方案與Tian 等提出的基于DHT 的審計方案（簡記為DHT Audit）［25］、Shen等提出的基于LA-DLIT的審計方案（簡記為LA-DLIT Audit）［27］和Wang 等提出的基于MHT 的審計方案（簡記為MHT Audit）［19］在計算開銷和通信開銷兩個方面進行了分析比較，結果如表3、4所示。

由表3可以看出，本文方案在RU端的數據計算階段、CSP證明階段和TPA驗證階段中與其他三個方案相比有顯著的優勢，因為本文方案通過引入HP 明顯減少了RU 的計算量，并對審計各實體分配不同的操作流程，實現了針對RU 的輕量級審計。在數據上傳生成簽名階段，本文方案比DHT Audit有顯著改進，因為在驗證過程中TPA無須生成驗證證明，而是分配到HP和CSP進行；本文方案只需做兩次配對就能完成驗證，計算開銷比LA-DLIT Audit和MHT Audit的低。

5.1.2 通信開銷

通信開銷主要針對的是驗證階段和數據動態更新兩個過程，由于各數據結構不同，以及存儲位置不同，導致它們的通信開銷也不同，具體情況如表4 所示。與LA-DLIT Audit 和MHT Audit 相比，本文方案的通信成本有顯著的優勢。因為LA-DLIT Audit 和MHT Audit 將數據結構存儲在CSP 端，這比起DHT Audit 將結構存儲在TPA 上和本方案將結構存儲在HP 上，需要更高的通信成本；與DHT Audit 相比，本文方案的優勢并不明顯，因為DHT Audit 的數據結構存儲在TPA 上可以減少計算成本和通信開銷。

表2 本文方案計算開銷Tab.2 Computational cost of the proposed scheme

表3 不同方案計算開銷對比Tab.3 Comparison of computational cost of different schemes

表4 不同方案通信開銷對比Tab.4 Comparison of communication cost of different schemes

5.2 實驗分析

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

5.2.1 初始化階段的時間開銷

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

5.2.2 證明驗證階段時間開銷

圖8 顯示了CSP 證明階段的開銷，CSP 在收到挑戰請求后，為該挑戰返回一個響應所需的時間成本。該過程總共處理3 000 個數據塊，挑戰的數據塊數從600 增加到1 500，間隔為100，由于本文方案對各審計實體分配不同的操作流程，在CSP證明階段只需完成c個累乘和累加的操作，所以時間開銷較低，相較對比方案有明顯的優勢。圖9 顯示了TPA 驗證階段的時間開銷，TPA 對返回的數據證明和標簽證明進行驗證所產生的時間成本。該過程共處理10 000 個數據塊，挑戰的數據塊數從500 增加到5 000，間隔為500，該TPA 驗證過程中，本文方案需要更少的冪運算、哈希和配對操作，因此相比其他方案有更低的計算開銷。

圖6 RU時間開銷Fig.6 Time cost of RU

圖7 數據上傳開銷Fig.7 Cost of data uploading

5.2.3 數據更新階段計算開銷

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

圖8 CSP證明開銷Fig.8 Cost of CSP certification

圖9 TPA驗證開銷Fig.9 Cost of TPA validation

圖10 動態更新開銷Fig.10 Cost of dynamic updating

6 結語

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

總的來說，本文方案對于資源受限用戶實現云數據完整性驗證有一定的積極作用。但目前本文方案還只探討了單個資源受限用戶的數據完整性驗證，如何高效且安全地實現多個輕量級用戶間云數據共享審計驗證將是下一步的研究方向。