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.
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.
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.
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.
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.
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.
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.
The essential of Yao’s millionaire problem is securely comparing two numbers,which is a basic building block of secure computations and has many important applications in e-commerce,such as bidding,auction and so on.But known solutions have some disadvantagesf,or example expensive costs of computing and communicatingl,imited ranges of compared numbers.This paper proposes a modified ElGamal algorithm,based on which multiplicative and subtractive homomorphic cryp-tosystem is presented and proved.Based on the homomorphic cryptosystem,Fair and Efficient Protocol for Secure Two-party Comparing(FEPSTC) under semi-honest model is constructed.The main properties of the FEPSTC are securityf,airnessl,ower costs of communication and computational complexity,and comparing real numbers.They are proved and illustrated by an ex-ample and by comparing with other protocols.