Page 260 - 《软件学报》2020年第12期

3926 Journal of Software 软件学报 Vol.31, No.12, December 2020

模型,能快速求出秘密共享数和叶子节点密文的计算方案.在该方案中,针对秘密共享数,每个非叶子节点对应
于一个 Map 操作,每个叶子节点对应于一个 Reduce 操作,并且每个 Map 操作需要知道对应节点其子树中所有
的叶子节点(若考虑每个 Map 操作计算一个节点在启动 Map 时间与计算节点时间之比太高,可考虑单个 Map
操作计算多个节点,具体几个可根据实验结果进行);每个 Map 操作为每个节点选择一个多项式,但常数项为 0
(根节点常数项为 s),然后计算 Q(1),Q(2)等,如果叶子节点在 Map 操作对应节点的第 1 个子树上,就发送 Q(1)的
值给对应叶子节点的 Reduce 操作,如图 1 的节点 a,将 Q(1)发送给 A,B,C,Q(2)发送给 E,等等;发送内容为〈叶子节
点 Reduce 标识,Q(index)〉,最后,叶子节点对应的 Reduce 将收到的值相加,即为秘密分量;针对叶子节点密文计算,
每个叶子节点与随机数相关的指数运算对应于一个 Map 操作,将其发送给对应叶子节点的 Reduce 操作,Reduce
操作进行秘密分量的指数运算,从而得到叶子节点完整密文.详细流程如图 1 所示.

2
3/3 a: Q(x)=3x +4x+5

b: Q(x)=2x+0 2/2 E 1/2 d: Q(x)=0

a: Q(2)=25
s E: 25

c: Q(x)=6x+0 2/3 D F G
a: Q(1)=12 a: Q(3)=44 a: Q(3)=44

b: Q(2)=4 d: Q(1)=0 d: Q(2)=0
s D: 16 s F: 44 s G: 44
A B C
a: Q(1)=12 a: Q(1)=12 a: Q(1)=12
b: Q(1)=2 b: Q(1)=2 b: Q(1)=2
c: Q(1)=6 c: Q(2)=12 c: Q(3)=18
s A: 20 s B: 26 s C: 32
Fig.1 Flow chart of secret value parallel distribution
图 1 秘密值并行分发流程图
2.2 安全共享机制
计算外包的难点在于,实现外包的同时还需要保证数据的安全.外包时,将密文共享访问树的计算工作外包
给 Spark 集群处理,但为了保证数据安全,Spark 集群计算共享访问树时,每个节点的多项式常数项均为 0,并在叶
子节点获取秘密分量后加一,计算完成后,将与属性相关的密文子项发回用户客户端与秘密值 s 做幂运算.
定理 2. 共享访问树在秘密值为 0 且叶子节点秘密分量加一或秘密值为 1 的情况下,相同叶子节点获得的
秘密分量相同.
证明:当共享访问树设置秘密值为 1 时,由定理 1 可知,叶子节点 r n 的秘密分量为
f n ,1 (0) = f ′ n− 1 (index ( )) ...r n + 1 ′ ( f index ( ))r 2 + f ′ + 0 (index ( )) 1r 1 + .
当共享访问树设置秘密值为 0 时,由定理 1 可知,叶子节点 r n 的秘密分量为
f n ,0 (0) = f ′ n− 1 (index ( )) ...r n + 1 ′ ( f index ( ))r 2 + f ′ + 0 (index ( )) 0r 1 + .
再加上一可得:
f n ,2 (0) = f n ,0 (0) 1+= f ′ n− 1 (index ( )) ...r n + + 1 ′ ( f index ( ))r 2 + f ′ 0 (index ( )) 1r 1 + .
即 f n,1 (0)=f n,2 (0),故命题成立. □
定理 3. 共享访问树在秘密值为 1 并且叶子节点秘密分量乘以 s 或秘密值为 s 的情况下,根节点的秘密值