Could Yao's Millionaires' problem be used as a problem of binary search?

Question

I recently started reading about Yao's Millionaires' problem. If the Yao's Millionaires' problem is capable of finding if one party has less money / more or equal money than the other party, then is it possible for one party to find the exact amount of money that the other party have?

I specifically read the articles posted by Professor Bill Buchanan:

• https://asecuritysite.com/rsa/mill2
• https://asecuritysite.com/zero/mill

Where as we can see the two parties that communicate with each other share a computed value (which is not the amount of money the have) and with the algorithm we are capable of finding out who has more money. As stated by Professor Bill : "In Millionaire's Problem, we can determine which of two millionaires has the most money, without them actually giving away the amount of money they have".

Now, let's move this problem to a program concept. Imagine a server that has a hardcoded value and accepts amounts from clients. Based on the Yao's Millionaires' problem, it responds to the users if their value is less than the servers (client_value < server_value) or if its greater or equal to the value that the server has (client_value >= server_value). Is it possible with some way for a client to find the exact value that the server have? (for example using binary search....?) And if its possible, then how? Remember that the clients and the server do not exchange their real values, but a value like Professor Buchanan showcases.

Answer 1

OK, the way it is normally stated, the two users A and B interact with a trusted server, behave according to the protocol and at the end learn which one has more money, let's say weather $w(A)\geq w(B),$ where $w$ is the wealth.

So your setup of the problem needs to be changed to $B$ being another trusted server with a fixed stored value $w(S')=w_0.$ If $A,S'$ behave according to a protocol that solves the millionaire's problem then indeed $A$ can learn if $w(A) \geq w(S').$

Binary search for $w$ (simple range, otherwise go to the next power of 2 and run this): If I have a range $[1,2^3]$ then I ask if $w \leq 2^2$ if yes split this interval into two and ask if $w \leq 2^1,$ etc. Split left if I keep getting yes otherwise split right.

Say $w=3$: Is $w\leq 2^2$? Yes; Is $w \leq 2^1$? No; So we know $w$ is in $[2^1+1,2^2]=[3,4]$. Then just query if $w \leq 3$ and you get the answer.

Use binary search in the following way, if you like start conservatively and let $w_1=\textrm{floor}[w(\textrm{Musk})/2].$ I put the queries to the Yao server as if statements.

So you can query if $w_0$ is in range $[1,w_1].$ If no, ask if $w_0$ is in the range $[w_1+1,2w_1]=[w_1+1,w(\textrm{Musk})].$ Otherwise continue binary search technique on $[1,w_1]$ splitting to the left half.