She wants to know how much I love her: a gentle tutorial of Yao's Millionaires' Problem

Recently my girlfriend wanted to know whether I love her more than she loves me. For this purpose, she asked me to rate my love in a scale of 1 to 10. To escape from her interrogation, I returned the same question to her. It ended with that both of us wanted to know how deep the other’s love is, but neither wanted to disclose his/her own secret. As a smart solution expert, I proposed to treat this dilemma as Yao’s Millionaires’ Problem.

In Yao’s problem, there were two millionaires, who wanted to compare their wealth without exchanging the information about the exact number of their wealth. Luckily, computer scientist Andrew Yao (1982) came to their rescue by designing a clever way to compare their wealth without either one disclosing his exact number of wealth.

In this post, I will provide a gentle tutorial of this solution. Let me use my girlfriend and I as an example… (Audience: hey, wake up, bro, since when did you have a girlfriend?) Well, well, then let us use the famous anime couple Kirito and Asuna as an example.

Question formulation

Kirito and Asuna both are honest and capable of rating their love in a scale of 1 to 10 (higher is stronger). Kirito rates his love as $i$, and Asuna rates her love as $j$. Asuna wants to know whether $i \ge j$ (If not, she will beat the shit out of Kirito), but Kirito refuses to communicate the exact value of $i$ to her. They need a boolean-valued function to compute whether $i \ge j$ is true or false without communicating the value of $i$ or $j$.

Preliminaries

To build this boolean-valued function, they will need an invertible obfuscating function $h$. This function should have the following properties:

  1. It has an inverse $h^{-1}$ such that $h^{-1} \circ h = h \circ h^{-1} = id$, where $id$ is the identity function.
  2. It is computationally expensive to compute $h^{-1}$ given $h$.
  3. It destroys statistical properties. That is, any structure on the set $S$ will be destroyed on the set $h(S):=\{ h(x) : x \in S \}$

Notice the wording computationally expensive in the second property. A function is essentially a table mapping $x$’s to $y$’s. By enumerating all possible $x$’s, we can check $y$’s value to find the corresponding $x$. That said, when there is an infinite number of $x$’s, it becomes computationally expensive to follow this approach.

One example satisfying these properties is known as RSA encryption. In each RSA encryption, there is a pair of keys, known as the public key and the private key. These two keys each defines an obfuscating function, and these two functions are mutually invertible.

Yao’s solution

Yao’s solution is composed of several steps.

0. Preparation

  • Public information:
    • Obfuscating function $h$
    • Prime $p$
  • Kirito’s private information:
    • His love score $i$
    • Inverse of the obfuscating function $h^{-1}$
  • Asuna’s private information:
    • Her love score $j$
    • Integer $x$

1. Asuna’s turn

Asuna first obfuscates $x$ and gets $h(x)$ and then puts it on the $j$-th position of a series of 10 contiguous integers. These 10 integers are \[ h(x)-j+1 \quad h(x)-j+2 \quad \ldots \quad h(x) \quad \ldots \quad h(x)-j+10 \]

She then sends these 10 integers to Kirito. Since they are contiguous, she only needs to send the value of $h(x)-j$, from which Kirito can rebuild the whole series.

In Asuna’s turn, she hides the information about her love score in this series. From Kirito’s perspective, all he sees is 10 contiguous integers.

2. Kirito’s turn

Now Kirito needs to embed the information about his love score in this series, just like Asuna did. As a solution, he decides to add 1 to each of the first $i$ contiguous integers and leave the remaining intact. When Asuna sees that $h(x)$ disappears from its previous position, she knows that $i \ge j$; otherwise, $i < j$. Such a method works, but it also exposes Kirito’s love score: the boundary where the contiguity breaks indicates $i$.

Therefore, Kirito needs to obfuscate the contiguous integers so as to destroy the contiguity in the first place. He applies $h^{-1}$ on these numbers and gets \[ h^{-1}(h(x)-j+1) \quad h^{-1}(h(x)-j+2) \quad \ldots \quad x \quad \ldots \quad h^{-1}(h(x)-j+10) \] Notice that how $h^{-1}(h(x))=x$ and it preserves Asuna’s input. Now all these number appear to be random (except $x$). Kirito then adds 1 to the first $i$ numbers.

I used the wording appear to be random because they are not truly random. The contiguity can be restored by applying $h$ back to negate the effect of $h^{-1}$. To prevent this, Kirito can calculate $\mod p$ for every number, which results in a permanent information loss and the contiguity can no longer be restored.

In this way, Kirito embeds his secret in these numbers and sends them back to Asuna. All Asuna can see is 9 random numbers and the information-carrying $j$-th number.

3. Asuna’s turn

Asuna checks whether the number in the $j$-th position equals to $x mod p$ or $(x+1) \mod p$. If it is equal to $(x+1) \mod p$, then $i \ge j$. If it is equal to $x \mod p$, then $i < j$ and Asuna will beat the shit out of Kirito.

After solving Asuna’s trouble, now let us review this process and check whether it can be simplified.

Role of the obfuscating function

In the beginning of the algorithm, Asuna obfuscated $x$ and got $h(x)$. This step looks pointless: why obfuscate it when it is a single number. Let us check what will happen if we omit this step.

Kirito will then receive \[ x-j+1 \quad x-j+2 \quad \ldots \quad x \quad \ldots \quad x-j+10 \] Now he applied the obfuscation. He has two choices: use $h$ or $h^{-1}$. Using the public $h$ is a bad idea, since every operation hence carried can be repeated by Asuna: Kirito cannot hide information. Then it remains the private $h^{-1}$, which yields \[ h^{-1}(x-j+1) \quad h^{-1}(x-j+2) \quad \ldots \quad h^{-1}(x) \quad \ldots \quad h^{-1}(x-j+10) \] Since $h^{-1}$ is unknown to Asuna, she will not be able to verify the value of $h^{-1}(x-j+10) \mod p$. Both choices fail.

In fact, $h$ is not an obfuscation but an armor to protect $x$ from the later obfuscation conducted by Kirito. Kirito knew that he was to do something obscure, so he threw a condom to Asuna in advance.

Exchange the obfuscation and the plus-one step

If these two steps are exchanged, Asuna will have a chance to know $i$. Imagine $i=j-1$, then after the plus-one step, Kirito gets \[ h(x)-j+2 \quad \ldots \quad h(x)-j+i+1 \quad h(x) \quad \ldots \quad h(x)-j+10 \] Since $h(x)-j+i+1=h(x)$, Asuna will discover that $i \ge j-1$ in addition to the information $i<j$ obtained from the normal process. Combining these two hints, she gets $i=j-1$.

Role of $x$

It looks like that all Asuna needs is 10 contiguous integers. Why not just make $x=j$ and send Kirito the following? \[ h(j)-j+1 \quad h(j)-j+2 \quad \ldots \quad h(j) \quad \ldots \quad h(j)-j+10 \] The reason is obvious: after Kirito’s obfuscation, they become \[ h^{-1}(h(j)-j+1) \quad h^{-1}(h(j)-j+2) \quad \ldots \quad j \quad \ldots \quad h^{-1}(h(j)-j+10) \] It is quite possible that $j$ is the only number between 1 to 10 in these ten numbers. Asuna’s secret leaks. Contrary to Kirito’s obfuscation provided by $h^{-1}$, Asuna’s obfuscation is not provided by $h$ but by $x$.

Exercises

This tutorial should be clear and complete enough for you to understand Yao’s solution. Once you think you master this solution, try out the following exercises. In this post, we tested the condition $i \ge j$. What can be done to test $i \le j$, $i<j$, $i>j$, and $i=j$?

Written on May 15, 2021