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

周搏洋 等:全委托的公共可验证的外包数据库方案 3911

定理 3. 若存在一个概率多项式时间的敌手A,满足 Adv A RU (PVDFD DB , )λ ≥ negl (λ ) ,则他可以创建一个有
,
效的算法B来打破 BDHE 难题.
证明:查询索引 x 对应的值为 y ,敌手A伪造了该值和证据,分别为 ˆ , ˆ π * .若伪造的值满足 ˆ y ≠ y 且
*
*
*
*
y
*
y
*
=
*
x
Verify ( params ,VK , , y ˆˆ ,π * ) 1 ,则伪造成功.敌手A利用伪造信息和真实的查询结果及证据可以构建一个算
DB y
法B来打破 BDHE 难题.
具体构建过程如下:令 c = ˆ y − * y ≠ * 0∈ Z ,即真值与伪造值的差值.由于验证通过,则一定满足以下等式:
p
*
x
( e σ DB , ∏ n i= 0 U ni − i ) = e ( ,g π ˆ y * ) (e PRF⋅ ( ,0),Uα n ) ˆ y ⋅RK − pp 1 (4)
∗
)
而对于真实结果和证据 (,y π ∗ ,满足以下等式:
y
*
x
( e σ DB , ∏ n i= 0 U ni − i ) = e ( ,g π y * ) (e PRF⋅ ( ,0),Uα n ) y ⋅RK − pp 1 (5)
根据公式(4)和公式(5),可以推出:
−
1
*
ˆ ⋅RK
(,π
⋅
(,π
e g * ) ( e PRF ( ,0),α U ) y * ⋅ − pp 1 = e g * ) (⋅ e PRF ( ,0),α U ) y RK pp ⎫
y n ˆ y n ⎪
*
ˆ ⋅RK
(,π
(,π
eg * ) (⋅ k α ,u α n 1 + ) y * ⋅ pp − 1 = e g * ) (⋅e g e g k α ,u α n 1 + ) y RK − pp 1 ⎪
⎪
y ˆ y ⎪
(,π
(,π
eg * ) (⋅ k α ,u α n 1 + ) y * = e g * ) (⋅e g e g α ,u α n 1 + ) ˆ y * ⎪
y ˆ y ⎪
eg * ) ( ,e g u α n + 2 ) y * = (,πeg * ) ( ,⋅eg u α n + 2 ) ˆ y * ⎪ (6)
(,π
⋅
⎬
y ˆ y ⎪
(,π
⋅
⋅
(,π
eg * ) ( ,e g U ) y * = e g * ) ( ,e g U ) ˆ y * ⎪
y n + 1 ˆ y n + 1 ⎪
1 c − 1 ⎪
⎛ (,π * ) ⎞ eg ˆ − y * ⎛ ( ,π * ) ⎞ eg ⎪
*
y
(,U
eg + ) = ⎜ y ⎟ = ⎜ y ⎟ ⎪
⎜ n 1 (,π * ) ⎟ eg ⎜ ( ,π * ) ⎟ eg ⎪
⎝ ˆ ⎠ y ⎝ ˆ ⎠ y ⎭
由公式(6)可知,敌手使用了有效的算法打破了 BDHE 难题. □
5 分 析
5.1 方案对比
本节将本方案 PVDFD 与 Miao 等人的方案 [24] (MVDB)、Chen 等人的方案 [18] (CVDB)、Benabbas 等人的方
[6]
案 (BVDB)、Backes 等人的方案 [21] (BFVDB)和 Wang 等人的方案 [23] (WVDB)进行了功能上的对比分析.主要比
较了方案是否需要较大的预处理开销、是否支持公共可验证和计算难题的假设.结果见表 2.
Table 2 Comparison among six schemes
表 2 方案对比
性能 MVDB [24] CVDB [18] BVDB [6] BFVDB [21] WVDB [23] PVDFD
昂贵的预处理操作 √ √ √ × × ×
公共可验证 √ √ × × × √
计算假设 CDH CDH DDH CDH q-SDH BDHE
从表 2 中可以看出,MVDB 方案、CVDB 方案和 BVDB 方案在预处理阶段均需要数据拥有者执行昂贵的
计算.这对于持有小型终端的数据拥有者而言,代价过于昂贵.而 BFVDB 方案和 WVDB 方案虽不存在预处理开
销大的问题,却不能实现公共可验证,BVDB 方案同样存在不支持公共可验证的问题.本文的 PVDFD 方案通过
采用将预处理开销委托给云计算的方式,不需要数据拥有者过大的预处理开销,且支持公共可验证.
5.2 复杂度分析
BVDB 方案、BFVDB 方案和 WVDB 方案不能实现公共可验证,本文的 PVDFD 方案在功能方面优于三者,