有理区间的安全多方计算与应用  

Secure Multiparty Computation of Rational Interval and Its Applications

作　　者：窦家维[1] 王文丽 刘旭红 李顺东[2] DOU Jia-wei;WANG Wen-li;LIU Xu-hong;LI Shun-dong(School of Mathematics and Information Science,Shaanxi Normal University,Xi′an,Shaanxi 710119,China;School of Computer Science,Shaanxi Normal University,Xi′an,Shaanxi 710119,China)

机构地区：[1]陕西师范大学数学与信息科学学院,陕西西安710119 [2]陕西师范大学计算机科学学院,陕西西安710119

出　　处：《电子学报》2018年第9期2057-2062,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61272435)

摘　　要：本文研究了有理数与有理区间的位置关系以及两个有理区间位置关系的安全多方计算.它们已广泛应用于数据库匹配、定位搜索等领域,是保密科学计算的一个重要分支.但目前已有文献在解决有理数与有理区间的位置关系时提出的协议效率较低,且两个有理区间位置关系问题的研究较为有限.针对这些问题,本文首先用多项式表示区间,将有理数与有理区间位置关系问题转化为整数向量的内积符号判定问题,设计了新的有理数与有理区间的保密计算协议.其次,以有理数与有理区间协议作为基础模块,设计了两个有理区间位置关系的保密计算协议.最后,理论分析及实验结果均表明本文方案是安全高效的,并给出了本文协议在有理数域上的百万富翁问题及计算几何问题的应用.The SMC(Secure Multiparty Computation)of the location relation between rational numbers and intervals,and that between two rational intervals has been investigated.As an important branch of the confidential scientific computing,this problem was widely applied in database matching,positioning search,etc.However,there still exist many problems,for example,current solutions to the location relation between rational numbers are low efficiency and the research on the location relation between two rational intervals is limited.In order to address the above gaps,firstly,we use polynomials to represent the interval,and convert the problem into determining the scalar product signs of two integer vectors.Thus,the new protocol of the problem between rational number and interval is worked out.Secondly,with the proposed scheme as the basic module,we construct the protocol of the location relation between two rational intervals.Finally,the theoretical analysis and experimental results prove that our protocols are safe and efficient,and we give the application of millionaire problem and computational geometry problem in rational domain.

关 键 词：密码学 安全多方计算 有理数 有理区间 数据库匹配 定位搜索 百万富翁问题 计算几何 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]