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.

How can a group of people figure out who is the oldest, without revealing any other information?

Revealing all the ages to a trusted third party is not allowed. Preferably I'm looking for solutions where nobody gets other information, not even a third party.

Preferably I'm looking for a solution which works for large (e.g. 64-bit or 1024-bit) age values as well. (Even though using the word age is not intuitive for such large numbers.)

I'm looking for a low-cost pencil-and-paper solution, or a solution in which each pair of people has a secure bidirectional communication channel (i.e. the digital equivalent of: anyone can write any message to a sheet of paper, fold it, and pass it to anyone else). I'm not looking for solutions which require building other kind of physical devices.

(Is there a book or web page describing such non-revealing algorithms?)

This question is not a duplicate of Non-revealing maximum , because this question doesn't ask for the maximum age value: it even explicitly forbids revealing the maximum age value, because that would be too much information shared. Having a solution to this question doesn't give us a solution to the other question. Having a solution to the other question doesn't give us a solution to this question.

The solution to Yao's Millionaires' Problem can be used to solve this question when the group size is 2. But in this question I'm interested in the answer for larger groups as well.

share|improve this question
    
I've listed the question in the meta thread for reopening questions. It already has $3$ reopen votes, so hopefully it will be reopened shortly. –  joriki Apr 12 '13 at 22:29
1  
Are the people in the group assumed to be trustworthy? In other words, we're looking for a protocol during which none of them will learn any additional information, assuming they all follow the rules. Does it also have to be secure against people not following the protocol? –  Greg Martin Apr 13 '13 at 1:29
1  
@Greg: Since only they themselves know their own age, the protocol can't be secure against them not following it; they could pretend to have any age they want. –  joriki Apr 13 '13 at 4:28
1  
Considering how complicated the $n=2$ case is (going by the solution given at the Yao link), I suspect the general case would take several pages to describe. –  Gerry Myerson Apr 13 '13 at 6:20
    
If you use the solution to Yao's Millionaires' Problem as your comparison function in a sorting algorithm, you can figure out who is the oldest. However, that reveals more information than your question asks for. For example, the youngest is also revealed. –  Snowball Apr 13 '13 at 8:17

2 Answers 2

  1. Have a computer generate two secret lists $q_1,\dots,q_{1000}$ and $r_1,\dots,r_{1000}$ of random numbers.
  2. Have each person privately give the computer their age $A$; the computer reveals $q_1,\dots,q_A$ and $r_1,\dots,r_A$ to that person.
  3. Any two people can now compare their ages by the following protocol: person #1, whose age is $A_1$, selects a number $j$ at random from $1$ to $A_1$. He queries person #2 by revealing the number $q_j$. If person #2 cannot correctly identify $r_j$, then person #1 is older. Otherwise, person #2 now selects a number $k$ at random from $1$ to her age $A_2$. She queries person #1 by revealing $q_k$; if person #1 can't identify $r_k$, then person #2 is older. They go back and forth until one person is revealed to be older.
  4. Once you can decide which of two people is older, you can iteratively decide which of a group of people is oldest.

In fact you could have the queries/responses happen among all people simultaneously, to speed things up. Also you'd want to add something to the protocol to prevent infinite loops due to ties in age.

share|improve this answer
4  
Thank you for coming up with this solution and sharing it. This solution needs a trusted third party (i.e. the computer). If we allow a trusted third party to know everyone's age, then the third party can find out who is the oldest, and just announce it. This sounds simpler than your solution. Or am I missing something? Anyway, I've extended the question stating that using a trusted third party is not allowed. –  pts Apr 12 '13 at 23:36
    
Resolving ties is not too interesting to me. For simplicity we can assume for now that everybody has a unique age. –  pts Apr 12 '13 at 23:36
1  
I don't think step 4 is OK. If two people compare their ages, and we repeat this many times to find the oldest person, some people get to know that they are older than specific other people. And that's too much information, because they are supposed to know only who the oldest is. Those people who are not the oldest must not gain any additional knowledge. –  pts Apr 12 '13 at 23:43
3  
@pts This solution might be able to be recast in a way that doesn't rely on a trusted third party. The bit about people learning parts of the total ordering is trickier - I need to take your "without revealing any other information" more seriously.... –  Greg Martin Apr 13 '13 at 1:07
    
It would be awesome if you could recast your solution to avoid the trusted third party and update your answer accordingly. –  pts Apr 13 '13 at 7:27

Ok, let's try this. We're assuming that all participants will honestly follow the protocol. Let's also assume that the participants have distinct ages that are integers between 2 and 99.

Each participant is given 100 tiny boxes, a rack that can hold the 100 boxes in a linear order, and 100 orange marbles and 100 yellow marbles. Each participant initializes their rack of boxes as follows: if their age is $A$, then they put orange marbles in the first $A$ boxes and yellow marbles in the last $(100-A)$ boxes. The boxes are then closed so that nobody can tell which color marble is inside any box. Note that everyone's box #1 contains an orange marble; everyone's box #100 contains a yellow marble; and there exists at least one index $n$ for which the $n$th boxes together contain exactly one orange marble, and for every such index, it is the oldest participant whose box contains the orange marble.

The group then generates a random permutation of $\{1,\dots,100\}$ which none of them individually know, and applies that permutation to every participant's rack. (The easiest way to do this: one participant secretly selects a random permutation of $\{1,\dots,100\}$ and applies it to everyone's rack in private; then a second participant does the same.) After the permutation is applied, each participant privately opens their box #1. Whichever color marble they see, they put a marble of that same color in a communal bag (each participant can place their marble secretly, without anyone seeing it and without seeing any other marbles).

The communal bag is then opened. If it contains exactly one orange marble, then the person who placed the orange marble admits it, and everyone learns that this person is the oldest. If it contains no orange marbles or at least two orange marbles, then the communal bag is emptied and we go back to the random permutation step. Eventually (with probability exponentially close to $1$), one of the random permutations will result in exactly one orange marble among the participants' #1 boxes.

share|improve this answer
    
Thank you for coming up with this answer and sharing it. I'm looking for an answer which doesn't need physical devices, but it can be implemented efficiently and cheaply by passing around notes written on (folded) paper. Also I'm looking for an answer which scales to 64-bit and then to 1024-bit ages. I've updated the question accordingly. –  pts Apr 13 '13 at 9:59
    
It seems you are consistently changing the question every time Greg answers! I think this is a great answer, btw. –  user641 Apr 13 '13 at 12:38
    
@pts It's hard for me to see how someone could think this protocol couldn't be implemented using folded pieces of paper. And you want 1024-bit ages, at the same time?! Well, there's probably a way - good luck with that. –  Greg Martin Apr 13 '13 at 18:04
    
@GregMartin: +1 for this answer. Thank you again for both of your answers, I've learned a lot from them. Also they gave me an opportunity to refine what I'm interested in. –  pts Apr 13 '13 at 18:52
    
No problem - fun to think about! –  Greg Martin Apr 13 '13 at 21:35

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.