  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.
