理性安全的公平两方比较协议

doi:10.11959/j.issn.1000-436x.2023220

通信学报 ›› 2023, Vol. 44 ›› Issue (12): 112-123.doi: 10.11959/j.issn.1000-436x.2023220

• 学术论文 • 上一篇

理性安全的公平两方比较协议

赵搏文¹, 祝遥¹, 肖阳², 裴庆祺², 李小国³, 刘西蒙⁴

¹ 西安电子科技大学广州研究院，广东广州 510555
² 西安电子科技大学综合业务网国家重点实验室，陕西西安 710071
³ 新加坡管理大学计算与信息系统学院，新加坡 178902
⁴ 福州大学计算机与大数据学院，福建福州 350108

修回日期:2023-12-01 出版日期:2023-12-01 发布日期:2023-12-01
作者简介:赵搏文（1992-），男，湖南双峰人，博士，西安电子科技大学副教授、硕士生导师，主要研究方向为隐私计算方法与隐私保护的计算智能
祝遥（2000- ），男，湖北孝感人，西安电子科技大学硕士生，主要研究方向为隐私计算及其应用
肖阳（1991- ），男，新疆石河子人，博士，西安电子科技大学讲师、硕士生导师，主要研究方向为图神经网络、信任评估和区块链
裴庆祺（1974- ），男，陕西西安人，博士，西安电子科技大学教授、博士生导师，主要研究方向为无线网络安全
李小国（1991- ），男，山西夏县人，博士，新加坡管理大学研究员，主要研究方向为可信计算、安全计算和公钥密码系统
刘西蒙（1988- ），男，陕西西安人，博士，福州大学教授、博士生导师，主要研究方向为安全计算、应用密码学和大数据安全
基金资助:
国家重点研发计划基金资助项目(2022YFB3102700);国家自然科学基金资助项目(62202358);国家自然科学基金资助项目(62072109);国家自然科学基金资助项目(62376097);国家自然科学基金资助项目(62102295);国家自然科学基金资助项目(62202114);中国博士后科学基金资助项目(2023TQ0258)

Rational-security and fair two-party comparison protocol

Bowen ZHAO¹, Yao ZHU¹, Yang XIAO², Qingqi PEI², Xiaoguo LI³, Ximeng LIU⁴

¹ Guangzhou Institute of Technology, Xidian University, Guangzhou 510555, China
² Xidian University State Key Laboratory of Integrated Service Networks, Xi’an 710071, China
³ School of Computing and Information Systems, Singapore Management University, Singapore 178902, Singapore
⁴ College of Computer and Data Science, Fuzhou University, Fuzhou 350108, China

Revised:2023-12-01 Online:2023-12-01 Published:2023-12-01
Supported by:
The National Key Research and Development Program of China(2022YFB3102700);The National Natural Science Foundation of China(62202358);The National Natural Science Foundation of China(62072109);The National Natural Science Foundation of China(62376097);The National Natural Science Foundation of China(62102295);The National Natural Science Foundation of China(62202114);China Postdoctoral Science Foundation(2023TQ0258)

摘要/Abstract

摘要：

现有的安全两方比较协议通常是让一方（如Alice）先获知比较结果，然后Alice将比较结果告知另一方（如Bob）。如果Alice拒绝或未将结果发送给Bob，则协议无法保障参与方都拿到比较结果，协议的公平性被破坏。为解决上述问题，结合门限 Paillier 密码系统与博弈论提出一种理性安全的公平两方比较协议 TEAM。具体地，首先利用门限 Paillier 密码系统设计一种新型的安全两方比较协议。接着引入博弈论机制，探寻所提安全两方比较协议双方均获得比较结果的博弈均衡点。严格的理论分析表明，TEAM保障理性的参与方可在不泄露各自数据的情况下正确地获得比较结果，即TEAM是一个正确、安全且公平的两方比较协议。实验结果显示，同等实验环境下TEAM的计算效率相较于现有的安全两方比较方法运行速度能提升超50倍。

关键词: 安全比较, 博弈论, 同态加密, 门限密码, 可信计算

Abstract:

Existing secure two-party comparison protocols usually allowed one party (e.g., Alice) to obtain a comparison result first, and then Alice informed the other one (e.g., Bob) of the comparison result.Obviously, if Alice refused or failed to send the comparison result to Bob, Bob learned nothing about the comparison result, which broke the fairness of the two-party comparison protocol.Based on this, a rational-security and fair two-party comparison protocol TEAM was proposed by seamlessly combining the threshold Paillier cryptosystem and game theory.Specifically, a novel secure two-party comparison protocol based on the threshold Paillier cryptosystem was designed and then searched for equilibrium points at which two parties could obtain comparison results.Strict theoretical analysis demonstrate that TEAM guarantees rational two-party to always obtain the comparison result without sacrificing any of their inputs.In other words, TEAM was correct, secure, and fair.In addition, the experimental results show that TEAM improves up to 50 times in terms of efficiency compared with previous methods under the same experimental settings.

Key words: secure comparison, game theory, homomorphic encryption, threshold cryptography, trusted computing

中图分类号:

TN92

赵搏文, 祝遥, 肖阳, 裴庆祺, 李小国, 刘西蒙. 理性安全的公平两方比较协议[J]. 通信学报, 2023, 44(12): 112-123.

Bowen ZHAO, Yao ZHU, Yang XIAO, Qingqi PEI, Xiaoguo LI, Ximeng LIU. Rational-security and fair two-party comparison protocol[J]. Journal on Communications, 2023, 44(12): 112-123.

图/表 9

表1

图1

图2

表2

s =0，Alice获得结果与真实结果比较"

x和y的大小关系	u₁	Alice获得结果	真实结果
x≥y	0	$\| s - u_{1} \| = 0$	0
x＜y	1	$\| s - u_{1} \| = 1$	1

表2

表3

s =1，Alice获得结果与真实结果比较"

x和y 的大小关系	u1	Alice获得结果	真实结果
x≥y	1	$\| s - u_{1} \| = 0$	0
x＜y	0	$\| s - u_{1} \| = 1$	1

表3

表4

效用矩阵"

Alice(P₁)	$Bob (P_{2}) = S_{2}^{2} S_{2}^{4}$	$Bob (P_{2}) = S_{2}^{2} {\bar{S}}_{2}^{4}$	$Bob (P_{2}) = {\bar{S}}_{2}^{2} S_{2}^{4}$	$Bob (P_{2}) = {\bar{S}}_{2}^{2} {\bar{S}}_{2}^{4}$
$S_{1}^{1} S_{1}^{3}$	$(ρ_{1} + ρ_{2} + \frac{ρ_{3}}{3}, ρ_{1} + ρ_{2} + \frac{ρ_{3}}{3})$	$(ρ_{1} + \frac{ρ_{3}}{2}, - ρ_{1} + ρ_{2} + \frac{ρ_{3}}{2})$	$(ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$
$S_{1}^{1} {\bar{S}}_{1}^{3}$	$(- ρ_{1} + ρ_{2} + \frac{ρ_{3}}{2}, ρ_{1} + \frac{ρ_{3}}{2})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$
${\bar{S}}_{1}^{1} S_{1}^{3}$	$(- ρ_{1} + ρ_{3}, ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$
${\bar{S}}_{1}^{1} {\bar{S}}_{1}^{3}$	$(- ρ_{1} + ρ_{3}, ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$	$(- ρ_{1} + ρ_{3}, - ρ_{1} + ρ_{3})$

表4

表5

不同协议的计算复杂度与通信复杂度的比较"

协议	计算复杂度	通信轮数/轮	通信开销/KB
ObliVM	⊥	4	14.80
ABY	⊥	4	10.29
GSV07	$9 〈 N 〉$	3+lb(p)	13.75
semiSMC	$9 v 〈 N 〉$	n (n+1)	49.90
TEAM	$10.5 〈 N 〉 + 6 σ$	4	1.25

表5

图3

图4

参考文献 22

[1]	YAO A C . Protocols for secure computations[C]// Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 1982: 160-164.
[2]	YAO A C C . How to generate and exchange secrets[C]// Proceedings of the 27th Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 1986: 162-167.
[3]	IOANNIDIS I , GRAMA A . An efficient protocol for Yao’s millionaires’ problem[C]// Proceedings of the 36th Annual Hawaii International Conference on System Sciences. Piscataway:IEEE Press, 2003:6.
[4]	LI S D , WANG D S , DAI Y Q ,et al. Symmetric cryptographic solution to Yao’s millionaires’ problem and an evaluation of secure multiparty computations[J]. Information Sciences, 2008,178(1): 244-255.
[5]	DAMGARD I , GEISLER M , KROIGARD M . Homomorphic encryption and secure comparison[J]. International Journal of Applied Cryptography, 2008,1(1): 22-31.
[6]	DAMLE S , FALTINGS B , GUJAR S . Blockchain-based practical multi-agent secure comparison and its application in auctions[C]// Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. New York:ACM Press, 2021: 430-437.
[7]	ZHOU L J , WANG Z Y , CUI H R ,et al. Bicoptor:two-round secure three-party non-linear computation without preprocessing for privacy-preserving machine learning[C]// Proceedings of 2023 IEEE Symposium on Security and Privacy (SP). Piscataway:IEEE Press, 2023: 534-551.
[8]	LIU X M , CHOO K K R , DENG R H ,et al. Efficient and privacy-preserving outsourced calculation of rational numbers[J]. IEEE Transactions on Dependable and Secure Computing, 2018,15(1): 27-39.
[9]	郭奕旻, 周素芳, 窦家维 ,等. 高效的区间保密计算及应用[J]. 计算机学报, 2017,40(7): 1664-1679.
	GUO Y M , ZHOU S F , DOU J W ,et al. Efficient privacy-preserving interval computation and its applications[J]. Chinese Journal of Computers, 2017,40(7): 1664-1679.
[10]	ZHAO B W , LIU X M , SONG A ,et al. PriMPSO:a privacy-preserving multiagent particle swarm optimization algorithm[J]. IEEE Transactions on Cybernetics, 2023,53(11): 7136-7149.
[11]	LIU C , WANG X S , NAYAK K ,et al. ObliVM:a programming framework for secure computation[C]// Proceedings of 2015 IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2015: 359-376.
[12]	DEMMLER D , SCHNEIDER T , ZOHNER M . ABY - a framework for efficient mixed-protocol secure two-party computation[C]// Proceedings of Network and Distributed System Security Symposium. Reston:Internet Society, 2015: 1-15.
[13]	KOLESNIKOV V , SCHNEIDER T . Improved garbled circuit:free xor gates and applications[C]// International Colloquium on Automata,Languages,and Programming. Berlin:Springer, 2008: 486-498.
[14]	CANETTI R , POBURINNAYA O , VENKITASUBRAMANIAM M . Equivocating Yao:constant-round adaptively secure multiparty computation in the plain model[C]// Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. New York:ACM Press, 2017: 497-509.
[15]	GROCE A , KATZ J . Fair computation with rational players[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 81-98.
[16]	LIN H Y , TZENG W G . An efficient solution to the millionaires’ problem based on homomorphic encryption[C]// Applied Cryptography and Network Security. Berlin:Springer, 2005: 456-466.
[17]	LIU X , LI S D , CHEN X B ,et al. Efficient solutions to two-party and multiparty millionaires’ problem[J]. Security and Communication Networks, 2017,2017: 1-11.
[18]	李顺东, 徐雯婷, 王文丽 ,等. 恶意模型下的最大(小)值保密计算[J]. 计算机学报, 2021,44(10): 2076-2089.
	LI S D , XU W T , WANG W L ,et al. Secure maximum (minimum) computation in malicious model[J]. Chinese Journal of Computers, 2021,44(10): 2076-2089.
[19]	ZHAO B W , YUAN J M , LIU X M ,et al. SOCI:a toolkit for secure outsourced computation on integers[J]. IEEE Transactions on Information Forensics and Security, 2022,17: 3637-3648.
[20]	VEUGEN T , BLOM F , HOOGH S J A D ,et al. Secure comparison protocols in the semi-honest model[J]. IEEE Journal of Selected Topics in Signal Processing, 2015,9(7): 1217-1228.
[23]	MAITRA A , PAUL G , PAL A K . Revisiting secure two-party computation with rational player[J]. Cryptology ePrint Archive, 2015: 1-13.
[24]	PAILLIER P . Public-key cryptosystems based on composite degree residuosity classes[C]// Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques. New York:ACM Press, 1999: 223-238.
[25]	DING C , PEI D Y , SALOMAA A . Chinese remainder theorem:applications in computing,coding,cryptography[M]. Singapore: World Scientific, 1996.
[26]	ACHIM O M , POP F , CRISTEA V . Reputation based selection for services in cloud environments[C]// Proceedings of 2011 14th International Conference on Network-Based Information Systems. Piscataway:IEEE Press, 2011: 268-273.
[27]	KATZ J , LINDELL Y . Introduction to modern cryptography[M]. Florida: Chapman and Hall/CRC, 2020.
[28]	GOLDREICH O . Foundations of cryptography:volume 2,basic applications[M]. Cambridge: Cambridge University Press, 2009.
[21]	DAMGARD I , FITZI M , KILTZ E ,et al. Unconditionally secure constant-rounds multi-party computation for equality,comparison,bits and exponentiation[C]// Theory of Cryptography. Berlin:Springer, 2006: 285-304.
[22]	HALPERN J , TEAGUE V . Rational secret sharing and multiparty computation:extended abstract[C]// Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. New York:ACM Press, 2004: 623-632.

协议	底层技术	公平的比较	效率
ObliVM^[11]	混淆电路	否	中
ABY^[12]	混淆电路	否	高
GSV07^[20]	秘密分享	否	中
semiSMC^[18]	同态加密	否	低
TEAM	同态加密	是	高

理性安全的公平两方比较协议

Rational-security and fair two-party comparison protocol

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 22

相关文章 15

Metrics

推荐阅读 0

[1]	马卓, 金嘉玉, 杨易龙, 刘洋, 应作斌, 李腾, 张俊伟. 基于门限同态加密的自适应联邦学习安全聚合方案[J]. 通信学报, 2023, 44(7): 76-85.
[2]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[3]	孙志国, 肖硕, 吴毅杰, 李诗铭, 王震铎. 面向认知通信防护的穿透式干扰效能评估方法[J]. 通信学报, 2023, 44(11): 161-172.
[4]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[5]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[6]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[7]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.
[8]	冯智斌, 徐煜华, 杜智勇, 刘鑫, 李文, 韩昊, 张晓博. 对抗智能干扰的主动防御技术[J]. 通信学报, 2022, 43(10): 42-54.
[9]	张红斌, 尹彦, 赵冬梅, 刘滨. 基于威胁情报的网络安全态势感知模型[J]. 通信学报, 2021, 42(6): 182-194.
[10]	高胜, 向康, 田有亮, 谭伟杰, 冯涛, 吴晓雪. 基于BCP的联合委托学习模型及协议[J]. 通信学报, 2021, 42(5): 137-148.
[11]	李瑞琪, 贾春福, 王雅飞. 基于NTRU的多密钥同态代理重加密方案及其应用[J]. 通信学报, 2021, 42(3): 11-22.
[12]	贾春福, 李瑞琪, 王雅飞. 基于同态加密的DBSCAN聚类隐私保护方案[J]. 通信学报, 2021, 42(2): 1-11.
[13]	周由胜,谭畅,唐飞. 面向雾增强型工业物联网的多维安全查询方案[J]. 通信学报, 2020, 41(8): 175-186.
[14]	赵临东,庄文芹,陈建新,周亮. 异构蜂窝网络中分层任务卸载：建模与优化[J]. 通信学报, 2020, 41(4): 34-44.
[15]	李沓,田有亮,向康,高鸿峰. 委托计算下基于区块链的公平支付方案[J]. 通信学报, 2020, 41(3): 80-90.