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

doi:10.3969/j.issn.0372-2112.2018.09.002

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

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

窦家维¹, 王文丽¹, 刘旭红¹, 李顺东²

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-wei¹, WANG Wen-li¹, LIU Xu-hong¹, LI Shun-dong²

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

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

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

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

中图分类号:

TP309

窦家维, 王文丽, 刘旭红, 等. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.

DOU Jia-wei, WANG Wen-li, LIU Xu-hong, et al. Secure Multiparty Computation of Rational Interval and Its Applications[J]. Acta Electronica Sinica, 2018, 46(9): 2057-2062.

参考文献

[1] Yao A C.Protocols for secure computations[A].Proceedings of the 23th IEEE Symposium on Foundations of Computer Science[C].Chicago,USA:IEEE Computer Society Press,1982.160-164.
[2] Cramer R,Damgard I B,Nielsen JB.Secure Multiparty Computation[M].London,UK:Cambridge University Press,2015.
[3] Goldreich O.The Fundamental of Cryptography:Basic Applications[M].London,UK:Cambridge University Press,2004.
[4] 李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803. Li Shun-dong,Wang Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese)
[5] 李顺东,左祥建,杨晓莉,等.安全向量优势协议及其应用[J].电子学报,2017,45(5):1117-1123. Li Shun-dong,Zuo Xiang-jian,Yang Xiao-li,et al.Secure vector dominance protocol and its applications[J].Acta Electronica Sinica,2017,45(5):1117-1123.(in Chinese)
[6] Tang Chun-ming,Shi Gui-hua,Yao Zheng-an.Secure multi-party computation protocol for sequencing problem[J].Science China Information Sciences,2011,54(8):1654-1662.
[7] Zhou Su-fang,Li Shun-dong,Dou Jia-wei,et al.Efficient secure multiparty subset computation[J].Security & Communication Networks,2017,2017(3):1-11.
[8] Nishide T,Ohta K.Multiparty Computation for Interval,Equality and Comparison Without Bit-Decomposition Protocol[M].Berlin:Springer Berlin Heidelberg,2007.343-360.
[9] 郭奕旻,周素芳,窦家维,等.高效的区间保密计算及应用[J].计算机学报,2017,40(07):1664-1679. Guo Yi-min,Zhou Su-fang,Dou Jia-wei,et al.Efficient privacy-preserving interval computation and its applications[J],Chinese Journal of Computers,2017,40(07):1664-1679.(in Chinese)
[10] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[A].G.Goos.Lecture Notes in Computer Science 1592[C].NY:Springer,1999.223-238.

[1]	李顺东, 赵雪玲, 家珠亮. 集合交集元素和的保密计算[J]. 电子学报, 2023, 51(1): 86-92.
[2]	金紫凤, 潘思聪, 危辉. 可变环境下基于位姿变换矩阵的机器人无标定手眼协调方法[J]. 电子学报, 2022, 50(10): 2318-2328.
[3]	赵璐, 刘春红, 杜蛟, 曹天庆. Z₄上两类具有最优自相关四元序列的线性复杂度研究[J]. 电子学报, 2021, 49(4): 631-636.
[4]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[5]	陈露, 相峰, 孙知信. 基于属性密码体制的区块链安全技术研究进展[J]. 电子学报, 2021, 49(1): 192-200.
[6]	窦家维, 王颖囡, 葛雪. 区间关系保密计算若干问题研究[J]. 电子学报, 2021, 49(1): 50-57.
[7]	戚珉, 陈明. 标准模型下基于身份的混淆乐观公平交换方案[J]. 电子学报, 2020, 48(8): 1516-1527.
[8]	杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(2): 291-295.
[9]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[10]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[11]	杨小东, 王美丁, 裴喜祯, 李雨潼, 陈春霖, 麻婷春. 一种标准模型下无证书签名方案的安全性分析与改进[J]. 电子学报, 2019, 47(9): 1972-1978.
[12]	杜蛟, 刘春红, 张恩, 尚玉婧, 董乐. 基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造[J]. 电子学报, 2018, 46(9): 2173-2180.
[13]	董丽华, 曾勇, 王春红, 胡予濮. LFCSR:基于FCSR的新密码学部件[J]. 电子学报, 2018, 46(8): 1924-1930.
[14]	窦家维, 李顺东. 数据相等问题的安全多方计算方案研究[J]. 电子学报, 2018, 46(5): 1107-1112.
[15]	李顺东, 杨晓莉, 左祥建, 周素芳, 亢佳, 刘新. 保护私有信息的图形相似判定[J]. 电子学报, 2017, 45(9): 2184-2189.

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

Secure Multiparty Computation of Rational Interval and Its Applications

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics