标题：Secure Comparison Under Ideal/Real Simulation Paradigm
作者：Zhao, Chuan; Zhao, Shengnan; Zhang, Bo; Jia, Zhongtian; Chen, Zhenxiang; Conti, Mauro
作者机构：[Zhao, Chuan; Zhang, Bo; Jia, Zhongtian; Chen, Zhenxiang] Univ Jinan, Shandong Prov Key Lab Network Based Intelligent C, Jinan 250022, Shandong, Peopl 更多
通讯作者地址：[Chen, ZX]Univ Jinan, Shandong Prov Key Lab Network Based Intelligent C, Jinan 250022, Shandong, Peoples R China;[Chen, ZX]Univ Jinan, Sch Informat Sc 更多
关键词：Ideal/real simulation paradigm; malicious model; secure comparison;; secure multi-party computation; simulation-based security; Yao's; millionaires' problem
摘要：Secure comparison problem, also known as Yao's Millionaires' problem, was introduced by Andrew Yao in 1982. It is a fundamental problem in secure multi-party computation. In this problem, two millionaires are interested in determining the richer one between them without revealing their actual wealth. Yao's millionaires' problem is a classic and fundamental problem in cryptography. The design of secure and efficient solutions to this problem provides effective building blocks for secure multi-party computation. However, only a few of the solutions in the literature have succeeded in resisting attacks of malicious adversaries, and none of these solutions has been proven secure in malicious model under ideal/real simulation paradigm. In this paper, we propose two secure solutions to Yao's millionaires' problem in the malicious model. One solution has full simulation security, and the other solution achieves one-sided simulation security. Both protocols are only based on symmetric cryptography. Experimental results indicate that our protocols can securely solve Yao's millionaires' problem with high efficiency and scalability. Furthermore, our solutions show better performance than the state-of-the-art solutions in terms of complexity and security. Specifically, our solutions only require O(vertical bar U vertical bar) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and vertical bar U vertical bar denotes the size of U.