Yao’s “Millionaires’ Problem”

Rosebud

Yao’s “millionaires’ problem” in cryptography involves 2 millionaires, A and B, who want to compare their wealth without revealing the exact amount to each other. This can be achieved through cryptographic techniques.

The box example is a metaphorical explanation of the millionaire’s problem, demonstrating the concept of comparing 2 individuals’ wealth without revealing the exact amounts.

The analogy illustrates uses cryptographic protocols, like the RSA algorithm for public-key encryption and asymmetric encryption, to enable secure comparisons of sensitive information without disclosing the information itself as a means to realize the privacy protocol.

As a naive example, let there be 10 boxes, and the wealth grades (range boxes) of 2 millionaires be 0 < i, j <= 10.

There are some following assumptions (which we will highlight during the routine), which are yet another list of problems, but we assumed them under certain conditions for now.

1. Setting: 2 millionaires, A and B. They each have their wealth stored in boxes, with each box representing a possible amount of wealth.

2. Initial Encryption: A selects a box (represented by index ‘i’) and puts a slip of paper with ‘0’ in all boxes before it and ‘1’ in the box at index ‘i’…