A novel solution to the millionaire problem
Yi Mu, Luke McAven, Shuo Zheng · Research Online (University of Wollongong) · 2007
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.