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

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

③ 计算 w i =u i /v 0 ,其中,i∈{0,…,n},并生成逻辑划分如下:
0 c
u 0 0 c ...u n n c = (v w 0 ) ...(v w n ) n c
0
0
= v 0 c ++ + n w 0 c ...w n c
1 ... c
c
0 0 n
= g k 4 (c + 0 c + 1 ... c n − ) k t 0 0 0 h g k th ⋅ (w ...w ) th w 0 b ...w n b
+
0 0 0
0 0
0 n 0 n
= g 2 k (s w 0 ...w n ) th w 0 0 b ...w n n b .
00
0
④ 选择随机数 r∈Z p ,计算 w′ = u′ i /v ,其中,i∈{0,…,n}.将 (u 0 0 c ...u n n c ) 进行逻辑划分如下:
r
1
i
r
(u 0 0 c ...u n n c ) = (vw′ 1 0 ) ...(vw′ rc 0 1 n ) rc n
1 ... c
0 c
= v 1 ( rc ++ + n ) (w′ 0 0 c ...w′ n n c ) r
5 (c ++ +
) k t
= g kr 0 c 1 ... c n − 1 1 1 h g kt 11 1 h (w′ ...w′ ⋅ ) t 1 1 h w′ 0 b′ ...w′ n b′
0 n 0 n
= g 3 k (s w′ 0 ...w′ n ) th w′ 0 0 b′ ...w′ n n b′ .
11
1
⑤ 计算满足 k 3 =k 5 r(c 0 +c 1 +…+c n )−k 1 t 1 h 1 和 rc = i b′ + i t h 的 b′ 和 t 1 h 1 ,其中,i∈{0,…,n};
11
i
⑥ 令验证密钥为{g 2 k ,g 3 k , , , }r t t ,求值密钥为{( ,h s w 0 ...w n ),( ,h s w′ 0 ...w′ n ),( ,b w i i∈ ) [ ]n ,( ,b w′ i ′ i i∈ ) [ ]n }.
0
0
0
1
i
1
1
2) ME.Compute(MExp.EK)→{ME.σ y ,ME.π y }
此步骤由服务器生成编码后的结果 ME.σ y 和证据 ME.π y .具体如下.
′
,
① 将 ME.EK 分解为 ( ,h s w 0 ...w n ),( ,h s w′ 1 0 ...w′ n ), ({ b w i i∈ [ ]n } 和{( ,bw′ i i∈ []n };
)
)
1
i
i
0
0
② 对于 i∈{0,…,n},计算 w 和 w′ i i b′ ;
i b
i
0 h
③ 令 R = (s w 0 ...w n ) 和 R = (s w′ 1 0 ...w′ n ) 1 h ;
0
1
0
}
④ 返回结果和证据,分别为 ME .σ = {{w i i b } i∈ [] n ,R 和 ME .π = {{w′ i i b′ } i∈ [] n , }.R 1
0
y
y
3) ME.Verify(ME.VK,ME.σ y ,ME.π y )→{ME,y,⊥}
此步骤为客户端验证计算结果的正确性,具体如下.
① 将 ME.VK 分解为{g 2 k ,g 3 k , , , }r t t ,ME.σ y 分解为{{w i i b } i∈ [] n ,R 0 } ,ME.π y 分解为{{w′ i i b′ } i∈ [] n , };R 1
0
1
② 计算是否满足等式:
1 t
0 t
2 k
0 b
r
3 k
(g Rw w 1 b ...w n b ) = g R w′ 0 b′ . .. w′ n b′ .
0 0 1 n 1 0 n
0 b
0 t
若不满足,则终止协议并输出⊥;否则,恢复计算结果 MEy = g R w w 1 b ...w n b .
2 k
.
0 0 1 n
MExp 协议有以下的性质.
1) 正确性:若服务器是诚实地遵循上述过程,协议可确保客户端总是可以输出 ME.y;
2) 零知识性:协议可确保不遵守协议的恶意服务器无法获得任何秘密输入和输出(运算结果)的信息;
3) α-可检查性:协议确保检测到恶意服务器返回的错误结果的概率不小于α.
3.2 方案详细设计
本节首先详细介绍了 PVDFD 方案中各个算法的具体构造,然后给出了正确性证明.下面分别进行描述.
1) 初始化算法.
该算法用于为方案中的所有实体生成公共参数.算法的主要步骤如下.
① 给定安全参数λ,可信第三方首先选择阶为 p∈poly(λ)的两个群G 1 和G 2 满足双线性映射 e:G 1 ×G 1 →G 2 ;
② 随机选取两个生成元 g,u∈G 1 ;
③ 令公共参数 pp=(p,g,u,G 1 ,G 2 ,e)并发送给云服务器、数据拥有者和授权用户.
2) 密钥生成算法.
该算法用于生成方案所需密钥.算法的主要步骤如下.
① 数据库 DB={(i,v i )|i∈{0,…,n}},其中,数据集大小为A=n+1.数据拥有者先将数据库 DB 插值为多项式
i
F ()x = ∑ n cx 的形式,使得对于任意的 i∈{0,…,n},均满足F(i)=v i .提取多项式F的系数集合为 C={c 0 ,c 1 ,…,c n };
i= 0 i