Security and Communication Networks

Efficient Solutions to Two-Party and Multiparty Millionaires’ Problem

Xin Liu, Shundong Li, Xiu‐Bo Chen, Gang Xu, Xiaolin Zhang, Yong Zhou

Published Jan 1, 2017• 23 citations

Abstract

The millionaires’ problem is the basis of secure multiparty computation and has many applications. Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determine x=y, x<y , or x>y in one execution. Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a. secure sorting problem), and this protocol can resist collusion attacks. We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.

DOI: 10.1155/2017/5207386

Related papers

Protocol for millionaires' problem in malicious models

顺东 LI, 文丽 WANG, 润萌 DU

Secure multiparty computation is a focus of the international cryptographic community. The millionaires problem is the most important problem in secure multiparty computation and is a building block for constructing other secure multiparty computation protocols. Several solutions are available to solve this problem, but except for protocols based on garbled circuits, the existing solutions based on public key cryptosystems are only secure in semihonest models. No solution based on a public key cryptosystem is secure against malicious adversaries. This state restricts the resolution of many secure multiparty computation problems in malicious scenarios. A solution that is secure in malicious models is highly applicable in practical application scenarios and is generally appealing. Therefore, the study of the solution to the millionaires problem in a malicious model is of great theoretical and practical significance. In this work, we propose a multiparty computation protocol for the millionaires problem that is secure in a semihonest model. The proposed protocol is simple and easily understandable. We analyze the possible malicious behaviors in this protocol and use zero-knowledge proof and cut-and-choose techniques to resist possible malicious behaviors and thereby convert the protocol into one that is secure in the malicious model. We prove that the proposed protocol is secure in the malicious model by using the well-accepted ideal-real paradigm. Theoretical efficiency analysis shows that the efficiency of our protocol is at least six times that of existing protocols.

Scientia Sinica InformationisDec 22, 202021 citations

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu +1 more

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.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)Jun 26, 20222 citations

Improvement and extension of secure vector dominance protocol

Zhengtao Jiang, Ting Yu, Huiqiang Li +1 more

The millionaire’s problem is the origin of secure multi-party computation. This problem has always been the focus of scholars' research, and it is also the design basis and important part of other secure multi-party computation protocols. An in-depth study of the millionaires’ problem is of great significance to promote the further development of secure multi-party computation. Based on millionaires’ problem and secure vector dominance protocol, we propose an improved protocol and an extended protocol. The improved protocol solves the problem of coarse granularity when comparing elements in the original protocol, and can realize that two parties can compare the relationships of greater than, equal to or less than between their elements by executing the protocol once. The improved protocol and the extended protocol are further applied to solve the problem of finding the cardinality of the intersection of the two-party sets in two cases. In addition, based on the integer division problem, we give a method to privately evaluate the greatest common factor of two integers.

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

An efficient protocol for Yao's millionaires' problem

I. Ioannidis, Ananth Y. Grama

The increase in volume and sensitivity of data communicated and processed over the Internet has been accompanied by a corresponding need for e-commerce techniques in which entities can participate in a secure and anonymous fashion. Even simple arithmetic operations over a set of integers partitioned over a network require sophisticated algorithms. As apart of our earlier work, we have developed a secure protocol for computing dot products of two vectors. In this paper, we present a secure protocol for Yao's millionaires' problem. In this problem, each of the two participating parties have a number and the objective is to determine whose number is larger without disclosing any information about the numbers. This problem has direct applications in on-line bidding and auctions. Furthermore, combined with a secure dot-product, a solution to this secure multiparty computation provides necessary building blocks for such basic operations as frequent item-set generation in association rule mining. Although an asymptotically optimal solution for the secure multiparty computation of the 'less-or-equal' predicate exists in literature, this protocol is not suited for practical applications. Here, we present a protocol which has a much simpler structure and is more efficient for numbers in ranges practically encountered in typical e-commerce applications. Furthermore, advances in cryptanalysis and the subsequent increase in key lengths for public-key cryptographic systems accentuate the advantage of the proposed protocol. We present experimental evidence demonstrating the efficiency of the proposed protocol both in terms of time and communication overhead.

Hawaii International Conference on System Sciences (HICSS)Jan 1, 2003109 citations

Symmetric Encryption Solutions to Millionaire's Problem and Its Extension

Shundong Li, Dai Yiqi, Wang Daoshun +1 more

Millionaire's problem is the base of secure multiparty computation, and its solutions have become basic blocks of many secure multi-party computation solutions. Unfortunately, most solutions to millionaire's problem are based on public key cryptography, and thus are inefficient. Furthermore, all solutions are designed to solve millionaire's problem for natural number case to privately determine which natural number is larger. If the numbers are real, these solutions do not directly work. In this paper, we first propose a symmetric key cryptographic solution to millionaire's problem for natural numbers case, and then generalize it to the case of real numbers, that is to privately determine which real number is larger. We further prove, by simulation paradigm, that these solutions are private. These solutions are really efficient.

International Conference on Digital Information ManagementApr 1, 20074 citations

Efficient solution to the millionaires' problem based on asymmetric commutative encryption scheme

Meng Liu, Yun Luo, Priyadarsi Nanda +2 more

Abstract Secure multiparty computation is an important scheme in cryptography and can be applied in various real‐life problems. The first secure multiparty computation problem is the millionaires' problem, and its protocol is an important building block. Because of the less efficiency of public key encryption scheme, most existing solutions based on public key cryptography to this problem are inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. In this paper, we formally analyse the vulnerability of this solution, and propose a new scheme based on the decisional Diffie‐Hellman assumption. Our solution also uses 0‐encoding and 1‐encoding generated by our modified encoding method to reduce the computation cost. We implement the solution based on symmetric encryption scheme and our protocol. Extensive experiments are conducted to evaluate the efficiency of our solution, and the experimental results show that our solution can be much more efficient and be approximately 8000 times faster than the solution based on symmetric encryption scheme for a 32‐bit input and short‐term security. Moreover, our solution is also more efficient than the state‐of‐the‐art solution without precomputation and can also compare well with the state‐of‐the‐art protocol while the bit length of private inputs is large enough.

Computational IntelligenceMay 23, 20194 citations