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

doi:10.3969/j.issn.0372-2112.2018.09.002

PDF(864 KB)

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

学术论文

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

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

作者信息 +

Secure Multiparty Computation of Rational Interval and Its Applications

DOU Jia-wei¹, WANG Wen-li¹, LIU Xu-hong¹, LI Shun-dong²

Author information +

文章历史 +

摘要

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

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.

导出引用

窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062. https://doi.org/10.3969/j.issn.0372-2112.2018.09.002

DOU Jia-wei, WANG Wen-li, LIU Xu-hong, LI Shun-dong. Secure Multiparty Computation of Rational Interval and Its Applications[J]. Acta Electronica Sinica, 2018, 46(9): 2057-2062. https://doi.org/10.3969/j.issn.0372-2112.2018.09.002

中图分类号： TP309

参考文献

[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.