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

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

的问题,还可以解决(分数形式的)实数范围内的问题,其实质是保密测定某数(本身是有理数)是否属于一个区间
(上、下界为有理数)但不泄露该数和区间的上、下界.具体描述如下:Alice 和 Bob 是分布式环境下的两个实体,
其中, Alice 拥有一个上、下界为分数或整数的区间 dom A =[a L ,a R ],Bob 拥有一个有理数 b,二者通过协同计算,测
定 b 是否落在区间 dom A 内,但不泄露下列有关双方的私有信息:a L ,a R ,b 的具体数值、a L 与 b 的关系、a R 与 b 的
关系.
2.1 数轴上数与区间保密关系测定协议Π 1
数 b 和区间 dom A =[a L ,a R ](其中,b,a L ,a R 均为有理数)的关系在数值上有 3 种情况:a L <b<a R ,b<a L ,b>a R ,这 3 种
情形在数轴上表现为 3 种位置关系,如图 2 所示.

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

Fig.2 Relationship between a point and a interval
图 2 点与区间的关系
1. 具体协议.
输入:系统安全参数κ=logn,Alice 的保密区间 dom A =[a L ,a R ],Bob 的保密数 b,其中,b,a L ,a R 均为有理数;
⎧ b 1
? ⎪ ⎪ 1, b ∈ / dom A
输出: ∈ b dom = ∂ = ⎨ 2 .
A
⎪ − 1, b 1 ∈ dom
⎪ ⎩ b 2 A
准备工作:Bob 先运行方案E的密钥生成算法,产生公私钥对(K Pub ,K Pri ),其中,K Pub =1+n,K Pri =λ;Alice 和 Bob 分
别将自己的数 a L ,a R 和 b 表示成数对形式 (a ,a ),(a ,a ) 与(b 1 ,b 2 ),使得:
1 L 2 L 1 R R 2
a a b
=
,
a L = 1 L ,a R = 1 R , = b 1 ,gcd(aa )gcd(a ,a R )gcd( , ) 1= b b = 1 2 .
a a b 1 L 2 L 1 R 2
2 L R 2 2
此处假定有理数都已经表示成分数形式了.
Step 1:Bob 利用自己的公钥将自己的数对(b 1 ,b 2 )加密:
C = (1 n r+ ) 1 b n mod n 2 (3a)
1 b 1 b
2 b
C = 2 b (1 n+ ) r n 2 b mod n 2 (3b)
,
并将得到的 (CC ) 发送给 Alice.
1 b 2 b
Step 2:Alice 收到 (CC ) 后按照如下方式工作.
,
1 b 2 b
*
,
① 随机选择 6 个不等的、长度为⎣logn⎦−1 的随机数 k 1 a ,k 2 a ,k′ 1 a ,k′ 2 a ,k′ 3 a ,k′ 4 a 和 4 个随机数 rr 2 a ,r 3 a ,r ∈ Z ,
4 a
n
1 a
利用 Paillier 变体方案加密及其同态性计算 2 个密文对 (C ( L b ⋅ a + ,C (a + ),(C ( R b +⋅ a ,C (a + ) :
2 1 ) k′ 1 a 1 L b ⋅ 2 ) k′ 1 a 2 1 ) k′ a 2 1 R b ⋅ 2 ) k′ a 2
′
C ( L b +⋅ 1 ) k′ = 1 a ((C 1 b ) 1 a k ⋅ a L 2 mod ) (1n × 2 + kkn )r n 1 a mod n 2 (4a)
1 a
a
1 a
2
+
′
C 2 ) k′ = ( ( C ) 1 a k ⋅ a 1 L mod n × 2 ) (1 kkn )r n mod n 2 (4b)
(a 1 L b ⋅ + 1 a 2 b 1 a 1 a 2 a
C ( R b +⋅ 1 ) k′ = ((C ) a k 2 a ⋅ R 2 mod ) (1n × 2 + k k′ ) n r n mod n 2 (5a)
a
2 a 2 1 b 2 a 2 a 3 a
C (a 1 R b ⋅ 2 ) k′ = + a 2 ((C 2 b ) a k 2 a ⋅ 1 R mod ) (1n × 2 + k k′ 2 a ) n r n 2 a mod n 2 (5b)
2 a
② 对两个密文对 (C ( L b ⋅ a + ,C (a + ),(C ( R b +⋅ a ,C (a + ) 同时在组内做相同的随机置换,并对两个密
2 1 ) k′ 1 a 1 L b ⋅ 2 ) k′ 1 a 2 1 ) k′ a 2 1 R b ⋅ 2 ) k′ a 2
文对也做随机置换得到密文对序列: (cc ),(c ,c ) ,简单地讲,随机选择下式并发给 Bob:
,
1 L 1 R 2 L R 2