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

(東北大學(xué)軟件學(xué)院 沈陽(yáng) 110169) (wangq3635@126.com)

隨著云計(jì)算的發(fā)展，數(shù)據(jù)庫(kù)外包服務(wù)[1]成為近些年新興的一種應(yīng)用模式.越來(lái)越多資源受限的客戶或企業(yè)為了節(jié)約硬件存儲(chǔ)資源和管理成本，取消自己的數(shù)據(jù)中心，將數(shù)據(jù)庫(kù)外包給專業(yè)的數(shù)據(jù)庫(kù)服務(wù)提供商[2]進(jìn)行管理和維護(hù).但是數(shù)據(jù)外包后，數(shù)據(jù)擁有者喪失了對(duì)數(shù)據(jù)的直接控制[3]，云服務(wù)器可能會(huì)篡改數(shù)據(jù)庫(kù)的內(nèi)容或偽造查詢結(jié)果來(lái)減少響應(yīng)的時(shí)間和計(jì)算代價(jià)，因此研究外包數(shù)據(jù)庫(kù)查詢結(jié)果的完整性問(wèn)題具有重要意義.

目前，為解決外包數(shù)據(jù)庫(kù)的查詢結(jié)果完整性驗(yàn)證問(wèn)題，國(guó)內(nèi)外學(xué)者展開了大量的研究，主要分為3類：基于數(shù)字簽名的[4-7]、基于認(rèn)證數(shù)據(jù)結(jié)構(gòu)的[8-16]、基于可驗(yàn)證計(jì)算的[17-25].1)使用數(shù)字簽名技術(shù)的方法[4-7]中，數(shù)據(jù)擁有者需要對(duì)外包數(shù)據(jù)庫(kù)中的每個(gè)元組進(jìn)行簽名，客戶查詢時(shí)，服務(wù)器需返回查詢結(jié)果和查詢結(jié)果中每個(gè)元組所對(duì)應(yīng)的簽名.但是該類方法存在的問(wèn)題是驗(yàn)證和更新的代價(jià)較高，且只支持范圍查詢.2)基于認(rèn)證數(shù)據(jù)結(jié)構(gòu)的方法是對(duì)基于數(shù)字簽名方法的改進(jìn)，通常是基于認(rèn)證樹和累加器的.基于認(rèn)證樹[8,11-12,14-15]不需要對(duì)每一條元組進(jìn)行簽名，而是先對(duì)元組排序，再使用Hash函數(shù)計(jì)算出樹中每個(gè)節(jié)點(diǎn)的Hash值，最終對(duì)樹的根節(jié)點(diǎn)簽名，客戶使用認(rèn)證路徑和根節(jié)點(diǎn)簽名值進(jìn)行驗(yàn)證.但是該類方法存在的問(wèn)題是由于葉子節(jié)點(diǎn)是排序好的元組的Hash值，任何一次更新都可能破壞已有認(rèn)證數(shù)據(jù)結(jié)構(gòu)，更新代價(jià)較高.認(rèn)證路徑隨元組的數(shù)量呈對(duì)數(shù)級(jí)增長(zhǎng)，只支持范圍和元素隸屬關(guān)系的查詢.另一種基于累加器的[9-10,13]，只支持集合交集、并集、差集及元素隸屬關(guān)系的查詢，不支持求和、計(jì)數(shù)、范圍，最大值和最小值查詢.此外，文獻(xiàn)[16]提出了一種基于可翻轉(zhuǎn)的布隆過(guò)濾器的外包數(shù)據(jù)庫(kù)驗(yàn)證方案，該方案雖解決了數(shù)據(jù)更新操作時(shí)額外的計(jì)算開銷，但布隆過(guò)濾器存在誤算率，會(huì)導(dǎo)致查詢結(jié)果的精準(zhǔn)性.3)基于可驗(yàn)證計(jì)算的方法分為2類：①針對(duì)特定查詢類型的[17-19]；②針對(duì)通用方案的[20-25].前者的效率優(yōu)于后者，但是查詢類型單一.例如Papadopoulos等人[19]基于雙線性映射累加器提出了支持多維范圍查詢的完整性驗(yàn)證的方案，該方案只支持多維范圍查詢且不支持高效地更新數(shù)據(jù).針對(duì)通用方案的可分為2類：基于電路的[20-21]和基于RAM(random access memory)模型的[22-25].兩者均是將外包庫(kù)編譯到程序中(表示成一個(gè)布爾/算數(shù)電路，或者是基于RAM模型進(jìn)行計(jì)算)，在編譯好的程序中輸入查詢語(yǔ)句，返回與之對(duì)應(yīng)的結(jié)果.這2種方法計(jì)算代價(jià)高并不實(shí)用.基于電路的方法效率低，程序中電路的大小至少與數(shù)據(jù)庫(kù)本身一樣大，不支持嵌套查詢，每進(jìn)行更新操作都需要重新編碼.基于RAM模型支持全部查詢操作，但是編碼難度較高和性能較差.

綜上所述，現(xiàn)有的方案存在的問(wèn)題：1)查詢類型單一不支持全操作；2)證據(jù)隨查詢結(jié)果呈線性或?qū)?shù)增長(zhǎng)；3)驗(yàn)證和更新代價(jià)較高；4)方案的整體效率低下難以應(yīng)用.

針對(duì)上述問(wèn)題，本文提出了一個(gè)基于雙線性映射的支持全操作的公共可驗(yàn)證外包數(shù)據(jù)庫(kù)(publicly verifiable database model with full operations based on bilinear map, BMPVDB)模型，該模型具有3個(gè)特點(diǎn)：

1) 功能全面(全操作).該模型支持的查詢操作全面，包含了交集、并集、補(bǔ)集等各種集合操作，求和、計(jì)數(shù)、最小值、最大值、范圍查詢以及嵌套查詢操作.

2) 高效.驗(yàn)證代價(jià)為常數(shù)級(jí)，獨(dú)立于外包數(shù)據(jù)庫(kù)的大小和查詢的中間結(jié)果.證據(jù)大小只依賴于查詢語(yǔ)句分解為單個(gè)查詢語(yǔ)句的數(shù)量，不依賴于外包數(shù)據(jù)庫(kù)和中間結(jié)果的大小.更新的代價(jià)為常數(shù)級(jí)，不依賴于外包數(shù)據(jù)庫(kù)和中間結(jié)果的大小.

3) 公共可驗(yàn)證、公共可更新.任何客戶擁有公鑰和摘要都能對(duì)查詢結(jié)果進(jìn)行完整性驗(yàn)證.任何一個(gè)被數(shù)據(jù)擁有者授權(quán)的客戶無(wú)需私鑰參與就能對(duì)外包的數(shù)據(jù)進(jìn)行更新.

1 相關(guān)知識(shí)

1.1 雙線性映射

雙線性映射指的是2個(gè)循環(huán)群之間相對(duì)應(yīng)的線性映射關(guān)系.定義一個(gè)概率多項(xiàng)式時(shí)間雙線性映射生成算法(e,g,G,GT,p)←BMGen(1λ)生成雙線性映射e:G×G→GT，其中p為λ比特的素?cái)?shù)，G和GT均為p階乘法循環(huán)群，g為群G的生成元，雙線性映射e滿足3個(gè)性質(zhì)：

1) 雙線性.對(duì)于任意的a,b∈p和P,Q∈G，均滿足e(Pa,Qb)=e(P,Q)ab.

2) 非退化性.e(g,g)≠1GT，其中1GT為群GT的單位元.

3) 可計(jì)算性.對(duì)于任意的P,Q∈G，都存在有效的算法計(jì)算出e(P,Q).

雙線性映射可通過(guò)超奇異橢圓曲線上的Weil和Tate配對(duì)來(lái)進(jìn)行構(gòu)造.

1.2 多項(xiàng)式分解定理

1.3 泰勒展開式

若函數(shù)f(x)在包含x0的某個(gè)閉區(qū)間[a,b]上具有n階導(dǎo)數(shù)，且在開區(qū)間(a,b)上具有(n+1)階導(dǎo)數(shù)，則對(duì)閉區(qū)間[a,b]上任意一點(diǎn)x，均有:

其中,f(i)(x)為f(x)的i階導(dǎo)數(shù)，Rn(x)為泰勒公式的余項(xiàng)，是(x-x0)n的高階無(wú)窮小.

1.4 雙線性q -階強(qiáng)判定性Diffie-Hellman假設(shè)[26]

雙線性q-階強(qiáng)判定性Diffie-Hellman困難性假設(shè)(bilinearq-strong Diffie-Hellman,q-BSDH)，給定(e,g,G,GT,p)←BMGen(1λ)和q元組(gα,…,gαq)，不存在一個(gè)概率多項(xiàng)式算法A能以不可忽略的概率輸出(c,h)，使得h=e(g,g)(α+c)-1.其形式化定義為

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

1.5 變體的雙線性Diffie-Hellman指數(shù)假設(shè)[27]

變體的雙線性Diffie-Hellman指數(shù)困難性假設(shè)(variant of bilinear Diffie-Hellman exponent, VBDHE)，給定(e,g,G,GT,p)←BMGen(1λ)，gαi(i∈[1,q])和gβiαj((i,j)∈[1,q]×[1,q]),不存在一個(gè)概率多項(xiàng)式算法A能以不可忽略的概率輸出(G(·),h)，使得h=e(g,g)G(α)βq.其形式化定義為

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

2 BMPVDB模型

本節(jié)主要介紹了基于雙線性映射的支持全操作的公共可驗(yàn)證外包數(shù)據(jù)庫(kù)BMPVDB模型.首先給出了模型的架構(gòu)及交互流程，然后對(duì)模型進(jìn)行了形式化定義，最后針對(duì)模型應(yīng)滿足的不同安全需求給出了安全性定義.

2.1 BMPVDB模型的架構(gòu)

BMPVDB模型中包含數(shù)據(jù)擁有者、客戶、云服務(wù)器3方實(shí)體，其中數(shù)據(jù)擁有者和客戶是可信的，云服務(wù)器是不可信的.其模型架構(gòu)圖如圖1所示：

Fig. 1 The architecture of BMPVDB圖1 BMPVDB方案的架構(gòu)

數(shù)據(jù)擁有者首先執(zhí)行密鑰生成算法生成公私鑰對(duì)，其中公鑰主要用于生成和驗(yàn)證證據(jù)，私鑰主要用于對(duì)外包數(shù)據(jù)庫(kù)的更新.然后執(zhí)行初始化算法生成外包數(shù)據(jù)庫(kù)摘要.將數(shù)據(jù)庫(kù)外包到云服務(wù)器進(jìn)行存儲(chǔ)和管理，同時(shí)將公鑰發(fā)送給云服務(wù)器.然后將公鑰和摘要發(fā)送給客戶.當(dāng)客戶向云服務(wù)器發(fā)起查詢請(qǐng)求后，云服務(wù)器返回查詢的結(jié)果和證據(jù).客戶利用本地儲(chǔ)存的公鑰、摘要及云服務(wù)器返回的證據(jù)對(duì)結(jié)果進(jìn)行驗(yàn)證.該模型中云服務(wù)是不可信的，可能篡改查詢的結(jié)果.為保證查詢結(jié)果的完整性，云服務(wù)器在返回查詢結(jié)果的同時(shí)，還將返回相應(yīng)的證據(jù)供客戶驗(yàn)證.驗(yàn)證時(shí)涉及公鑰和摘要，且均為公開的，因此該方案支持公共可驗(yàn)證，即擁有公鑰的客戶都可對(duì)查詢的結(jié)果進(jìn)行驗(yàn)證.

2.2 BMPVDB的形式化定義

該模型可用五元組表示為{KeyGen,Setup,Query,Verify,Update}，五元組中每個(gè)元組都代表一個(gè)多項(xiàng)式時(shí)間算法.5個(gè)算法具體描述如下：

1) 密鑰生成算法(PK,SK)←KeyGen(1λ).輸入安全參數(shù)λ，數(shù)據(jù)擁有者執(zhí)行該算法生成公私鑰對(duì)(PK,SK).其中私鑰SK被數(shù)據(jù)擁有者私密保存，公鑰PK被公開.

2) 初始化算法σDB←Setup(PK,DB).數(shù)據(jù)擁有者將公鑰PK和外包數(shù)據(jù)庫(kù)DB作為輸入，調(diào)用該算法得到數(shù)據(jù)庫(kù)摘要σDB，最后公開σDB.

3) 查詢算法(R,π)←Query(Q,PK,DB).云服務(wù)器將公鑰PK，外包數(shù)據(jù)庫(kù)DB和客戶給定的查詢Q輸入至該算法，算法輸出查詢的結(jié)果R及證據(jù)π.

4) 驗(yàn)證算法{‘1’ or ‘0’}←Verify(PK,σDB,R,π).客戶對(duì)云服務(wù)器返回的結(jié)果進(jìn)行驗(yàn)證.算法輸出‘1’表示驗(yàn)證通過(guò)，接受查詢結(jié)果R，否則輸出‘0’，拒絕查詢結(jié)果R.

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

2.3.1 正確性

模型的正確性簡(jiǎn)單來(lái)說(shuō)，當(dāng)模型中每個(gè)算法都正確執(zhí)行，驗(yàn)證算法Verify始終輸出‘1’，即永遠(yuǎn)不會(huì)拒絕一個(gè)正確的查詢結(jié)果.其形式化定義為

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

2.3.2 安全性

模型的安全性是針對(duì)不可信云服務(wù)器來(lái)說(shuō)的.簡(jiǎn)單來(lái)說(shuō)，云服務(wù)器偽造一個(gè)惡意的結(jié)果和證據(jù)始終不能通過(guò)驗(yàn)證.下面通過(guò)構(gòu)造敵手A和挑戰(zhàn)者C之間的安全性實(shí)驗(yàn)∑來(lái)定義該模型的安全性.

對(duì)于任意的查詢Q，敵手A試圖通過(guò)4個(gè)步驟來(lái)偽造一個(gè)查詢結(jié)果和證據(jù)并通過(guò)驗(yàn)證：

1) 給定安全參數(shù)λ，C執(zhí)行算法KeyGen生成公私鑰對(duì)(PK,SK)，并將PK發(fā)送給A，私鑰SK私密保留.

2) 敵手A選定一個(gè)外包數(shù)據(jù)庫(kù)DB，并將DB發(fā)送給挑戰(zhàn)者C.

3) 挑戰(zhàn)者C在接收到DB后，執(zhí)行算法Setup，生成外包數(shù)據(jù)庫(kù)DB的摘要σDB.

4) 敵手A可向挑戰(zhàn)者C發(fā)起多項(xiàng)式poly(λ)次更新與查詢：

更新.A選定更新操作upd，將upd發(fā)送給C.C

查詢.A對(duì)于查詢Q偽造一個(gè)結(jié)果R*和證據(jù)π*.如果算法Verify(PK,σDB,R*,π*)輸出‘1’，敵手獲勝.

對(duì)于任意一個(gè)概率多項(xiàng)式時(shí)間的敵手A，如果A在上述安全性實(shí)驗(yàn)∑中獲勝的概率是可忽略的，則稱BMPVDB是安全的.

3 BMPVDB模型的實(shí)施方案

本節(jié)主要介紹了基于雙線性映射的支持全操作的公共可驗(yàn)證外包數(shù)據(jù)庫(kù)BMPVDB模型的實(shí)施方案.首先給出了該模型實(shí)施方案的總體描述及核心思想，然后給出了該模型實(shí)施方案中各算法的詳細(xì)設(shè)計(jì)，并給出了安全性證明.最后給出了該模型實(shí)施方案的擴(kuò)展及應(yīng)用.

3.1 BMPVDB模型實(shí)施方案的總體描述

對(duì)數(shù)據(jù)庫(kù)任意查詢操作都可看成對(duì)表中行或列的操作，而數(shù)據(jù)庫(kù)表中每行或每列所包含的元素均可看作一個(gè)集合，因此對(duì)數(shù)據(jù)庫(kù)的查詢就相當(dāng)于對(duì)集合的操作.從查詢輸入和輸出的類型可以將查詢分成5類：

1) 輸入2個(gè)集合輸出1個(gè)集合，該類型的查詢對(duì)應(yīng)于交集∩、并集∪、差集和對(duì)稱差集Δ.

2) 輸入輸出均為一個(gè)集合，該類型的查詢對(duì)應(yīng)于補(bǔ)集和范圍查詢RANGE.

3) 輸入一個(gè)集合輸出一個(gè)整數(shù)，該類型的查詢包含最大值MAX、最小值MIN、計(jì)數(shù)COUNT和求和SUM.

4) 輸入一個(gè)集合輸出為一個(gè)布爾值，該類型的查詢包含了屬于∈x和不屬于?x.

5) 嵌套查詢，該類型查詢是上述4種類型查詢的自由組合.

在本方案中類型1和類型2中所包含的查詢均可通過(guò)交集查詢來(lái)實(shí)現(xiàn)(詳見(jiàn)3.2節(jié))，范圍查詢可通過(guò)最大值，最小值和集合操作來(lái)實(shí)現(xiàn)詳見(jiàn)(詳見(jiàn)3.2節(jié))，嵌套查詢可通過(guò)復(fù)合上述4種類型查詢來(lái)實(shí)現(xiàn)詳見(jiàn)(詳見(jiàn)3.2節(jié))，下面將重點(diǎn)介紹集合交集、最大值、最小值、求和、計(jì)數(shù).

(α1+α2+α3)(β2αq-2+β3αq-3+β4αq-4)=
(β2αq-1+β3αq-2+β4αq-3)+(β2αq+β3αq-1+
β4αq-2)+(β2αq+1+β3αq+β4αq-1)=
(β2+β3)αq+Q(β,α).

3.2 BMPVDB模型實(shí)施方案的詳細(xì)設(shè)計(jì)及安全性證明

本節(jié)首先詳細(xì)介紹了基于雙線性映射的支持全操作的公共可驗(yàn)證外包數(shù)據(jù)庫(kù)方案中密鑰生成算法，初始化算法和更新算法.然后給出了不同查詢類型下的查詢算法與驗(yàn)證算法的具體構(gòu)造，并進(jìn)行了安全性證明.下面分別對(duì)其進(jìn)行描述.

1) 密鑰生成算法(PK,SK)←KeyGen(1λ).該算法用于生成公私鑰對(duì)(PK,SK).算法的主要步驟為：

② 給定安全參數(shù)λ，調(diào)用算法BMGen生成(e,g,G,GT,p).

③ 對(duì)于所有的i，j∈q，計(jì)算gαi和gβiαj，其中q=poly(λ).

④ 將(e,g,G,GT,p)，gαi(i∈[1,q])和gβiαj((i,j)∈[1,q]×[1,q])當(dāng)作公鑰PK.

⑤ 輸出(PK,SK).

2) 初始化算法σX←Setup(PK,X).該算法主要用于計(jì)算集合X的摘要.算法主要步驟為:

② 輸出集合X的摘要σX=(σX(α),σX(β,α)).

4) 查詢與驗(yàn)證算法

查詢算法用于返回查詢的結(jié)果和證據(jù).驗(yàn)證算法用于驗(yàn)證查詢結(jié)果的正確性.

① 交集I=X∩Y

查詢：

(i) 計(jì)算出集合X，Y交集的結(jié)果I.

(ii) 根據(jù)集合X，I和Y中元素，求得多項(xiàng)式

(iii) 求得多項(xiàng)式

Q(y,x)=X (x)Y(y,x)-I(y)xq.

(iv) 根據(jù)公鑰PK，計(jì)算出證據(jù)π=(gI(β),gQ(β,α))，返回I和π.說(shuō)明：如果證據(jù)π中包含2個(gè)元素，則令π=(π[0],π[1]).

驗(yàn)證：

(ii) 根據(jù)公鑰PK，σX(α)，σY(β,α)和證據(jù)π來(lái)驗(yàn)證下列等式是否成立：

e(σX(α),σY(β,α))=e(π[0],gαq)e(π[1],g).

(iii) 如果等式成立，則接受交集查詢的結(jié)果I，輸出‘1’，否則拒絕結(jié)果I，輸出‘0’.

安全性證明見(jiàn)定理1：

定理1. 如果在概率多項(xiàng)式時(shí)間內(nèi)存在一個(gè)敵手A能以不可忽略的概率偽造出錯(cuò)誤的結(jié)果I*和證據(jù)π*=(g∑aiβi,g∑bi,jαiβj)通過(guò)驗(yàn)證(即贏得安全性實(shí)驗(yàn)∑)，那么任意一個(gè)敵手A能找到一個(gè)有效的算法B解決VBDHE難題和q-BSDH難題.

證明. 因?yàn)锳偽造的結(jié)果及證據(jù)通過(guò)驗(yàn)證，則有:

e(σX(α),σY(β,α))=e(π*[0],gαq)e(π*[1],g),

(1)

對(duì)于正確的結(jié)果和證據(jù)，則有:

e(σX(α),σY(β,α))=e(π[0],gαq)e(π[1],g).

(2)

由式(1)和式(2)可得：

e(π[0],gαq)e(π[1],g)=
e(π*[0],gαq)e(π*[1],g)?
e(π[0],gαq)e(π[1],g)=
e(g∑aiβi,gαq)e(g∑bi,jαiβj,g)?

gI(β)αq+Q(β,α)=g(∑aiβi)αq+∑bi,jαiβj?

g(I(β)-∑aiβi)αq=g∑bi,jαiβj-Q(β,α).

令G(β)=I(β)-∑aiβi，如果I(β)≠∑aiβi，可求得gG(β)αq=g∑bi,jαiβj-Q(β,α)，因此A可找到有效的算法B解決VBDHE問(wèn)題.又因?yàn)樵搯?wèn)題是難解的，所以I(β)≠∑aiβi不成立，故有π*[0]=π[0]且I≠I*.令xmin為I∪I*中最小元素，因?yàn)棣?[0]=π[0]，所以:

(3)

式(3)右邊提供了有效的算法B解決q-BSDH問(wèn)題.又因?yàn)樵搯?wèn)題是難解的，所以π*[0]=π[0]且I ≠I*不成立.

綜上，在概率多項(xiàng)式時(shí)間內(nèi)A難以以不可忽略的概率贏得安全性實(shí)驗(yàn)∑，因此該方案是安全的.

證畢.

② 其他集合操作

集合的其他操作可通過(guò)交集來(lái)實(shí)現(xiàn)[28]，其查詢算法，驗(yàn)證算法和安全性證明均與交集相似，這里將不在贅述，只給出驗(yàn)證查詢結(jié)果正確性的等式.

σZ(α)=σX(α)σY(α)σI(α).

(ii) 差集D=XY(D=X∩I)，驗(yàn)證等式：

σD(α)=σX(α)σI(α).

(iii) 對(duì)稱補(bǔ)集S=XΔY(S=XI)∪(YI)，驗(yàn)證等式：

σS(α)=σX(α)σY(α)σI(α)2.

(v) 子集X?Y(X =X∩Y)，驗(yàn)證等式：

σX(α)=σI(α).

(vi) 屬于x∈X ({x}=X∩(x))，驗(yàn)證等式：

σI(α)=gαx.

(vii) 不屬于x?X (?=X∩(x))，驗(yàn)證等式:

σI(α)=1.

③ 計(jì)數(shù)count(X)

查詢：

(iii) 根據(jù)多項(xiàng)式分解定理(詳見(jiàn)1.2節(jié))，計(jì)算出多項(xiàng)式Q(x)=(X (x)-X (1))(x-1).

(iv) 根據(jù)公鑰PK，計(jì)算出證據(jù)π=gQ(α)，并返回R和π.

驗(yàn)證：

(i) 利用查詢返回的結(jié)果R，計(jì)算gR.

(ii) 根據(jù)公鑰PK，σX(α)和證據(jù)π來(lái)驗(yàn)證下列等式是否成立：

e(σX(α),g)=e(g,gR)e(π,gα-1).

(iii) 如果等式成立，則接受交集查詢的結(jié)果R，輸出‘1’，否則拒絕結(jié)果R，輸出‘0’.

安全性證明見(jiàn)定理2：

定理2. 如果在概率多項(xiàng)式時(shí)間內(nèi)存在一個(gè)敵手A能以不可忽略的概率偽造出錯(cuò)誤的結(jié)果R*和證據(jù)π*通過(guò)驗(yàn)證(即贏得安全性實(shí)驗(yàn)∑)，那么任意一個(gè)敵手A能找到一個(gè)有效的算法B解決q-BSDH難題.

證明. 因?yàn)锳偽造的結(jié)果及證據(jù)通過(guò)驗(yàn)證，則有:

e(σX(α),g)=e(g,gR*)e(π*,gα-1)=
e(g,gR*)e(gQ*(α),gα-1),

(4)

對(duì)于正確的結(jié)果和證據(jù)，則有:

e(σX(α),g)=e(g,gR)e(π,gα-1)=
e(g,gR)e(gQ(α),gα-1).

(5)

由式(4)和式(5)可得：

(6)

式(6)右邊提供了有效的算法B解決q-BSDH問(wèn)題.又因?yàn)樵搯?wèn)題是難解的，所以在概率多項(xiàng)式時(shí)間內(nèi)A難以以不可忽略的概率贏得安全性實(shí)驗(yàn)∑，因此該方案是安全的.

證畢.

④ 求和sum(X)

查詢：

(iii) 計(jì)算X (1)，根據(jù)泰勒展開式(詳見(jiàn)1.3節(jié)，其中n=2)，計(jì)算出多項(xiàng)式Q(x)=(X (x)-X (1)-X′(1)(x-1))(x-1)2.

(iv) 根據(jù)公鑰PK，計(jì)算出gQ(α)，將(X (1),gQ(α))作為證據(jù)π，返回R和π.

驗(yàn)證：

(i) 利用查詢返回的結(jié)果R，計(jì)算gR.

(ii) 根據(jù)公鑰PK，σX(α)和證據(jù)π來(lái)驗(yàn)證下列等式是否成立：

e(σX(α),g)=
e(gπ[0],g)e(gR,g(α-1))e(π[1],g(α-1)2).

(iii) 如果等式成立，則接受交集查詢的結(jié)果R，輸出‘1’，否則拒絕結(jié)果R，輸出‘0’.

安全性證明見(jiàn)定理3：

定理3. 如果在概率多項(xiàng)式時(shí)間內(nèi)存在一個(gè)敵手A能以不可忽略的概率偽造出錯(cuò)誤的結(jié)果R*和證據(jù)π*通過(guò)驗(yàn)證(即贏得安全性實(shí)驗(yàn)∑)，那么任意一個(gè)敵手A能找到一個(gè)有效的算法B解決q-BSDH難題.

證明. 因?yàn)锳偽造的結(jié)果及證據(jù)通過(guò)驗(yàn)證，則有:

e(σX(α),g)=
e(gπ*[0],g)e(gR*,g(α-1))e(π*[1],g(α-1)2)=
e(gπ*[0]+R*(α-1),g)e(π*[1],g(α-1)2),

(7)

對(duì)于正確的結(jié)果和證據(jù)，則有:

e(σX(α),g)=
e(gπ[0],g)e(gR,g(α-1))e(π[1],g(α-1)2)=
e(gπ[0]+R(α-1),g)e(π[1],g(α-1)2).

(8)

由式(7)和式(8)可得：

上式右邊提供了有效的算法B解決q-BSDH問(wèn)題.又因?yàn)樵搯?wèn)題是難解的，所以在概率多項(xiàng)式時(shí)間內(nèi)A難以以不可忽略的概率贏得安全性實(shí)驗(yàn)∑，因此該方案是安全的.

證畢.

⑤ 最小值min(X)

查詢：

(ii) 查看集合中最小元素或?qū)⒍囗?xiàng)式最小指數(shù)最為最小值查詢的結(jié)果R=min(X).

(iii) 根據(jù)公鑰PK，計(jì)算出證據(jù)π=g(X(α)-αR)αR+1，并返回R和π.

驗(yàn)證：

(i) 根據(jù)公鑰PK，σX(α)，證據(jù)π和結(jié)果R來(lái)驗(yàn)證下列等式是否成立：

e(σX(α),g)=e(gαR,g)e(π,gαR+1).

(ii) 如果等式成立，則接受交集查詢的結(jié)果R，輸出‘1’，否則拒絕結(jié)果R，輸出‘0’.

安全性證明見(jiàn)定理4：

定理4. 如果在概率多項(xiàng)式時(shí)間內(nèi)存在一個(gè)敵手A能以不可忽略的概率偽造出錯(cuò)誤的結(jié)果R*和證據(jù)π*通過(guò)驗(yàn)證(即贏得安全性實(shí)驗(yàn)∑)，那么任意一個(gè)敵手A能找到一個(gè)有效的算法B解決q-BSDH難題.

證明. 如果敵手A偽造的結(jié)果及證據(jù)通過(guò)驗(yàn)證，則有：

e(σX(α),g)=e(gαR*,g)e(π,gαR*+1).

(9)

當(dāng)R*

e(gαR*,g)=e(σX(α),g)e(π*,gαR*+1)?
e(g,g)=e(σX(α),(gαR*+1)-1)e(π*,g).

(10)

當(dāng)R*>R=min(X)時(shí)，定義U={i∈X:i

(11)

因?yàn)閁∩W=?，可得αR是U(α)和W(α)最大公因子，再由廣義歐幾里德定理可得，存在2個(gè)多項(xiàng)式a(α)和b(α)，使得：

因此式(11)可得：

上式右邊提供了有效的算法B解決q-BSDH問(wèn)題.又因?yàn)樵搯?wèn)題是難解的，所以在概率多項(xiàng)式時(shí)間內(nèi)A難以以不可忽略的概率贏得安全性實(shí)驗(yàn)∑，因此該方案是安全的.

證畢.

⑥ 最大值max(X)

查詢：

(i) 根據(jù)集合X中的元素，求得

(ii) 查看集合中最大元素或?qū)⒍囗?xiàng)式中關(guān)于y最大指數(shù)作為最大值查詢的結(jié)果R=max(X).

(iii) 根據(jù)公鑰PK，計(jì)算出證據(jù)π=g(X(β,α)-βRαq-R)αq-R+1，并返回R和π.

驗(yàn)證：

(i) 根據(jù)公鑰PK，σX(α)，證據(jù)π和結(jié)果R來(lái)驗(yàn)證下列等式是否成立：

e(σX(β,α),g)=e(gβRαq-R,g)e(π,gαq-R+1).

(ii) 如果等式成立，則接受交集查詢的結(jié)果R，輸出‘1’，否則拒絕結(jié)果R，輸出‘0’.

最大值查詢的安全性證明與最小值查詢類似，因此不再贅述.

⑦ 范圍查詢r(jià)ange(l,r)

查詢：

(i) 根據(jù)查詢范圍[l,r]，將被查詢集合X分割成3個(gè)不相交集合U，V，W，其中U={i:i∈X,ir}.

(ii) 分別調(diào)用集合U∩V，U∩W和V∩W查詢算法返回對(duì)應(yīng)的結(jié)果和證據(jù).

(iii) 分別調(diào)用集合U和W的最大值和最小值查詢算法返回對(duì)應(yīng)的結(jié)果和證據(jù).

驗(yàn)證：

(i) 分別調(diào)用集合U∩V，U∩W和V∩W驗(yàn)證算法，若驗(yàn)證失敗，輸出‘0’，否則，執(zhí)行下一步.

(ii) 分別調(diào)用集合U和W的最大值和最小值驗(yàn)證算法，若驗(yàn)證失敗，輸出‘0’，否則，執(zhí)行下一步.

(iii) 驗(yàn)證max(U)r.若成立，則接受查詢結(jié)果R，輸出‘1’，否則拒絕結(jié)果R，輸出‘0’.

范圍查詢的安全性證明依賴于集合的交集、最大值和最小值查詢的安全性，上文已證，因此不再贅述.

⑧ 嵌套查詢

本方案是嵌套查詢，查詢時(shí)遞歸調(diào)用嵌套查詢中的每個(gè)查詢，但是無(wú)需返回中間的結(jié)果，只需返回中間結(jié)果的摘要和對(duì)應(yīng)的證據(jù).驗(yàn)證時(shí)，同樣遞歸調(diào)用嵌套查詢中的每個(gè)查詢所對(duì)應(yīng)的驗(yàn)證算法，驗(yàn)證查詢結(jié)果的正確性.該查詢的安全性依賴于上述各類查詢的安全性，因此該查詢也是安全的.

4 性能分析

4.1 方案對(duì)比

Table1 Comparison with Prior Work表1 方案對(duì)比

Notes:√ means the scheme is applicable;× means the scheme is not applicable.

4.2 效率分析

根據(jù)4.1節(jié)中方案的對(duì)比分析可知：基于簽名的可驗(yàn)證外包數(shù)據(jù)庫(kù)方案無(wú)論在功能上還是性能上都低于其他2類方法；基于認(rèn)證數(shù)據(jù)結(jié)構(gòu)的方法中，雖然在部分方案與基于可驗(yàn)證計(jì)算的方案中性能相近，但是前者所支持的操作遠(yuǎn)小于基于可驗(yàn)證計(jì)算方案所支持的操作.因此只與基于可驗(yàn)證計(jì)算的方案相比較.而在基于可驗(yàn)證計(jì)算的方案中，基于電路的方案所支持的查詢操作不及基于RAM的方案豐富，且基于RAM的方案中SNARK方案[25]較高效.因此在實(shí)驗(yàn)分析中只與SNARK 方案進(jìn)行對(duì)比.實(shí)驗(yàn)中，主機(jī)的配置為Intel?CoreTMi7-4770 3.40 GHz主頻的處理器和32 GB內(nèi)存，選定的安全參數(shù)λ=128，測(cè)試語(yǔ)句為嵌套查詢語(yǔ)句count((X∩Y)∪(U ∩W))，其中每個(gè)集合大小相等均為n.數(shù)據(jù)集利用偽隨機(jī)數(shù)生成器以時(shí)間戳為輸入隨機(jī)產(chǎn)生.每次執(zhí)行時(shí)，數(shù)據(jù)集都不相同.保證了數(shù)據(jù)集的隨機(jī)可靠性和程序的健壯性.對(duì)本方案和SNARK方案中的初始化算法的效率、查詢算法的效率、驗(yàn)證算法的效率、證據(jù)的大小和云服務(wù)器所需的存儲(chǔ)空間進(jìn)行了測(cè)試、對(duì)比與分析.

兩方案中初始化算法的效率比較結(jié)果如圖2所示，橫坐標(biāo)為集合的大小，縱坐標(biāo)為該算法運(yùn)行的時(shí)間.將本方案運(yùn)行時(shí)間放大10 000倍，仍遠(yuǎn)小于SNARK方案的運(yùn)行時(shí)間.因此，在初始化算法上，雖然理論分析上兩方案相近，但本方案更高效.

Fig. 2 Comparison for setup in time cost圖2 初始化算法運(yùn)行時(shí)間比較

兩方案查詢算法的效率比較結(jié)果如圖3所示，將本方案運(yùn)行時(shí)間放大100倍，仍小于SNARK方案的運(yùn)行時(shí)間.因此，在查詢算法上，雖然理論分析上兩方案相同，但本方案更高效.

Fig. 3 Comparison for query in time cost圖3 查詢算法運(yùn)行時(shí)間比較

兩方案中驗(yàn)證算法的效率比較結(jié)果如圖4示，兩方案中驗(yàn)證效率均為常數(shù)級(jí)，不隨集合大小增加而增大，且本方案驗(yàn)證效率小于SNARK方案.因此在驗(yàn)證算法上，雖然理論分析上兩方案相近，但本方案更高效.在進(jìn)行更新操作時(shí)，本方案在任意大小的數(shù)據(jù)下所消耗的時(shí)間大約為2.6 μs.由于SNARK對(duì)硬件要求較高，在現(xiàn)有的實(shí)驗(yàn)條件內(nèi)未測(cè)出SNARK更新操作所需的精準(zhǔn)時(shí)間，但實(shí)驗(yàn)表明了其所需時(shí)間要遠(yuǎn)大于本方案所需時(shí)間.此外，4.1節(jié)理論分析可知，更新時(shí)，SNARK的效率為Ω(logn)，本方案的效率為O(1)遠(yuǎn)小于SNARK的效率.基于以上2點(diǎn)，本方案中更新算法的效率遠(yuǎn)高于SNARK方案中更新算法的效率.

Fig. 4 Comparison for verify in time cost圖4 驗(yàn)證算法運(yùn)行時(shí)間比較

兩方案中證據(jù)的大小比較結(jié)果如圖5所示，兩方案中證據(jù)的大小恒定不變，不隨集合大小的增加而增加，且本方案中證據(jù)的大小小于SNARK方案.因此在證據(jù)的大小上，雖然理論分析上兩方案相同，但本方案通信代價(jià)更低.

Fig. 5 Comparison for witness size圖5 證據(jù)大小比較

兩方案中云服務(wù)器所需要的存儲(chǔ)空間比較結(jié)果如圖6所示，橫坐標(biāo)為集合的大小，縱坐標(biāo)為云服務(wù)器所需的存儲(chǔ)空間.將本方案所需的存儲(chǔ)空間放大10倍，仍小于SNARK方案.因此本方案的數(shù)據(jù)膨脹率更低.

Fig. 6 Comparison for storage size圖6 存儲(chǔ)空間比較

以上實(shí)驗(yàn)結(jié)果表明，本方案在初始化算法的效率、查詢算法的效率、驗(yàn)證算法的效率、證據(jù)的大小及存儲(chǔ)空間上均優(yōu)于SNARK方案.因此本方案效率更高、通信代價(jià)更小、數(shù)據(jù)膨脹率更低，更適合應(yīng)用于實(shí)際.

5 結(jié) 論

針對(duì)現(xiàn)有可驗(yàn)證外包數(shù)據(jù)方案存在查詢類型單一、效率低下、驗(yàn)證和更新代價(jià)較高，難以應(yīng)用于實(shí)際等問(wèn)題，深入系統(tǒng)地研究了國(guó)內(nèi)外關(guān)于可驗(yàn)證外包數(shù)據(jù)庫(kù)相關(guān)方案，并總結(jié)各方案的優(yōu)缺點(diǎn).在此基礎(chǔ)上，基于雙線性映射提出了一個(gè)支持全操作的公共可驗(yàn)證外包數(shù)據(jù)庫(kù)方案，給出了該方案的形式化定義，正確性及安全性定義.然后給出了方案的構(gòu)建，并證明了方案的安全性.最后將本方案與已有方案相比較，理論與實(shí)驗(yàn)分析表明該方案功能更全面性，效率更高，數(shù)據(jù)的膨脹率更低，更新計(jì)算代價(jià)更低.本方案中數(shù)據(jù)的驗(yàn)證和更新不依賴于私鑰，實(shí)現(xiàn)了公共可驗(yàn)證和公共可更新.因此本方案對(duì)外包數(shù)據(jù)庫(kù)查詢結(jié)果完整性問(wèn)題的研究具有一定的理論意義和實(shí)踐價(jià)值.