基于双线性映射的支持全操作的公共可验证外包数据库模型

随着云计算的发展，数据库外包服务[1]成为近些年新兴的一种应用模式.越来越多资源受限的客户或企业为了节约硬件存储资源和管理成本，取消自己的数据中心，将数据库外包给专业的数据库服务提供商[2]进行管理和维护.但是数据外包后，数据拥有者丧失了对数据的直接控制[3]，云服务器可能会篡改数据库的内容或伪造查询结果来减少响应的时间和计算代价，因此研究外包数据库查询结果的完整性问题具有重要意义.

目前，为解决外包数据库的查询结果完整性验证问题，国内外学者展开了大量的研究，主要分为3类：基于数字签名的[4-7]、基于认证数据结构的[8-16]、基于可验证计算的[17-25].1)使用数字签名技术的方法[4-7]中，数据拥有者需要对外包数据库中的每个元组进行签名，客户查询时，服务器需返回查询结果和查询结果中每个元组所对应的签名.但是该类方法存在的问题是验证和更新的代价较高，且只支持范围查询.2)基于认证数据结构的方法是对基于数字签名方法的改进，通常是基于认证树和累加器的.基于认证树[8,11-12,14-15]不需要对每一条元组进行签名，而是先对元组排序，再使用Hash函数计算出树中每个节点的Hash值，最终对树的根节点签名，客户使用认证路径和根节点签名值进行验证.但是该类方法存在的问题是由于叶子节点是排序好的元组的Hash值，任何一次更新都可能破坏已有认证数据结构，更新代价较高.认证路径随元组的数量呈对数级增长，只支持范围和元素隶属关系的查询.另一种基于累加器的[9-10,13]，只支持集合交集、并集、差集及元素隶属关系的查询，不支持求和、计数、范围，最大值和最小值查询.此外，文献[16]提出了一种基于可翻转的布隆过滤器的外包数据库验证方案，该方案虽解决了数据更新操作时额外的计算开销，但布隆过滤器存在误算率，会导致查询结果的精准性.3)基于可验证计算的方法分为2类：①针对特定查询类型的[17-19]；②针对通用方案的[20-25].前者的效率优于后者，但是查询类型单一.例如Papadopoulos等人[19]基于双线性映射累加器提出了支持多维范围查询的完整性验证的方案，该方案只支持多维范围查询且不支持高效地更新数据.针对通用方案的可分为2类：基于电路的[20-21]和基于RAM(random access memory)模型的[22-25].两者均是将外包库编译到程序中(表示成一个布尔/算数电路，或者是基于RAM模型进行计算)，在编译好的程序中输入查询语句，返回与之对应的结果.这2种方法计算代价高并不实用.基于电路的方法效率低，程序中电路的大小至少与数据库本身一样大，不支持嵌套查询，每进行更新操作都需要重新编码.基于RAM模型支持全部查询操作，但是编码难度较高和性能较差.

综上所述，现有的方案存在的问题：1)查询类型单一不支持全操作；2)证据随查询结果呈线性或对数增长；3)验证和更新代价较高；4)方案的整体效率低下难以应用.

针对上述问题，本文提出了一个基于双线性映射的支持全操作的公共可验证外包数据库(publicly verifiable database model with full operations based on bilinear map, BMPVDB)模型，该模型具有3个特点：

1) 功能全面(全操作).该模型支持的查询操作全面，包含了交集、并集、补集等各种集合操作，求和、计数、最小值、最大值、范围查询以及嵌套查询操作.

2) 高效.验证代价为常数级，独立于外包数据库的大小和查询的中间结果.证据大小只依赖于查询语句分解为单个查询语句的数量，不依赖于外包数据库和中间结果的大小.更新的代价为常数级，不依赖于外包数据库和中间结果的大小.

3) 公共可验证、公共可更新.任何客户拥有公钥和摘要都能对查询结果进行完整性验证.任何一个被数据拥有者授权的客户无需私钥参与就能对外包的数据进行更新.

1 相关知识

1.1 双线性映射

双线性映射指的是2个循环群之间相对应的线性映射关系.定义一个概率多项式时间双线性映射生成算法(e,g,G,GT,p)←BMGen(1λ)生成双线性映射e:G×G→GT，其中p为λ比特的素数，G和GT均为p阶乘法循环群，g为群G的生成元，双线性映射e满足3个性质：

1) 双线性.对于任意的a,b∈

p和P,Q∈G，均满足e(Pa,Qb)=e(P,Q)ab.

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

3) 可计算性.对于任意的P,Q∈G，都存在有效的算法计算出e(P,Q).

双线性映射可通过超奇异椭圆曲线上的Weil和Tate配对来进行构造.

1.2 多项式分解定理

对于任意的n元多项式f(x1,x2,…,xn)，给定输入(a1,a2,…,an)，则多项式f(x1,x2,…,xn)-f(a1,a2,…,an)可表示为

1.3 泰勒展开式

若函数f(x)在包含x0的某个闭区间[a,b]上具有n阶导数，且在开区间(a,b)上具有(n+1)阶导数，则对闭区间[a,b]上任意一点x，均有:

其中,f(i)(x)为f(x)的i阶导数，Rn(x)为泰勒公式的余项，是(x-x0)n的高阶无穷小.

1.4 双线性q -阶强判定性Diffie-Hellman假设[26]

双线性q -阶强判定性Diffie-Hellman困难性假设(bilinear q -strong Diffie-Hellman, q -BSDH)，给定(e,g,G,GT,p)←BMGen(1λ)和q元组(gα,…,gαq)，不存在一个概率多项式算法A能以不可忽略的概率输出(c,h)，使得h=e(g,g)(α+c)-1.其形式化定义为

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

1.5 变体的双线性Diffie-Hellman指数假设[27]

变体的双线性Diffie-Hellman指数困难性假设(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]),不存在一个概率多项式算法A能以不可忽略的概率输出(G(·),h)，使得h=e(g,g)G(α)βq.其形式化定义为

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

2 BMPVDB模型

本节主要介绍了基于双线性映射的支持全操作的公共可验证外包数据库BMPVDB模型.首先给出了模型的架构及交互流程，然后对模型进行了形式化定义，最后针对模型应满足的不同安全需求给出了安全性定义.

2.1 BMPVDB模型的架构

BMPVDB模型中包含数据拥有者、客户、云服务器3方实体，其中数据拥有者和客户是可信的，云服务器是不可信的.其模型架构图如图1所示：

数据拥有者首先执行密钥生成算法生成公私钥对，其中公钥主要用于生成和验证证据，私钥主要用于对外包数据库的更新.然后执行初始化算法生成外包数据库摘要.将数据库外包到云服务器进行存储和管理，同时将公钥发送给云服务器.然后将公钥和摘要发送给客户.当客户向云服务器发起查询请求后，云服务器返回查询的结果和证据.客户利用本地储存的公钥、摘要及云服务器返回的证据对结果进行验证.该模型中云服务是不可信的，可能篡改查询的结果.为保证查询结果的完整性，云服务器在返回查询结果的同时，还将返回相应的证据供客户验证.验证时涉及公钥和摘要，且均为公开的，因此该方案支持公共可验证，即拥有公钥的客户都可对查询的结果进行验证.

2.2 BMPVDB的形式化定义

该模型可用五元组表示为{KeyGen,Setup,Query,Verify,Update}，五元组中每个元组都代表一个多项式时间算法.5个算法具体描述如下：

1) 密钥生成算法(PK,SK)←KeyGen(1λ).输入安全参数λ，数据拥有者执行该算法生成公私钥对(PK,SK).其中私钥SK被数据拥有者私密保存，公钥PK被公开.

2) 初始化算法σDB←Setup(PK,DB).数据拥有者将公钥PK和外包数据库DB作为输入，调用该算法得到数据库摘要σDB，最后公开σDB.

3) 查询算法(R,π)←Query(Q,PK,DB).云服务器将公钥PK，外包数据库DB和客户给定的查询Q输入至该算法，算法输出查询的结果R及证据π.

4) 验证算法{‘1’ or ‘0’}←Verify(PK,σDB,R,π).客户对云服务器返回的结果进行验证.算法输出‘1’表示验证通过，接受查询结果R，否则输出‘0’，拒绝查询结果R.

5) 更新算法

数据拥有者给定外包数据库摘要σDB，更新信息upd∈{(ADD,x),(REMOVE,x),(MODIFY,x)}和私钥SK，执行该算法输出更新后的摘要

2.3 BMPVDB的正确性及安全性定义

模型的正确性简单来说，当模型中每个算法都正确执行，验证算法Verify始终输出‘1’，即永远不会拒绝一个正确的查询结果.其形式化定义为

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

模型的安全性是针对不可信云服务器来说的.简单来说，云服务器伪造一个恶意的结果和证据始终不能通过验证.下面通过构造敌手A和挑战者C之间的安全性实验∑来定义该模型的安全性.

对于任意的查询Q，敌手A试图通过4个步骤来伪造一个查询结果和证据并通过验证：

1) 给定安全参数λ，C执行算法KeyGen生成公私钥对(PK,SK)，并将PK发送给A，私钥SK私密保留.

2) 敌手A选定一个外包数据库DB，并将DB发送给挑战者C.

3) 挑战者C在接收到DB后，执行算法Setup，生成外包数据库DB的摘要σDB.

4) 敌手A可向挑战者C发起多项式poly(λ)次更新与查询：

更新.A选定更新操作upd，将upd发送给C.C

执行算法Update后，将更新的摘要

发送给A.

查询.A对于查询Q伪造一个结果R*和证据π*.如果算法Verify(PK,σDB,R*,π*)输出‘1’，敌手获胜.

对于任意一个概率多项式时间的敌手A，如果A在上述安全性实验∑中获胜的概率是可忽略的，则称BMPVDB是安全的.

3 BMPVDB模型的实施方案

本节主要介绍了基于双线性映射的支持全操作的公共可验证外包数据库BMPVDB模型的实施方案.首先给出了该模型实施方案的总体描述及核心思想，然后给出了该模型实施方案中各算法的详细设计，并给出了安全性证明.最后给出了该模型实施方案的扩展及应用.

3.1 BMPVDB模型实施方案的总体描述

对数据库任意查询操作都可看成对表中行或列的操作，而数据库表中每行或每列所包含的元素均可看作一个集合，因此对数据库的查询就相当于对集合的操作.从查询输入和输出的类型可以将查询分成5类：

1) 输入2个集合输出1个集合，该类型的查询对应于交集∩、并集∪、差集\和对称差集Δ.

2) 输入输出均为一个集合，该类型的查询对应于补集和范围查询RANGE.

3) 输入一个集合输出一个整数，该类型的查询包含最大值MAX、最小值MIN、计数COUNT和求和SUM.

4) 输入一个集合输出为一个布尔值，该类型的查询包含了属于∈x和不属于∉x.

5) 嵌套查询，该类型查询是上述4种类型查询的自由组合.

在本方案中类型1和类型2中所包含的查询均可通过交集查询来实现(详见3.2节)，范围查询可通过最大值，最小值和集合操作来实现详见(详见3.2节)，嵌套查询可通过复合上述4种类型查询来实现详见(详见3.2节)，下面将重点介绍集合交集、最大值、最小值、求和、计数.

为了便于表述，假定集合X={1,2,3},Y={2,3,4} ⊆

交集I=X∩Y={2,3}.分别计算X,Y的摘要

和

其中α,β为从域

中随机选取的2元素，在本方案中当作私钥.对于交集查询，σX (α)和σY(β,α)指数的乘积为

(α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(β,α).

不难看出上述多项式中βiαq项中的i所组成的集合就是交集的结果.为保证结果的正确性，将σI(β)和gQ(β,α)当作证据.客户通过验证e(σX (α),σY(β,α))=e(σI(β),gαq)e(g,gQ(β,α))和

为了便于描述，令X (α)=α1+α2+α3.X (1)为对集合X计数查询的结果.X′(1)为对集合X求和查询的结果.多项式X (α)中最小指数值为最小值查询的结果.多项式X (α)中最大指数值为最大值查询的结果.

3.2 BMPVDB模型实施方案的详细设计及安全性证明

本节首先详细介绍了基于双线性映射的支持全操作的公共可验证外包数据库方案中密钥生成算法，初始化算法和更新算法.然后给出了不同查询类型下的查询算法与验证算法的具体构造，并进行了安全性证明.下面分别对其进行描述.

1) 密钥生成算法(PK,SK)←KeyGen(1λ).该算法用于生成公私钥对(PK,SK).算法的主要步骤为：

① 从

随机选取2个随机数α和β作为SK.

② 给定安全参数λ，调用算法BMGen生成(e,g,G,GT,p).

③ 对于所有的i，j∈

q，计算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])当作公钥PK.

2) 初始化算法σX←Setup(PK,X).该算法主要用于计算集合X的摘要.算法主要步骤为:

① 根据公钥PK计算σX (α)和σX (β,α)，其中

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

3) 更新算法

该算法主要用于更新摘要.当upd=(ADD,x)时，计算

和

返回更新后的摘要

当upd=(REMOVE,x)，计算

gαx和

σX(β,α)

gβxαq-x，返回更新后的摘要

当upd=(MODIFY,x)，可通过上述2种操作实现.

4) 查询与验证算法

查询算法用于返回查询的结果和证据.验证算法用于验证查询结果的正确性.

(i) 计算出集合X，Y交集的结果I.

(ii) 根据集合X，I和Y中元素，求得多项式

(iii) 求得多项式

(iv) 根据公钥PK，计算出证据π=(gI(β),gQ(β,α))，返回I和π.说明：如果证据π中包含2个元素，则令π=(π[0],π[1]).

(i) 利用查询返回的结果I，计算

验证等式σI(β)=π[0]是否成立.如果不成立，拒绝结果I，输出‘0’，否则继续进行.

(ii) 根据公钥PK，σX(α)，σY(β,α)和证据π来验证下列等式是否成立：

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

(iii) 如果等式成立，则接受交集查询的结果I，输出‘1’，否则拒绝结果I，输出‘0’.

安全性证明见定理1：

定理1. 如果在概率多项式时间内存在一个敌手A能以不可忽略的概率伪造出错误的结果I*和证据π*=(g∑aiβi,g∑bi,jαiβj)通过验证(即赢得安全性实验∑)，那么任意一个敌手A能找到一个有效的算法B解决VBDHE难题和q -BSDH难题.

证明. 因为A伪造的结果及证据通过验证，则有:

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

对于正确的结果和证据，则有:

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

由式(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)⟺

令G(β)=I(β)-∑aiβi，如果I(β)≠∑aiβi，可求得gG(β)αq=g∑bi,jαiβj-Q(β,α)，因此A可找到有效的算法B解决VBDHE问题.又因为该问题是难解的，所以I(β)≠∑aiβi不成立，故有π*[0]=π[0]且I≠I*.令xmin为I∪I*中最小元素，因为π*[0]=π[0]，所以:

式(3)右边提供了有效的算法B解决q -BSDH问题.又因为该问题是难解的，所以π*[0]=π[0]且I ≠I*不成立.

综上，在概率多项式时间内A难以以不可忽略的概率赢得安全性实验∑，因此该方案是安全的.

② 其他集合操作

集合的其他操作可通过交集来实现[28]，其查询算法，验证算法和安全性证明均与交集相似，这里将不在赘述，只给出验证查询结果正确性的等式.

(i) 并集Z=X ∪Y(Z=X ∪(Y width=8,height=14,dpi=110

I)，验证等式：

(ii) 差集D=X\Y(D=X∩I)，验证等式：

(iii) 对称补集S=X ΔY(S=X width=8,height=14,dpi=110

I)∪(Y

I)，验证等式：

(iv) 补集

其中U=[q-1])，验证等式：

(v) 子集X⊆Y(X =X∩Y)，验证等式：

(vi) 属于x∈X ({x}=X∩(x))，验证等式：

(vii) 不属于x∉X (∅=X∩(x))，验证等式:

(i) 根据集合X中的元素，求得

计算X (1)或者统计X中的元素个数作为计数查询的结果R=count(X).

(iii) 根据多项式分解定理(详见1.2节)，计算出多项式Q(x)=(X (x)-X (1)) width=8,height=14,dpi=110

(x-1).

(iv) 根据公钥PK，计算出证据π=gQ(α)，并返回R和π.

(i) 利用查询返回的结果R，计算gR.

(ii) 根据公钥PK，σX (α)和证据π来验证下列等式是否成立：

(iii) 如果等式成立，则接受交集查询的结果R，输出‘1’，否则拒绝结果R，输出‘0’.

安全性证明见定理2：

定理2. 如果在概率多项式时间内存在一个敌手A能以不可忽略的概率伪造出错误的结果R*和证据π*通过验证(即赢得安全性实验∑)，那么任意一个敌手A能找到一个有效的算法B解决q -BSDH难题.

证明. 因为A伪造的结果及证据通过验证，则有:

对于正确的结果和证据，则有:

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

e(g,gR*)e(gQ*(α),gα-1)=
e(g,gR)e(gQ(α),gα-1)⟺
e(g,g)(α-1)(Q*(α)-Q(α))=e(g,g)R-R*⟺

式(6)右边提供了有效的算法B解决q -BSDH问题.又因为该问题是难解的，所以在概率多项式时间内A难以以不可忽略的概率赢得安全性实验∑，因此该方案是安全的.

(i) 根据集合X中的元素，求得

计算X′(1)或者对X中的元素求和作为计数查询的结果R=sum(X).

(iii) 计算X (1)，根据泰勒展开式(详见1.3节，其中n=2)，计算出多项式Q(x)=(X (x)-X (1)-X′(1)(x-1)) width=8,height=14,dpi=110

(x-1)2.

(iv) 根据公钥PK，计算出gQ(α)，将(X (1),gQ(α))作为证据π，返回R和π.

(i) 利用查询返回的结果R，计算gR.

(ii) 根据公钥PK，σX (α)和证据π来验证下列等式是否成立：

(iii) 如果等式成立，则接受交集查询的结果R，输出‘1’，否则拒绝结果R，输出‘0’.

安全性证明见定理3：

定理3. 如果在概率多项式时间内存在一个敌手A能以不可忽略的概率伪造出错误的结果R*和证据π*通过验证(即赢得安全性实验∑)，那么任意一个敌手A能找到一个有效的算法B解决q -BSDH难题.

证明. 因为A伪造的结果及证据通过验证，则有:

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),

对于正确的结果和证据，则有:

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)和式(8)可得：

e(gπ*[0]+R*×(α-1),g)e(π*[1],g(α-1)2)=
e(gπ[0]+R×(α-1),g)e(π[1],g(α-1)2)⟺
e(gπ*[0]+R*×(α-1),g)e(π*[1],g(α-1)2)=
e(gπ[0]+R×(α-1),g)e(gQ(α),g(α-1)2)⟺
e(gπ*[0]+R*×(α-1),g)e(π*[1],g(α-1)2)=
e(gπ[0]+R×(α-1)+Q(α)×(α-1)2,g)⟺
e(π*[1],g(α-1)2)=
e(g(π[0]-π*[0])+(R-R*)×(α-1)+Q(α)×(α-1)2,g)⟺

上式右边提供了有效的算法B解决q -BSDH问题.又因为该问题是难解的，所以在概率多项式时间内A难以以不可忽略的概率赢得安全性实验∑，因此该方案是安全的.

(i) 根据集合X中的元素，求得

(ii) 查看集合中最小元素或将多项式最小指数最为最小值查询的结果R=min(X).

(iii) 根据公钥PK，计算出证据π=g(X(α)-αR) width=8,height=14,dpi=110

αR+1，并返回R和π.

(i) 根据公钥PK，σX (α)，证据π和结果R来验证下列等式是否成立：

(ii) 如果等式成立，则接受交集查询的结果R，输出‘1’，否则拒绝结果R，输出‘0’.

安全性证明见定理4：

定理4. 如果在概率多项式时间内存在一个敌手A能以不可忽略的概率伪造出错误的结果R*和证据π*通过验证(即赢得安全性实验∑)，那么任意一个敌手A能找到一个有效的算法B解决q -BSDH难题.

证明. 如果敌手A伪造的结果及证据通过验证，则有：

当R*<R=min(X)时，由式(9)可得：

e(gαR*,g)=e(σX (α),g) width=8,height=14,dpi=110

e(π*,gαR*+1)⟺
e(g,g)1 width=8,height=14,dpi=110

α=e(σX (α),(gαR*+1)-1) width=8,height=14,dpi=110

e(π*,g).

当R*>R=min(X)时，定义U={i∈X:i<R}和W={i∈X:i≥R}.因为U∪W=X且U∩W=∅，故可得σX (α)=σU(α)×σW(α)，因此式(9)可得：

e(σX (α),g)=e(gαR*,g)e(π,gαR*+1)⟺
e(σU(α),g)e(σW(α),g)=e(gαR*,g)e(π,gαR*+1)⟺

⟺

因为U∩W=∅，可得αR是U(α)和W(α)最大公因子，再由广义欧几里德定理可得，存在2个多项式a(α)和b(α)，使得：

因此式(11)可得：

(i) 根据集合X中的元素，求得

(ii) 查看集合中最大元素或将多项式中关于y最大指数作为最大值查询的结果R=max(X).

(iii) 根据公钥PK，计算出证据π=g(X(β,α)-βRαq-R) width=8,height=14,dpi=110

αq-R+1，并返回R和π.

(i) 根据公钥PK，σX (α)，证据π和结果R来验证下列等式是否成立：

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

(ii) 如果等式成立，则接受交集查询的结果R，输出‘1’，否则拒绝结果R，输出‘0’.

最大值查询的安全性证明与最小值查询类似，因此不再赘述.

⑦ 范围查询range(l,r)

(i) 根据查询范围[l,r]，将被查询集合X分割成3个不相交集合U，V，W，其中U={i:i∈X,i<l}，V={i:i∈X,l≤i≤r}，U={i:i∈X,i>r}.

(ii) 分别调用集合U∩V，U∩W和V∩W查询算法返回对应的结果和证据.

(iii) 分别调用集合U和W的最大值和最小值查询算法返回对应的结果和证据.

(i) 分别调用集合U∩V，U∩W和V∩W验证算法，若验证失败，输出‘0’，否则，执行下一步.

(ii) 分别调用集合U和W的最大值和最小值验证算法，若验证失败，输出‘0’，否则，执行下一步.

(iii) 验证max(U)<l，min(V)≥l，max(V)≤r，min(W)>r.若成立，则接受查询结果R，输出‘1’，否则拒绝结果R，输出‘0’.

范围查询的安全性证明依赖于集合的交集、最大值和最小值查询的安全性，上文已证，因此不再赘述.

本方案是嵌套查询，查询时递归调用嵌套查询中的每个查询，但是无需返回中间的结果，只需返回中间结果的摘要和对应的证据.验证时，同样递归调用嵌套查询中的每个查询所对应的验证算法，验证查询结果的正确性.该查询的安全性依赖于上述各类查询的安全性，因此该查询也是安全的.

4 性能分析

4.1 方案对比

本节将本文所提方案与基于签名、基于RSA累加器、基于双线性映射累加器、基于电路和基于RAM的5类方案进行了对比.功能方面，主要比较了各类型方案中所支持的查询类型和是否支持更新操作.性能方面，主要从理论上比较了各类型方案中，初始化算法、查询算法、验证算法和更新算法的计算代价及证据的大小.比较结果如表1所示，其中n,|R|,d分别为外包数据集的大小，查询结果的大小，嵌套查询中分解为单个查询的数量，

从表1可看出，在功能方面上，只有本文所提出的方案和基于RAM的方案支持全操作即集合操作、求和、计数、最大值/最小值、范围、嵌套和更新操作.在性能方面上，在初始化算法上，本方案与基于签名、基于RAM、基于电路和基于RSA累加器的方案所消耗的代价相同均为O(n)，且优于基于双线性映射累加器的方案.在查询算法上，本方案与基于签名和基于RSA累加器的方案所消耗的代价相同均为O(n)，且优于其他3个方案.在验证算法上，由于本方案与基于RAM的方案支持嵌套查询，查询验证的时间与嵌套查询中分解为单个查询的数量d有关，且2类方案验证所消耗的代价相同均为O(d+|R|).在不进行嵌套查询时，验证的效率与其他4类相同均为O(|R|).在更新算法上，本方案所花费的代价为常数级，均优于其他方案.在不进行嵌套查询时，本方案中证据大小与其他方案中证据的大小相同均为O(1).在进行嵌套查询时，基于RAM方案中证据的大小小于本方案的大小.综合以上分析，理论上本文所提方案在功能及性能方面与基于RAM方案相似，整体上均优于其他方案.

4.2 效率分析

根据4.1节中方案的对比分析可知：基于签名的可验证外包数据库方案无论在功能上还是性能上都低于其他2类方法；基于认证数据结构的方法中，虽然在部分方案与基于可验证计算的方案中性能相近，但是前者所支持的操作远小于基于可验证计算方案所支持的操作.因此只与基于可验证计算的方案相比较.而在基于可验证计算的方案中，基于电路的方案所支持的查询操作不及基于RAM的方案丰富，且基于RAM的方案中SNARK方案[25]较高效.因此在实验分析中只与SNARK 方案进行对比.实验中，主机的配置为Intel® CoreTM i7-4770 3.40 GHz主频的处理器和32 GB内存，选定的安全参数λ=128，测试语句为嵌套查询语句count((X∩Y)∪(U ∩W))，其中每个集合大小相等均为n.数据集利用伪随机数生成器以时间戳为输入随机产生.每次执行时，数据集都不相同.保证了数据集的随机可靠性和程序的健壮性.对本方案和SNARK方案中的初始化算法的效率、查询算法的效率、验证算法的效率、证据的大小和云服务器所需的存储空间进行了测试、对比与分析.

两方案中初始化算法的效率比较结果如图2所示，横坐标为集合的大小，纵坐标为该算法运行的时间.将本方案运行时间放大10 000倍，仍远小于SNARK方案的运行时间.因此，在初始化算法上，虽然理论分析上两方案相近，但本方案更高效.

两方案查询算法的效率比较结果如图3所示，将本方案运行时间放大100倍，仍小于SNARK方案的运行时间.因此，在查询算法上，虽然理论分析上两方案相同，但本方案更高效.

两方案中验证算法的效率比较结果如图4示，两方案中验证效率均为常数级，不随集合大小增加而增大，且本方案验证效率小于SNARK方案.因此在验证算法上，虽然理论分析上两方案相近，但本方案更高效.在进行更新操作时，本方案在任意大小的数据下所消耗的时间大约为2.6 μs.由于SNARK对硬件要求较高，在现有的实验条件内未测出SNARK更新操作所需的精准时间，但实验表明了其所需时间要远大于本方案所需时间.此外，4.1节理论分析可知，更新时，SNARK的效率为Ω(log n)，本方案的效率为O(1)远小于SNARK的效率.基于以上2点，本方案中更新算法的效率远高于SNARK方案中更新算法的效率.

两方案中证据的大小比较结果如图5所示，两方案中证据的大小恒定不变，不随集合大小的增加而增加，且本方案中证据的大小小于SNARK方案.因此在证据的大小上，虽然理论分析上两方案相同，但本方案通信代价更低.

两方案中云服务器所需要的存储空间比较结果如图6所示，横坐标为集合的大小，纵坐标为云服务器所需的存储空间.将本方案所需的存储空间放大10倍，仍小于SNARK方案.因此本方案的数据膨胀率更低.

以上实验结果表明，本方案在初始化算法的效率、查询算法的效率、验证算法的效率、证据的大小及存储空间上均优于SNARK方案.因此本方案效率更高、通信代价更小、数据膨胀率更低，更适合应用于实际.

5 结论

针对现有可验证外包数据方案存在查询类型单一、效率低下、验证和更新代价较高，难以应用于实际等问题，深入系统地研究了国内外关于可验证外包数据库相关方案，并总结各方案的优缺点.在此基础上，基于双线性映射提出了一个支持全操作的公共可验证外包数据库方案，给出了该方案的形式化定义，正确性及安全性定义.然后给出了方案的构建，并证明了方案的安全性.最后将本方案与已有方案相比较，理论与实验分析表明该方案功能更全面性，效率更高，数据的膨胀率更低，更新计算代价更低.本方案中数据的验证和更新不依赖于私钥，实现了公共可验证和公共可更新.因此本方案对外包数据库查询结果完整性问题的研究具有一定的理论意义和实践价值.

[1]Li Jingwei, Squicciarini A C, Lin Dan, et al. MMBcloud -Tree: Authenticated index for verifiable cloud service selection[J]. IEEE Transactions on Dependable and Secure Computing, 2017, 14(2): 185-198

[2]Khan S, Gani A, Wahab A W A, et al. Cloud log forensics: Foundations, state of the art, and future directions[J]. ACM Computing Surveys, 2016, 49(1): 1-42

[3]Kellaris G, Kollios G, Nissim K, et al. Generic attacks on secure outsourced databases[C]//Proc of the 23rd ACM Conf on Computer and Communications Security. New York: ACM, 2016: 1329-1340

[4]Mykletun E, Narasimha M, Tsudik G. Signature bouquets: Immutability for aggregated/condensed signatures[C]//Proc of the 9th European Symp on Research in Computer Security. Berlin: Springer, 2004: 160-176

[5]Jang M, Yoon M, Song Y, et al. A signature-based data authentication method with bitmap-based transformed datain database outsourcing[J]. Procedia Computer Science, 2015, 52(1): 680-684

[6]Yang Yin, Papadias D, Papadopoulos S, et al. Authenticated join processing in outsourced databases[C]//Proc of ACM SIGMOD’09. New York: ACM, 2009: 5-18

[7]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)

[8]Miller A J, Hicks M, Katz J, et al. Authenticated data structures, generically[J]. ACM SIGPLAN Notices, 2014, 49(1): 411-423

[9]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

[10]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 Practice and Theory in Public Key Cryptography. Berlin: Springer, 2009: 481-500

[11]Niaz M S, Saake G. Merkle hash tree based techniques for data integrity of outsourced data[C]//Proc of the 27th GI-Workshop on Foundations of Databases. Volkse, Germany: Workshop Grundlagen von Datenbanken, 2015: 66-71

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

[13]Papamanthou C, Tamassia R, Triandopoulos N. Optimal verification of operations on dynamic sets[C]//Proc of the 31st Annual Int Cryptology Conf. Berlin: Springer, 2011: 91-110

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

[15]Zhou Rui. Study of outsourced data query authentication technology in cloud computing[D]. Guangzhou: Jinan University, 2015 (in Chinese)(周锐. 云计算下外包数据查询验证技术的研究[D]. 广州: 暨南大学, 2015)

[16]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)

[17]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

[18]Azraoui M, Elkhiyaoui K, Onen M, et al. Publicly verifiable conjunctive keyword search in outsourced databases[C]//Proc of IEEE CNS’15. Piscataway, NJ: IEEE, 2015: 619-627

[19]Papadopoulos D, Papadopoulos S, Triandopoulos N. Taking authenticated range queries to arbitrary dimensions[C]//Proc of the 21st ACM Conf on Computer and Communications Security. New York: ACM, 2014: 819-830

[20]Costello C, Fournet C, Howell J, et al. Geppetto: Versatile verifiable computation[C]//Proc of the 36th IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2015: 253-270

[21]Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[C]//Proc of the 34th IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2013: 238-252

[22]Braun B, Feldman A J, Ren Zuocheng, et al. Verifying computations with state[C]//Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 341-357

[23]Bensasson E, Chiesa A, Tromer E, et al. Scalable zero knowledge via cycles of elliptic curves[C]//Proc of the 34th Annual Int Cryptology Conf. Berlin: Springer, 2014: 276-294

[24]Bensasson E, Chiesa A, Genkin D, et al. SNARKs for C: Verifying program executions succinctly and in zero knowledge[C]//Proc of the 33rd Annual Int Cryptology Conf. Berlin: Springer, 2013: 90-108

[25]Bensasson E, Chiesa A, Tromer E, et al. Succinct non-interactive zero knowledge for a von Neumann architecture[C]//Proc of the 23rd USENIX Security Symp. Berkeley, CA: USENIX Association, 2014: 781-796

[26]Boneh D, Boyen X. Short signatures without random oracles and the SDH assumption in bilinear groups[J]. Journal of Cryptology, 2008, 21(2): 149-177

[27]Boneh D, Boyen X, Goh E J. Hierarchical identity based encryption with constant size ciphertext[C]//Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 440-456

[28]Papamanthou C, Tamassia R, Triandopoulos N. Optimal verification of operations on dynamic sets[C]//Proc of the 31st Annual Int Cryptology Conf. Berlin: Springer, 2011: 91-110