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

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

2.2 数轴上分数范围内的点与区间保密关系测定协议应用举例
点与区间保密关系测定协议可以作为基础模块,用于构造解决保密几何计算 [26] 与保密社交 [27] 等问题的协
议.而分数范围内的点与区间保密关系测定协议更符合现实应用场景.例如:可用点 a 与区间[b L ,b R ]保密关系测
2
2
定协议解决点 P(x,y)与圆面 x + y ≤ b 保密关系测定问题如图 3(a)所示,可以用于解决点 P(x,y)与环面
2
R
2
2
b ≤ L 2 x + y ≤ 2 b 保密关系测定问题如图 3(b)所示,还可以用于解决点 P(x,y)与无限射影区域关系测定问题如
R
图 3(c)所示.
•
• • •
•
• •

(a) (b) (c)
Fig.3 Relationship between a rational number and a rational interval
图 3 点与区间的关系

3 多维点与区间关系保密测定问题

本节将点与区间关系保密问题拓展成多维点与区间保密关系测定问题.多维点与区间保密关系测定问题
具体描述为:不失一般性,假定 Alice 和 Bob 是两个参与者,他们分别拥有保密向量 A=([a 11 ,a 12 ],[a 21 ,a 22 ],…,[a n1 ,
a n2 ])和 B=(b 1 ,b 2 ,…,b n ),其中,a i1 和 a i2 分别表示第 i 个区间[a i1 ,a i2 ]的下、上界,a i1 ,a i2 ,b i 是分数形式的实数或有理
数,a i1 <a i2 ,i=1,2,…,n.Alice 与 Bob 协同完成向量 B 与向量 A 关系的保密测定.具体而言,二者协同完成关系测定:
对于任意的 i=1,2,…,n,a i1 ≤b i ≤a i2 是否都成立,但协同计算不会泄露双方的保密输入,如图 4 所示.

1 L a 1 L a ≤ b b 1 ? 1 b 1 b ≤ 1 R a ? ? 1 R a
2 L a 2 L a ≤ 2 ? 2 b 2 b ≤ R a 2 2 R a
… …
k L a k L a ≤ k b ? n b b ≤ k R a ? k R a
k

Fig.4 Relationship of multi-dimensional rational point and multi-dimensional rational interval
图 4 多维点与区间的关系
3.1 多维点与区间保密关系测定协议Π 2
协议的输入:Alice 的私有向量 A = ([a 11 ,a 12 ],[a 21 ,a 22 ],...,[a 1 ,a 2 ]) 和 Bob 的私有向量 B = ( , ,..., )b b 2 b ,其中,

1
[a i1 ,a i2 ]表示一个端点为有理数的连续区间,a i1 与 a i2 分别是此区间的下、上界,b i 为有理数,i=1,2,…, .
协议的输出:二进制向量 O = (,O O 2 ,...,O ,其中,O i =0 表示 b i ∉[a i1 ,a i2 ],O i =1 表示 b i ∈[a i1 ,a i2 ].
)

1
准备阶段:Bob 运行密钥生成算法E生成密钥对(K Pub ,K Pri ),其中,K Pub =1+n,K Pri =λ;Alice 和 Bob 分别将他们的
ˆ
b b
,
a L 和 a R ,(b)表示成整数对 ˆ (aa ) 与 ˆ (a ,a ),(( , )) ,使得构成这些整数对的元素满足:
i L i L i R i R i i
ˆ a ˆ a b ˆ
ˆ
b b =
ˆ ,
a = i L ,a = i R ,b = i ,gcd(aa ) = gcd(a ˆ ,a ) = gcd( , ) 1.
i L a i R a i b i L i L i R i R i i
i L i R i
并行计算阶段:对于 i=1,2,…, ,Alice 与 Bob 按照如下方式协同运算.

ˆ
Step 1:Bob 利用自己的公钥计算数对 (, ) 对应的密文:
bb
i i
n
C = (1 n r+ ) ˆ b i ˆ mod n 2 (7a)
ˆ b i b
i