4
$\begingroup$

Situation: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a > b$, $a = b$, or $a < b$, but neither wishes to reveal their chosen number to the other party.

How can Alice and Bob make this determination?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Bidding? This smells of auctions. $\endgroup$ – John Dvorak Nov 14 '13 at 5:22
  • 4
    $\begingroup$ Just a pointer to an answer at the moment, the problem is called "Yao's Millionaire's Problem" for which there is a protocol. $\endgroup$ – Luke Mathieson Nov 14 '13 at 5:40
  • $\begingroup$ @LukeMathieson Ah, that's great, thanks! I'd seen this somewhere before and couldn't remember what the problem was called. $\endgroup$ – senshin Nov 14 '13 at 5:42
  • $\begingroup$ @LukeMathieson expand it to an answer ? $\endgroup$ – Subhayan Nov 14 '13 at 14:44
1
$\begingroup$

As pointed out by Luke Mathieson in the comments, this problem is called Yao's Millionaire Problem, for which protocols can easily be found by Googling.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I do not understand the problem well enough at this point to write a good answer for this question. If somebody does write a good answer (or really, any answer), I will unaccept this answer and accept that instead. $\endgroup$ – senshin Nov 18 '13 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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