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

3954 Journal of Software 软件学报 Vol.31, No.12, December 2020

(2) 加密底数可以由无密钥一方计算的良好性质,该性质在半诚实模型下的保密计算两个数的比值与“1”
的大小关系问题中可以确保无密钥一方私有数据的安全性.
保密计算两个数的比值与“1”的大小关系问题描述:不失一般性,假设 Alice(私有输入为 x a )和 Bob(私有输入
为 x b )是两个参与方,二者通过协作计算 x a /x b 与“1”的大小关系而不泄露 x a 与 x b 的数值.
假定 Alice 拥有 Paillier 变体加密方案的私钥,Bob 只有公钥,则 Alice 与 Bob 按照如下方式可以保密计算
x a /x b 与“1”的大小关系而不泄露 x a 与 x b 的数值.
+
① Alice 随机选择一个数 r ∈ Z ,并用自己的公钥做部分加密计算下式,然后将 C a1 发送给 Bob:
1 a
n
2
C = a 1 Enc ()x a = (1 x+ a n ⋅ ) mod r a n n ;
+
② 在 Alice 计算 C a1 的同时,Bob 随机选择 4 个数 rr ,r k ∈ Z ,并计算:
,
,
1 b b 2 b 3 n
2
C = 2 g kx⋅ b r+ b 3 r b n 2 mod n = 2 (1 (k x+ ⋅ b + r b 3 ) n⋅ )r b n 2 mod n ;
收到 C a1 后,Bob 利用密文分量的同态特性实施换底运算下式,然后将密文对(C 1 ,C 2 )发送给 Alice:
k
C = 1 C g r n 1 b mod n = 2 (1 (k x+ ⋅ a + r b 3 ) )n r n 1 b mod n ;
2
b r
3
1 a
③ Alice 收到(C 1 ,C 2 )后,利用自己的私钥计算:
( LC λ mod )n 2 k x⋅ + r
m = R 1 = a b 3 ,
2
n
( LC λ mod ) k x⋅ b + r b 3
2
根据 m R 与 1 的关系,Alice 可以得出 x a 与 x b 的大小关系.
显然,在该协议中,Alice 虽然是加密系统私钥的拥有者,她却无法通过解密运算得到 Bob 的私有输入 x b .这
是因为在这个过程中至多得到两个关于 3 个未知数 x b ,r b3 ,k 的方程.具体的安全性证明与本文中定理 1 的证明
过程相同,在此不再赘述.
(3) 与其他同态加密方案相比,文献[22]所述方案更适用于解决数轴上的保密关系测定问题.数轴上保密关
系测定问题实质是保密计算两个数的比值与“1”的大小关系问题;而保密比值传递是解决保密计算两个数的比
值与“1”的大小关系问题的关键技术.相比 ElGamal [23] ,DJ [24] 和 Paillier 等同态加密方案,文献[22]所述方案更适
用于解决保密比值传递(具体论述详见文献[22]的第 2.4 节).
1.2 关于安全多方计算的安全性定义 [22,25]
本文用到的关于安全多方计算的安全性定义包括定义 1(理想保密计算协议)、定义 2(半诚实参与者)以及
函数的保密计算的形式化定义,这些定义的详细表述请见文献[22].
根据定义 [22,25] ,对于 f,如果存在概率多项式时间模拟算法S 1 与S 2 使得:
c
{( ( , ( , )),a f a bS 1 1 f 2 ( , ))}a b , ab ≡ {(view 1 π ( , ),a b output π 2 ( , ))}a b , ab (2a)
c
{( ( , ),f a b S 2 ( ,a f 2 ( , )))}a b , ab ≡ {(output 1 π ( , ),a b view π 2 ( , ))}a b , ab (2b)
1
c
成立(其中, ≡ 表示计算上不可区分),则称π可以保密地计算 f(a,b).
1.3 安全多方计算通信模型

安全多方计算协议包含两种通信模型:信息论模型和密码学模型.信息论模型规定参与者之间必须通过一
条安全信道传递所有信息,并且假定攻击者具有无限的计算能力;密码学模型规定攻击者可以看到通信者之间
传递的信息但不能改动这些信息,并且假定攻击者具有概率多项式时间的攻击能力.因本文协议是基于同态密
码系统设计的,即参与者之间的通信属于密码学模型通信范畴,所以本文从同态密码学语义不可区分安全的角
度去分析协议的安全性.

2 数轴上数与区间保密关系测定通用协议

本文中,数与区间保密关系测定“通用协议”指的是数与区间保密关系测定协议不仅可以解决整数范围内