Ciphertext Comparison, a New Solution to the Millionaire Problem

摘要

A new cryptographic protocol —ciphertext comparison— can compare two ciphertexts without revealing the two encrypted messages. Correctness of the comparison can be publicly verified. This technique provides an efficient and publicly verifiable solution to the famous millionaire problem. It is the first solution to the millionaire problem to output a precise result (the two messages are equal or which is larger). Privacy in this new solution is achieved with an overwhelmingly large probability and strong enough in practice.