基于無雙線性對的可信云數據完整性驗證方案

袁文勇，李秀廣，2*，李瑞峰，易錚閣，楊曉元，3

（1.武警工程大學 密碼工程學院，西安 710086；2.綜合業務網理論及關鍵技術國家重點實驗室（西安電子科技大學），西安 710071；3.網絡與信息安全武警部隊重點實驗室，西安 710086）

0 引言

隨著計算能力的發展，用戶需要掌握的數據越來越多，為了節省存儲空間和管理成本，用戶往往把數據外包到云服務器［1］。由于用戶外包數據后通常會刪除本地數據以釋放空間，數據保留在云中，用戶失去對數據的直接控制，導致云存儲出現各種安全問題［2］。數據的完整性就是其中的重點研究問題之一。

為保證數據的完整性，多種審計方案被提出。早期方案［3-4］都是采用絕對性檢測，用戶需要重新下載所需檢測的數據，再與本地數據進行對比，實現完整性驗證的目的。頻繁下載數據來檢查完整性對用戶來說成本是昂貴且不合理的。2007 年Ateniese 等［5］提出數據持有性證明（Provable Data Posssession，PDP）方案，開創性提出抽樣檢測的方法驗證數據完整性，用戶檢測數據完整性無需下載數據即可完成驗證，減輕了用戶計算開銷。2008 年Ateniese 等［6］提出可擴展的PDP 方案，實現對數據的部分動態操作。以上方案由用戶承擔大部分驗證開銷，用戶實際計算能力有限并缺乏專業性。為了解決上述矛盾，2009 年Wang 等［7］提出一種基于第三方審計機構（Third Party Auditor，TPA）的審計模型，TPA 具有專業的計算能力且被行業承認。用戶授權TPA 對外包數據進行審計并代表用戶完成云中數據的完整性驗證。但TPA 不能保證完全可信，有可能窺探用戶隱私。為了在審計過程中保護用戶數據隱私，Wang 等［8］在審計過程加入隨機掩碼技術，對參與審計的數據塊聚合進行盲化，保證TPA 無法通過對相同數據進行驗證從而獲取用戶數據。隨著TPA模型推廣，如何保證TPA 如實完成審計請求成為云審計安全的重要問題之一。2017 年張鍵紅等［9］設計出一種新的審計方案，對數據和數據標簽進行雙重驗證，以加強對TPA 的控制并提高用戶的審計能力。2019 年Xue 等［10］利用區塊鏈技術提出了一種抵抗惡意TPA 的完整性審計方案，方案有效抵抗了TPA 可能的欺騙行為，并保證了審計結果的正確性，但區塊鏈數據存儲成本高昂［11］。Qian 等［12］利用偽隨機比特生成器隨機生成挑戰信息，使TPA 必須每次執行用戶的審計請求，避免了TPA 跳過審計直接返回結果的欺騙行為。以上方案均是基于雙線性映射的思想，生成標簽和驗證過程繁瑣，對云和TPA 計算能力要求高。

為提高計算效率，防止TPA 欺騙行為和保護數據隱私，本文基于離散對數假設構建新的標簽生成算法，利用偽隨機比特生成器保證挑戰信息的隨機性，增加用戶和TPA 審計結果的交互過程，檢查數據完整性，保證審計結果的可信。計算過程無雙線性映射參與，能有效提高計算效率。

1 預備知識

1.1 離散對數問題

G是一個階為大素數q的乘法循環群，其中g是循環群的生成元。已知g和ga，求a的值是困難的，這稱為離散對數問題（Discrete Logirathm Problem，DLP）［13］。

1.2 單向散列函數

密碼學哈希函數又被稱為單向散列函數，它可以將任意長度的消息轉化為固定長度的哈希值。單向散列函數具有單向性和抗碰撞性。

1）單向性：由一個輸入求得散列值是容易的，由散列值求輸入是困難的。

2）弱抗碰撞性：要找到和某條消息具有相同散列值的另一條消息是非常困難的。

3）強碰撞性：要找到散列值相同的兩條不同消息是非常困難的［14］。

1.3 偽隨機比特生成器

Zhang 等［15］提出比特幣新區塊生成可被看成是基于時間的偽隨機資源，對偽隨機比特生成器的定義：

函數的輸入是過去或者當前時間t，在比特幣系統中容易計算出；如果是未來的時間，函數的輸出是不可預測的。本文方案輸入審計的當前時間，利用式（1）計算挑戰信息。假設挑 戰的數 據塊數目為n，則只需 用{θ‖0，θ‖1，…，θ‖(n-1) }分別作為一個映射到數據塊集合中的哈希函數的輸入，得到的輸出便是要挑戰的數據塊索引集合［15］。

2 審計模型和設計目標

2.1 審計模型

本文可信審計模型有3 個參與方：用戶、云服務器（Cloud Server Provider，CSP）和第三方審計機構（TPA）。

用戶 上傳數據和數據標簽到云服務器，委托云對數據進行保管。

CSP 接收用戶數據和對應標簽，對用戶數據進行存儲管理，節省用戶存儲空間和計算資源。云服務器不會惡意對外泄露用戶數據信息，否則用戶利用云進行存儲管理數據將失去意義。

TPA 接收用戶的審計請求，對云中用戶數據進行完整性驗證，并將結果返回給用戶。本文模型相較于傳統TPA 審計模型增加了TPA 生成的挑戰信息與用戶的交互，把傳統的TPA 直接返回審計結果變成結果對比，具體模型如圖1所示。

圖1 可信審計模型Fig.1 Model of trusted audit

①用戶將數據和數據塊標簽上傳至CSP。

②用戶向TPA 發送檢驗數據完整性的請求。

③TPA 利用偽隨機比特生成器生成挑戰信息，將挑戰分別發送給用戶和云服務器。

④CSP 接收挑戰后，生成數據完整的證明給TPA。

⑤TPA 接收證明，通過計算返回一個審計值給用戶，用戶通過檢查計算結果判斷數據是否完整以及TPA 是否如實完成審計請求。

可信審計模型包括以下多項式算法。

Setup：系統初始化，選取合適的群和哈希函數作為系統參數，并公開。

KeyGen(s) →(pk，sk)：選取合適參數生成用戶密鑰對。

TagGen(M，sk) →(M，K)：用戶對數據分塊后使用簽名算法對數據進行簽名，將數據M和標簽K發送給CSP 后，刪除本地數據。

ChallengeGen(t) →C：審計者利用當前時間t和用戶的公鑰pk，執行ChallengeGen 算法產生挑戰C，發送給CSP。

ProofGen(C，M，pk，K) →P：CSP 輸入挑戰C，數據M、標簽K和用戶的公鑰pk，輸出證據響應P，發送給TPA。

VerifyProof(C，P，pk) →W1：審計者輸入挑戰C，用戶公鑰pk，生成計算結果W1并發送給用戶，用戶對比計算結果判斷數據完整性。

2.2 設計目標

針對TPA 存在的惡意行為，本文構建了一種無雙線線對的可信云審計方案。利用偽隨機比特生成器生成隨機挑戰，保證挑戰時效性。增加TPA 發送計算結果給用戶驗證，由用戶判斷數據完整性。設計方案可滿足以下目標：

1）存儲正確性。只有CSP 完整存儲用戶的文件的情況下，才能通過審計方案的驗證。

2）可信審計。方案能夠發現TPA 的惡意行為

3）隱私保護。TPA 在審計過程中無法獲取用戶數據。

4）安全性。方案可以抵抗來自CSP 的偽造攻擊和代替攻擊。

5）批量審計。實現多個數據的批量驗證，無需進行多次單項審計。

6）高效性。方案的審計過程中不需進行雙線性對運算，節省計算開銷。

3 無雙線性對的云審計方案設計

3.1 系統建立階段

Setup：選取階為大素數q的乘法循環群G1，令g為群G1生成元，Q是群上 的一個 隨機元 素，H1：{0，1}*→Ζq，H2：{0，1}*×G→Ζq是兩個 哈希函 數。公開系 統參數{G，g，Q，q，H1，H2}。

KeyGen(s) →(pk，sk)：用戶選取隨機數計算用戶私鑰和公鑰。其中{pk，sk}={S，gs}，S∈。

TagGen(M，sk) →(M，K)：用戶對數據文件M分塊，表示為：M={m1，m2，…，mn}。完成分塊后利用密鑰進行簽名。對每個數據塊mi具體簽名過程如下。

用戶選取隨機數λi，計算：

其中：ID為用戶身份；{σi，Ri，H1(λi)}作為數據塊mi的標簽，將{mi，σi，Ri，H1(λi)}上傳到云服務器并刪除本地數據。

3.2 挑戰階段

ChallengeGen(t) →C：TPA 接收用戶審計請求生成挑戰信息。TPA 利用式（1）輸入當前時間t，生成θ，計算ρ=H1(θ)，從集合{1，2，…，n}選取非空子集I，生成挑戰C={ρ，I}發送給云服務器和用戶。

3.3 證據生成階段

ProofGen(C，M，pk，K) →P：云服務 器接收挑戰C={ρ，I}。計算：

最后把P={σ，u}發送給審計者。

3.4 驗證階段

VerifyProof(C，P，pk) →W1：TPA 輸入挑戰C、證據P和用戶公鑰pk，計算審計值W1。

TPA 把W1發送給用戶，用戶計算

用戶接收到挑戰信息，計算vi和云服務器利用式（4）計算過程一致。用戶對式（9）進行驗證：

如果式（9）成立，證明數據保存完整，TPA 如實完成審計請求。

4 安全分析

4.1 方案正確性

如果云服務器完整存儲用戶數據，則能夠通過如下證明：

通過以上數學證明可知，如果用戶正確存儲數據且TPA如實執行審計請求，則能夠通過證明；否則數據不完整或者TPA 沒有如實進行審計。

4.2 抗代替攻擊

如果生成證據階段云服務器利用完好的數據塊代替損壞的數據塊進行證據生成，那么生成的證明無法通過式（9）驗證。

證明 假設數據塊和標簽{mj，σj，Rj，H1(λj) }已經損壞，CS 利用完好的數據塊和標簽{mj，σj，Rj，H1(λj) }去代替進行證據生成，CS 進行如下計算：

用戶計算的W2是根據挑戰計算的，不會因為證據而改變。要通過完整性驗證，則需要：

4.3 抗偽造攻擊

如果離散對數成立，則云服務器無法為不完整數據偽造證據通過完整性驗證。

證明 利用文獻［16］的安全模型，假設云服務器能夠為不完整數據偽造證據通過完整性驗證，則說明能夠解決離散對數問題。證明過程如下：

其中：分母r2Δu不為0，r2不為0，r2是在隨機數上選取的，不為0 的概率為1/q，得到解決DL 問題的概率為1 -1/q，q為大素數，1 -1/q大小不可忽略。如果云服務器能夠利用不完整數據偽造證據通過驗證，則云服務器能夠以不可忽略的概率1 -1/q解決DL 問題，這與DL 假設相矛盾。

4.4 隱私保護

4.5 檢驗TPA惡意行為

證明 1）抵抗TPA 生成不隨機的挑戰信息。本文方案利用偽隨機比特生成器生成挑戰信息，規定TPA 輸入當前的審計時間，因此每次得到的式（1）結果都是不一樣的；再利用函數輸出結果生成挑戰信息，保證了挑戰信息的隨機性。文獻［17-18］是TPA 進行隨機數挑選，人為機構無法保證挑戰信息的隨機性。本文方案中，如果TPA 重復使用之前的挑戰信息，由于TPA 要發送挑戰信息給用戶，用戶通過對比之前接收的挑戰，很容易識別TPA 這種惡意行為。

2）抵抗TPA 跳過審計直接返回結果的惡意行為。在文獻［17-18］中，TPA 直接返回“0”或者“1”說明數據的完整性情況。有可能存在惡意TPA 為了節省開銷，直接返回之前的審計結果給用戶，不進行審計計算。本文方案通過比較TPA計算的和用戶計算的，由用戶進行判別審計結果，避免了TPA 跳過審計直接返回結果的惡意行為。

通過以上對TPA 行為的判定，說明本文方案的審計結果是可信的。

5 擴展方案

實際使用的云環境中存在大量用戶和海量數據，TPA 往往需要一次性檢查多個用戶數據的完整性。在支持單項數據審計的方案基礎上，擴展為滿足多用戶數據的審計方案，實現對多用戶云環境的數據審計要求。設參與驗證的用戶的數量為L，用戶l(1 ≤l≤L)擁有文件Ml，滿足多用戶多數據的具體審計算法如下。

setup：系統參數設置與單項審計方案一致。

{σl，i，Rl，i，H1(λl，i)}作為數據塊的標簽K。將標簽上傳到云服務器，并刪除本地數據ml，i，其中IDl為用戶l身份。

ChallengeGen(t) →C：挑戰生成過程與單項審計方案相同。

ProofGen(C，Ml) →P：云服務 器接收挑戰C={ρ，I}，計算：

最后把證據P={σ，u}發送給審計者。

VerifyProof(C，P，pk) →W1：TPA 輸入挑戰C、證據P和用戶l公鑰pkl（1 ≤l≤L），計算審計值W1。

TPA 把W1發送給用戶l，用戶l計算

用戶接收到挑戰信息，計算vi和云服務器利用式（4）計算過程一致。用戶對W1=W2進行驗證，如果等式成立，證明審計的多項數據保存完整，且TPA 如實完成審計請求。

對擴展方案的正確性進行證明：

批量審計方案是基于單項審計方案擴展而來，滿足檢驗數據完整性、抗代替攻擊、偽造攻擊和數據隱私保護。證明方法與單項審計方案相同。

6 效能分析

本文方案的計算開銷主要在用戶生成標簽階段、挑戰生成階段和驗證階段。在證據生成階段中，不涉及群元素和哈希函數的計算，故計算開銷可以忽略。下面主要對單項審計方案性能進行分析。

定義H為一次單向哈希函數的計算代價，M為在群G1上做一次乘法運算的代價，E為在群G1上做一次指數運算的代價，P為一次雙線性對運算的代價，n為文件中數據塊的數量，c為查詢數據塊的數量。|G1|為群G1中元素比特長度，|n|為［1，n］中元素的比特長度，|P|為Zq中元素比特長度。

6.1 計算代價

TagGen(M，sk) →K：生成一個標簽主要有一次計算群元素Ri的冪運算和計算σi的兩次哈希運算。文件M分為n塊，故生成標簽計算開銷為nE+2nH。

ChallengeGen(t) →C：挑戰階段開銷主要計算ρ，故挑戰階段計算開銷為H。

VerifyProof(C，P，pk) →W1：驗證階段開銷為TPA 計算W1和用戶計算W2。計算W1為兩次群冪運算和一次群乘法運算；計算W2為一次群冪運算和c-1 次群乘法運算，故驗證階段計算開銷為3E+cM。

主要對比傳統存在雙線性對云審計文獻［8］、無雙線性對的云審計文獻［17］以及基于Merkle 哈希樹的無雙線性對（Merkle-Hash-Tree based Without Bilinear PAiring，MHT-WiBPA）審計方案［18］。為了便于比較，統一計算標簽數量為n，查詢數據塊為c。由于單次哈希運算開銷很小，忽略本文方案中在挑戰階段的一次哈希運算開銷。具體對比情況如表1 所示。

表1 計算開銷對比Tab.1 Comparison of computational cost

6.2 通信代價

本文方案通信開銷集中在發送挑戰和返回證據兩個階段。發送挑戰C={ρ，I}過程，審計者可以直接發送一個時間給CSP 即可，由CSP 通過偽隨機比特器計算挑戰信息，只需將C={ρ，I}發送至用戶，通信量為c|P|+|n|；返回證據P={σ，u}通信量為2|P|。故本文方案總通信開銷為（c+2）|P|+|n|。為使結果更加直觀，設置 |G1|=|P|=160 bit，|n|=32 bit。具體對比上述文獻［8，17-18］情況如表2 所示。

表2 通信開銷對比Tab.2 Comparison of communication cost

6.3 實驗對比

實驗使用Java 語言和利用JPBC 庫實現。運行平臺是2.5 GHz，i5CPU，Windows 10 操作系統64 位，8 GB 內存。在實驗中，設置基域的大小為512 bit，在ZP中一個元素的大小|P|=160 bit，選擇的挑戰數據塊數據量為c=460，每個數據塊大小為2 KB，在不同數據塊數量進行實驗。

選取不同大小的文件，規定單個數據塊大小為2 KB，文件分塊數量從500 遞增至3 000，分別計算各個方案的標簽生成時間（如圖2 所示）、證據生成時間（如圖3 所示）、驗證證據時間（如圖4 所示）。

圖2 標簽生成時間Fig.2 Time of label generation

圖3 證據生成時間Fig.3 Time of evidence generation

圖4 驗證證據時間Fig.4 Time of verifying evidence

根據實驗對比，本文方案在標簽生成、證據生成和驗證證據3 個過程中，計算開銷均有所下降。在證據生成階段，由于本文計算證據無群元素參與，只涉及整數運算，故時間不到50 ms。其中本文方案與MHT-WiBPA 方案計算開銷最為接近。相較于MHT-WiBPA 方案，在驗證證據開銷接近，但標簽生成時間存在優勢。計算本文方案與MHT-WiBPA 方案在6 次不同挑戰塊數量標簽生成提高效率，從500、1 000、1 500、2 000、2 500、3 000 提高效 率分別約為50.07%、50.06%、50.10%、49.90%、49.50%、50.10%。對6 次提高效率取平均值，計算得本文標簽生成時間比MHT-WiBPA 方案提高約49.96%。相較于其他方案，本文無雙線性對參與，減少了群元素的計算，能夠有效提高效率。

7 結語

針對TPA 存在的惡意欺騙行為，本文利用偽隨機比特生成器并增加用戶與TPA 結果的交互過程，提出一種無雙線性對的可信審計方案。本文方案中，利用偽隨機比特生成器增強了挑戰信息的隨機性和時效性，解決了之前方案TPA 重復利用挑戰信息的缺陷。用戶通過對比TPA 的審計值自行判斷數據完整性，有效抵抗TPA 的惡意審計行為。在方案設計過程中，減少了群元素的計算和無雙線性對參與，利用實驗證明了效率的提高；但由于本文方案標簽需用戶自己生成，對用戶計算能力要求較高，因此，本研究未來工作是構建一個標簽外包計算的安全云審計方案。