玄鵬開， 周福才， 王 強(qiáng)， 陳春雨， 吳淇毓

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

0 引言

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

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

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

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

1.1 雙線性映射

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

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不會(huì)將G1×G1中的所有元素都映射到G2的單位元上.

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

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

1.2 離散對數(shù)問題

2 問題描述

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

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

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

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

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

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

3 方案構(gòu)造

3.1 模型定義

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

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

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

3)Sign(v,tid,SK)→σv簽名算法，由代理者執(zhí)行.將數(shù)據(jù)v、數(shù)據(jù)的唯一標(biāo)識(shí)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}驗(yàn)證算法，由代理者執(zhí)行.將證據(jù)φ、簽名σv和查詢結(jié)果I作為輸入，輸出為0或1，0代表驗(yàn)證未通過，1代表驗(yàn)證通過.

3.2 安全性定義

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

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

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

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

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

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

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

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

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

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

則稱方案滿足安全性.

3.3 方案詳細(xì)描述

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

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

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

mk=pkname.

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

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

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

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

(2)

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

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

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

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

1) 插入操作

如圖2所示，當(dāng)代理者在v1和v2之間插入v′時(shí)，代理者向服務(wù)器發(fā)送插入請求，服務(wù)器插入數(shù)據(jù)并返回插入數(shù)據(jù)的前一個(gè)元組和后一個(gè)元組的唯一標(biāo)識(shí)tid1=p和tid2=2p，代理者計(jì)算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í)行驗(yàn)證算法VerifyProof(φ,δ,I)→1.驗(yàn)證過程如下.

4.2 安全性證明

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

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

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

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

5 效率分析

5.1 理論分析

(3)

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

(4)

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

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

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

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

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

圖4 本方案和文獻(xiàn)[15]的計(jì)算時(shí)間Fig.4 Computation time of our scheme and reference [15]

6 結(jié)束語

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