In this thesis we present an efficient solution to Yao's millionaires' problem. The problem describes two millionaires who want to know which of them is richer without revealing their actual wealth. The problem has many solutions, but older ones are inefficient, as they compare the integers bit by bit, which means each bit has to be encrypted and decrypted separately. On the contrary, our protocol compares the entire integers, which means we only need one encryption, if only the integers are not too big. We begin by describing a homomorphic cryptosystem, whose properties allow us to compare two integers without decrypting them. We also prove semantic security of the described cryptosystem. We continue by describing a protocol for secure integer comparison. We notice the aforementioned homomorphic cryptosystem is not enough for secure integer comparison, as it exposes the difference between the integers in some cases. That is why we add another round of encryption to our protocol. For that purpose we use the exponential version of ElGamal cryptosystem. At the end we prove the protocol works correctly and prove its security.
|
