Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Ronald May 22 '12 at 17:41
1  
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! –  Qiaochu Yuan May 22 '12 at 17:44
3  
Here's a start: en.wikipedia.org/wiki/Secure_multiparty_computation –  Ronald May 22 '12 at 17:51
    
I can compare them, but the result of this comparison is a secret on its own and I can't tell you the result. :-) –  Asaf Karagila May 22 '12 at 20:10

3 Answers 3

up vote 8 down vote accepted

Aye, this is Yao's Millionaires Problem!

share|improve this answer
2  
Maybe math.se isn't the place to ask this, but is there a back-of-the-napkin version of this algorithm? –  Jeremy Stein May 22 '12 at 18:10
1  
An Efficient Protocol for Yao's Millionaires Problem (PDF) has a summary on pages 2–3. –  MJD May 22 '12 at 18:19

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.

share|improve this answer
    
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. –  Ronald May 22 '12 at 22:38

Here's one suggestion. Take turns giving intervals of (rapidly) decreasing size that contain your secret number, until such time as the intervals no longer overlap, at which point, you'll know which number is bigger, but not what each other's number is. The drawback to this, of course, is if you choose the same number!

share|improve this answer
5  
If your goal is for the two parties not to learn anything other than which number is bigger, this would seem to be a bad idea. –  Qiaochu Yuan May 22 '12 at 17:40
3  
Also, if your partner is dishonest (i.e. allowed to lie), then s/he could exploit this protocol & engage you in a binary search, and learn your secret number exactly. –  user2468 May 22 '12 at 18:02
    
@QiaochuYuan: True, if you don't want to reveal anything, but it does the trick without revealing the number. –  Cameron Buie May 22 '12 at 19:49
    
@J.D.: Well, if your partner is allowed to lie, then what's the point at all? (I actually mean this as a serious question, by the way.) –  Cameron Buie May 22 '12 at 19:52
    
@CameronBuie when establishing the security proof for a cryptographic protocol, you typically assume a model (I forgot the correct terminology). Stronger protocols are immune to dishonest partners. –  user2468 May 22 '12 at 20:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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