一种高效的百万富翁问题协议及其应用

doi:10.19678/j.issn.1000-3428.0057131

计算机工程 ›› 2021, Vol. 47 ›› Issue (2): 168-175. doi: 10.19678/j.issn.1000-3428.0057131

一种高效的百万富翁问题协议及其应用

张静, 何铮, 葛炳辉, 汤永利, 叶青

河南理工大学计算机科学与技术学院, 河南焦作 454000

收稿日期:2020-01-06 修回日期:2020-02-19 出版日期:2021-02-15 发布日期:2020-03-11
作者简介:张静(1978-),女,副教授、博士,主研方向为网络与信息安全、安全多方计算;何铮、葛炳辉,硕士研究生;汤永利,教授、博士;叶青,讲师、博士。
基金资助:
国家自然科学基金（61802117）；河南省高等学校重点科研项目（18B520018，19A520025）；河南理工大学创新型科研团队支持计划（T2018-1）。

An Efficient Protocol for Millionaires' Problem and Its Application

ZHANG Jing, HE Zheng, GE Binghui, TANG Yongli, YE Qing

College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454000, China

Received:2020-01-06 Revised:2020-02-19 Online:2021-02-15 Published:2020-03-11

摘要/Abstract

摘要： 百万富翁问题是安全多方计算的基础问题，但现有解决方案计算复杂度高且效率较低，在两数相等时无法进行精确比较。针对该问题，提出一种基于0-1编码的百万富翁问题协议。使用改进的0-1保密数据编码规则构建向量，利用ElGamal同态加密变体算法的同态性质，将百万富翁问题转化为向量中两元素求和的问题，同时在半诚实模型下利用模拟范例证明协议的正确性与安全性，并将其应用于安全两方集合交集个数问题的求解。实验结果表明，与采用ElGamal和Paillier同态加密算法的协议相比，该协议计算复杂度更低且效率更高，可在两数相等时进行准确对比。

关键词: 安全多方计算, 百万富翁问题, 0-1编码, 同态加密, 集合交集个数

Abstract: The existing solutions to the Millionaires' Problem(MP),a basic problem in Secure Multi-Party Computation(SMC),have high computational complexity and low efficiency,and the two numbers can not be compared accurately when they are equal.To solve the problems,this paper proposes a protocol for MP based on 0-1 coding.The improved 0-1 secret data coding rule is used to construct the vector.By using the homomorphic property of the ElGamal homomorphic encryption variant algorithm,the MP is transformed into the sum of two elements in the vector.In the semi-honest model,the simulation examples are used to prove the correctness and security of the protocol,and the protocol is applied to solving the number of intersection sets of two secure parties.Experimental results show that compared with the protocols using ElGamal and Paillier homomorphic encryption algorithms,the proposed protocol has lower computational complexity and higher efficiency,and the two numbers can be compared accurately when they are equal.

Key words: Secure Multi-Party Computation(SMC), Millionaires' Problem(MP), 0-1 coding, homomorphic encryption, number of set intersections

中图分类号:

TP309

张静, 何铮, 葛炳辉, 汤永利, 叶青. 一种高效的百万富翁问题协议及其应用[J]. 计算机工程, 2021, 47(2): 168-175.

ZHANG Jing, HE Zheng, GE Binghui, TANG Yongli, YE Qing. An Efficient Protocol for Millionaires' Problem and Its Application[J]. Computer Engineering, 2021, 47(2): 168-175.

https://www.ecice06.com/CN/Y2021/V47/I2/168

图/表 5

20210225092119

20210225092143

20210225092147

20210225092154

20210225092158

参考文献 22

[1]	FRITCHMAN K,SAMINATHAN K,DOWSLEY R,et al.Privacy-preserving scoring of tree ensembles:a novel framework for AI in healthcare[C]//Proceedings of 2018 IEEE International Conference on Big Data.Washington D.C.,USA:IEEE Press,2018:2413-2422.
[2]	SUNDARI S,ANANTHI M.Secure multi-party computation in differential private data with data integrity protection[C]//Proceedings of 2015 International Conference on Computing and Communications Technologies.Washington D.C.,USA:IEEE Press,2015:180-184.
[3]	CUI Weirong,DU Chenglie,CHEN Jinchao.PSP:proximity-based secure pairing of mobile devices using WIFI signals[J].Wireless Networks,2019,25(2):733-751.
[4]	YAO A C.Protocols for secure computations[C]//Proceedings of the 23rd IEEE Sympsoium on Foundations of Computer Science.Washington D.C.,USA:IEEE Press,1982:160-164.
[5]	GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing.New York,USA:ACM Press,1987:218-229.
[6]	YAO A C.How to generate and exchange secrets[C]//Proceedings of the 27th Annual Symposium on Foundations of Computer Science.Washington D.C.,USA:IEEE Press,1986:162-167.
[7]	IOANNIDIS I,GRAMA A.An efficient protocol for Yao's millionaires' problem[C]//Proceedings of the 36th Annual Hawaii International Conference on System Sciences.Washington D.C.,USA:IEEE Press,2003:6-9.
[8]	QIN Jing,ZHANG Zhenfeng,FENG Dengguo,et al.A protocol of comparing information without leaking[J].Journal of Software,2004,15(3):421-427.(in Chinese)秦静,张振峰,冯登国,等.无信息泄露的比较协议[J].软件学报,2004,15(3):421-427.
[9]	JIA Hengyue,WEN Qiaoyan,SONG Tingting,et al.Quantum protocol for millionaire problem[J].Optics Communications,2011,284(1):545-549.
[10]	JAWUREK M,KERSCHBAUM F,ORLANDI C.Zero-knowledge using garbled circuits:how to prove non-algebraic statements efficiently[C]//Proceedings of 2013 ACM SIGSAC Conference on Computer and Communications Security.New York,USA:ACM Press,2013:955-966.
[11]	NAKAI T,TOKUSHIGE Y,MISAWA Y,et al.Efficient card-based cryptographic protocols for millionaires' problem utilizing private permutations[C]//Proceedings of 2016 International Conference on Cryptology and Network Security.Berlin,Germany:Springer,2016:500-517.
[12]	MIYAHARA D,HAYASHI Y,MIZUKI T,et al.Practical and easy-to-understand card-based implementation of Yao's millionaire protocol[C]//Proceedings of 2018 International Conference on Combinatorial Optimization and Applications.Berlin,Germany:Springer,2018:246-261.
[13]	ONO H,MANABE Y.Efficient card-based cryptographic protocols for the millionaires' problem using private input operations[C]//Proceedings of 2018 Asia Joint Conference on Information Security.Washington D.C.,USA:IEEE Press,2018:23-28.
[14]	MOHASSEL P,ROSULEK M,ZHANG Y.Fast and secure three-party computation:the garbled circuit approach[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security.New York,USA:ACM Press,2015:591-602.
[15]	ZHAO Chuan,ZHAO Shengnan,ZHANG Bo,et al.Secure comparison under ideal/real simulation paradigm[J].IEEE Access,2018,6(5):31236-31248.
[16]	LIN H Y,TZENG W G.An efficient solution to the millionaires' problem based on homomorphic encryption[C]//Proceedings of 2005 International Conference on Applied Cryptology and Network Security.Berlin,Germany:Springer,2005:456-466.
[17]	LIU Xin,LI Shundong,LIU Jian,et al.Secure multiparty computation of a comparison problem[J].SpringerPlus,2016,5(1):1489-1497.
[18]	LIU M,NANDA P,ZHANG X,et al.Asymmetric commutative encryption scheme based efficient solution to the millionaires problem[C]//Proceedings of 2018 IEEE International Conference on Big Data Science and Engineering.Washington D.C.,USA:IEEE Press,2018:990-995.
[19]	LI Zhanli,CHEN Lichao,CHEN Zhenhua,et al.Design and applications of efficient protocol of millionaires' problem based on 1-r encoding[J].Journal of Cryptologic Research,2019,6(1):50-60.(in Chinese)李占利,陈立朝,陈振华,等.基1-r编码的高效百万富翁问题协议及应用[J].密码学报,2019,6(1):50-60.
[20]	LI Shundong,ZUO Xiangjian,YANG Xiaoli,et al.Secure vector dominance protocol and its applications[J].Acta Electronica Sinica,2017,45(5):1117-1123.(in Chinese)李顺东,左祥建,杨晓莉,等.安全向量优势协议及其应用[J].电子学报,2017,45(5):1117-1123.
[21]	ZUO Xiangjian,LI Shundong,YANG Xiaoli.An efficient homomorphic encryption based solution to millionaires' problem[J].Journal of Chinese Computer Systems,2017,38(3):455-459.(in Chinese)左祥建,李顺东,杨晓莉.同态加密的百万富翁问题高效解决方案[J].小型微型计算机系统,2017,38(3):455-459.
[22]	FREEDMAN M J,HAZAY C,NISSIM K,et al.Efficient set intersection with simulation-based security[J].Journal of Cryptology,2016,29(1):115-155.

选择文件类型/文献管理软件名称

选择包含的内容

一种高效的百万富翁问题协议及其应用

An Efficient Protocol for Millionaires' Problem and Its Application

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王以良, 周鹏, 叶卫, 戚伟强. 基于金字塔网络的非侵入式负荷辨识及其隐私保护方案[J]. 计算机工程, 2024, 50(5): 182-189.
[2]	于莹莹, 丁红发, 蒋合领. 图数据精确最短距离的隐私保护外包计算方案[J]. 计算机工程, 2023, 49(9): 158-171.
[3]	杨越佳, 华蓓, 钟志威, 高咪. 基于同态加密的隐私保护逻辑回归协同计算[J]. 计算机工程, 2023, 49(4): 23-31.
[4]	郑云涛, 叶家炜. 基于茫然传输协议的FATE联邦迁移学习方案[J]. 计算机工程, 2023, 49(2): 24-30.
[5]	张晓均, 张经伟, 黄超, 唐伟. 可验证的云存储医疗加密数据统计分析方案[J]. 计算机工程, 2021, 47(6): 32-37,43.
[6]	王元庆, 刘百祥. 一种去中心化的隐私保护匿名问卷方案[J]. 计算机工程, 2021, 47(6): 123-131.
[7]	李秋贤, 周全兴, 王振龙, 丁红发, 潘齐欣. 基于隐私保护的可证明安全委托计算协议[J]. 计算机工程, 2021, 47(5): 131-137.
[8]	胡乔木, 邓昀. 基于压缩HMAC算法的传感器网络范围查询方法[J]. 计算机工程, 2021, 47(12): 200-208.
[9]	陈丽燕, 芮廷先, 吕光金. 基于区块链智能合约的个人征信隐私保护方案[J]. 计算机工程, 2020, 46(7): 30-35.
[10]	刘文超, 潘峰, 杨晓元, 周潭平, 涂广升. 基于cuFHE的同态比较运算器[J]. 计算机工程, 2019, 45(9): 143-146,152.
[11]	王彩芬,赵冰,刘超,成玉丹,许钦百. 基于整数多项式环的多对一全同态加密算法[J]. 计算机工程, 2019, 45(4): 130-135.
[12]	李志佳, 夏玮. 基于差值直方图平移的密文域可逆信息隐藏算法[J]. 计算机工程, 2019, 45(11): 152-158.
[13]	沈鑫娣,翟东君,张得天,刘安. 基于LSH的隐私保护POI推荐算法[J]. 计算机工程, 2019, 45(1): 96-102.
[14]	刘卓,马敏耀,邱克娥,冯君. 一种安全两群体认证协议[J]. 计算机工程, 2018, 44(9): 141-148.
[15]	孙霓刚,朱浩然,陈宣任. 一种缩短公钥尺寸的整数上全同态加密方案[J]. 计算机工程, 2018, 44(9): 149-152.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种高效的百万富翁问题协议及其应用

An Efficient Protocol for Millionaires' Problem and Its Application

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价