International Association
for Cryptologic Research

In 2005, Lin and Tzeng proposed a solution to Yao\'s Millionaires problem in the setting of semi-honest parties. At the end of the protocol only the party (Alice) who is responsible for setting up the system parameters knows the outcome. It does not specify how to have the other party (Bob) know the result. In this note, we present an improvement of the Lin-Tzeng solution. It requires that Alice and Bob alternately perform the original protocol twice. Under the reasonable assumption that a participator does not deviate from the prescribed steps before he/she obtains the outcome, Alice and Bob can almost simultaneously obtain the result. To the best of our knowledge, it is the first time to show that one participator has only an advantage of $\\mbox{ln}\\,n/n$ possibility to cheat the other in the reasonable setting.