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?

$\endgroup$
4
  • $\begingroup$ Bidding? This smells of auctions. $\endgroup$ Nov 14, 2013 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$ Nov 14, 2013 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, 2013 at 5:42
  • $\begingroup$ @LukeMathieson expand it to an answer ? $\endgroup$
    – Subhayan
    Nov 14, 2013 at 14:44

1 Answer 1

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.

$\endgroup$
1
  • $\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, 2013 at 23:59

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.