A novel solution to the millionaire problem
RIS ID
22125
Abstract
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.
Publication Details
Zheng, S., McAven, L. F. & Mu, Y. (2007). A novel solution to the millionaire problem. International Conference on Information Technology and Applications (pp. 66-71). Sydney: Macquarie Scientific Publishing.