IEEE/ACIS International Conference on Computer and Information Science (ICIS)

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu, Ye Chen

Published Jun 26, 2022• 2 citations

Abstract

Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.

DOI: 10.1109/icis54925.2022.9882463

Related papers

Secure two party comparison over encrypted data

Parisa Kaghazgaran, Sadeghyan Babak

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

World Congress on Information and Communication TechnologiesDec 1, 201110 citations

Improvement of the protocol for millionaires’ problem

Zhengtao Jiang, Ye Chen, Huiqiang Li +1 more

As the basic problem that introduces the idea of secure multi-party computation (SMC), millionaires’ problem (MP) is one of the research highlights in the field of SMC. However, most of current protocols for MP are only secure in semi-honest model, which using public key cryptography schemes, and there are few secure schemes in malicious model exist security defects. Therefore, this paper analyzes the Li et al.’s protocol for MP that secure in malicious model. Firstly, we point out several behaviours that can be successfully implemented in Li et al.’s protocol. Secondly, by using the zero-knowledge proof (ZKP) for the equality of discrete logarithm (DL), cut-and-choose method etc. We propose the improved protocol and show how to detect malicious behaviours. Finally, we analyze the correctness and security against malicious behaviours of the improved protocol.

International Conference on Computer Information Science and Application Technology (CISAT)Oct 20, 20220 citations

Secure multi-party computation solution to Yao's millionaires' problem based on set-inclusion

Shundong Li, Dai Yiqi, You Qi-you

Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaries' problem have high computational complexity or communication complexity. In this study, based on the 1-out of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation patadigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.

Progress in Natural Science Materials InternationalSep 1, 20054 citations

Secure Comparison Under Ideal/Real Simulation Paradigm

Chuan Zhao, Shengnan Zhao, Bo Zhang +3 more

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.

IEEE AccessJan 1, 20181 citation

A novel solution to the millionaire problem

Yi Mu, Luke McAven, Shuo Zheng

We give an efficient symmetric--key based protocol to solve Yao'smillionaire problem. We assume a semi--honest server assists incomparing values held by two different parties. We assume thisserver only executes the protocol precisely and does not colludewith any other participants. We protect the participants against theserver getting any information about the numbers or theirrelationship, by using encryption and hash chains. The protocol hasthree communication phases; initialisation, computation andannouncement. Each of the two parties and the server sends twomessages during the protocol. Each phase requires the two parties torun one of their three algorithms. We discuss the correctness,security properties and efficiency of our scheme. We compare thecommunication and computational costs against other solutions to themillionaire problem, using an RSA based implementation and using anAES based implementation. The computational cost is generally verylow by comparison with other methods, even when we use the lessefficient RSA.

Jan 1, 20070 citations

Some Efficient Solutions to Yao's Millionaire Problem

Ashish Kumar, Anupam Gupta

We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction uses a partially homomorphic Encryption Scheme and is a 4-round scheme using 2 encryptions, 2 homomorphic circuit evaluations (subtraction and XOR) and a single decryption. The second construction uses an untrusted third party and achieves a communication overhead linear in input bit-size with the help of an order preserving function.Moreover, the second construction does not require an apriori input bound and can work on inputs of different bit-sizes. The third construction does not use a third party and, even though, it has a quadratic communication overhead, it is a fairly simple construction.

arXiv:1310.8063Oct 30, 20135 citations