Yao's millionaire problem

The millionaire problem was formulated in 1982 by the Taiwanese computer scientist Andrew Yao :

Two millionaires want to know who is richer. However, they do not inadvertently want to find out any further information about their mutual wealth. How can you have such a conversation?

It laid the foundation for multiparty computation , which is still a central research area in cryptology today. In the abstract, the problem is about aligning or comparing data between systems without disclosing the data of the respective systems. This can be necessary, for example, if no trustworthy remote station or connection can be guaranteed.

Algorithmic solution

For the sake of simplicity it is assumed that the capacities are elements of a known finite set . Yao showed that the problem can then be solved without a trusted third party , so the data to be protected are not known to any other person. He suggested the following protocol:

Preconditions

Alice has the power A and Bob's assets B . Let us know that the two assets A and B are elements of the set {1, ..., 10} (for example in millions of dollars). Let k be a bijective trapdoor function on the numbers of length N bits whose private key Alice has, that is, only Alice can efficiently compute the inverse function k ⁻¹ . Every public key cryptosystem is suitable for this.

Then the following algorithm makes it possible to determine which of the two is richer without revealing the exact wealth.

algorithm

1. Bob chooses a random number X of length N bits and sends it to Alice . ${\displaystyle k(X)-B+1}$
2. Alice calculates with for . ${\displaystyle Y_{1},\ldots ,Y_{10}}$ ${\displaystyle Y_{i}=k^{-1}(k(X)-B+i)}$ ${\displaystyle i\in \{1,2,\dots ,10\}}$
3. Alice chooses a random prime number P of length ( N / 2) bits, so that for all pairs from the sequence with and . Also must be for everyone . ${\displaystyle |Z_{i}-Z_{j}|\geq 2}$ ${\displaystyle Z_{1},\ldots ,Z_{10}}$ ${\displaystyle Z_{i}=Y_{i}\,{\bmod {\,}}P}$ ${\displaystyle i,j\in \{1,2,\dots ,10\}}$ ${\displaystyle Z_{i}\leq p-1}$ ${\displaystyle i}$
4. Alice sends and P to Bob. ${\displaystyle Z_{1},\ldots ,Z_{A},Z_{A+1}+1,\ldots ,Z_{10}+1}$
5. If the B th entry from this list is X mod P , then A ≥ B , otherwise A < B .
6. Bob informs Alice of his result.

Individual evidence

1. ^ ^{A b} Andrew C. Yao: Protocols for Secure Computations (extended abstract). ( PDF file, 116 kB) In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Chicago 1982, pp. 160-164. (English)