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

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

n
LHS = ∏ ( e σ ,U ) x i
DB n i −
i= 0
n ⎛ ⎛ n nj i+ 2 ⎞ i+ n i − 1 + ⎞ x i
+−
= ⎜ ⎜ eg ni − ) e g⋅ ⎜ ∏ ⎜ , ∏ u j c α ⋅ ⎟ ⎟ ⋅ ( eg α 1 ,u α ) ⎟ i c ⎟
γ
(,U
i= 0 ⎝ ⎝ j= 0, j i ≠ ⎠ ⎠
n ⎛ ⎛ n ⎞ ⎞ ⎛ ⎞ x i
= ⎜ eg ni − γ ) ⋅ ⎜ e , g ∏ U n j i − ⎜ + j c + ⎜ ⎜ 1 ⎟ ⎟ ⋅ ( e g α ,u α n+ 1 ) ⎟ ⎜ ∏ i c ⎟ ⎟
(,U
i= 0 ⎝ ⎝ ⎝ j= 0, j i ≠ ⎠ ⎠ ⎟ ⎠
n ⎛ ⎛ n ⎞ ⎞ ⎛ ⎞ x i
= ⎜ eg ni − γ ) ⋅ ⎜ e ⎜ ∏ , g ∏ U n j i − ⎜ + j c + ⎟ 1 ⎟ ⋅ ( eg α ,U n ) ⎟ i c ⎟ ⎟
(,U
i= 0 ⎝ ⎜ ⎜ ⎝ ⎝ j= 0, j i ≠ ⎠ ⎠ ⎟ ⎠
n ⎛ n ⎞ ⎞ ⎛ x i
= ∏ ⎜ eg ,U ni − ⎜ γ ⋅ U n j i − + j c +∏ 1 ⎟ ⎟ ⋅ ( e g α ,U n ) ⎟ ⎜ i c ⎟
⎜
i= 0 ⎝ j= 0, j i ≠ ⎝ ⎠ ⎠
n
= (( ,eg W ⋅ ∏ i ) (e g α ,U n ) ) x i .
i c
i= 0
又由公式(3)等式的右边(right-hand side,简称 RHS)可知:
⎛ n i ⎞ RK pp ⋅ ∑ n i ⎛ n i ⎞ ⎛ − 1 n i c ⎞ x i
1
−
RHS = e ⎜ , g ∏ W i ⎟ x ⋅ ( e PRF ( ,0),Uα n ) i= 0 i cx = e ⎜ , g ∏ W i ⎟ x ⋅ e PRF ( ,0)α RK pp , ∏ U n ⎟
⎜
⎝ i= 0 ⎠ ⎝ i= 0 ⎠ ⎝ i= 0 ⎠
n − 1 i n i
= ∏ ( ( ,eg W ⋅ i ) (e g kαRK pp ,U n i c )) = x ∏ ( ( ,e g W ⋅ i ) (e g α ,U n ) ) .
x
i c
i= 0 i= 0
即 LHS=RHS,公式(3)成立.因此,若方案步骤都是正确执行,产生的结果都是未被篡改的,则结果 (σ VK DB ,
π ) 和(y,π y )总能分别通过数据拥有者及授权用户的验证.
VK DB
4 安全性证明
定理 1. 若存在一个概率多项式时间的敌手A,满足 Adv A Privacy (PVDFD ,)λ ≥ negl ( )λ ,则他可以创建一个有效
的算法B来打破可验证外包模幂计算的零知识性.
证明:根据文献[31],若敌手A已知公共参数信息,且能够构建一个算法B区分计算结果和哪一个输入相关,
即打破了可验证外包模幂计算的零知识性.
敌手A的挑战过程如下:已知公共参数为 pp,敌手通过模拟器随机构造两个数据库的计算密钥 EK DB 0 和
EK DB 1 ,并将其发送给挑战者;挑战者随机选择其中一个密钥 EK DB b ,调用算法 VKeval pp ,EK DB b ) 执行模幂运算,
(
并将结果σ 和证据 π 返回给敌手;敌手收到结果和证据后,利用算法B猜测出 b 的值,即区分出计算结果
VK
DB b VK DB b
与哪一个计算请求相关.由此可知,敌手使用了有效的算法打破了可验证外包模幂计算的零知识性. □
定理 2. 若存在一个概率多项式时间的敌手A,满足 Adv VKU (PVDFD ,λ )≥ negl ( )λ ,则他可以创建一个有效
A
的算法B来打破可验证外包模幂计算的α-可检查性.
∗
∗
证明:根据文献[31],若敌手A伪造了结果和证据,分别将其中的 R 0 和 R 1 替换为 R 和 R ,且满足
0
1
1 t ∗
0 t ∗
n b′
r
2 k
3 k
(g Rw 0 0 b ...w n n b ) = g R w′ 0 0 b′ ...w′ ,则伪造成功.敌手A利用伪造信息和真实的值可以构建一个算法B来打破可
0
n
1
验证外包模幂计算的α-可检查性.
∗
1 t
具体构建过程如下:敌手A随机选择值 R 满足 R 0 tr = R .令 R = R ⋅ R ,R = ∗ R R⋅ ,根据等式:
0 0 1 1
1 h
1 t
2 k
r
0 t
0 h
(gw 0 b ...w n b ( (R s w ...w ) ) ) = g w′ 3 k 0 b′ ...w′ n b′ ( (R s w′ ...w′ ) )
0 n 0 0 n 0 n 1 0 n
n b′
2 k
1 t ∗
0 t ∗
r
3 k
可知敌手用伪造的结果和证据,满足了等式 (g Rw 0 b ...w n b ) = g R w′ 0 b′ ...w′ ,通过了客户端的验证.因此,敌手
0 0 n 1 0 n
使用有效的算法打破了可验证外包模幂计算的α-可检查性. □