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

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

n
② 计算结果 y = ()x = F ∑ c x i ;
i
i= 0
n i n
③ 计算相关的证据 π = ∏ W i x ,其中,W = i U n i − γ ⋅ U n+ j c 1 j i −∏ + ;
y
i= 0 j= 0, j i ≠
④ 将结果 y 和证据π y 发回给授权的用户.
6) 验证算法.
该算法用于对云服务器返回的查询结果进行验证.算法的主要步骤如下.
① 授权用户收到结果 y 和证据π y 后,首先将VK DB 分解为{σ DB ,{U j } j∈[2n+2]\{n+1} ,RK pp ,PRF(α,0)};
② 计算 ∏ n U x i ;
i= 0 ni −
③ 验证以下等式是否成立:
( e σ , ∏ n U x i ) = e ( ,g π ) (e PRF⋅ ( ,0),Uα ) y⋅RK − pp 1 (3)
DB i= 0 ni − y n
若成立,则接受并输出 1;否则,拒绝并输出 0.
注:本方案亦可直接用于外包多项式的可验证计算,此时,多项式的更新效率为常量级.假设F为 n 阶的原外
包多项式,F′为系数更新后的外包多项式, σ 对应上文中的σ DB , VK 对应上文中的VK DB 表示外包多项式的验
F F
证密钥,upd 为更新信息.具体更新算法为
Update (VK RK pp , ′ →F ) (upd ,VK F ′ ).
,
F
该算法在保证多项式的阶不变的情况下,可高效地对多项式的任意系数进行更新.算法的主要步骤如下.
① 假设更新的系数位置为 i∈{0,…,n},令 upd = (, , )i c c′ .其中,c i 为系数更改前的值, c′ 为更改后的值;
i
i
i
② 计算σ F ′ = σ F PRF (, )iα ( i c′ − i c ) / RK pp ,并将 VK 更新为 VK F ; ′
F
③ 外包多项式的用户将 upd 发送给云服务器,并将更新后的验证密钥 VK 重新发送给授权用户,即可实
′
F
现外包多项式的更新.
3.3 正确性证明
本节将基于公式(1)~公式(3)的正确性来证明整个方案的正确性.公式(1)、公式(2)可根据文献[31]来证明.
而对于公式(3),其等式的左边(left-hand side,简称 LHS)有:
⎛ n i ⎞ n n
i
LHS = e σ ⎜ , ∏ U ni − x = ( e σ ,U ni − ⎟ x i ) = ∏ ∏ ( e σ ,U n i− ) ,
x
⎝ DB i= 0 ⎠ i= 0 DB i= 0 DB
⎛ n j+ 1 ⎞ x i
i
γ
x
( e σ DB ,U n i − ) = e g ⋅ ∏ g j c α ,U n i − ⎟ ⎟
⎜
⎜
⎝ j= 0 ⎠
⎛ ⎛ n j+ 1 ⎞ ⎞ x i
= ⎜ ( eg γ ,U ) e ⋅ g j c α ⋅ ,U ⎟ ∏ ⋅ ⎜ ( e g i c α ⋅ i+ 1 ,U )⎟
⎜ n i − ⎜ ni − ⎟ ni − ⎟
⎝ j=⎝ 0, j i ≠ ⎠ ⎠
⎛ ⎛ n j+ 1 ⎞ i+ ⎞ x i
= eg γ ) e g ∏ U j c α ⋅ ⋅ ⎟ ( eg i c α⋅ 1 ,U )⎟
⋅ ⎜
,
⎜
( ,U
⎜ ni − ⎜ ni − ⎟ ni − ⎟
⎝ j= ⎝ 0, j i ≠ ⎠ ⎠
⎛ ⎛ n ni −+ 1 j+ 1 ⎞ i+ ni −+ 1 ⎞ x i
= eg γ ) e g ∏ u α ⋅ j c α ⋅ ⎟ ⋅ ( eg i c α ⋅ 1 ,u α )⎟
,
( ,U
⋅ ⎜
⎜
⎜ ni − ⎜ ⎟ ⎟
⎝ j= ⎝ 0, j i ≠ ⎠ ⎠
⎛ ⎛ n nj i+ 2 ⎞ ⎞ x i
+−
= eg γ ) e g ∏ u j c α ⋅ ⎟ ⋅ ( eg α i 1+ ,u α ni − 1 + ) ⎟ i c .
⋅ ⎜
⎜
,
( ,U
⎜ ni − ⎜ ⎟ ⎟
⎝ j= ⎝ 0, j i ≠ ⎠ ⎠