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

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

•
• •
• •
•
• •
(a) (b)

•
• •
• •
• •
• •
•
• •
•
(c) (d)
Fig.5 Multi-dimensional relation between a rational number and a rational domain
图 5 点与区间的关系

4 数轴上面向有理数的保密区间关系测定问题

面向有理数的保密区间关系测定问题,实质就是保密测定两个(上下界为有理数的)区间相交与否,并且协
同计算完成后不会泄露双方的私有信息 a L ,a R ,b L ,b R 以及相交区间位于各自区间的哪一端.具体描述如下.
Alice 和 Bob 是分布式环境下的两个实体,他们分别拥有一个(上下界为分数形式的实数或有理数的)区间
dom A =[a L ,a R ]和 dom B =[b L ,b R ],二者通过协作保密测定两个区间的关系,如果相交,二者协同计算完成后不会泄露
双方的私有信息 a L ,a R ,b L ,b R 以及 a L 与 b R ,a R 与 a L ,a R ,b L ,b R 的大小关系.
4.1 数轴上面向有理数的保密区间关系测定协议Π 3
两个(上下界为有理数的)区间 dom A =[a L ,a R ]和 dom B =[b L ,b R ]的相对位置关系在数轴上表现为 4 种情型,如图
6 所示.

a L b L a R b R b L a L b R a R
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
(1) (2)

a L a R b L b R b L b R a L a R
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
(3) (4)

Fig.6 Relationship between two rational intervals
图 6 两有理区间的关系

1. 具体协议.
输入:系统安全参数:κ=logn,Alice 的(上、下界为有理数的)区间 dom A =[a L ,a R ],Bob 的(上、下界为有理数的)
区间 dom B =[b L ,b R ];
⎧ 1, dom ∩ dom ≠ ∅
输出: ∂= ⎨ B A .
⎩ 0, dom ∩ B dom = A ∅
准备工作:Bob 先运行方案E的密钥生成算法,产生公私钥对(K Pub ,K Pri ),其中,K Pub =1+n,K Pri =λ;Alice 和 Bob 分
别将自己的区间 dom A =[a L ,a R ],dom B =[b L ,b R ]的端点表示成数对形式 (a ,a ),(a ,a ) 与 (bb ),(b ,b ) ,使得:
,
1 L 2 L 1 R R 2 1 L 2 L 1 R R 2