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

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

Abstract

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

CLC Number:

TN92

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.

Figures/Tables 9

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

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

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})$

协议	计算复杂度	通信轮数/轮	通信开销/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

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

Metrics

Recommended 0

No Suggested Reading articles found!

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

Rational-security and fair two-party comparison protocol

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 22

Related Articles 15

Metrics

Recommended 0

[1]	Zhuo MA, Jiayu JIN, Yilong YANG, Yang LIU, Zuobin YING, Teng LI, Junwei ZHANG. Adaptive federated learning secure aggregation scheme based on threshold homomorphic encryption [J]. Journal on Communications, 2023, 44(7): 76-85.
[2]	Xindi MA, Qinghua LI, Qi JIANG, Zhuo MA, Sheng GAO, Youliang TIAN, Jianfeng MA. Byzantine-robust federated learning over Non-IID data [J]. Journal on Communications, 2023, 44(6): 138-153.
[3]	Zhiguo SUN, Shuo XIAO, Yijie WU, Shiming LI, Zhenduo WANG. Evaluation method of penetrating jamming effectiveness for cognitive communication protection [J]. Journal on Communications, 2023, 44(11): 161-172.
[4]	Shengxing YU, Zhong CHEN. Efficient secure federated learning aggregation framework based on homomorphic encryption [J]. Journal on Communications, 2023, 44(1): 14-28.
[5]	Yatao YANG, Deli LIU, Peihe LIU, Ping ZENG, Song XIAO. BFV-Blockchainvoting: blockchain-based electronic voting systems with BFV full homomorphic encryption [J]. Journal on Communications, 2022, 43(9): 100-111.
[6]	Xuewang ZHANG, Zhihong LI, Jinzhao LIN. Privacy protection scheme based on fair blind signature and hierarchical encryption for consortium blockchain [J]. Journal on Communications, 2022, 43(8): 131-141.
[7]	Haining YU, Hongli ZHANG, Xiangzhan YU, Jiaxing QU, Mengmeng GE. Privacy-preserving trajectory similarity computation method [J]. Journal on Communications, 2022, 43(11): 1-13.
[8]	Zhibin FENG, Yuhua XU, Zhiyong DU, Xin LIU, Wen LI, Hao HAN, Xiaobo ZHANG. Active defense technology against intelligent jammer [J]. Journal on Communications, 2022, 43(10): 42-54.
[9]	Hongbin ZHANG, Yan YIN, Dongmei ZHAO, Bin LIU. Network security situational awareness model based on threat intelligence [J]. Journal on Communications, 2021, 42(6): 182-194.
[10]	Sheng GAO, Kang XIANG, Youliang TIAN, Weijie TAN, Tao FENG, Xiaoxue WU. BCP-based joint delegation learning model and protocol [J]. Journal on Communications, 2021, 42(5): 137-148.
[11]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[12]	Chunfu JIA, Ruiqi LI, Yafei WANG. Privacy protection scheme of DBSCAN clustering based on homomorphic encryption [J]. Journal on Communications, 2021, 42(2): 1-11.
[13]	Li ZHANG,Tian LIAO,Yejun HE. Dual-target WOA spectrum sharing algorithm based on Stackelberg game [J]. Journal on Communications, 2020, 41(9): 170-178.
[14]	Yousheng ZHOU,Chang TAN,Fei TANG. Multi-dimensional secure query scheme for fog-enhanced IIoT [J]. Journal on Communications, 2020, 41(8): 175-186.
[15]	Lindong ZHAO,Wenqin ZHUANG,Jianxin CHEN,Liang ZHOU. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization [J]. Journal on Communications, 2020, 41(4): 34-44.