可有效更新的低存储开销公共可验证数据库方案

吴淇毓 周福才 王 强 李宇溪

(东北大学软件学院 沈阳 110169) (kathywuqy@gmail.com)

围绕外包数据的计算效率和查询结果完整性问题,展开对可验证数据库的研究,提出了一个可有效更新的低存储开销公共可验证数据库模型.给出其算法形式化定义及安全模型,并利用素数阶双线性群构造了一个具体的可有效更新的低存储开销公共可验证数据库方案.该方案允许资源受限的客户将大型数据库外包到专业数据库服务提供商,不仅可以从其查询或更新数据记录,而且能够检测并验证所查询数据的完整性.方案的安全性可以规约为Square-CDH问题假设.与已有方案相比,该方案基于素数阶双线性群,提高了计算效率,并在初始化阶段构造了独立于数据库大小的公共参数,减小了客户的存储开销.同时,方案验证无需私钥参与,从而实现了公共可验证.此外,该方案不仅支持对数据进行修改,还支持对数据的插入及删除操作.性能分析表明,该方案满足客户查询、更新和验证等操作开销独立于数据库大小.

关键词 可验证数据库;公共可验证;外包存储;常量大小;双线性映射

随着互联网应用的迅速发展,数据量和用户数快速增长,使得客户对数据的存储、管理与维护变得更具挑战性.越来越多资源受限的客户将大型数据库外包到专业数据库服务提供商(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 G T p 阶循环群, g G 的生成元.定义2个群上的双线性映射为 e : G × G G T ,且满足以下性质:

1) 双线性. e ( g a , g b )= 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 G T 为双线性映射,给定 g , g α G ,其中 p ,计算 g α 2 .概率多项式时间算法A计算出 G 上的Square-CDH问题的概率定义为 Pr [A( g , g a )= g a 2 ].

定义2 . Square-CDH困难问题假设.如果不存在一个概率多项式时间算法能够以不可忽略的概率 ε 来计算出 G 上的Square-CDH问题,即 Pr [A( g , g a )= g a 2 ]≤ 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 )→( v i , P i )数据查询算法.客户将待查询数据的位置 i 作为输入,服务器执行数据查询算法并返回 i 处的数据 v i 及证据 P i .

3) Verify( PK , i , v i , P i )→{0,1}公共可验证算法.客户对服务器返回的查询结果进行验证.如果 v i = D ( i )验证正确,则算法接受结果 v i 并输出1,反之输出0.其中1代表验证结果正确,0代表验证结果错误.

数据更新算法.数据拥有者执行此算法,利用私钥对位置 i 处的数据进行修改、添加或删除,最终输出 其中包括更新后的公钥 PK ′以及更新信息 U .

数据库更新算法.根据 U 的信息,服务器执行此算法将数据库中的记录进行更新.

2 . 2 PVDB - EL的正确性及安全性定义

2.2.1 正确性

λ 是初始化选定的安全参数, D 是数据库,定义算法check为多项式时间算法,其以数据库中位置 i 、查询结果 v i 、数据库 D 为输入,当 D 中位置 i 处数据确为 v i 时,返回accept,否则返回reject,即{accept,reject}←check( i , v i , D ( i )).

对于任何 i =0,1,…, poly ( λ ),PVDB-EL方案是正确的,则要求各算法正确执行后,算法查询结果满足:

其中, neg ( λ )为可忽略函数.

2.2.2 安全性

假设所有的外包服务器均为不可信,即外包服务器会试图获取额外的信息,从而可能会对数据库的内容进行篡改.在PVDB-EL的安全模型中,敌手能够查询外包数据库中的任意数据,并针对数据库的某一位置,试图伪造一个与数据拥有者的初始数据不相等的数据返回给用户,且能够通过用户的验证.

λ 是初始化选定的安全参数, D 是数据库,下面通过敌手A和挑战者C的安全游戏Π给出安全性定义.

安全游戏Π:

定义敌手A,对于选定变量,它试图通过以下阶段来伪造一个结果通过验证.

Setup: C执行Setup算法,并把公钥 PK 以及数据库编码 S 发送给A.

Phase1: A对C进行查询.A发送数据位置 i 给C,C返回位置对应的数据值 v i .A对C进行了 j 次(1≤ j T , T = poly ( λ ))更新查询,每一次查询C进行一次ClientUpdate更新算法,并将更新后得到的数据 i j 发送至A.

Challenge: 查询结束后,A对于特定位置 i * 输出一个伪造结果 v * 及伪造证据 P * .如果Verify( PK , i * , v * , P * )输出为1,且有 v * ≠⊥并且 v * ,则A伪造成功,否则A失败.

定义3 . 在上述安全游戏过程中,如果敌手A伪造成功的概率满足:

其中 neg ( λ )为可忽略函数,则称PVDB-EL是安全的,满足不可伪造性.

3 PVDB - EL方案的描述

3 . 1 算法详细设计

在本节中,对PVDB-EL方案中的5个多项式时间算法即初始化算法、数据查询算法、公共可验证算法、数据更新算法、数据库更新算法进行详细的设计和描述.

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

该算法用于生成密钥以及对数据库进行编码.算法的主要步骤如下:

λ 为安全参数,数据库 D ={( i , v i )}(1≤ i n , n = poly ( λ )),其中 i ∈( q , n ]时 v i =0( q ∈[1, n ]).数据拥有者将数据库外包到服务器.首先生成一个 λ 位的素数 p ,再生成 p 阶循环群 G G T ,及双线性映射函数 e .

② 随机选择种子 k 并利用伪随机函数 F k ( i )= z i p 生成 z i ,取 G 中生成元 g ,计算 i ∈[1, n ]),利用 s i 计算

③ 随机选择参数 α p ,并计算 pk = g α .

④ 令辅助信息 aux 包括数据库内存储的数据,则 aux =( v 1, v 2,…, v n ),其中 v i =0( q < i n ),公共参数 pp =( g , k ).

⑤ 输出公钥 PK =( pp , C , pk ),私钥 SK = α ,对数据库 D 进行编码得到 S =( pp , aux , D ).

2) 数据查询算法Query( PK , S , i )→( v i , P i )

该算法用于返回客户查询的数据及用于验证该数据完整性的证据.算法的主要步骤如下:

① 以位置 i 为输入,根据 v i = D ( i ),服务器返回 v i 的值.

② 计算位置 i 处数据的证据 P i = .

3) 公共可验证算法Verify( PK , i , v i , P i )→{0,1}

该算法利用服务器返回的证据,验证所查询数据是否正确.算法的主要步骤如下:

① 利用公钥 PK 、位置 i 、服务器返回的数据 v i 、证据 P i 及双线性映射 e 来验证等式

(1)

是否成立.

② 如果式(1)成立,则该算法接受结果 v i ,输出1;反之拒绝结果 v i 并且输出0.

4) 数据更新算法

该算法用于返回更新后的公钥及相关更新信息.算法的主要步骤如下:

① 位置 i 处的数据由 v i 更新为 重新计算 C ′= C × .

② 数据更新包括3种情况:修改数据、添加数据以及删除数据.其中,添加数据时令 i ∈( q , n ];删除数据时令

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

④ 更新相关信息.令 利用私钥 SK 使用一种安全签名方案 Sign 对更新信息进行签名,得到 Sign SK ( U ).

⑤ 输出

5) 数据库更新算法

该算法用于更新数据库记录.算法的主要步骤如下:

① 根据 Sign SK ( U )的信息,验证签名是否正确,即验证更新请求是否来自数据拥有者.

② 若验证签名正确,则将数据库位置 i 处的记录修改为

3 . 2 方案详细设计

本节将通过对数据拥有者、客户和服务器这3个实体间的交互对方案的详细设计进行描述.

1) 在初始化阶段,数据拥有者首先选定待外包的数据库,然后运行算法Setup(1 λ , D )为系统生成密钥以及数据库的编码.对于已选定的数据库,数据拥有者将通过编码的方式来保证数据库内数据的机密性.

2) 数据拥有者将编码后的数据库外包到服务器,将私钥自己留存,把公钥发送给客户和服务器.

3) 当客户(包括数据拥有者在内)想要对服务器中的数据库进行查询时,运行Query( PK , S , i )算法来查询位置 i 处对应的数据.算法返回数据 v i 及用于验证该数据完整性的证据给客户.

4) 客户在接收到数据及证据后,将利用Verify( PK , i , v i , P i )算法对数据的完整性进行验证.若验证通过,则接受 v i ,反之拒绝 v i .

5) 当需要对外包的数据库进行更新时,由数据拥有者运行 算法,将生成更新后的公钥及相关更新信息.

6) 服务器在接收到数据拥有者的更新请求后,运行 算法对数据库内存储的数据进行更新.

4 正确性及安全性证明

4 . 1 正确性证明

定理1 . 如果方案步骤都是正确执行,产生的结果都是按照正确步骤执行得到、没有被恶意篡改的,则客户端将以极大概率接受结果,即客户端执行验证算法Verify( PK , i , v i , P i )→1.

证明. 正确执行Setup(1 λ , D )→( PK , SK , S )以及Query( PK , S , i )→( v i , P i ),利用得到的 PK , i , v i , P i 进行验证.验证过程如下:

因此Verify( PK , i , v i , P i )→1,定理1成立,方案满足正确性.

证毕.

4 . 2 安全性证明

定理2 . 如果存在一个敌手A可以在不可忽略的概率多项式时间内赢得安全游戏Π,那么就存在一个有效算法B能够以不可忽略的概率解决Square-CDH问题.

证明. 为了证明针对数据库内的同一位置,敌手A不能返回给客户2个不同的数据,接下来先证明如何构建一个有效的算法B来使A能够以不可忽略的概率解决Square-CDH问题.

Setup: B执行Setup算法,得到 并把公钥 PK 以及数据库编码 S 发送给A.

Phase1: A对B进行查询.A发送数据位置 i 给B,B返回位置对应的数据值 v i .A对B进行了 j 次(1≤ j T , T = poly ( λ ))更新查询,为了回答这些更新查询,针对每一次查询,B进行一次Client-Update更新算法,并将更新后得到的数据 i j 发送至A.

Challenge: 游戏的最后,A对于特定位置 i * 返回一个伪造的结果 v * 及伪造的证据 P * .如果A赢得了安全游戏,则Verify( PK , i * , v * , P * )输出为1,并且有 v * ≠⊥且 v * ,这里 代表的是经过 T 次更新查询后数据库中位置 i * 对应的正确数据.

B利用Query算法计算得到真实的证据 P i * ,并且输出( C , i * , , v * , P i * , P * ).由于A打破了可验证数据库的安全性,则一定存在Verify( PK , i * , v * , P * )→1.

由于 v * P * P i * 都能在位置 i * 验证通过,则有:

e ( C , s x * )= e ( , s x * ) e ( P x * , g )=

s i * = g α ,则化简得到:

e ( P i * , g ),
P i * , g ),
P i * , g ),
P i *
g α 2 =( P *

由此可以计算出 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 ( n 2 ),会随着数据库的增大呈幂增长,而本文所提方案构造了常量大小的公共参数,减小了客户的存储负担;本方案查询算法的计算代价同文献[17-18]一样,优于文献[16];本方案验证算法的计算代价虽略逊于文献[16-17],却优于文献[18];客户更新算法的计算代价与文献[17]相同,优于文献[16,18].

综合以上对比,本文所提方案在功能及性能方面整体上优于对比方案.

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

PerformanceRef[16]Ref[17]Ref[18]Our SchemeComputational ModelAmortized ModelAmortized ModelAmortized ModelAmortized ModelBilinear GroupsComposite OrderPrime OrderPrime OrderPrime OrderComputational AssumptionSubgroup MemberSquare-CDHSquare-CDHSquare-CDHPublic VerifiabilityNoYesYesYesData Insertion∕DeletionNoNoYesYesClient Storage SizeO(1)O(n2)O(n2)O(1)Query Computation(n-1)M+2P(n-1)(M+E)(n-1)(M+E)(n-1)(M+E)Verify Computation4M+3E+1P1M+1E+1I+2P2M+1E+1I+4P1M+2E+3PClientUpdate Computation2M+3E+1P1M+1E2M+(L+1)E+1I1M+1E

5 . 2 效率分析

由于本方案在功能方面优于文献[16],因此在本节中通过相关实验,分别对本方案及文献[17-18]中方案的存储开销、验证效率以及更新效率进行测试、对比与分析.实验采用JPBC库实现双线性群的初始化,对大小为[5 000,40 000]的数据集分别进行了测试,测试的每一个数据结果均是10次运行结果的平均值,其中排除了明显错误的数据.运行实验程序的计算机配有Intel ® Core TM i3-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 ( n 2 ),当数据库增大时,客户查询更新和验证等操作开销将会变得很大.本方案中客户在公共参数 pp 中不需要存储所有的参数 s i ,只需要存储 g 以及伪随机函数的种子 k ,存储开销为 O (1).利用这2个参数,可以计算出 C ,最终得到公钥.在验证服务器返回的数据时,客户只需要利用 g k 生成特定的 s i 来验证返回结果是否正确.本方案公共参数 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

本文深入系统地研究了国内外关于外包数据库查询结果完整性的相关方案,总结各方案的优缺点,并进一步研究了可验证数据库相关理论,提出了一个可有效更新的低存储开销公共可验证数据库方案.文中给出了方案的形式化定义以及证据的生成、查询结果的验证和数据的更新方法,同时给出了正确性及安全性分析与证明.与已有方案相比,该方案基于素数阶双线性群,提高了计算效率,并在初始化阶段构造了独立于数据库大小的公共参数,减小了客户的存储开销.同时,方案验证无需私钥参与,从而实现了公共可验证.该方案不仅支持对数据进行修改,还支持对数据的插入及删除操作.性能分析表明方案满足客户查询、更新和验证等操作开销独立于数据库大小,因此具有验证速度快、更新效率高的优势.该方案对于外包数据库查询结果完整性问题具有一定理论意义和实际应用价值.

参考文献

[1]Li Feifei, Hadjileftheriou M, Kollios G, et al. Authenticated index structures for outsourced databases[C] Proc of the 2006 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2006: 121-132

[2]Mykletun E, Narasimha M, Tsudik G. Authentication and integrity in outsourced databases[J]. ACM Trans on Storage, 2006, 2(2): 107-138

[3]Zhang Min, Hong Cheng, Chen Chi. Server transparent query authentication of outsourced database[J]. Journal of Computer Research and Development, 2010, 47(1): 182-190 (in Chinese)

(张敏, 洪澄, 陈驰. 一种服务器透明的外包数据库查询验证方法[J]. 计算机研究与发展, 2010, 47(1): 182-190)

[4]Papamanthou C, Tamassia R. Time and space efficient algorithms for two-party authenticated data structures[C] Proc of the 9th Int Conf on Information and Communications Security. Berlin: Springer, 2007: 1-15

[5]Tamassia R, Triandopoulos N. Certification and authentication of data structures[C OL] Proc of the 4th Alberto Mendelzon Int Workshop on Foundations of Data Management. 2010[2010-05-20]. http: ceur-ws.org

[6]Martel C, Nuckolls G, Devanbu P, et al. A general model for authenticated data structures[J]. Algorithmica, 2004, 39(1): 21-41

[7]Naor M, Nissim K. Certificate revocation and certificate update[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(4): 561-570

[8]Zhang Yupeng, Katz J, Papamanthou C. IntegriDB: Verifiable SQL for outsourced databases[C] Proc of the 22nd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2015: 1480-1491

[9]Xian Hequn, Feng Dengguo. An integrity checking scheme in outsourced database model[J]. Journal of Computer Research and Development, 2010, 47(6): 1107-1115 (in Chinere)

(咸鹤群, 冯登国. 外包数据库模型中的完整性检测方案[J]. 计算机研究与发展, 2010, 47(6): 1107-1115)

[10]Zhou Rui. Study of outsourced data query authentication technology in cloud computing[D]. Guangzhou: Jinan University, 2015 (in Chinese)

(周锐. 云计算下外包数据查询验证技术的研究[D]. 广州: 暨南大学, 2015)

[11]Wang Jianfeng. Study on efficient search and secure audit for outsourced data in cloud computing[D]. Xi’an: Xidian University, 2016 (in Chinese)

(王剑锋. 云环境下外包数据的高效检索及安全审计技术研究[D]. 西安: 西安电子科技大学, 2016)

[12]Wang Jianfeng, Chen Xiaofeng, Huang Xinyi, et al. Verifiable auditing for outsourced database in cloud computing[J]. IEEE Trans on Computers, 2015, 64(11): 3293-3303

[13]Camenisch J, Lysyanskaya A. Dynamic accumulators and application to efficient revocation of anonymous credentials[C] Proc of the 22nd Annual Int Cryptology Conf. Berlin: Springer, 2002: 61-76

[14]Camenisch J, Kohlweiss M, Soriente C. An accumulator based on bilinear maps and efficient revocation for anonymous credentials[C] Proc of the 12th Int Workshop on Public Key Cryptography. Berlin: Springer, 2009: 481-500

[15]Nguyen L. Accumulators from bilinear pairings and applications[C] Proc of the 5th Int Conf on Topics in Cryptology. Berlin: Springer, 2005: 275-292

[16]Benabbas S, Gennaro R, Vahlis Y. Verifiable delegation of computation over large datasets[C] Proc of the 31st Annual Int Cryptology Conf. Berlin: Springer, 2011: 111-131

[17]Catalano D, Fiore D. Vector commitments and their applications[C] Proc of the 16th Int Conf on Practice and Theory in Public-Key Cryptography. Berlin: Springer, 2013: 55-72

[18]Miao Meixia, Wang Jianfeng, Ma Jianfeng, et al. Publicly verifiable databases with efficient insertion deletion operations[J]. Journal of Computer and System Sciences, 2017, 86: 49-58

[19]Bao Feng, Deng R H, Zhu Huafei. Variations of Diffie-Hellman problem[C] Proc of the 5th Int Conf on Information and Communications Security. Berlin: Springer, 2003: 301-312

Wu Qiyu , 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.

Zhou Fucai , 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.

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

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

Publicly Verifiable Databases Scheme with Efficient Updates and Low Storage Overhead

Wu Qiyu, Zhou Fucai, Wang Qiang, and Li Yuxi

( Software College , Northeastern University , Shenyang 110169)

Abstract Aiming at the computational efficiency of outsourcing database and the completeness of query results, we propose a publicly verifiable database model with efficient updates and low storage overhead. Its description and security model are formalized, besides, a specific publicly verifiable database scheme with efficient updates and low storage overhead using the prime order bilinear groups is also proposed. Our scheme allows a resource-constrained client to securely outsource a very large database to a professional database service provider so that it could later retrieve or update a database record and verify the integrity of the retrieved data. The security of our scheme can be reduced to the hardness of the Square-CDH problem. Compared with the existing schemes, our scheme improves the computational efficiency by using the prime order bilinear groups. We construct the constant size parameter which is independent of the database that reduces the storage overhead of the client. In the meanwhile, the verification phase in the scheme does not require the data owner’s private key so it can be publicly verifiable. In addition, our scheme not only supports the modification of data, but also supports the insertion and deletion on data. The performance analysis shows that the cost of query, verification and update is independent of the database size.

Key words verifiable database; public verifiability; outsourcing storage; constant size; bilinear map

中图法分类号 TP309

通信作者 周福才(fczhou@mail.neu.edu.cn)

基金项目 国家自然科学基金项目(61772127);中央高校基本科研业务费专项资金项目(N171704005)

This work was supported by the National Natural Science Foundation of China (61772127) and the Fundamental Research Funds for the Central Universities (N171704005).

收稿日期 2017-05-12;

修回日期: 2017-08-29

DOI: 10.7544/issn1000-1239.2018.20170320