If you and I each have a secret number, is there a way we can find out whose is larger without either of us revealing our secret number?

Clearly a trusted third party could do the job, but I was wondering if there's some mathematical or cryptographic trick that could be used.

For practical examples, consider two people who want to compare salary, or age, or number of speeding tickets, etc.

  • $\begingroup$ I have seen this posed as a problem elsewhere. And so, I recall that Cameron's answer is sub-optimal. Let me have a look... meanwhile Crypto.SE might recognise this as a standard question. $\endgroup$ – Ronald May 22 '12 at 17:41
  • 1
    $\begingroup$ You don't need a trusted third party. An untrusted third party and a zero-knowledge proof (en.wikipedia.org/wiki/Zero-knowledge_proof) would seem to do... if she blurts out one of your secret numbers, just assume she's lying! $\endgroup$ – Qiaochu Yuan May 22 '12 at 17:44
  • 3
    $\begingroup$ Here's a start: en.wikipedia.org/wiki/Secure_multiparty_computation $\endgroup$ – Ronald May 22 '12 at 17:51
  • $\begingroup$ I can compare them, but the result of this comparison is a secret on its own and I can't tell you the result. :-) $\endgroup$ – Asaf Karagila May 22 '12 at 20:10

Aye, this is Yao's Millionaires Problem!


Not mathematically rigorous, but perhaps more practical:

Let's assume we can narrow down the numbers to one of ten values. Perhaps you're willing to round your salaries to the nearest 5K and you think they're between 50K and 95K, or you were both willing to announce that you had less than 10 speeding tickets.

Each of you should take half a deck of cards. Pick one card to be your marker (perhaps an Ace - something easy to remember) and show the other person. Now, as you together count up through the possible values, you take turns placing a card face down onto a common pile. When you get to your number, you put your marker card down. When you're done counting, you have 20 cards in the pile and whichever marker card is on top would indicate the person who has the higher number, but you can't look yet!

For example, if the first person has 2 speeding tickets (marker card in green), and the second has 4 (marker card in red), the pile would grow like this:

card piles

Now you each take turns holding the pile under the table while you put some of your remaining cards on the top of the pile and some underneath the pile. After you've each done this, you don't know how deep in the deck your original pile of 20 cards is. But it's somewhere, and the top marker card still indicates whose number is higher.

For the above example, the deck would now look something like this:

sideways card pile

Then you can flip the cards off the top of the pile until you hit one of your marker cards. If it's the marker of the person who was placing his card second on each number announcement, you should check the next card also, to see if you have a tie. Immediately shuffle the deck.

  • $\begingroup$ Nice! One small concern is about the fixed bounds - if both players are towards the top of the range, say, then one player gets a whole lot of information about the other. Yao's method also has this problem, but you can easily agree an implausibly high bound. A statistical/probabilistic argument based on the number of cards in the top or bottom of deck may also glean extra info about the opponent's number. $\endgroup$ – Ronald May 22 '12 at 22:38

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.