1
$\begingroup$

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:

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for the response:) But I think what you say is that the two parties share their actual amount of money the have, while in the Yao's Millionaire problem they share a computed value that contained the digits that their value have and based on that you can determine if someone has more or equal / less money than the other. See here : 1) asecuritysite.com/zero/mill , 2) asecuritysite.com/rsa/mill2. Based on these two articles from Mr. Bill , I would like to somehow apply binary search on shared values , where shared values are not the actual amount of money. $\endgroup$
    – bd55
    Sep 23, 2023 at 13:56
  • 1
    $\begingroup$ your question is not properly stated then. I only use the Yao algorithm as a black box. I interpreted your question not two person but as one person trying to find out the stored secret income value. Please fix your question $\endgroup$
    – kodlu
    Sep 23, 2023 at 18:16
  • $\begingroup$ @kodlue Im sorry if my question was not clear:/ Could you kindly review my edited question and let me know of your thoughts about the problem? Thank you in advance. $\endgroup$
    – bd55
    Sep 23, 2023 at 18:44
  • 1
    $\begingroup$ If I understood correctly, it is exactly what kodlu answered already. $\endgroup$
    – kelalaka
    Sep 24, 2023 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.