Secure Comparison Under Ideal/Real Simulation Paradigm

IEEE Access

Mauro Conti¹  Shengnan Zhao²  Chuan Zhao³  Bo Zhang³  Zhenxiang Chen³  Zhongtian Jia³ 

[1] Department of Mathematics, University of Padova, Padua, Italy;School of Computer Science and Technology, Shandong University, Jinan, China;Shandong Provincial Key Laboratory of Network Based Intelligent Computing, University of Jinan, Jinan, China;

关键词: Ideal/real simulation paradigm;    malicious model;    secure comparison;    secure multi-party computation;    simulation-based security;    Yao’s millionaires’ problem;   

DOI  :  10.1109/ACCESS.2018.2837665

来源: DOAJ

【 摘 要 】

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 onesided 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(|U|) symmetric operations at most to achieve simulation-based security against malicious adversaries, where U denotes the universal set and |U| denotes the size of U.

【 授权许可】

Unknown