Can we compare two secret numbers?

Question

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.

Answer 1

Aye, this is Yao's Millionaires Problem!

Answer 2

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:

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:

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.