全委托的公共可驗證的外包數據庫方案*

周搏洋,陳春雨,王 強,周福才

1(東北大學 軟件學院,遼寧 沈陽 110169)

2(中國科學院 沈陽自動化研究所,遼寧 沈陽 110016)

隨著信息技術的高速發展,智能手機等小型終端設備成為人們生活中不可或缺的一部分.然而,這些終端設備受限于較弱的計算和存儲能力,無法承受龐大的數據量所帶來的昂貴代價.伴隨著云計算[1-3]的高速發展,這些弱計算能力的終端可以將數據外包給云服務提供商[4]管理,即用戶將龐大的數據通過外包的形式讓擁有強大計算能力的云服務器來存儲和計算.通過這種將數據外包的方式,用戶可以隨時隨地發出查詢請求,云服務器則會根據不同的請求執行查詢操作,并將結果返回給用戶.因此,用戶本地只需負責數據傳輸等簡單操作即可,使得其持有輕量級設備即可執行查詢操作.然而,由于用戶喪失了對數據的直接控制[5],云服務器可能會偽造查詢結果來減少響應時間和查詢代價.這種資源租用的模式也帶來了查詢的安全性、正確性和隱私性等諸多問題.在這種情況下,如何使得用戶能夠檢測和驗證查詢結果的完整性,成為了亟待解決的問題.

針對上述問題,Benabbas 等人于2011 年首次提出了可驗證數據庫(verifiable database,簡稱VDB)的概念[6],包括三方實體:數據擁有者、云服務器和用戶.其中:數據擁有者持有數據庫,并將其外包給云服務器存儲;用戶則可根據索引對數據庫進行查詢.由于具有可驗證性,當用戶對索引進行查詢時,云服務器返回查詢結果和一個能夠驗證結果完整性的證據.用戶便可根據該證據來驗證結果是否被篡改,即:得到查詢結果的同時,又能驗證其完整性.而其中需要滿足的一個關鍵條件是:用戶查詢驗證的開銷要遠遠小于其在本地執行查詢計算的開銷,否則便失去了外包的意義.對于持有小型終端設備的數據擁有者而言,由于計算能力的限制,方案能實際應用的關鍵是,其使用輕量級設備在可接受的時間內能完成協議中的步驟.在可驗證數據庫方案中,數據擁有者的工作量主要由外包預處理階段的開銷構成,包括初始化和密鑰生成算法.

近年來,國內外研究人員針對可驗證數據庫做了大量的研究[7-25],其中的很多方案在預處理階段的開銷超出了持有小型終端的數據擁有者的計算能力,以至于無法在現實中使用.如文獻[18]利用向量承諾[26]的信息隱藏性和位置綁定性構建了一個可驗證數據庫方案,但由于向量承諾所需開銷較大,數據擁有者在預處理階段要 執行O(?2)量級的指數運算才能實現初始化和密鑰生成等操作,其中,?為數據庫中數據集的大小.當數據庫很龐 大時,這樣的開銷對于輕量級的設備而言是不可接受的.為解決這一問題,文獻[19]提出了一種分攤模型,將昂貴的預處理開銷分攤到方案后面的查詢步驟中,從而對每次查詢而言“減小”其預處理階段的開銷.然而實際上,對數據擁有者而言,分攤的方式并沒有減少其在整個方案中的工作量.因此,分攤模型依然不滿足數據擁有者的關鍵要求.此外,在當前很多方案中,如文獻[6,21],用戶的驗證過程需要私鑰的參與,也就是說,只有持有私鑰的用戶才能驗證查詢結果的完整性.而在實際場景中,用戶可能希望通過代理來驗證查詢結果,公共可驗證則恰好滿足此要求.在公共可驗證的方案中,任何一個被數據擁有者授權,即持有驗證密鑰的用戶均可以對外包數據庫的查詢結果進行驗證.綜上,在實際的不可信云環境中,如何在實現外包數據庫完整性驗證的前提下,又能夠降低數據擁有者在預處理階段的開銷成為了關鍵,現有方案未能同時解決數據擁有者預處理開銷大及公共可驗證的問題.

針對上述要求,本文提出了一個全委托的公共可驗證的外包數據庫(publicly verifiable outsourced database with full delegation,簡稱PVDFD)模型,該模型具有以下兩個特點.

1) 數據擁有者預處理開銷小.利用可驗證外包模冪運算,將預處理階段大量的模冪運算委托給云服務器,使得數據擁有者與云服務器交互獲得驗證密鑰的工作量小于自己生成驗證密鑰的工作量,同時保證驗證密鑰的保密性.這里的全委托是指除了將數據庫外包給云服務器來檢索外,還將預處理階段生成驗證密鑰的部分運算交給云來完成;

2) 公共可驗證.本方案支持公共可驗證,即任何持有驗證密鑰的用戶均可根據任意用戶發送的查詢請求及云服務器返回的結果和證據進行驗證.

1 相關知識

本文所用符號見表1.

Table 1 Notations表1 符號說明

1.1 雙線性映射

雙線性映射[27-29]是指兩個循環群之間相對應的線性映射關系.G1和G2均為p階乘法循環群,g為群G1的生成元,定義2 個群上的雙線性映射為e:G1×G1→G2,滿足以下性質.

(1) 雙線性:對于任意的a,b∈Zp和u,v∈G1,均滿足e(ua,vb)=e(u,v)ab;

(3) 可計算性:對于任意的u,v∈G1,都存在有效的算法計算出e(u,v).

1.2 雙線性Diffie-Hellman指數難題

雙線性Diffie-Hellman 指數難題(bilinear diffie-hellman exponent,簡稱BDHE)[30]:G1和G2均為p階乘法循環群,g,u為群G1的兩個生成元,群上的雙線性映射為e:G1×G1→G2.隨機選擇α∈Zp,給定一個元組(U0,U1,…,Un,Un+2,…,U2n),使得對于任意的i∈{0,…,n,n+2,…,2n}均滿足.計算是困難的.

2 PVDFD 模型

本節主要介紹了全委托的公共可驗證的外包數據庫PVDFD 模型.首先給出了模型的架構及交互流程,然后給出了模型的形式化定義和安全性定義.

2.1 PVDFD模型架構

全委托的公共可驗證的外包數據庫模型PVDFD 中包含4 方實體,分別是可信第三方、數據擁有者、云服務器以及授權用戶,其中,云服務器是不可信的,其他實體是可信的.模型架構如圖1 所示.

Fig.1 Architecture of PVDFD圖1 PVDFD 模型架構

可信第三方首先執行初始化算法生成公共參數,并將其分發給數據擁有者、授權的用戶以及云服務器.數據擁有者在外包數據庫之前,利用可信第三方生成的公共參數執行密鑰生成算法生成密鑰,包括數據庫的查詢密鑰、驗證密鑰的計算密鑰、驗證密鑰的恢復密鑰和驗證密鑰的檢索密鑰,并將驗證密鑰的計算密鑰發送給云服務器.云服務器執行驗證密鑰計算算法,返回編碼后的驗證密鑰及相應的證據.數據擁有者利用驗證密鑰恢復算法驗證,在驗證通過的情況下完成驗證密鑰的恢復操作,將其發送給授權的用戶,并將數據庫的查詢密鑰發給云服務器.接著,授權的用戶便可以向云服務器發送查詢索引.由于云服務器是不可信的,其執行查詢算法返回結果及證據,授權的用戶執行驗證算法實現驗證操作,若算法輸出1,則表示云服務器執行了正確的查詢.由于持有驗證密鑰的用戶均可對查詢結果進行驗證,因此該方案支持公共可驗證.

注:本文中的數據庫為NoSQL 類型,表示為DB={(i,vi)|i∈{0,…,n}},數據庫中數據集大小為?=n+1.

2.2 PVDFD的形式化定義

該模型可由概率多項式時間算法六元組PVDFD=(Setup,KeyGen,VKeval,VKrec,Query,Verify)表示,其中每項都代表一個多項式時間算法.6 個算法具體描述如下.

1)Setup(1λ)→pp:初始化算法.初始化算法由可信第三方執行,算法根據輸入的安全參數λ生成公共參數pp,并發送給方案中的其他實體;

2)KeyGen(pp,DB)→(EKDB,EKpp,VKpp,RKpp):密鑰生成算法.密鑰生成算法由數據擁有者執行,算法輸入數據庫DB和公共參數pp,生成數據庫的查詢密鑰EKDB、驗證密鑰的計算密鑰EKpp、驗證密鑰的恢復密鑰VKpp和驗證密鑰的檢索密鑰RKpp.其中,EKDB用來查詢數據庫,EKpp,VKpp,RKpp分別用來計算、恢復和檢索數據庫的驗證密鑰VKDB(數據庫的驗證密鑰VKDB在下文驗證密鑰恢復算法VKrec中定義);

3)VKeval(pp,EKpp) →:驗證密鑰計算算法.驗證密鑰計算算法由云服務器執行,算法輸入公共參數pp和驗證密鑰的計算密鑰EKpp,輸出編碼后的數據庫驗證密鑰和相關的證據;

5)Query(EKDB,x)→(y,πy):查詢算法.查詢算法由云服務器執行,算法輸入數據庫的查詢密鑰EKDB及授權 用戶發來的查詢索引x∈domain(DB),輸出對應的查詢結果和證據對(y,πy);

6)Verify(pp,VKDB,x,y,πy)→{0,1}:驗證算法.驗證算法由持有數據庫驗證密鑰的用戶執行,算法輸入公共參數pp、驗證密鑰VKDB、查詢索引x和云服務器返回的查詢結果y的證據πy.驗證通過輸出1,否則 輸出0.

2.3 PVDFD的正確性及安全性定義

2.3.1 正確性

PVDFD 方案的正確性,即:若模型中的每個算法都被正確地執行,則永遠不會拒絕正確的結果.其形式化定義如下,其中,negl(λ)為關于安全參數λ的可忽略函數.

2.3.2 安全性

1) 驗證密鑰的機密性

驗證密鑰的機密性是針對不可信的云服務器而言的.簡單來說,云服務器無法獲取外包數據庫的驗證密鑰.下面通過安全性實驗來定義該模型中的驗證密鑰的機密性.定義敵手A(·)=(A0,A1),其中,A0,A1為兩個概率多項 式時間模擬器,設計安全實驗如下:

對于任意的λ∈N,定義敵手A在PVDFD 中的優勢如下:

定義1.若,,則PVDFD 方案實現了驗證密鑰的機密性.其中,negl(λ)為可忽略函數.

2) 驗證密鑰的不可偽造性

驗證密鑰的不可偽造性是針對不可信的云服務器而言的,即,云服務器偽造一個驗證密鑰始終不能通過數 據擁有者的驗證.下面通過安全性實驗來定義該模型中的驗證密鑰的不可偽造性.定義敵手A(·)=(A0,A1,A2),其中,A0,A1,A2為3 個概率多項式時間模擬器,設計安全實驗如下:

對于任意的λ∈N,定義敵手A在PVDFD 中的優勢如下:

定義2.若,則PVDFD 方案實現了驗證密鑰的不可偽造性.其中,negl(λ)為可忽 略函數.

3) 查詢結果的不可偽造性

查詢結果的不可偽造性是針對不可信的云服務器而言的,即云服務器偽造一個查詢結果和證據始終不能 通過授權用戶的驗證.下面通過安全性實驗來定義該模型中的查詢結果的不可偽造性.定義敵手A(·)=(A0,A1),其中,A0,A1為兩個概率多項式時間模擬器,設計安全實驗如下:

對于任意的λ∈N,定義敵手A在PVDFD 中的優勢如下:

定義3.若(PVDFD,DB,λ) ≤negl(λ),則PVDFD 方案實現了結果的不可偽造性.其中,negl(λ)為可忽 略函數.

3 PVDFD 方案的描述

本節首先介紹了方案構建中用到的一個子協議MExp[31],然后詳細介紹了PVDFD 方案中的各個算法,并給 出了正確性證明.由于本方案的安全性歸約為BDHE 難題,在此難題中需要O(?)量級的冪運算,因此數據擁有者 在預處理階段要生成驗證密鑰所需的開銷很大.而MExp協議為可驗證的外包模冪運算協議,數據擁有者可以利用此協議,將這些冪運算外包給云服務器計算,同時又能驗證結果的完整性.在此過程中需要注意的是:云服務器不能獲取驗證密鑰的信息,否則,其可以偽造結果和證據而不被驗證者察覺.

3.1 子協議:可驗證外包模冪運算MExp

PVDFD 方案在預處理階段的云服務器和數據擁有者交互生成驗證密鑰的過程中,用到了可驗證外包模冪 運算協議MExp[31]作為子協議.為簡單起見,令p為大素數,ui∈Zp作為底,ci∈Zp作為冪,其中,i∈{0,…,n}.MExp協 議由Ding 等人于2017 年提出,協議中存在兩方實體:誠實的客戶端和不可信的服務器.客戶端希望將乘法模冪 計算外包給計算能力強但不可信的服務器來計算,而客戶端能夠驗證結果的完整性.簡單地提 取該協議中的系統模型,表示為以下3 個步驟,其中均省略modp操作.

1)ME.Setup(u0,…,un,c0,…,cn,p)→(ME.EK,ME.VK)

② 計算bi和t0h0,使其滿足k2=k4(c0+c1+…+cn)-k0t0h0,其中,i∈{0,…,n};

③ 計算wi=ui/v0,其中,i∈{0,…,n},并生成邏輯劃分如下:

④ 選擇隨機數r∈Zp,計算,其中,i∈{0,…,n}.將進行邏輯劃分如下:

⑤ 計算滿足k3=k5r(c0+c1+…+cn)-k1t1h1和rci=+t1h1的bi′和t1h1,其中,i∈{0,…,n};

2)ME.Compute(MExp.EK)→{ME.σy,ME.πy}

此步驟由服務器生成編碼后的結果ME.σy和證據ME.πy.具體如下.

① 將ME.EK分解為和;

② 對于i∈{0,…,n},計算和;

④ 返回結果和證據,分別為ME.σy=和ME.πy=.

3)ME.Verify(ME.VK,ME.σy,ME.πy)→{ME,y,⊥}

此步驟為客戶端驗證計算結果的正確性,具體如下.

① 將ME.VK分解為,ME.σy分解為 {,ME.πy分解為;

② 計算是否滿足等式:

若不滿足,則終止協議并輸出⊥;否則,恢復計算結果ME.y=.

MExp協議有以下的性質.

1) 正確性:若服務器是誠實地遵循上述過程,協議可確?？蛻舳丝偸强梢暂敵鯩E.y;

2) 零知識性:協議可確保不遵守協議的惡意服務器無法獲得任何秘密輸入和輸出(運算結果)的信息;

3) α-可檢查性:協議確保檢測到惡意服務器返回的錯誤結果的概率不小于α.

3.2 方案詳細設計

本節首先詳細介紹了PVDFD 方案中各個算法的具體構造,然后給出了正確性證明.下面分別進行描述.

1) 初始化算法.

該算法用于為方案中的所有實體生成公共參數.算法的主要步驟如下.

① 給定安全參數λ,可信第三方首先選擇階為p∈poly(λ)的兩個群G1和G2滿足雙線性映射e:G1×G1→G2;

② 隨機選取兩個生成元g,u∈G1;

③ 令公共參數pp=(p,g,u,G1,G2,e)并發送給云服務器、數據擁有者和授權用戶.

2) 密鑰生成算法.

該算法用于生成方案所需密鑰.算法的主要步驟如下.

① 數據庫DB={(i,vi)|i∈{0,…,n}},其中,數據集大小為?=n+1.數據擁有者先將數據庫DB插值為多項式的形式,使得對于任意的i∈{0,…,n},均滿足F(i)=vi.提取多項式F的系數集合為C={c0,c1,…,cn};

② 選擇兩個隨機數γ,k∈Zp.令驗證密鑰的檢索密鑰RKpp=k,數據庫的查詢密鑰EKDB=(C,γ);

③ 選擇隨機數α∈Zp作為偽隨機函數(PRF)的密鑰,并建立偽隨機函數PRF(α,t)為:;

④ 記j為模冪操作的索引,對于?j∈[2n+2]{n+1},執行MExp協議的初始化算法ME.Setup(u,αj+1,p)生成模冪計算求值密鑰ME.EK[j]和驗證密鑰ME.VK[j].其中,u和αj+1分別為底和冪.當j=2n+2 時,執行算法ME.Setup(F,C,p)生成求值密鑰ME.EK[j]和驗證密鑰ME.VK[j],其中,F={PRF(α,i)|i=0,1,…,n}為底;

⑤ 令驗證密鑰的恢復密鑰VKpp={ME.VK[j]|0≤j≤2n+2∧j≠n+1}、計算密鑰EKpp={ME.EK[j]|0≤j≤2n+2∧j≠n+1}.其中,

⑥ 最終,數據擁有者保持PRF密鑰α,EKDB,VKpp和RKpp私有,并將EKpp發送給云服務器.值得注意的是:數 據擁有者在執行算法ME.Setup時只選擇一次隨機的六元組,在后面的操作中都使用該六元組.也就是說:對于所有的i∈[5]和j∈[2n+2]{n+1},均滿足kj,i=k0,i.

3) 驗證密鑰計算算法.

該算法根據接收到的驗證密鑰的計算密鑰來計算編碼后的驗證密鑰.算法的主要步驟如下.

① 云服務器收到驗證密鑰的計算密鑰EKpp后,將其分解為{ME.EK[j]|0≤j≤2n+2∧j≠n+1};

② 云服務器執行算法ME.Compute(ME.EK[j])生成編碼后的結果ME.σy[j]和證據ME.πy[j];

4) 驗證密鑰恢復算法.

該算法用于對云服務器返回的結果進行驗證,并恢復出數據庫的驗證密鑰.算法的主要步驟如下.

② 執行算法ME.Verify(ME.VK[j],ME.σy[j],ME.πy[j]).

③ 當j∈[2n+2]{n+1}時,數據擁有者驗證是否滿足如下等式:

若不滿足,則輸出⊥并丟棄;否則,令:

當j=2n+2 時,驗證是否滿足等式:

若不滿足,則輸出⊥并丟棄;否則,令:

④ 數據擁有者將{Uj}j∈[2n+2]{n+1}添加到數據庫的查詢密鑰EKDB中,并將更新后的該值發送給云服務器.此時,EKDB={C,γ,{Uj}j∈[2n+2]{n+1}}.

⑤ 數據擁有者最終令VKDB={σDB,{Uj}j∈[2n+2]{n+1},RKpp,PRF(α,0)},并通過安全的信道發送給授權的用戶.

5) 查詢算法.

該算法用于查詢數據庫即執行多項式求值計算.算法的主要步驟如下.

① 當云服務器收到數據擁有者發來的EKDB以及授權用戶發來的查詢索引x后,首先將EKDB分解為{C,γ,{Uj}j∈[2n+2]{n+1}},并令X={1,x,x2,…,xn};

④ 將結果y和證據πy發回給授權的用戶.

6) 驗證算法.

該算法用于對云服務器返回的查詢結果進行驗證.算法的主要步驟如下.

① 授權用戶收到結果y和證據πy后,首先將VKDB分解為{σDB,{Uj}j∈[2n+2]{n+1},RKpp,PRF(α,0)};

③ 驗證以下等式是否成立:

若成立,則接受并輸出1;否則,拒絕并輸出0.

注:本方案亦可直接用于外包多項式的可驗證計算,此時,多項式的更新效率為常量級.假設F為n階的原外包多項式,F′為系數更新后的外包多項式,σF對應上文中的σDB,VKF對應上文中的VKDB表示外包多項式的驗 證密鑰,upd為更新信息.具體更新算法為

該算法在保證多項式的階不變的情況下,可高效地對多項式的任意系數進行更新.算法的主要步驟如下.

① 假設更新的系數位置為i∈{0,…,n},令upd=.其中,ci為系數更改前的值,為更改后的值;

③ 外包多項式的用戶將upd發送給云服務器,并將更新后的驗證密鑰VKF′重新發送給授權用戶,即可實 現外包多項式的更新.

3.3 正確性證明

本節將基于公式(1)～公式(3)的正確性來證明整個方案的正確性.公式(1)、公式(2)可根據文獻[31]來證明.而對于公式(3),其等式的左邊(left-hand side,簡稱LHS)有:

又由公式(3)等式的右邊(right-hand side,簡稱RHS)可知:

即LHS=RHS,公式(3)成立.因此,若方案步驟都是正確執行,產生的結果都是未被篡改的,則結果和(y,πy)總能分別通過數據擁有者及授權用戶的驗證.

4 安全性證明

定理1.若存在一個概率多項式時間的敵手A,滿足,則他可以創建一個有效的算法B來打破可驗證外包模冪計算的零知識性.

證明:根據文獻[31],若敵手A已知公共參數信息,且能夠構建一個算法B區分計算結果和哪一個輸入相關,即打破了可驗證外包模冪計算的零知識性.

敵手A的挑戰過程如下:已知公共參數為pp,敵手通過模擬器隨機構造兩個數據庫的計算密鑰和,并將其發送給挑戰者;挑戰者隨機選擇其中一個密鑰,調用算法執行模冪運算,并將結果和證據返回給敵手;敵手收到結果和證據后,利用算法B猜測出b的值,即區分出計算結果 與哪一個計算請求相關.由此可知,敵手使用了有效的算法打破了可驗證外包模冪計算的零知識性.

定理2.若存在一個概率多項式時間的敵手A,滿足,則他可以創建一個有效的算法B來打破可驗證外包模冪計算的α-可檢查性.

證明:根據文獻[31],若敵手A偽造了結果和證據,分別將其中的R0和R1替換為和,且滿足,則偽造成功.敵手A利用偽造信息和真實的值可以構建一個算法B來打破可 驗證外包模冪計算的α-可檢查性.

具體構建過程如下:敵手A隨機選擇值R滿足.令,根據等式:

定理3.若存在一個概率多項式時間的敵手A,滿足,則他可以創建一個有效的算法B來打破BDHE 難題.

證明:查詢索引x*對應的值為y*,敵手A偽造了該值和證據,分別為.若偽造的值滿足且=1,則偽造成功.敵手A利用偽造信息和真實的查詢結果及證據可以構建一個算法B來打破BDHE 難題.

具體構建過程如下:令c=,即真值與偽造值的差值.由于驗證通過,則一定滿足以下等式:

根據公式(4)和公式(5),可以推出:

由公式(6)可知,敵手使用了有效的算法打破了BDHE 難題.

5 分 析

5.1 方案對比

本節將本方案PVDFD 與Miao 等人的方案[24](MVDB)、Chen 等人的方案[18](CVDB)、Benabbas 等人的方案[6](BVDB)、Backes 等人的方案[21](BFVDB)和Wang 等人的方案[23](WVDB)進行了功能上的對比分析.主要比較了方案是否需要較大的預處理開銷、是否支持公共可驗證和計算難題的假設.結果見表2.

Table 2 Comparison among six schemes表2 方案對比

從表2 中可以看出,MVDB 方案、CVDB 方案和BVDB 方案在預處理階段均需要數據擁有者執行昂貴的計算.這對于持有小型終端的數據擁有者而言,代價過于昂貴.而BFVDB 方案和WVDB 方案雖不存在預處理開銷大的問題,卻不能實現公共可驗證,BVDB 方案同樣存在不支持公共可驗證的問題.本文的PVDFD 方案通過采用將預處理開銷委托給云計算的方式,不需要數據擁有者過大的預處理開銷,且支持公共可驗證.

5.2 復雜度分析

BVDB 方案、BFVDB 方案和WVDB 方案不能實現公共可驗證,本文的PVDFD 方案在功能方面優于三者,因此在本節中不做對比.本節主要對比了本方案和CVDB 方案、MVDB 方案及不進行全委托計算的方案(without full delegation scheme)分別在預處理階段、查詢階段和驗證階段的計算復雜度.其中,不進行全委托計算的方案是指將本方案中由云服務器和數據擁有者交互生成驗證密鑰的過程由數據擁有者獨立完成,即數據擁有者獨立計算驗證密鑰,而其他步驟不改變所形成的方案.由于插值操作、雙線性映射和指數運算的計算開銷較大,因此忽略其他的運算,僅對比3 種方案中的插值操作開銷、雙線性映射開銷和指數運算開銷,結果見表 3.在表3 中,?,Interplt,Pairing,Exp分別代表數據庫中的數據集大小、插值操作的開銷、雙線性映射的開銷以及 指數運算的開銷.

Table 3 Comparison of computation cost表3 計算復雜度對比

PVDFD 方案在預處理階段,數據擁有者首先需要將數據庫進行插值操作,并執行6 次指數運算生成Mexp協議中6 個隱藏的對;其次執行VKrec算法,執行2?次指數運算以恢復驗證密鑰.因此,預處理階段數據擁有者共需(2?+6)次指數運算和一次插值操作.若不進行全委托計算,在本地執行全部的密鑰生成操作則需要進行一次插值操作及3?次指數運算.而CVDB 方案基于向量承諾實現,MVDB 方案基于向量承諾和布隆過濾器實現,二者在預處理階段所需代價均為O(?2).昂貴的平方量級的指數運算操作遠遠超出了數據擁有者的計算能力,尤其是 當數據庫中的數據集較大時,其開銷是不可接受的.顯然,本文的PVDFD 方案在預處理階段的工作量最低,證明了全委托方案的優越性.而在用戶驗證階段,CVDB 方案和MVDB 方案的開銷較小,為常量級;本方案和不進行全委托的方案的開銷均要執行與數據庫大小呈線性量級的指數運算,但線性量級的開銷是用戶可以接受的.CVDB 方案和MVDB 方案雖然在驗證過程中開銷較小,但在預處理階段開銷過大,使其仍無法實際應用.此外,由于云服務器可以認為是擁有海量計算資源的實體,擁有強大的計算能力.在PVDFD 方案中,云服務器執行的任務量最大,是對其強大計算能力的充分利用.CVDB 方案、MVDB 方案和不進行全委托計算的方案對云服務器的利用較小,不能使其充分發揮作用以減小數據擁有者本地的開銷.

5.3 效率分析

本節通過實驗對比分析了本方案與CVDB 方案、MVDB 方案及不進行全委托計算(without FD scheme,即第5.2 節所述數據擁有者獨立計算驗證密鑰形成的方案)這3 種方案在預處理階段、驗證密鑰生成過程、驗證階段和查詢階段的開銷.實驗采用PBC 庫實現雙線性群的初始化,采用NTL 庫實現數據庫的插值操作.運行實驗程序的計算機配置為:Intel(R) Core(TM) i7-6700 CPU@3.40GHz 3.41GHz 主頻的處理器和8GB 內存.

1) 比較本方案與CVDB 方案、MVDB 方案及不進行全委托計算的方案在預處理階段的時間開銷.

預處理階段包括初始化操作和密鑰生成操作.實驗結果如圖2 所示,其中,橫坐標表示外包數據庫中的數據集大小,縱坐標表示3 種方案在預處理階段的執行時間.實驗結果表明:本方案和不進行全委托計算的方案在預處理階段時間開銷較低;且當數據集越大時,兩方案的時間開銷越接近.這是由于數據集越大,數據庫插值的時間則越長,指數運算的時間可以被忽略.而MVDB 方案和CVDB 方案的時間開銷均遠遠高于二者,在數據集大小為10 000 時的開銷甚至達到了約100 000s.其原因是MVDB 方案和CVDB 方案在預處理階段需要過于昂貴的平方量級的指數運算操作,另兩方案則只需線性量級的指數運算即可完成.當數據集較大時,MVDB 方案和CVDB 方案的時間開銷是持有小型終端的數據擁有者所不能接受的.

2) 比較本方案和不進行全委托計算的方案生成驗證密鑰的時間開銷.

實驗結果如圖3 所示,其中,橫坐標表示外包數據庫中的數據集大小,縱坐標表示兩種方案生成驗證密鑰的執行時間.實驗結果表明:兩方案的執行時間幾乎都與數據集大小呈線性關系,而本方案生成驗證密鑰所需時間 更低.由上文,要計算驗證密鑰中的σDB和{Uj},不進行全委托計算的方案需要進行3?次指數運算,?為數據庫大小.而本方案執行驗證密鑰恢復算法,進行2?次指數運算即可求得驗證密鑰.因此,本方案的開銷更小,尤其當數 據集大小較大時,優勢更加明顯.

Fig.2 Comparison of time cost in pre phase圖2 預處理階段開銷對比圖

Fig.3 Comparison of time cost in VKEval phase圖3 計算驗證密鑰的開銷對比圖

3) 比較本方案與CVDB 方案、MVDB 方案及不進行全委托計算的方案在驗證階段的時間開銷.

實驗結果如圖4 所示,其中,橫坐標表示外包數據庫中的數據集大小,縱坐標表示3 種方案在用戶驗證階段的執行時間.實驗結果表明:隨著數據集大小的增長,本方案和不進行全委托計算的方案所需的時間開銷隨之線性增長;而CVDB 方案和MVDB 方案中驗證操作的時間開銷則為常量級,獨立于數據集的大小.這是由于本方案為了實現公共可驗證性,使得用戶執行線性量級的指數運算操作.但由圖4 中可看出:當數據集大小為10 000時,時間開銷約為14s,這對于用戶而言是完全可以接受的.而CVDB 方案和MVDB 方案由于將大部分開銷都放在預處理階段執行,因此在驗證階段開銷較小;然而其在預處理操作中過于昂貴的開銷,使其難以實際應用.

4) 比較本方案與CVDB 方案、MVDB 方案及不進行全委托計算的方案在查詢階段的時間開銷.

實驗結果如圖5 所示,橫坐標表示外包數據庫中的數據集大小,縱坐標表示3 種方案在云服務器查詢階段的執行時間.實驗結果表明:CVDB 方案和MVDB 方案對云服務器的利用率最低,其次是不進行全委托計算的方案,而本方案對云服務器的利用率最高.這是由于CVDB 方案和MVDB 方案將大部分的開銷放在了預處理階段,數據擁有者執行昂貴的預處理操作,使得其查詢和驗證的開銷較小.然而,云服務器的計算能力很強,數據擁有者的計算能力卻是有限的,僅僅使用云服務器進行數據庫的查詢操作,是對其計算能力的浪費.此外,持有小型終端的數據擁有者執行如此昂貴的預處理開銷是不現實的.因此,CVDB 和MVDB 兩方案沒有利用好云服務器的特性減小數據擁有者的開銷.而不進行全委托的計算方案同樣沒有利用好云服務器的計算能力.本文把預處理階段全委托給云服務器計算,合理地利用了云服務器強大的計算能力,減少了數據擁有者在預處理階段的時間開銷,雖然使得用戶的驗證開銷略有增長,但該增長是在用戶接受范圍內的,這使得本方案更適于實際應用.

Fig.4 Comparison of time cost in verify phase圖4 驗證階段開銷對比圖

Fig.5 Comparison of time cost in query phase圖5 查詢階段開銷對比圖

以上實驗結果表明:PVDFD 方案很好地利用了云服務器具有強大計算能力的特性,使得數據擁有者在預處理操作的開銷上有很大的優勢;尤其當數據集較大時,優勢更加明顯.其原因是:在本方案中,數據擁有者將預處理操作全委托給云計算,而本地只需執行密鑰生成操作及驗證密鑰恢復操作即可,兩個操作的執行時間之和仍小于對比文獻及不進行全委托計算的方案執行預處理操作的時間,因此本方案實用性更強.

6 總 結

本文提出了一個全委托的公共可驗證的外包數據庫方案PVDFD.通過將預處理階段的工作量委托給云服務器計算,減少了數據擁有者的計算成本,且云無法獲得任何與驗證密鑰相關的信息.此外,本方案支持公共可驗證,使得任何持有驗證密鑰的授權用戶均可向云服務器發出查詢請求,并可以根據云服務器返回的計算結果和證據進行驗證,實現了公共可驗證.此外,本方案亦可用于外包多項式的可驗證計算,且其更新的代價為常量級.本文還證明了PVDFD 方案的正確性和安全性.最后,通過理論和實驗分析表明:PVDFD 方案解決了可驗證數據庫方案中,數據擁有者預處理階段開銷過高及不能公共可驗證的問題.