可有效更新的低存儲開銷公共可驗證數據庫方案

吳淇毓 周福才 王 強 李宇溪

(東北大學軟件學院 沈陽 110169) (kathywuqy@gmail.com)

隨著互聯網應用的迅速發展，數據量和用戶數快速增長，使得客戶對數據的存儲、管理與維護變得更具挑戰性.越來越多資源受限的客戶將大型數據庫外包到專業數據庫服務提供商(database service provider, DSP)[1]，并希望得到安全保證，使其可以從DSP查詢或更新數據記錄，且可以檢測并驗證所查詢數據的完整性.效率方面，要求客戶的計算開銷獨立于數據庫的大小；安全性方面，要求客戶能夠檢測出數據是否被篡改.

近年來，研究者們提出了一系列方案來解決上述問題.一種最直接的方法是利用數字簽名[2-3]來實現.然而，該方案需要在本地記錄每一次更新，存儲開銷較大，不支持大量的數據更新.為了減少簽名的次數，基于認證數據結構[4-11]的方法被提出，可以利用驗證樹對其根結點簽名，從而減小構造驗證信息的計算量，或者基于可翻轉的布隆過濾器[12]，有效避免數據更新操作時額外的計算開銷，但布隆過濾器存在誤算率.此外，為了減少服務器與用戶之間交互的通信量，研究者們還提出了基于動態累加器[13-15]的方法，可以有效驗證查詢結果并對數據進行更新.然而上述2種方法或依賴于非常量大小(non-constant size)的困難假設(如q-Strong DH假設)，或需要完成生成素數等計算負擔較大的操作.

Benabbas等人[16]首次提出了一個支持有效查詢和更新的可驗證數據庫(verifiable database，VDB)方案.他們的方案依賴于合數階雙線性群(bilinear groups of composite order)常量大小的困難假設，然而不支持公共可驗證，即只有數據庫的擁有者才可以對數據查詢結果進行驗證.

為了解決該問題，Catalano等人[17]將向量承諾方案應用于可驗證數據庫，依賴于標準常量大小假設，提出了一種公共可驗證數據庫方案.但該方案中公共參數的大小依賴于數據庫大小，因此客戶在預處理階段的計算開銷和存儲開銷會隨著數據庫增大呈冪增長.此外，該方案中的更新算法只支持修改數據，不支持添加或刪除數據.

基于文獻[17]，Miao等人[18]利用分層承諾的思想首次提出了一個支持修改、刪除和添加數據的可驗證數據庫方案，并滿足標準計算性Diffie-Hellman假設.然而，客戶進行更新操作的計算負擔隨著分層數量的增加而增大，并且該方案同文獻[17]一樣，沒有解決客戶的存儲開銷問題.

本文在上述文獻的基礎上對可驗證數據庫展開研究，以降低客戶的存儲負擔、支持對數據的添加和刪除操作為目標，提出一個可有效更新的低存儲開銷公共可驗證數據庫模型，并對其正確性和安全性給出了形式化定義，構造了一個具體的可有效更新的低存儲開銷公共可驗證數據庫方案(publicly verifiable databases scheme with efficient updates and low storage overhead, PVDB-EL).方案支持客戶對外包數據庫中數據查詢結果的公共可驗證，與已有方案相比，該方案基于素數階雙線性群，提高了計算效率；同時，在初始化階段構造了獨立于數據庫大小的公共參數，減小了客戶的存儲開銷；此外，該方案支持對外包數據的修改、添加及刪除操作.通過對其計算效率的分析，方案滿足客戶查詢、更新和驗證等操作開銷獨立于數據庫大小，保證了效率.方案的安全性可以規約為平方計算性Diffie-Hellman(square computational Diffie-Hellman， Square-CDH)問題假設.

1 相關知識

1.1 雙線性映射

設G和GT為p階循環群，g為G的生成元.定義2個群上的雙線性映射為e:G×G→GT，且滿足以下性質：

1) 雙線性.e(ga,gb)=e(g,g)ab，對所有的a,b∈均成立.

2) 非退化性.e(g,g)≠1.

3) 可計算性.存在有效算法來計算t=e(g,g).

1.2 平方計算性Diffie-Hellman問題及困難性假設

定義1. Square-CDH問題[19].設λ∈為安全參數，G為素數p階群，g是G的生成元，e:G×G→GT為雙線性映射，給定g,gα∈G，其中p，計算gα2.概率多項式時間算法A計算出G上的Square-CDH問題的概率定義為Pr[A(g,ga)=ga2].

定義2. Square-CDH困難問題假設.如果不存在一個概率多項式時間算法能夠以不可忽略的概率ε來計算出G上的Square-CDH問題，即Pr[A(g,ga)=ga2]≤neg(λ)，其中neg(λ)為可忽略函數，則稱群G上的Square-CDH問題是困難的.

2 PVDB-EL的形式化定義及安全模型

PVDB-EL方案的應用場景包括數據擁有者、客戶和DSP這3個實體.如圖1所示，數據擁有者在初始化階段對數據庫進行編碼并生成公鑰和私鑰，之后將數據庫外包到DSP進行存儲和管理.其中，公鑰包含用于驗證查詢階段服務器返回的證據的公共參數，私鑰用于對外包數據庫進行更新.只有數據擁有者可以對數據庫進行更新；該方案支持公共可驗證，多個客戶都可以對DSP中的外包數據庫進行查詢；由于DSP是不可信的，可能會對數據庫的內容進行篡改，因此在返回查詢結果的同時，DSP還將返回相應證據來證明客戶端所查詢數據的完整性，數據擁有者和客戶可以利用獲得的公鑰進行驗證.

Fig. 1 The application scenario of PVDB-EL圖1 PVDB-EL方案應用場景

2.1 PVDB-EL的形式化定義

該方案由5個概率多項式時間算法組成：初始化算法、數據查詢算法、公共可驗證算法、數據更新算法、數據庫更新算法.下面分別對其進行具體的描述.

1) Setup(1λ,D)→(PK,SK,S)初始化算法.輸入安全參數λ和數據庫D，數據擁有者執行初始化算法，對數據庫編碼得到S并發送給服務器.私鑰SK由客戶私密保存，公鑰PK被分發給所有想對數據庫進行驗證的客戶.

2) Query(PK,S,i)→(vi,Pi)數據查詢算法.客戶將待查詢數據的位置i作為輸入，服務器執行數據查詢算法并返回i處的數據vi及證據Pi.

3) Verify(PK,i,vi,Pi)→{0,1}公共可驗證算法.客戶對服務器返回的查詢結果進行驗證.如果vi=D(i)驗證正確，則算法接受結果vi并輸出1，反之輸出0.其中1代表驗證結果正確，0代表驗證結果錯誤.

2.2 PVDB-EL的正確性及安全性定義

2.2.1 正確性

設λ是初始化選定的安全參數，D是數據庫，定義算法check為多項式時間算法，其以數據庫中位置i、查詢結果vi、數據庫D為輸入，當D中位置i處數據確為vi時，返回accept，否則返回reject，即{accept,reject}←check(i,vi,D(i)).

對于任何i=0,1,…,poly(λ)，PVDB-EL方案是正確的，則要求各算法正確執行后，算法查詢結果滿足：

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

2.2.2 安全性

假設所有的外包服務器均為不可信，即外包服務器會試圖獲取額外的信息，從而可能會對數據庫的內容進行篡改.在PVDB-EL的安全模型中，敵手能夠查詢外包數據庫中的任意數據，并針對數據庫的某一位置，試圖偽造一個與數據擁有者的初始數據不相等的數據返回給用戶，且能夠通過用戶的驗證.

設λ是初始化選定的安全參數，D是數據庫，下面通過敵手A和挑戰者C的安全游戲Π給出安全性定義.

安全游戲Π：

定義敵手A，對于選定變量，它試圖通過以下階段來偽造一個結果通過驗證.

Setup: C執行Setup算法，并把公鑰PK以及數據庫編碼S發送給A.

定義3. 在上述安全游戲過程中，如果敵手A偽造成功的概率滿足：

其中neg(λ)為可忽略函數，則稱PVDB-EL是安全的，滿足不可偽造性.

3 PVDB-EL方案的描述

3.1 算法詳細設計

在本節中，對PVDB-EL方案中的5個多項式時間算法即初始化算法、數據查詢算法、公共可驗證算法、數據更新算法、數據庫更新算法進行詳細的設計和描述.

1) 初始化算法Setup(1λ,D)→(PK,SK,S)

該算法用于生成密鑰以及對數據庫進行編碼.算法的主要步驟如下：

①λ∈為安全參數，數據庫D={(i,vi)}(1≤i≤n,n=poly(λ))，其中i∈(q,n]時vi=0(q∈[1,n]).數據擁有者將數據庫外包到服務器.首先生成一個λ位的素數p，再生成p階循環群G和GT，及雙線性映射函數e.

② 隨機選擇種子k并利用偽隨機函數Fk(i)=zi→p生成zi，取G中生成元g，計算?i∈[1,n])，利用si計算

③ 隨機選擇參數α→p,并計算pk=gα.

④ 令輔助信息aux包括數據庫內存儲的數據，則aux=(v1,v2,…,vn)，其中vi=0(q

⑤ 輸出公鑰PK=(pp,C,pk)，私鑰SK=α，對數據庫D進行編碼得到S=(pp,aux,D).

2) 數據查詢算法Query(PK,S,i)→(vi,Pi)

該算法用于返回客戶查詢的數據及用于驗證該數據完整性的證據.算法的主要步驟如下：

① 以位置i為輸入，根據vi=D(i)，服務器返回vi的值.

3) 公共可驗證算法Verify(PK,i,vi,Pi)→{0,1}

該算法利用服務器返回的證據，驗證所查詢數據是否正確.算法的主要步驟如下：

① 利用公鑰PK、位置i、服務器返回的數據vi、證據Pi及雙線性映射e來驗證等式

(1)

是否成立.

② 如果式(1)成立，則該算法接受結果vi，輸出1；反之拒絕結果vi并且輸出0.

該算法用于返回更新后的公鑰及相關更新信息.算法的主要步驟如下：

③ 得到更新后的公鑰PK′=(pp,C′,pk).

該算法用于更新數據庫記錄.算法的主要步驟如下：

3.2 方案詳細設計

本節將通過對數據擁有者、客戶和服務器這3個實體間的交互對方案的詳細設計進行描述.

1) 在初始化階段，數據擁有者首先選定待外包的數據庫，然后運行算法Setup(1λ,D)為系統生成密鑰以及數據庫的編碼.對于已選定的數據庫，數據擁有者將通過編碼的方式來保證數據庫內數據的機密性.

2) 數據擁有者將編碼后的數據庫外包到服務器，將私鑰自己留存，把公鑰發送給客戶和服務器.

3) 當客戶(包括數據擁有者在內)想要對服務器中的數據庫進行查詢時，運行Query(PK,S,i)算法來查詢位置i處對應的數據.算法返回數據vi及用于驗證該數據完整性的證據給客戶.

4) 客戶在接收到數據及證據后，將利用Verify(PK,i,vi,Pi)算法對數據的完整性進行驗證.若驗證通過，則接受vi，反之拒絕vi.

4 正確性及安全性證明

4.1 正確性證明

定理1. 如果方案步驟都是正確執行，產生的結果都是按照正確步驟執行得到、沒有被惡意篡改的，則客戶端將以極大概率接受結果，即客戶端執行驗證算法Verify(PK,i,vi,Pi)→1.

因此Verify(PK,i,vi,Pi)→1，定理1成立，方案滿足正確性.

證畢.

4.2 安全性證明

定理2. 如果存在一個敵手A可以在不可忽略的概率多項式時間內贏得安全游戲Π，那么就存在一個有效算法B能夠以不可忽略的概率解決Square-CDH問題.

證明. 為了證明針對數據庫內的同一位置，敵手A不能返回給客戶2個不同的數據，接下來先證明如何構建一個有效的算法B來使A能夠以不可忽略的概率解決Square-CDH問題.

令si*=gα，則化簡得到：

由此可以計算出gα2，即B算法可以在概率多項式的時間內解決Square-CDH問題.

又由于Square-CDH問題是難解的，因此定理2不成立，即不存在概率多項式時間內的敵手A能夠以不可忽略的概率贏得安全游戲.因此方案是安全的.

證畢.

5 性能分析

5.1 方案對比

本節將本文所提方案與文獻[16-18]進行對比.功能方面主要比較了方案是否支持公共可驗證、是否支持數據插入及刪除操作、雙線性群的類型、計算性假設的類型等；性能方面主要比較了客戶的存儲開銷復雜度及算法的計算代價，算法包括服務器的查詢算法、客戶的驗證算法以及更新算法.比較結果如表1所示.

從表1可以看出，功能方面，文獻[16]不能支持公共可驗證，且基于合數階雙線性群，計算效率較低；文獻[17]雖然支持了公共可驗證，但卻不支持數據的插入和刪除操作；本文所提方案基于素數階雙線性群，支持對查詢結果的公共可驗證，并支持對外包數據的插入和刪除操作.

性能方面，定義n是外包數據庫的大小，M是G上乘法的計算代價，E是G上指數的計算代價，I是G上求逆的計算代價，P是雙線性對的計算代價，L是當前數據庫中的總層數.文獻[17-18]中客戶的存儲開銷均為O(n2)，會隨著數據庫的增大呈冪增長，而本文所提方案構造了常量大小的公共參數，減小了客戶的存儲負擔；本方案查詢算法的計算代價同文獻[17-18]一樣，優于文獻[16]；本方案驗證算法的計算代價雖略遜于文獻[16-17]，卻優于文獻[18]；客戶更新算法的計算代價與文獻[17]相同，優于文獻[16,18].

綜合以上對比，本文所提方案在功能及性能方面整體上優于對比方案.

Table 1 Comparison Among Four Schemes表1 方案比較

5.2 效率分析

由于本方案在功能方面優于文獻[16]，因此在本節中通過相關實驗，分別對本方案及文獻[17-18]中方案的存儲開銷、驗證效率以及更新效率進行測試、對比與分析.實驗采用JPBC庫實現雙線性群的初始化，對大小為[5 000,40 000]的數據集分別進行了測試，測試的每一個數據結果均是10次運行結果的平均值，其中排除了明顯錯誤的數據.運行實驗程序的計算機配有Intel?CoreTMi3-3240 3.40 GHz主頻的處理器和8 GB內存.

1) 比較本方案與文獻[17-18]中客戶的存儲開銷，客戶需要存儲PK用于之后的查詢及驗證操作.實驗結果如圖2所示，由于數量級相差較大，圖2中左面的縱坐標表示對比文獻中客戶的存儲開銷，右面的縱坐標表示本方案的存儲開銷，橫坐標為外包數據庫中的數據集大小.實驗結果表明，本方案的存儲開銷為常量，獨立于數據集大小，并且遠遠小于文獻[17-18]中測試結果的數量級.它們的方案在數據集大小為5 000時的存儲開銷已達到約7 GB.

Fig. 2 Comparison of storage size圖2 存儲開銷對比

這是因為在對比文獻中，初始化階段的公共參數pp的大小為O(n2)，當數據庫增大時，客戶查詢更新和驗證等操作開銷將會變得很大.本方案中客戶在公共參數pp中不需要存儲所有的參數si，只需要存儲g以及偽隨機函數的種子k，存儲開銷為O(1).利用這2個參數，可以計算出C，最終得到公鑰.在驗證服務器返回的數據時，客戶只需要利用g和k生成特定的si來驗證返回結果是否正確.本方案公共參數pp的大小為常量，減小了客戶的存儲負擔，并使得客戶驗證和更新等操作開銷均獨立于數據庫大小.

2) 比較本方案與文獻[17-18]中驗證操作的執行時間.實驗結果如圖3所示，圖3中縱坐標為操作的執行時間，橫坐標為外包數據庫中的數據集大小.實驗結果表明，本方案中驗證操作的時間開銷高于文獻[17]、低于文獻[18]，且驗證開銷為常量.這是因為本方案比文獻[17]多進行了一次雙線性配對操作，文獻[18]比本方案多進行了一次配對操作.由于本方案獨立于數據集大小，因此可以對外包數據庫的查詢結果進行有效驗證.

Fig. 3 Comparison of running time for Verify圖3 驗證操作執行時間對比

3) 比較本方案與文獻[17-18]中客戶更新操作的執行時間.實驗結果如圖4所示，其中文獻[17]相關數據以層數L=1為例，圖4中縱坐標為操作的執行時間，橫坐標為外包數據庫中的數據集大小.實驗結果表明，本方案中更新操作的時間開銷與文獻[17]一致，明顯優于文獻[18]，且更新操作的時間開銷為常量.這是因為文獻[18]比本方案及文獻[17]多進行了1次G上乘法運算及L次G上指數運算.由于本方案獨立于數據集大小，因此可以對外包數據庫的查詢結果進行有效更新.

Fig. 4 Comparison of running time for ClientUpdate圖4 更新操作執行時間對比

4) 比較本方案中初始化操作、驗證操作及更新操作的執行時間.實驗結果如圖5所示，由于數量級相差較大，圖5中左面的縱坐標表示驗證操作及更新操作的執行時間，右面的縱坐標表示初始化操作的執行時間，橫坐標為外包數據庫中的數據集大小.實驗結果表明，數據進行初始化操作的執行時間在數據集大小為5 000時已約為4 ks.而驗證操作和更新操作的執行時間遠遠小于對數據進行初始化操作的執行時間，滿足外包數據庫方案的要求，有利于外包數據庫的公共可驗證，并且驗證及更新操作的時間開銷為常量，獨立于數據集大小，可以對外包數據庫進行有效驗證及更新.

Fig. 5 Comparison for Setup, Verify and ClientUpdate圖5 初始化、驗證、更新操作執行時間對比

以上4個實驗的結果表明，可有效更新的低存儲開銷公共可驗證數據庫方案在客戶的存儲開銷、驗證查詢結果的執行時間以及對數據進行更新操作的執行時間上都有很大的優勢，并且數據庫中數據集越大，優勢越明顯.其原因是：本方案中客戶在初始化階段中的公共參數pp中只存儲了g以及偽隨機函數的種子k這2個常量參數，在驗證和更新操作時，客戶只需要利用該常量的公共參數來進行計算，由于公共參數的大小為常量，減小了客戶的存儲負擔，并使得客戶驗證和更新等操作開銷均獨立于數據庫大小.

6 結 論

本文深入系統地研究了國內外關于外包數據庫查詢結果完整性的相關方案，總結各方案的優缺點，并進一步研究了可驗證數據庫相關理論，提出了一個可有效更新的低存儲開銷公共可驗證數據庫方案.文中給出了方案的形式化定義以及證據的生成、查詢結果的驗證和數據的更新方法，同時給出了正確性及安全性分析與證明.與已有方案相比，該方案基于素數階雙線性群，提高了計算效率，并在初始化階段構造了獨立于數據庫大小的公共參數，減小了客戶的存儲開銷.同時，方案驗證無需私鑰參與，從而實現了公共可驗證.該方案不僅支持對數據進行修改，還支持對數據的插入及刪除操作.性能分析表明方案滿足客戶查詢、更新和驗證等操作開銷獨立于數據庫大小，因此具有驗證速度快、更新效率高的優勢.該方案對于外包數據庫查詢結果完整性問題具有一定理論意義和實際應用價值.

WuQiyu, born in 1994. Received her master degree from the Software College, Northeastern University in July 2018. PhD candidate. Her main research interests include verifiable computation and network security.

ZhouFucai, born in 1964. PhD, professor and PhD supervisor. Senior member of CCF. His main research interests include cryptography and network security, trusted computing, and critical technology in electronic commerence.

WangQiang, born in 1991. PhD candidate. His main research interests include verifiable computation and outsourced database.

LiYuxi, born in 1990. PhD candidate. Her main research interests include secure cloud storage and searchable encryption.