支持多用戶操作的外包數(shù)據(jù)庫可驗證方案

玄鵬開， 周福才， 王 強， 陳春雨， 吳淇毓

(東北大學(xué) 軟件學(xué)院 遼寧 沈陽 110169)

0 引言

隨著云計算的不斷發(fā)展，外包數(shù)據(jù)庫[1]為用戶和企業(yè)提供了靈活的數(shù)據(jù)管理服務(wù).然而外包數(shù)據(jù)庫服務(wù)器是不可信的，數(shù)據(jù)擁有者將數(shù)據(jù)存儲在外包數(shù)據(jù)庫服務(wù)器上無法保證數(shù)據(jù)的安全性[2]，即數(shù)據(jù)修改和查詢結(jié)果的安全性.因此支持多用戶操作數(shù)據(jù)的外包數(shù)據(jù)庫可驗證問題值得被關(guān)注.

目前大多數(shù)外包數(shù)據(jù)庫可驗證方案[3-6]只針對數(shù)據(jù)擁有者能夠修改數(shù)據(jù)的場景，而不能滿足多個用戶操作數(shù)據(jù)庫.原因有兩個：第一，現(xiàn)有的方案使用認證數(shù)據(jù)結(jié)構(gòu)[7-8](ADS)支持可驗證計算服務(wù)，多用戶場景會帶來昂貴的計算代價；第二，現(xiàn)有的方案如果被拓展到支持多用戶的安全性保證上，會給數(shù)據(jù)擁有者帶來過重的負載.為了支持多用戶操作的外包數(shù)據(jù)庫的可驗證計算，文獻[9-10]提出了基于MHT (Merkle hash tree)的B樹，但MHT結(jié)構(gòu)主要的問題在于昂貴的維護代價.文獻[11-12]給出了MR 樹(MR-tree)和XB樹(XOR-B tree)的概念，實現(xiàn)了快速查詢的完整性驗證.文獻[13-14]提出利用基于環(huán)簽名的同態(tài)認證方式，當(dāng)數(shù)據(jù)很大時成本很高，其擴展性受到了限制.文獻[15-16]提出利用第三方審計實現(xiàn)多用戶操作數(shù)據(jù)，但效率不高.文獻[17]提出的方案則不能有效地對多用戶進行管理.因此，目前仍然沒有一個非常有效的方案來解決支持多用戶操作的外包數(shù)據(jù)庫可驗證問題.

為解決目前外包數(shù)據(jù)庫可驗證方案不能滿足多用戶操作數(shù)據(jù)的問題，提出了一個支持多用戶操作的外包數(shù)據(jù)庫可驗證方案.利用代理者集中處理所有用戶的請求，實現(xiàn)對多用戶的訪問控制.利用基于身份標(biāo)識的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)對數(shù)據(jù)進行修改，提高計算效率，解決認證數(shù)據(jù)結(jié)構(gòu)帶來的昂貴開銷.利用數(shù)字簽名算法和挑戰(zhàn)應(yīng)答的方式對查詢結(jié)果進行驗證，保證查詢結(jié)果的完整性.

1 預(yù)備知識

1.1 雙線性映射

定義雙線性映射生成算法[18]BilinearMapGen(1λ)→(e,g,G1,G2,p)生成一個雙線性映射[17]e:G1×G1→G2，其中G1和G2是階為p的乘法循環(huán)群，g是群G1的一個生成元，并且e滿足3個屬性：

1) 雙線性.對于任意的P,P1,P2,Q,Q1,Q2∈G1，a,b∈Zp，滿足

e(aP,bQ)=e(P,Q)ab，e(P1+P2,Q)=e(P1,Q)°e(P2,Q)，e(P,Q1+Q2)=e(P,Q1)°e(P,Q2).

2) 非退化性.g1,g2為G1的生成元，即e不會將G1×G1中的所有元素都映射到G2的單位元上.

3) 可計算性.存在有效算法計算任意的e(P,Q).

雙線性映射可根據(jù)超奇異橢圓曲線上的Weil和Tate配對來進行構(gòu)造.

1.2 離散對數(shù)問題

2 問題描述

方案場景模型如圖1所示，系統(tǒng)包括四方實體：數(shù)據(jù)擁有者、普通合法用戶、代理者和外包數(shù)據(jù)庫服務(wù)器.

圖1 方案場景模型Fig.1 Model of scheme

1) 數(shù)據(jù)擁有者擁有原始數(shù)據(jù)，將數(shù)據(jù)上傳至外包數(shù)據(jù)庫服務(wù)器.

2) 普通合法用戶通過代理進行數(shù)據(jù)的查詢和修改.

3) 代理者對用戶的權(quán)限進行驗證，保證為合法的用戶返回正確的查詢結(jié)果.同時與外包數(shù)據(jù)庫服務(wù)器進行交互，發(fā)送查詢和修改請求，對數(shù)據(jù)進行數(shù)字簽名，并利用數(shù)字簽名對服務(wù)器返回的查詢結(jié)果進行挑戰(zhàn)應(yīng)答，從而驗證查詢結(jié)果的正確性和完整性.

4) 外包數(shù)據(jù)庫服務(wù)器為代理者返回查詢數(shù)據(jù)并執(zhí)行數(shù)據(jù)修改操作.

3 方案構(gòu)造

3.1 模型定義

本方案的模型由一個六元組算法{Setup,VerifyUser,Sign,GenChal,GenProof,VerifyProof}組成，各算法的具體描述為：

1)Setup(1λ)→(AK,u,q,H)初始化算法，由代理者執(zhí)行.輸入一個安全參數(shù)λ，輸出算法所需要的全局參數(shù)(AK,u,q,H).

2)VerifyUser(name,SKname)→{0,1}驗證用戶算法，代理者執(zhí)行.將用戶名name和私鑰SKname作為輸入，輸出為0或1，0代表用戶不合法，1代表用戶合法.

3)Sign(v,tid,SK)→σv簽名算法，由代理者執(zhí)行.將數(shù)據(jù)v、數(shù)據(jù)的唯一標(biāo)識tid和私鑰SKname作為輸入，輸出為簽名σv.

4)GenChal(I)→chal挑戰(zhàn)算法，由代理者執(zhí)行.將查詢結(jié)果I作為輸入，輸出為挑戰(zhàn)信息chal.

5)GenProof(chal,I)→φ生成證據(jù)算法，由服務(wù)器執(zhí)行.將挑戰(zhàn)信息chal和查詢結(jié)果I作為輸入，輸出為證據(jù)φ.

6)VerifyProof(φ,δv,I)→{0,1}驗證算法，由代理者執(zhí)行.將證據(jù)φ、簽名σv和查詢結(jié)果I作為輸入，輸出為0或1，0代表驗證未通過，1代表驗證通過.

3.2 安全性定義

在這一節(jié)中，給出了方案的正確性和安全性定義.

3.2.1正確性 設(shè)λ為初始化選定的安全參數(shù)，D為數(shù)據(jù)庫，定義checkUser算法為多項式時間算法，以用戶名name、私鑰SKname為輸入，當(dāng)用戶合法時返回accept，否則返回reject，即checkUser(name,SKname)→{accept,reject}；定義checkProof算法為多項式時間算法，以查詢結(jié)果I、數(shù)據(jù)的簽名δv、證據(jù)φ為輸入，當(dāng)查詢結(jié)果確實為I時，返回accept，否則返回reject.定義支持多用戶操作的外包數(shù)據(jù)庫可驗證方案是正確的，則要求各算法正確執(zhí)行后，算法結(jié)果滿足

其中neg(λ)為可忽略函數(shù).

3.2.2安全性 通過敵手A和挑戰(zhàn)者β的挑戰(zhàn)實驗給出安全性定義.

挑戰(zhàn)實驗：定義敵手A試圖通過以下步驟來偽造一個結(jié)果通過驗證.

1) 挑戰(zhàn)者β執(zhí)行算法Setup，將密鑰AK發(fā)送給A.

2)A向β進行查詢，β向A返回查詢結(jié)果I.

3)A對于特定的查詢輸出一個偽造的查詢結(jié)果I*以及偽造的證據(jù)φ*.

4) 若VerifyProof(φ*,δv,I*)輸出為1，且有I*≠I，則A偽造成功，否則偽造失敗.

支持多用戶操作的外包數(shù)據(jù)庫可驗證方案如果使得任意敵手A不能以不可忽略的概率贏得安全性實驗：

則稱方案滿足安全性.

3.3 方案詳細描述

3.3.1算法詳細描述 在多用戶操作外包數(shù)據(jù)庫場景下，考慮多個用戶通過代理與外包數(shù)據(jù)庫服務(wù)器交互的方式.方案具體算法描述如下.

1)Setup(1λ)→(AK,u,q,H)初始化算法.代理者首先調(diào)用BilinearMapGen算法生成安全參數(shù)AK=(e,g,G1,G2,p)，隨機選取G1中的兩元素u和q，定義單向哈希函數(shù)H:{0,1}*→Zp.

2)VerifyUser(name,SKname)→{0,1}驗證用戶算法.代理者計算mk=gSKname，驗證式(1)是否成立，

mk=pkname.

表1存儲了合法用戶的用戶名及公鑰，若式(1)成立，則代理者接受用戶請求并輸出1，反之，代理者拒絕用戶請求并輸出0.

3)Sign(v,tid,SK)→σv簽名算法.代理者計算插入或更新的數(shù)據(jù)v的簽名σv=(H(tid)·uv)SK.

4)GenChal(I)→chal挑戰(zhàn)算法.設(shè)服務(wù)器返回查詢結(jié)果為I={S1,…,Sc}，代理者為每一個查詢結(jié)果生成隨機數(shù)mi，并輸出挑戰(zhàn)信息chal={(i,mi)}i∈I.

6)VerifyProof(φ,δv,I)→{0,1}驗證算法.代理者利用證據(jù)φ={R,μ,l}、生成的簽名σv、查詢結(jié)果I以及雙線性映射e來驗證式(2)是否成立，

(2)

若式(2)成立，則該算法接受查詢結(jié)果I，輸出1；反之拒絕查詢結(jié)果I，并且輸出0.

3.3.2外包數(shù)據(jù)操作 現(xiàn)存的外包數(shù)據(jù)庫可驗證方案中大多采用認證數(shù)據(jù)結(jié)構(gòu)，在多用戶場景會帶來昂貴的計算代價，尤其是插入或刪除數(shù)據(jù)時需要重新生成所有數(shù)據(jù)的簽名，帶來昂貴的維護代價，因此本方案構(gòu)建了基于身份標(biāo)識的數(shù)據(jù)結(jié)構(gòu)機制(如圖2所示).使用此機制的好處在于插入一個新的數(shù)據(jù)時，不需要重新計算其他數(shù)據(jù)的標(biāo)識，而且數(shù)據(jù)是有序存儲的，如果vi>vj，則tidi>tidj.代理者被允許修改元組但無須改變其他元組的標(biāo)識.這樣就能夠提高多用戶場景下的計算效率，解決認證數(shù)據(jù)結(jié)構(gòu)帶來的昂貴開銷.

圖2 數(shù)據(jù)修改操作Fig.2 Operation of data update

下面給出數(shù)據(jù)修改的幾種形式.

1) 插入操作

如圖2所示，當(dāng)代理者在v1和v2之間插入v′時，代理者向服務(wù)器發(fā)送插入請求，服務(wù)器插入數(shù)據(jù)并返回插入數(shù)據(jù)的前一個元組和后一個元組的唯一標(biāo)識tid1=p和tid2=2p，代理者計算tid′=(tid1+tid2)/2作為v′的tid并通過Sign(v,tid,SK)→σv算法生成v′的簽名，代理者將簽名發(fā)送給服務(wù)器，服務(wù)器完成更新簽名操作即完成了插入操作.

2) 刪除操作

3) 更新操作

4 安全性證明

4.1 正確性證明

本方案是正確的，表示如果方案步驟都是正確執(zhí)行，產(chǎn)生的結(jié)果都是按步驟執(zhí)行得到的，沒有被惡意篡改的，則代理者以極大概率接受結(jié)果，即代理者執(zhí)行驗證算法VerifyProof(φ,δ,I)→1.驗證過程如下.

4.2 安全性證明

本方案滿足不可偽造性，即敵手試圖偽造正確信息，使得代理者通過驗證是不可行的.

在認證授權(quán)即驗證公鑰階段，假設(shè)敵手能夠偽造私鑰SK*，且使得代理者通過驗證，即gSK*≠gSK且VerifyUser(name,SK)→1，說明敵手通過公鑰pk=gSK能夠計算出私鑰SK，與離散對數(shù)問題矛盾，說明敵手偽造私鑰不成立.

保證授權(quán)階段和查詢完整性驗證階段的數(shù)據(jù)無法被偽造證明了本方案具有良好的安全性.

表2 密碼學(xué)操作定義

5 效率分析

5.1 理論分析

(3)

另一方面，代理者接收到證據(jù)φ=(μ,l,R)之后，對應(yīng)的計算代價為

(4)

5.2 實驗分析

基于理論分析對本方案進行實驗，運行實驗程序的計算機配有3.40 GHz主頻的處理器和8 GB內(nèi)存，利用了Java pairing-based cryptography library實現(xiàn)雙線性配對.將安全參數(shù)設(shè)置為160 Bit，查詢數(shù)據(jù)塊數(shù)量從c=0逐漸增加到c=800.

實驗結(jié)果(如圖3所示)表明，代理者和服務(wù)器計算的成本基本相同，代理者執(zhí)行驗證算法，服務(wù)器執(zhí)行計算算法，因此代理者的計算成本應(yīng)該小于等于服務(wù)器的計算成本，因此實驗數(shù)據(jù)表明該算法適合應(yīng)用于多用戶操作的外包數(shù)據(jù)庫可驗證方案中.

通過將本方案與文獻[15]進行對比(如圖4所示)，結(jié)果表明，隨著查詢結(jié)果數(shù)量的增加，本方案具有較高的效率.

圖3 代理者和服務(wù)器的計算時間Fig.3 Computation time of delegator and server

圖4 本方案和文獻[15]的計算時間Fig.4 Computation time of our scheme and reference [15]

6 結(jié)束語

本文針對外包數(shù)據(jù)庫的可驗證方案中只能滿足數(shù)據(jù)擁有者能夠操作數(shù)據(jù)的問題，提出了支持多用戶操作的外包數(shù)據(jù)庫可驗證方案，利用代理支持多用戶管理，基于身份標(biāo)識的數(shù)據(jù)結(jié)構(gòu)動態(tài)修改數(shù)據(jù)，并利用數(shù)字簽名保證了能夠驗證查詢結(jié)果的完整性.效率分析和實驗結(jié)果表明該方案能有效地滿足需求，且具有很高的效率.