Who is the oldest? (in a non-revealing way)

Question

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.

Answer 1

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.

Answer 2

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.