电子学报 ›› 2018, Vol. 46 ›› Issue (9): 2057-2062.DOI: 10.3969/j.issn.0372-2112.2018.09.002

• 学术论文 • 上一篇    下一篇

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

窦家维1, 王文丽1, 刘旭红1, 李顺东2   

  1. 1. 陕西师范大学数学与信息科学学院, 陕西西安 710119;
    2. 陕西师范大学计算机科学学院, 陕西西安 710119
  • 收稿日期:2017-09-20 修回日期:2018-02-08 出版日期:2018-09-25
    • 作者简介:
    • 窦家维 女,1963年生于陕西.现为陕西师范大学数学与信息科学学院硕士生导师.主要研究方向为应用数学和密码学.E-mail:jiawei@snnu.edu.cn;王文丽 女,1991年生于河南.研究生.主要研究方向为应用数学和密码学.E-mail:wenliwang@snnu.edu.cn;刘旭红 女,1992年生于山西.研究生.主要研究方向为应用数学和密码学.E-mail:xuhongliu@snnu.edu.cn;李顺东 男,1963年生于河南.陕西师范大学计算机科学学院博士生导师.主要研究方向为信息安全.E-mail:shundong@snnu.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.61272435)

Secure Multiparty Computation of Rational Interval and Its Applications

DOU Jia-wei1, WANG Wen-li1, LIU Xu-hong1, LI Shun-dong2   

  1. 1.School of Mathematics and Information Science, Shaanxi Normal University, Xi'an, Shaanxi 710119, China;
    2.School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710119, China
  • Received:2017-09-20 Revised:2018-02-08 Online:2018-09-25 Published:2018-09-25
    • Supported by:
    • National Natural Science Foundation of China (No.61272435)

摘要: 本文研究了有理数与有理区间的位置关系以及两个有理区间位置关系的安全多方计算.它们已广泛应用于数据库匹配、定位搜索等领域,是保密科学计算的一个重要分支.但目前已有文献在解决有理数与有理区间的位置关系时提出的协议效率较低,且两个有理区间位置关系问题的研究较为有限.针对这些问题,本文首先用多项式表示区间,将有理数与有理区间位置关系问题转化为整数向量的内积符号判定问题,设计了新的有理数与有理区间的保密计算协议.其次,以有理数与有理区间协议作为基础模块,设计了两个有理区间位置关系的保密计算协议.最后,理论分析及实验结果均表明本文方案是安全高效的,并给出了本文协议在有理数域上的百万富翁问题及计算几何问题的应用.

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

Abstract: 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.

Key words: cryptography, secure multiparty computation, rational number, rational interval, database matching, positioning search, millionaire problem, computation geometry

中图分类号: