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

巩林明 等:数轴上保密关系测定协议 3963

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