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

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

定问题,但该协议在调用 Paillier 同态加密方案的基础还需要 3 次调用百万富翁协议.文献[21]采用比特值串联
和放大倍数的思想设计了一个点与区间关系的保密测定协议,该协议试图解决一个实数点是与一个连续实数
区间关系测定问题,但该协议并未考虑下列不成功的情形:假定实数点为 a=30.0000000073,连续实数区间的一
10
个端点为 b j =30.0000000073221,j∈{L,R},L,R 分别用于标识一个区间的下、上界,如果采用该方法都扩大 10 后
再作为保密输入解决一个实数点与一个连续实数区间关系测定问题,不但不能解决问题,还给协议带来繁重的
计算开销.
上述 3 个区间保密计算协议很好地解决了数轴上保密关系测定问题的一个子问题:点与区间保密关系测
定,但还有很多需要改进的地方,还有其他保密区间计算问题需要开拓.
本文借鉴百万富翁问题的解决思路,采用两个数的比值与 1 的保密关系测定,将保密区间计算问题拓展到
新的、更大的解决范围:保密数和区间的端点为有理数.将保密区间计算问题转化为一个分数与两个分数的保
密比较在同一进程中一次并发执行问题.基于该方法设计了 3 个高效的区间保密计算协议:(1) 面向有理数或分
数的点与区间关系的保密测定协议;(2) 面向有理数或分数的多维点与区间保密关系测定协议;(3) 面向有理数
或分数的区间与区间关系的保密测定协议.
本文的主要贡献:
1. 提出了数轴上的保密关系测定问题应分为 3 个值得研究的子问题:(1) 点与区间关系的保密测定;
(2) 多维点与区间保密关系测定;(3) 区间与区间关系的保密测定;
2. 基于“两个数的安全比值与 1 的关系判定两个数的大小”,设计了 3 个用于解决面向有理数或分数的保
密区间计算协议,拓展了问题的解决范围;
3. 提出一种高效的百万富翁问题通用解决方法,该方法可以用于解决同一进程中一个数与两个数关系
的保密比较问题,同时还将百万富翁问题的解决范围拓展至分数范围.
1 预备知识

1.1 Paillier变体同态加密方案
文献[22]构造了一个 Paillier 变体同态加密方案,如图 1 所示.

符号记法:
p 与 q 是大素数,|p|=|q|,n=pq,λ=lcm(p−1,q−1),g=1+n,

X − 1 *
() =
LX , X ∈ Z 2
n n
加密:
对于明文 m<n
选择 3 个随机数 0<k,r 1,r 2<n
计算密文:
mn
g k=(1+n) mod n , c = k 2 k g r 1 mod ,n c = 2 k g r 2 mod n ;
2
n
1 2
2
对于密文对(c 1,c 2),其中,c 1,c 2< n

λ
( Lc 1 mod )n 2
恢复明文 m = mod n

( mod )n
Lc λ 2 2
Fig.1 A variant scheme from Paillier’s homomorphic scheme
图 1 Paillier 变体同态加密方案
该方案在高阶剩余类判定性困难假设下被证明具有选择明文攻击不可区分安全性(证明详见文献[22]第
2.3 节).该方案与 Paillier 原方案相比具有如下性质.
(1) 该方案中两个密文分量各自保持了良好的加法同态性:
C i (x+y)=C i (x)⋅C i (y) (1a)
( ×
Cx ) y = C i y ( )x = C i x ( )y (1b)
i
其中,C i (x),C i (y),C i (x+y)分别是明文 x,y 与 x+y 对应的第 i(i∈{1,2})个密文分量.