How can a group of people find out their maximum age without revealing any other information to each other?

(Is there a book or web site about such non-revealing algorithms?)

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.

This a problem belongs to the group of secure multi-party computation.

Yao's Millionaires' Problem is similar but different problem. The linked article also contains its solution.

  • $\begingroup$ Does the "revealing any other information to each other" mean that "one person alone cannot figure out the maximum age", or "if all but one person cooperate, they still cannot figure out the maximum age"? $\endgroup$ – Henry Swanson Apr 12 '13 at 23:07
  • 1
    $\begingroup$ The solution suggested by Kundor can be easily employed using pencil-and-paper, specifically a single pencil and two sheets of paper, one of which is ruled, particularly assuming that all participants are honest. Just have people mark their age on the ruled paper, sliding the other sheet sideways over their marks, and after the last person does her mark, just lower the paper until the first mark appears. There is one problem though: it will reveal how many people have the maximal age. $\endgroup$ – tomasz Apr 12 '13 at 23:24
  • $\begingroup$ @HenrySwanson: "one person alone" would be good enough for me, but "all but one person cooperate" sounds more interesting. So if you have a solution for either, I'm interested. $\endgroup$ – pts Apr 12 '13 at 23:28
  • $\begingroup$ @tomasz: Great adaptation: cheap and simple, thanks! I'm more interested now in a solution with a digital equivalent (see in the question). $\endgroup$ – pts Apr 12 '13 at 23:31

Construct a device in which participants insert pegs at a height corresponding to their age. Participants take turns entering a closed room with the device. The peg is inserted through an aperture which only allows access to one column of peg holes. After inserting the peg, the participant rotates the aperture to the next column. Construct the device with ratchets such that the aperture can only advance, and can only go around once, never coming back to the first column (this is a one-use-only device.) Then the participant leaves the room and the next takes his turn.

After everyone is done, the lid of the device is lowered as far as it will go. Its height corresponds to the maximum age of the group.

Afterwards, destroy the device. (Or put in a reset button which ejects all the pegs and resets the ratchet.)

If you are worried, make it so that many handles must be used simultaneously to lower the lid, to prevent an untrustworthy participant from lowering the lid prematurely to discover the maximum age so far.

  • $\begingroup$ Thank you for the idea. I was looking for a low-cost pencil-and-paper solution. Clarifying the question... $\endgroup$ – pts Apr 12 '13 at 20:42

If the group consists of only 2 people, we can use the solution for Yao's Millionaires' Problem to solve this one. With that solution we can figure out who is older. Then the older person tells his age to the younger person. This doesn't reveal too much information, because for any good protocol the younger person gets to know the age of the other person, because he got to know the maximum age.

If the group size is larger than 2, and we can relax the requirements a bit, then I have a solution protocol. The relaxed requirements are: there is a chairman outside the group, and the group trusts this chairman with some aggregate information about the ages of some people (but they don't trust the chairman with their individual age).

The protocol consists of rounds. In each round at least one group member, who is not of the maximum age, is secretly eliminated. Every group member knows whether he has already been eliminated, but he doesn't know about the status of others. After each round the chairman announces a number, or he announces that the protocol is over. The last number announced is the answer (i.e. the maximum age). Each round goes like this: 1. The group (including eliminated members) and the chairman sit down to a round table in any random order. 2. The chairman picks two large random integers, writes them to a slip of paper, folds it, and passes it to the next person on the right. 3. This step is repeated for each group member. The next person reads the 2 numbers from the slip he has received. If the person is already eliminated, then he copies the numbers to a new slip of paper, folds it, and passes it on. Otherwise he picks a random positive integer coefficient, and adds his age multiplied by the coefficient to the first number, and adds the coefficient to the second number, writes the resulting two numbers to a new slip of paper, folds it, and passes it on. 4. The chairman receives the final slip, subtracts his own original random numbers, and divides the first result by the second result. The resulting ratio is a weighted average of the ages of the non-eliminated group members. 5. The chairman announces this weighted average, and declares that everybody not older than that is now eliminated. (This eliminates at least one person, the youngest of the non-eliminated ones.) 6. This is the end of the round. The protocol ends when the chairman has to divide by zero in step 4. The answer is the ratio he computed (and announced) in the previous round.

Having a chairman is indeed necessary. For example, if there was no chairman, but the first group member assumed that role (in addition to his normal duties in the protocol), too much information could be revealed. For example, let's assume that there are 3 people in the group, with the first one being the oldest, everybody has a different age, and the division-by-zero happens in the 4th round. In this case the first person can think like this: I got eliminated after the 3rd round, so in each round exactly one person was eliminated. So at the end of the 2nd round a single other person was eliminated. Based on the information I received as the chairman at the end of the 2nd round, I can compute both the coefficient and the age of that other person. I don't know who he is, but I know a non-maximal age value in the group. And that's too much information.


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.