安全向量优势协议及其应用

doi:10.3969/j.issn.0372-2112.2017.05.014

电子学报 ›› 2017, Vol. 45 ›› Issue (5): 1117-1123.DOI: 10.3969/j.issn.0372-2112.2017.05.014

安全向量优势协议及其应用

李顺东, 左祥建, 杨晓莉, 巩林明

陕西师范大学计算机科学学院, 陕西西安 710119

收稿日期:2016-01-18 修回日期:2016-07-04 出版日期:2017-05-25
- 作者简介:
- 李顺东 男,1963年12月生,河南平顶山人.2003年在西安交通大学获计算机科学与技术工学博士学位.陕西师范大学计算机科学学院教授、博士生导师.主要从事密码学与信息安全研究.E-mail:shundong@snnu.edu.cn;左祥建 男,1990年6月生,湖北荆州人.陕西师范大学硕士研究生,主要研究领域为密码学与信息安全.E-mail:zuoxiangjian@snnu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61272435）; 陕西师范大学研究生培养创新基金 (No.2015CX029）

Secure Vector Dominance Protocol and Its Applications

LI Shun-dong, ZUO Xiang-jian, YANG Xiao-li, GONG Lin-ming

School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710119, China

Received:2016-01-18 Revised:2016-07-04 Online:2017-05-25 Published:2017-05-25
- Supported by:
- National Natural Science Foundation of China (No.61272435); Postgraduate Cultivation Innovation Fund of Shaanxi Normal University (No.2015CX029)

摘要/Abstract

摘要：

百万富翁问题是安全多方计算研究的热点问题之一，也是其他安全多方计算协议的基本构成模块.安全向量优势统计问题是百万富翁问题的推广，用于两方在不泄漏自己保密向量信息的前提下统计出满足大于关系的分量的数目.本文基于同态加密算法，通过对保密的数据进行编码，设计了一个计算百万富翁问题的协议，并利用模拟范例对协议进行安全性证明.然后利用这个新的协议作为基本模块，设计了一个向量优势统计协议，通过效率分析显示我们的方案是简单、高效的.最后将向量优势统计协议应用到整除判定问题和点与若干直线关系判定问题.

关键词: 安全多方计算, 百万富翁问题, 同态加密, 向量优势统计

Abstract:

The millionaires' problem is an important problem in secure multiparty computation and a basic building block of secure multiparty computation protocols.Secure vector dominance statistic problem is a problem generalized for the millionaires' problem,which can be used to get the number of y_i>x_i without leaking further information.In this paper,we first propose an encoding scheme to encode private numbers; then based the new encoding scheme and homomorphic encryption scheme,we design a protocol for millionaires' problem and prove that the protocol is secure in the semi-honest model using the simulation paradigm.Then,we utilize this scheme to propose a solution to secure vector dominance statistic problem.The performance analysis indicates that our protocol is simpler and more efficient than the others.Finally,we use the scheme to solve the integer division problem and privately determine the relation between point and lines.

Key words: secure multi-party computation, millionaires' problem, homomorphic encryption, vector dominance statistic problem

中图分类号:

TP309

李顺东, 左祥建, 杨晓莉, 等. 安全向量优势协议及其应用[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.

参考文献

[1] C Yao.Protocols for secure computations[A].Proceedings of the 23th IEEE Symposium on Foundations of Computer Science[C].Chicago:IEEE Press,1982.160-164.
[2] Goldreich O,Micali S,Wigderson A.How to play any mental game[A].Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing[C].New York:ACM,1987.218-229.
[3] Goldreich O.Foundations of Cryptography:Volume 2,Basic Applications[M].London:Cambridge University Press,2004.599-764.
[4] Du W,Atallah M J.Privacy-preserving cooperative scientific computations[A].Proceedings of the 14th IEEE workshop on Computer Security Foundations[C].Canada:IEEE Computer Society,2001.273.
[5] Choi S G,Hwang K W,Katz J,et al.Secure Multi-Party Computation of Boolean Circuits with Applications to Privacy in On-line Marketplaces[M].Berlin:Springer Berlin Heidelberg,2012.416-432.
[6] Li Y,Chen M,Li Q,et al.Enabling multilevel trust in privacy preserving data mining[J].Knowledge and Data Engineering,IEEE Transactions on,2012,24(9):1598-1612.
[7] Toft T.Secure data structures based on multi-party computation[A].Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing[C].New York:ACM,2011.291-292.
[8] Loftus J,Smart N P.Secure Outsourced Computation[M].Progress in Cryptology-AFRICACRYPT 2011.Berlin:Springer Berlin Heidelberg,2011.1-20.
[9] A C Yao.How to generate and exchange secrets[A].Proceedings of 27th Annual Symposium on Foundations of Computer Science (FOCS'86)[C].Toronto:IEEE,1986.162-167.
[10] Ioannidis and A.Grama.An efficient protocol for Yao's millionaires' problem[A].Proceedings of the 36th Hawaii Interna-tional Conference on System Sciences[C].Hawaii:IEEE,2003.6-9.
[11] 秦静,张振峰,冯登国,李宝.无信息泄漏的比较协议[J].软件学报,2004,15(3):421-427. Qin Jing,Zhang Zhen-feng,Feng Deng-guo,Li Bao.A protocol of comparing information without leaking[J].Journal of Software,2004,15(3):421-427.(in Chinese)
[12] Sheikh R,Mishra D K,Kumar B.Secure multiparty computation:from millionaires problem to anonymizer[J].Information Security Journal:A Global Perspective,2011,20(1):25-33.
[13] Grigoriev D,Shpilrain V.Yao's millionaires' problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(04):409-417.
[14] Karimian Ardestani N.Efficient Non-Interactive Secure Two-Party Computation for Equality and Comparison[D].Canada:University of Calgary,2015.
[15] Lipmaa H,Toft T.Secure Equality and Greater-Than Tests with Sublinear Online Complexity[M].Automata,Languages and Programming.Berlin:Springer Berlin Heidelberg,2013.645-656.
[16] Lin H Y,Tzeng W G.An efficient solution to the millionaires' problem based on homomorphic encryption[A].Applied Cryptography and Network Security[C].Berlin:Springer Berlin Heidelberg,2005.456-466.
[17] 李顺东,王道顺.基于同态加密的高效多方保密计算[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)
[18] Atallah M J,Du W.Secure Multi-Party Computational Geometry[M].Algorithms and Data Structures.Berlin:Springer Berlin Heidelberg,2001.165-179.
[19] 刘文,罗守山,王永滨.安全两方向量优势统计协议及其应用[J].电子学报,2010,38(11):2573-2577. Liu Wen,Luo Shou-shan,Wang Yong-bin.Secure two-party vector dominance statistic protocol and Its application[J].Acta Electronica Sinica,2010,38(11):2573-2577.(in Chinese)
[20] 钱小强,仲红,石润华.无茫然第三方的安全两方向量优势统计协议[J].计算机工程,2014,40(2):148-152. Qian Xiao-qiang,Zhong Hong,Shi Run-hua.Secure two-party vector dominance statistic protocol without oblivious third party[J].Computer Engineering,2014,40(2):148-152.(in Chinese)
[21] Paillier P.Public-key cryptosystems based on composite degree residuosity classes[A].Advances in cryptology-EUROCRYPT'99[C].Berlin:Springer Berlin Heidelberg,1999.223-238.

安全向量优势协议及其应用

Secure Vector Dominance Protocol and Its Applications

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李顺东, 赵雪玲, 家珠亮. 集合交集元素和的保密计算[J]. 电子学报, 2023, 51(1): 86-92.
[2]	丁毅, 沈薇, 李海生, 钟琼慧, 田明宇, 李洁. 面向CNN的区块链可信隐私服务计算模型[J]. 电子学报, 2022, 50(6): 1399-1409.
[3]	汪榆淋, 窦家维. k-min问题安全多方计算方案及应用[J]. 电子学报, 2021, 49(11): 2256-2260.
[4]	宋秀丽, 周道洋, 文爱君. d维(t,n)门限量子同态加密算法的设计与仿真[J]. 电子学报, 2020, 48(5): 846-853.
[5]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[6]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[7]	侯红霞, 杨波, 张丽娜, 张明瑞. 安全的两方协作SM2签名算法[J]. 电子学报, 2020, 48(1): 1-8.
[8]	李秋贤, 田有亮, 王缵. 基于全同态加密的理性委托计算协议[J]. 电子学报, 2019, 47(2): 470-474.
[9]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[10]	窦家维, 李顺东. 数据相等问题的安全多方计算方案研究[J]. 电子学报, 2018, 46(5): 1107-1112.
[11]	李子臣, 张卷美, 杨亚涛, 张峰娟. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938-944.
[12]	段然, 顾纯祥, 祝跃飞, 郑永辉, 陈莉. 一种NTRU格上基于身份全同态加密体制设计[J]. 电子学报, 2018, 46(10): 2410-2417.
[13]	李顺东, 杨晓莉, 左祥建, 周素芳, 亢佳, 刘新. 保护私有信息的图形相似判定[J]. 电子学报, 2017, 45(9): 2184-2189.
[14]	窦家维, 马丽, 李顺东. 最小值问题的安全多方计算及其应用[J]. 电子学报, 2017, 45(7): 1715-1721.
[15]	陈振华, 李顺东, 王道顺, 黄琼, 张卫国. 集合成员关系的安全多方计算及其应用[J]. 电子学报, 2017, 45(5): 1109-1116.