Some Efficient Solutions to Yao's Millionaire Problem
This work provides incremental improvements in secure multi-party computation protocols for privacy-preserving comparisons.
The paper tackles Yao's Millionaire Problem by presenting three efficient protocols for non-colluding, semi-honest parties, achieving constructions with varying round counts, encryption uses, and communication overheads.
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.