Yao's Millionaires' Problem
The millionaire problem was formulated in 1982 by the Taiwanese computer scientist Andrew Yao:
It laid the foundation for multi- party computation, which still represents a major area of cryptology. In the problem it is abstract it, to do the adjustment or the comparison of data between systems, without disclosing the data of each system. This may be necessary, for example if there is no trusted remote terminal or connection can be guaranteed.
Algorithmic solution
It is the simplifying assumption that the assets are elements of a known finite set. Yao showed that it is then possible to solve the problem without trusted third party, which therefore also any other person known data to be protected. He suggested this before following protocol:
Preconditions
Alice had the assets A and Bob 's assets B. It is known that the two assets A and B elements of the set {1, ..., 10 } are (for example, in million dollars). Let k be a bijective trapdoor function on the numbers of length N bits, has the private key, Alice, that is, only Alice can the inverse k-1 efficiently compute.
Then enable the following algorithm to determine who is richer of the two, without revealing the exact assets.