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

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

,
((cc ),(c ,c )) {((∈ ′ C ,C ),(C ,C )),
1 L 1 R 2 L R 2 ( L 2 ⋅ 1 )+ 1 (a 1 L b ⋅b 2 )+ a k ′ 1 ( R b ⋅ 1 )+ a k ′ 2 (a 1 R b ⋅ 2 )+ a k ′ a k 2
a
a
2
((C ,C ),(C ,C )),
a
a
( R ⋅ 1 )+ ′ (a 1 R b ⋅b 2 )+ a k ′ ( L ⋅ 1 )+ a k ′ (a 1 L b ⋅b 2 )+ a k ′ 1 a k
2 2 2 2 1
((C (a ⋅b ′ ,C a ⋅ ′ ),(C (a ⋅b ′ ,C ( R b ⋅ ′ )),
a
1 L 2 )+ 1 ( L 2 1 )+ a k 1 a k 1 R b 2 )+ 2 2 1 )+ a k a k 2
((C ,C ),(C ,C ))}.
(a 1 R ⋅ 2 )+ ′ 2 ( R b ⋅b 1 )+ a k ′ 2 (a 1 L b ⋅ 2 )+ a k ′ 1 a ( L a 2 ⋅b 1 )+ k ′ 1 a k
a
2
,
Step 3:Bob 收到 (cc ),(c ,c ) 后计算下式,然后将∂发送给 Alice:
1 L 1 R 2 L R 2
⎛ ( Lc λ ) ⎞ ⎛ ( Lc λ ) ⎞ ⎧ − 1, X ≤ 1
∂= P⎜ 1 L ⎟ P⎜ 2 L , ⎟ 其中 , ( )P X = ⎨ (6)
⎜ ( Lc λ ) ⎟ ⎜ ( L c λ ) ⎟ 1, X > 1
⎝ 1 R ⎠⎝ R 2 ⎠ ⎩
2. 数理计算的正确性.
a a a a ⎧ − 1, X ≤ 1
PX
(1) 如果 b∈dom A ,即 a L <b<a R ,则有 L ≤ 1, R ≥ 1,所以 L , R 经函数 () = ⎨ 作用后的乘积满足:
b b b b ⎩ 1, X > 1
⎛ L ⎞ a ⎛ R ⎞ a
∂ = P ⎜ ⎟ ⋅ P ⎜ ⎟ = − 1 ;
⎝ ⎠ b ⎝ ⎠ b
a a a a ⎧ − 1, X ≤ 1
PX
(2) 如果(b∉dom A )∧(b<a L ),则有 L > 1, R > 1 ,因此 L , R 经函数 () = ⎨ 作用后的乘积:
b b b b ⎩ 1, X > 1
⎛ L ⎞ a ⎛ R ⎞ a
∂= P ⎜ ⎟ ⋅ P ⎜ ⎟ = (1) ( 1) 1− ⋅ − = ;
⎝ ⎠ b ⎝ ⎠ b
a a a a ⎧ − 1, X ≤ 1
(3) 如果(b∉dom A )∧(a R <b),则有 L < 1, R < 1,因此 L , R 经函数 () = ⎨ 作用后的乘积:
PX
b b b b ⎩ 1, X > 1
⎛ L ⎞ a ⎛ R ⎞ a
∂ = P ⎜ ⎟ ⋅ P ⎜ ⎟ = 11 1⋅ = .
⎝ ⎠ b ⎝ ⎠ b
3. 安全性
定理 1. 在半诚实模型下,保密测定某数(有理数)是否属于一个(上、下界为有理数的)区间协议Π 1 是安全的.
证明:衡量保密测定某数是否属于某个区间协议的安全性,关键是看协议执行结束后有没有造成 Alice 与
Bob 两方私有信息的泄露.下面将严格按照定义 1 与定义 2 声明的安全标准和方法证明:通过协同执行第 2.1 节
中的保密计算协议,Alice 与 Bob 会得到保密计算结果(属于或者不属于),但不会得到对方的具体数值(a L ,a R ,b).
I. Bob 私有信息在协议执行后是安全的.
在最坏的情形下,即在 Alice 受控于攻击者的情形下,构造一个模拟器 S Π 1 模拟协议Π 1 的执行过程.显然,模
1
拟器是潜在的、能力最强的攻击者.如果多项式时间内的敌手 S 1 Π 1 获得的信息并不多于 Alice 在实际执行协议
中的视图内容,则称协议Π 1 执行完毕后没有造成 Bob 具体数值 b 的泄露,即 Bob 私有信息是安全的.
构造一个在最坏的情形下,即在 Alice 受敌手控制的情形下、能够在多项式时间内模拟协议Π 1 整个执行过
程的模拟器 S 1 Π 1 ,其输入为:敌手根据 Alice 区间的下、上界 a L ,a R (二者均为分数形式的有理数)随机选择利于它
, ′
获取 Bob 数值 b 的两个分数 ′ aa 、Bob 随机选择的两个不等的随机数 rr ∈ Z 以及 Bob 的数值对应的整型
*
,
L R 1 b 2 b n
有序对表示(b 1 ,b 2 ) (gcd(b 1 ,b 2 )=1).作为能力最强的、多项式时间的敌手,模拟器 S 1 Π 1 产生的视图为
(C = (1 n r n mod n 2 ,C = (1 n ) r n mod n 2 ( , c′ ,c′ ) ,(c′ ,c′ )),
+
1 b
+
2 b
)
1 b 1 b 2 b 2 b 1 L 1 R 2 L R 2
其中,
′
( ′ C ′ a L 2 1 )+ a k ′ ⋅b 1 = ((C 1 b ) 1 a k ⋅a ′ L 2 mod ) (1+ n 2 × kkn )r n 1 a mod n 2
1 a
1 a
′
( ′ C ′ 1 L a 1 )+ a k ′ ⋅b 1 = ((C 2 b ) 1 a k ⋅a ′ 1 L mod ) (1+ n 2 × kkn )r n 2 a mod n 2
1 a
1 a
′ = ((C ) a k 2 ⋅a ′ R 2 mod ) (1+ n 2 × k k ′ C ) n r n mod n 2
( ′ a 1 )+b a k ′ ⋅ R 1 b 2 a 2 a 3 a
2 2
d
′ C = ((C ) a k 2 ⋅ ′ a 1 R mod ) (1+ n 2 × k ′ k ) n r n mo n 2
a
( ′ ⋅b 2 )+ a k ′ 2 2 b 2 a 2 a 2 a
R
1