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

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

解决数轴上的保密关系测定问题实质是解决同一进程中一个数与两个数关系的保密比较问题,属于安全
多方计算中百万富翁问题的推广.一般百万富翁问题是两个数据的一次保密比较,而点和与区间关系的保密测
定问题是一个数与两个数在同一进程中的保密比较问题,它比一般百万富翁问题在安全性方面要求更苛刻.区
间上的保密计算问题与百万富翁问题有相同之处,同时也有它独有的特点:设计解决区间上的保密计算问题的
协议时,一方面需要采用百万富翁问题的思想;另一方面,还需要考虑同一进程中被重复利用两次的私有数据的
特殊安全性问题.
• 相关研究
姚期智教授在文献[1]中提出了著名的百万富翁问题:两个百万富翁想通过协同计算得知谁更富有,但协同
计算完成后,二者在得到谁更富有的同时,不能向对方泄露彼此的财产值,因此需要设计一个安全比较协议满
足:在不泄露双方私有数据的前提下,参与双方通过协同计算得出双方私有数据的大小关系.该问题激发了密码
学者们的研究热情,目前,研究者在该领域取得了诸多成果.
[9]
Boudot 等人 基于离散对数困难假设构造了一个解决百万富翁问题的公平协议,该协议在公平模型下解
决了两个数的相等与否的保密测定.Fischlin [10] 基于概率加密方案 [11] ,在半诚实模型下设计了一个非交互式百
万富翁协议.该协议的一次执行可以保密地测定出两个数的关系是大于还是小于等于,却不能具体测定出小于
和等于的关系.Ioannidis 等人 [12] 构造了基于二选一不经意传输的百万富翁协议,该协议的效率取决于保密输入
的长度和安全参数.文献[13]设计了相比 Yao 协议效率高、解决百万富翁问题的协议,但该协议仍然存在计算冗
余.文献[14]首先提出一种 0-1 编码方法,然后利用该方法将百万富翁问题归约到保密集合交集计算问题,最后
结合同态加密,漂亮地解决了百万富翁问题,该协议的效率会随着保密输入长度的增加而降低.Garay 等人 [15] 构
造了两个通信复杂度分别为对数轮和常数轮的协议,它们只能用于解决整数范围内的百万富翁问题.文献[16]
首先设计了一个新的 0-1 编码方法,然后利用该方法将百万富翁问题归约到保密向量标积计算问题,最后基于
Paillier 同态加密方案,构造了一个高效的百万富翁协议,该协议的效率会随着保密输入长度的增加而降
低.Gordon 等人 [17] 基于不经意函数计算思想构造了一个完全公平的、解决百万富翁问题的协议,该协议的一次
执行可以测定出两个保密数是大于还是小于等于,却不能测定出小于和等于.
文献[18]利用对称密码和归约思想(将百万富翁问题归约到保密集合元素的测定问题)设计了一个解决百
万富翁问题的高效协议,该协议因采用对称密码设计,效率较上述协议有了很大提高,但该协议的一次执行不能
测定出两个保密数是大于和等于的关系.有限集合元素的测定问题可以形式化描述为测定一个正整数是否是
?
+
一个正整数构成的集合的元素: x X∈ ,其中,X={x 1 ,…,x k },x,x 1 ,…,x k ∈Z .该问题可以看作数轴上保密关系测定问
题的一种特殊情形,因为集合 X 是由数轴上离散的整数点构成,因而解决保密集合元素测定协议的计算开销会
随着集合元素的增多而呈线性增长.而以有理数为端点的区间是无限集合,在此种情况下,面向整数的保密有限
集合元素测定协议将变得不实用.
上述诸多成果非常好地解决了百万富翁问题,但还存在一些问题需要改进和一些未彻底解决的问题需要
继续解决:现有解决百万富翁问题的协议大都解决的是整数集上的比较问题,数轴上保密关系测定问题实质是
百万富翁协议在一个进程的两次执行,如果也采用这些协议中的方法解决数轴上保密关系测定问题,则注定所
设计的数轴上保密关系测定协议只能解决整数集上的问题,从而限定了数轴上保密关系测定问题的研究意义
和应用范围.如果数轴上保密关系测定能够解决以有理数为端点的连续区间上的保密计算(一个保密有理数与
一个以保密有理数为端点的连续区间的包含关系测定)问题,则其具有更大的研究价值和应用价值.因此在研究
数轴上保密关系测定问题时,不仅要借鉴现有百万富翁协议问题的解决方法,还需要在此方法上加以创新,才能
使数轴上保密关系测定协议具有更广泛的应用天地,更贴合实际的应用场景.
数轴上保密区间关系测定问题最初由 Nishide 等人 [19] 以保密区间计算问题的形式提出.Nishide 等人设计
的保密区间计算协议很好地解决了整数轴上关于开区间上关系的保密测定问题,但在安全性方面,并没有实现
对参与方隐私的充分保护,会造成整数点靠近保密区间上界还是下界这一信息泄露的安全隐患.文献[20]采用
几何保密计算方法设计了一个点与区间关系的保密测定协议,漂亮地解决了有理点与有理区间关系的保密测