Page 240 - 《软件学报》2021年第12期

3904 Journal of Software 软件学报 Vol.32, No.12, December 2021

可信第三方首先执行初始化算法生成公共参数,并将其分发给数据拥有者、授权的用户以及云服务器.数
据拥有者在外包数据库之前,利用可信第三方生成的公共参数执行密钥生成算法生成密钥,包括数据库的查询
密钥、验证密钥的计算密钥、验证密钥的恢复密钥和验证密钥的检索密钥,并将验证密钥的计算密钥发送给云
服务器.云服务器执行验证密钥计算算法,返回编码后的验证密钥及相应的证据.数据拥有者利用验证密钥恢复
算法验证,在验证通过的情况下完成验证密钥的恢复操作,将其发送给授权的用户,并将数据库的查询密钥发给
云服务器.接着,授权的用户便可以向云服务器发送查询索引.由于云服务器是不可信的,其执行查询算法返回
结果及证据,授权的用户执行验证算法实现验证操作,若算法输出 1,则表示云服务器执行了正确的查询.由于持
有验证密钥的用户均可对查询结果进行验证,因此该方案支持公共可验证.
注:本文中的数据库为 NoSQL 类型,表示为 DB={(i,v i )|i∈{0,…,n}},数据库中数据集大小为A=n+1.

2.2 PVDFD的形式化定义
该模型可由概率多项式时间算法六元组 PVDFD=(Setup,KeyGen,VKeval,VKrec,Query,Verify)表示,其中每项
都代表一个多项式时间算法.6 个算法具体描述如下.
λ
1) Setup(1 )→pp:初始化算法.初始化算法由可信第三方执行,算法根据输入的安全参数λ生成公共参数
pp,并发送给方案中的其他实体;
2) KeyGen(pp,DB)→(EK DB ,EK pp ,VK pp ,RK pp ):密钥生成算法.密钥生成算法由数据拥有者执行,算法输入
数据库 DB 和公共参数 pp,生成数据库的查询密钥EK DB 、验证密钥的计算密钥EK pp 、验证密钥的恢
复密钥VK pp 和验证密钥的检索密钥RK pp .其中,EK DB 用来查询数据库,EK pp ,VK pp ,RK pp 分别用来计
算、恢复和检索数据库的验证密钥VK DB (数据库的验证密钥VK DB 在下文验证密钥恢复算法 VKrec 中
定义);
3) VKev lpa ( p ,EK pp ) → (σ VK DB ,π VK DB ) : 验证密钥计算算法.验证密钥计算算法由云服务器执行,算法输入
公共参数 pp 和验证密钥的计算密钥EK pp ,输出编码后的数据库验证密钥 σ VK DB 和相关的证据 π VK DB ;
⊥
4) VKrec ( pp ,VK pp ,σ VK DB ,π VK DB ,RK pp ) → {VK DB , } :验证密钥恢复算法.验证密钥恢复算法由数据拥有者
执行,算法输入公共参数 pp、验证密钥的恢复密钥VK pp 、验证密钥的检索密钥RK pp 和云服务器返回
的编码后的数据库的验证密钥 σ 及证据 π . 若验证通过,则输出解码后的数据库的验证密钥
VK DB VK DB
VK DB ;否则,输出⊥;
5) Query(EK DB ,x)→(y,π y ):查询算法.查询算法由云服务器执行,算法输入数据库的查询密钥EK DB 及授权
用户发来的查询索引 x∈domain(DB),输出对应的查询结果和证据对(y,π y );
6) Verify(pp,VK DB ,x,y,π y )→{0,1}:验证算法.验证算法由持有数据库验证密钥的用户执行,算法输入公共
参数 pp、验证密钥VK DB 、查询索引 x 和云服务器返回的查询结果 y 的证据π y .验证通过输出 1,否则
输出 0.
2.3 PVDFD的正确性及安全性定义
2.3.1 正确性
PVDFD 方案的正确性,即:若模型中的每个算法都被正确地执行,则永远不会拒绝正确的结果.其形式化定
义如下,其中,negl(λ)为关于安全参数λ的可忽略函数.
⎡ Setup (1 ) → pp , ⎤
λ
⎢ ⎥
)
,
⎢ KeyGen ( pp DB → (EK DB ,EK pp ,VK pp ,RK pp ⎥ ), ⎡ Query (EK DB , ) x → ( , y π y ) : ⎤
−
−
( ),且
Pr ⎢ ) → (σ ,π ⎥ ≥ 1 negl λ Pr ⎢ , , , y π ) → ⎥ ≥ 1 negl (),λ
⎢ VKeval ( pp ,EK pp VK DB VK DB ) : ⎥ ⎣ Verify ( pp ,VK DB x y 1 ⎦
⎢ ⎣ VKrec (pp ,VK pp ,σ VK DB ,π VK DB ,RK pp ) → VK DB ⎦ ⎥