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

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

problem, however, there are many other secure multi-computation problems needed to be investigated. This study involves private
relationship test on number axis, which covers three subproblems: (1) secure test on the relationship between a confidential number and a
private interval; (2) multi-dimensional secure test on the relationship between multi-number and multi-interval; (3) secure test on the
relationship between two confidential intervals. Private relationship test on number axis has an extensive application in the field of privacy
protection, and it can be employed as a basic block to construct other SMC protocols. Based on a variant encryption scheme of Paillier’s
homomorphic encryption (in which, who encrypts message who evaluates the base), three protocols for private relationship test on number
axis are designed. They are secure test on the relationship between a confidential number and a private interval, multi- dimension secure
test on the relationship between multi-number and multi-interval, and secure test on the relationship between two confidential intervals.
And their security is analyzed using simulation framework (idea/real) in the standard model. The idea of private ratio calculation in these
three protocols can be directly used to solve the millionaire problem within the range of rational numbers. More widely, these three
protocols can be employed as a basic block to solve the following SMC problems: private test on relationship between a point and an
annulus, private test on relationship between a point and a convex polygon, and private proximity test.
Key words: private relationship test; privacy protection; multiparty secure computation; distributed and collaborative computation

[1]
安全多方计算(secure multiparty computation,简称 SMC)首先由 Yao 以百万富翁问题的形式提出,是分布
式环境下一种用于保护用户隐私或数据安全的关键技术,是一种将密码学和分布式计算融合于一体的隐私保
[5]
护技术,是空间网络安全领域的研究热点之一,对于大数据用户隐私保护 [2−4] 、物联网用户隐私保护 、社交网
[8]
络用户隐私保护 [6,7] 、数据挖掘用户隐私保护 等具有重要意义.
自 SMC 提出后的 30 年间,很多学者从其可行性、计算模型与方法论、安全证明模型及理论、公平性以及
专有协议(或称用于解决专门问题的协议)等方面进行了大量研究并取得成果,但安全多方计算在分布式协同计
算领域还有若干值得研究的内容.在基础理论研究方面,需要研究一些更实用的理论模型;在基础协议方面,需
要设计更多高效的基础协议作为基本模块来构造其他安全多方计算协议.另外,还需要设计更多简单、高效且
实用的安全多方计算协议来满足越来越多的实际应用问题.
越来越多的实际应用需要将现有整数轴上关系的保密测定推广到有理数轴上关系的安全测定,迫切需要
解决点与区间关系的安全测定、多维点与区间关系的安全测定和区间之间关系的安全测定等问题.
(1) 点与区间关系的保密测定问题具体可以描述为:两个互不信任的参与者(其中一个拥有一个有理数 a,
?
另外一个拥有一个数据区间[b L ,b R ],其中,b L ,b R 皆为有理数)想通过协同计算完成保密关系的测定 a∈
[b L ,b R ]而不泄露双方的隐私.解决该问题的协议需要实现:两个互不信任的参与者协同完成保密关系
判定后,双方只能得到信息“保密有理数是否在区间内”;并且当保密有理数不在数域中时,协同计算不
会泄露保密有理数与数域上、下界的关系(小于上界、大于下界);
(2) 多维点与区间保密关系测定问题实质是点与区间保密关系测定问题的拓展,多维点与区间保密关系
测定问题具体描述为:不失一般性,假定 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 ,i=1,2,…,n,并且 a i1 ,a i2 ,b i 皆为有理数.Alice 与 Bob 想协同完成向量 B 与向量 A 关系的保密测定,具
体而言,Alice 与 Bob 想协同完成保密测定:对于任意的 i=1,2,…,n 而言,a i1 <b i <a i2 是否都成立;
(3) 两个区间关系的保密测定问题实质也是点与区间保密关系测定问题的拓展,两个区间关系的保密测
定具体可以描述为:两个互不信任的参与者(分别拥有一个上下界为有理数的区间)想通过协同计算
完成两区间保密关系的测定而不泄露双方的隐私.解决该问题的协议需要实现:分布式网络中的两个
用户(分别拥有一个上下界为有理数的数域)协同完成保密关系判定后,双方只能得到信息“保密区间
相交与否”;并且当两个保密区间相交时,协同计算不会泄露相交区间相交于双方各自区间的哪一端.
数轴上的保密关系测定问题不仅是安全多方计算中一个独立的新分支问题,还可作为基础工具,用于解决
分布式环境中某些专门安全多方计算问题.例如,可以作为基础工具,用于解决安全点与圆域包含关系测定问
题、安全点与无限区域包含关系测定问题、点与凸多边形包含关系测定问题(关于这些应用的具体阐释详见本
文第 2.2 节和第 3.2 节).