A Fair and Efficient Protocol for the Millionaires’ Problem

In the semi-honest model, Lin and Tzengproposed an efficient solution to the millionaires’ problem based on homomorphic encryption. They reduced theproblem to the set intersection problem by encoding theprivate inputs in a special way (the encoding method allows an efficient protocol for the set intersection problem).This paper modifies Lin and Tzeng’s protocol by introducing an Oblivious third party, and the modification is fairand secure in the same model. Compared with some ofthe previous fair protocols, our protocol relaxes the cryptographic assumption or the trust model. Compared withother previous fair protocols, our protocol are more efficient. We also consider security against malicious adversaries, i.e., malicious participants (the twomillionaires) andthird party.