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

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

, ′
(( ′ cc ),( ′ c , ′ c )) {(( ′ C ( ′ ∈ , ′ ( ′ C ),( ′ ( ′ C , ′ ( ′ C )),
1 L 1 R 2 L R 2 a L 2 1 )+ ′ ⋅ 1 a 1 L b 2 )+ a k ′ ⋅b 1 a R 2 1 )+ a k ′ ⋅ 2 a 1 R b 2 )+ a k ′ ⋅b a k 2
(( ′ ( ′ C 1 L a 2 )+ ′ ⋅ 1 , ′ ( ′ C a L 2 1 )+ a k ′ ⋅ 1 a k ),( ′ ( ′ C a R b 2 )+b ′ ⋅b 2 , ′ C ( ′ a k a R b ⋅ 1 )+ a k ′ 2 )),
2
1
(( ′ ( ′ C a R 2 1 )+ ′ ⋅ 2 , ′ ( ′ C a R b 2 )+ a k ′ ⋅b 2 ),( ′ ( ′ C a L 2 1 )+ a k ′ ⋅ 1 ,C ( ′ 1 L a b 2 )+ a k ′ ⋅ b 1 a k )),
1
(( ′ ( ′ a 1 R 2 )+ ′ ⋅ 2 , ′ C C ( ′ a R b 1 )+ a k a k ′ ⋅b 2 ),( ′ C ( ′ a ⋅ L 1 2 )+ ′ 1 , ′ C ( ′ L a 2 b 1 )+ a k ′ ⋅b 1 a k ))}.
2
而 Alice 在协议Π 1 的实际执行中产生的视图为
(C = (1 n r+ ) 1 b n mod n 2 ,C = (1 n+ ) r n mod n 2 , (c ,c ),(c ,c )),
2 b
1 b 1 b 2 b 2 b 1 L 1 R 2 L R 2
其中,
a
′
C ′ = ((C ) 1 a k ⋅ L 2 mod ) (1+ n 2 × kkn )r n mod n 2
a
( L ⋅b 1 )+ a k 1 b 1 a 1 a 1 a
2 1
′
C (a 1 L ⋅b 2 )+ a k ′ = 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
a
′
C ′ = ((C ) a k 2 ⋅ R 2 mod ) (1+ n 2 × kkn )r n mod n 2
a
( R ⋅b 1 )+ a k 1 b 2 a 2 a 3 a
2 2
′
×
C (a 1 R ⋅ 2 )+b ′ = ((C ) a k 2 ⋅a 1 R mod n 2 ) (1+ kkn )r n 2 a mod n 2
a k
2 a
2 b
2 a
2
∈
((cc ),(c ,c )) {((C ,C ),(C ,C )),
,
a
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
2
((C ,C ( ), C ,C )),
a
a
a
( R ⋅ 1 )+ ′ ( R b ⋅b 2 )+ a k a k ′ ( L ⋅ 1 )+ ′ (a 1 L b ⋅b 2 )+ a k ′ 1 a k
2 2 1 2 2 1
((C ,C ),(C ,C )),
a
(a 1 L ⋅ 2 )+ ′ 1 ( L b ⋅b 1 )+ a k ′ 1 ( R b ⋅ 2 )+ a k ′ 2 ( R b ⋅ 1 )+ a k ′ a k 2
a
a
2
2
1
((C (a 1 R ⋅ 2 )+ ′ 2 ,C ( R b ⋅b 1 )+ a k a k ′ 2 ),(C (a 1 L ⋅ 2 )+ ′ 1 ,C ( L b ⋅b 1 )+ a k ′ 1 a k )),
a
a
2
2
((C ,C ),(C ,C )),
a
a
a
( R ⋅ 1 )+ ′ ( R b ⋅b 2 )+ a k ′ ( L ⋅ 1 )+ a k ′ 1 a (a 1 L b ⋅b 2 )+ k ′ 1 a k
2 2 1 2 2
((C ′ ,C ′ ),(C ′ ,C ′ )),
a
a
a
⋅b
( L 2 ⋅ 1 )+ 1 (a 1 L b 2 )+ a k 1 ( R 2 ⋅ 1 )+ a k 2 ( R b ⋅b 2 )+ a k a k 2
1
((C (a 1 R ⋅ 2 )+ ′ 2 ,C ( R b ⋅b 1 )+ a k ′ 2 ),(C (a 1 L b ⋅ 2 )+ a k ′ 1 a k ,C ( L b ⋅ 1 )+ ′ 1 a k )),
a
a
2
2
((C (a ⋅b ′ ,C ( L b ⋅ ′ ),(C a ′ ,C ( R b ⋅ ⋅b ′ a k ))}.
a
a
1 L 2 )+ 1 a k 2 1 )+ 1 ( R 1 2 )+ a k 2 2 1 )+ a k 2
Alice 无论在模拟协议还是实际协议中,接收到的有关 Bob(或 S 1 Π 1 )的信息都是经E加密后的密文,一方面因
为 Alice 没有E的解密密钥;另一方面,加密方案E已被证明在选择明文攻击下具有语义不可区分安全,即经加密
方案E加密生成的密文是语义不可区分的.因此可得:
+
1 b
模拟视图 (C′ 1 b (1 n r n 1 b mod n 2 ,C′ = 2 b (1 n ) r n 2 b mod n 2 ( , c′ = 1 L ,c′ + 1 R ),(c′ 2 L ,c′ R 2 ) ) 与真实视图 (C = 1 b (1 n r+ ) 1 b n 1 b
2 b
)
2 b
mod nC = (1 n+ ) r n mod n 2 , (c ,c ),(c ,c ) ) 是计算不可区分的.也就说, S Π 1 满足安全定义关系式(1a).
2
,
2 b 2 b 1 L 1 R 2 L R 2 1
II. Alice 私有信息在协议执行后是安全的.
在最坏的情形下,即在 Bob 受控于攻击者的情形下,构造一个模拟器 S Π 1 模拟协议Π 1 的执行过程.显然,模
2
拟器是潜在的、能力最强的攻击者;如果多项式时间内的敌手 S 2 Π 1 获得的信息并不多于 Bob 在实际执行协议中
的视图内容,则称协议Π 1 完成后没有造成 Alice 区间下、上界 a L ,a R (a L ,a R 为有理数)的泄露,即 Alice 私有信息是
安全的.
假定敌手 S 2 Π 1 控制着 Bob,并且在 Bob 不参与的情况下,能够在多项时间内模拟协议Π 1 执行的全过程.如果
在该假定条件下,多项式时间内的敌手 S Π 1 获得的信息并不多于 Bob 在实际执行协议中的视图内容,则 Alice 私
2
有信息(区间的下、上界 a L ,a R )是安全的.
首先构造一个在 Bob 受敌手控制的情形下、能够在多项式时间内模拟协议Π 1 整个执行过程的模拟器 S Π 1 ,
2
其输入为:敌手根据 Bob 数值 b(b 是分数形式的实数或有理数)随机选择利于它获取 Alice 区间的下、上界 a L ,a R
*
的一个分数形式的实数或有理数 b′、Bob 随机选择的两个不等的随机数 rr ∈ Z 以及 Alice 区间的下、上界
,
n
1 b
2 b
,
a L , a R 对应的整型有序对表示 (a a 2 L ),(a 1 R ,a R 2 )(gcd(a 1 L ,a 2 L ) 1,gcd(a= 1 R ,a R 2 ) 1)= .作为潜在的、能力最强的敌手,
1 L
,
模拟器 S Π 1 产生的视图为 (CC ( , c′ ,c′ ),(c′ ,c′ )), 其中,
2 1 b′ 2 b′ 1 L 1 R 2 L R 2
2 b′
2
• CC 是 S 2 Π 1 利用 Bob 的公钥按照如下计算的: C = 1 b′ (1 n r+ ) 1 b′ n 1 b′ mod n 2 ,C = 2 b′ (1 n+ ) r n 2 b′ mod n ;
,
1 b′
2 b′