## Cryptology ePrint Archive: Report 2013/788

Improvement of Lin-Tzeng Solution to Yao's Millionaires Problem and Its Cheating Advantage Analysis

Zhengjun Cao and Lihua Liu

Abstract: 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.

Category / Keywords: cryptographic protocols / Multiplicative homomorphic encryption; Semi-honest assumption; Exponentially lifting transform