Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Multiplicative homomorphic encryptionSemi-honest assumptionExponentially lifting transform
- Contact author(s)
- liulh @ shmtu edu cn
- History
- 2013-11-30: received
- Short URL
- https://ia.cr/2013/788
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/788,
author = {Zhengjun Cao and Lihua Liu},
title = {Improvement of Lin-Tzeng Solution to Yao's Millionaires Problem and Its Cheating Advantage Analysis},
howpublished = {Cryptology ePrint Archive, Paper 2013/788},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/788}},
url = {https://eprint.iacr.org/2013/788}
}
