39
$\begingroup$

Ana, Barbara, Carol and Diana want to know their average age. But no lady wants to disclose her age.

They decide a strategy and use a calculator (one that doesn't store steps) and tapped some keys and passed it to other ladies. After some time, they had the sum of their ages and nobody could know the exact age of the other ladies.

Question
What was the strategy?

Improve this question
$\endgroup$
2
  • $\begingroup$ When you describe the calculator as one that doesn't store steps, does this mean it doesn't have the M+, M-, and MRC buttons? $\endgroup$
    – Jabe
    Apr 13, 2015 at 17:00
  • $\begingroup$ @Jabe Some calculators store intermediate steps and you can replay the steps or correct input. This calculator is a basic model and doesn't support storing of each step. $\endgroup$
    – Mohit Jain
    Apr 14, 2015 at 1:13

4 Answers 4

Reset to default
39
$\begingroup$

A puts in her age plus a random addition, B, C and D add the same..

Then A removes her addition, then B, C and D do the same.

In equation form where A is the actual age and a is the random addition chosen by A:
(A + a) + (B + b) + (C + c) + (D + d) - a - b - c - d = A + B + C + D which is sum of all their ages

Then divide by 4.

Improve this answer
$\endgroup$
21
  • 5
    $\begingroup$ Only the first person would have to add that random addition, because the sum of two random numbers still would be one random number. And since the number is random, Ana does not really have to add a number, only act like she did, and no one will know her age for sure. $\endgroup$
    – Peter B
    Apr 10, 2015 at 14:43
  • 4
    $\begingroup$ If someone watch the calculator at every step they could figure out everyone's age. For example, if A knows the total sum before and after B enters their value, A knows B's (age+random). If A knows the total sum before and after B removes the random value, A knows B's random value. $\endgroup$
    – DHall
    Apr 10, 2015 at 15:15
  • 5
    $\begingroup$ Note that this strategy, if implemented naïvely, may still leak some information, especially if the distribution of the random numbers is known (or can be guessed). For example, let's say Ana picks her random number uniformly between 0 and 100; that's surely random enough to totally obscure her age, right? But if the sum of her age and the random number turns out to be, say, 15 or 185, then Barbara has some pretty strong bounds on Ana's age. (To fix this, Ana could choose her random number between, say, 0 and 999, and reduce the sum modulo 1000 before handing it to Barbara, who does the same.) $\endgroup$
    – Ilmari Karonen
    Apr 10, 2015 at 19:37
  • 3
    $\begingroup$ Great idea, it won't work for 2 people though. $\endgroup$
    – Keivan
    Apr 11, 2015 at 1:09
  • 29
    $\begingroup$ @Keivan: There is no scheme that will work for two people: if I know my own age and the average of your age and mine, I can easily calculate your age. $\endgroup$
    – Ilmari Karonen
    Apr 11, 2015 at 15:36
20
$\begingroup$

The strategy suggested by Jiminion might work fairly well in practice, but it does risk revealing some extra information about the ladies' ages if the distribution of the random number(s) is known (or can be guessed).

For example, let's say Ana picks her random number uniformly between 0 and 100; that's surely random enough to totally obscure her age, right? But if the sum of her age and the random number turns out to be, say, 15 or 185, then Barbara has some pretty strong upper / lower bounds on Ana's age.

The way to eliminate this information leak is to use modular arithmetic, e.g. like this:

  1. Ana picks a random number between 0 and 999 (inclusive)1, adds her age to it, and hands the last three digits2 of the result to Barbara.

  2. Barbara adds her age to this number (it is not necessary for her to add a second random number), and hands the last three digits of the result to Carol.

  3. Carol and Diana do as Barbara did, with Diana handing the last three digits of the resulting sum back to Ana.

  4. Ana adds 1000 to the sum, subtracts her original random number, takes the last three digits and divides them by 4. The result is the average age of the ladies.

Notes:
    1) The modulus 1000 is chosen because it's presumably larger than the sum of the ladies' ages; any suitably large modulus M could be used, with the random number chosen from between 0 and M−1.
    2) To avoid side channel attacks, the reduction modulo 1000 should be done in a way that does not reveal whether the original number was over 999 or not; in particular, simply subtracting 1000 from any four-digit result could leak information, since the other ladies might see you push some extra buttons on the calculator to do it. It's safer to just re-type the last three digits from memory. The same goes for the final subtraction and reduction by Ana, too.

It's easy enough to prove that Barbara cannot learn anything about Ana's age at step 2, since, regardless of Ana's actual age, the number Barbara gets from her is equally likely to be any number between 0 and 999. By a similar argument, it's also clear that Carol and Diana cannot learn anything about the other ladies' ages at step 3. Finally, at step 4, the number Ana receives from Diana is simply the sum of all their ages (which the protocol is designed to reveal), plus her own random number, so it tells her nothing but the information she was supposed to get.

However, note that this protocol is not secure against collusion: Ana and Carol together can figure out Barbara's age by comparing the number Ana gave out to what Carol received. (They can also figure out Diana's age the same way — but if they do both, then they also end up revealing their own ages to each other!) Of course, Barbara and Diana can also collude to learn the age of Ana and/or Carol the same way.

It might seem that Barbara could protect herself from such collusion attacks by also adding a random number of her own to the sum, and then subtracting it during a second round (as in Jiminion's original protocol), but alas, this doesn't actually help: if Ana and Carol collude, they can compare their numbers again during this second pass, and so learn Barbara's random number, and thus her age.

BTW, this puzzle is a simple example of secure multiparty computation, which is an active subfield of cryptography. The specific protocol described here is also somewhat reminiscent of various secret sharing schemes, which might also make interesting further reading.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Your solution really does not improve the accepted answer that much. Seeing as the age of the ladies is going to be greater than 0 and (most likely) and less than 100 (obviously the gap is realistically going to be even less), the modulo arithmetic will only come into play if the randomly selected number is in the range of 0 to 99 or in the range of 900 to 999 which would leave the remaining range of 100 through 899 (80% of the randomly selected numbers) completely unaffected. $\endgroup$
    – Warlord 099
    Apr 10, 2015 at 21:05
  • $\begingroup$ 0..99 would be a better pick. If anyone is over 100, they wouldn't care about hiding their age anyways. $\endgroup$
    – Thebluefish
    Apr 10, 2015 at 22:43
  • 5
    $\begingroup$ @Warlord099 In some circles, learning about something secret one time out of five is an astronomically (and unacceptably) large percentage of the time. $\endgroup$
    – Daniel Wagner
    Apr 10, 2015 at 22:54
  • $\begingroup$ @DanielWagner What is your point and what does it have to do with me? $\endgroup$
    – Warlord 099
    Apr 11, 2015 at 23:35
  • 1
    $\begingroup$ I will admit that my answer might not be optimal, but the problem seemed to indicate that knowing/not knowing the exact age was the issue, not a probability of being close to guessing it. Also, by having everyone do the same thing (adding and subtracting a random number) that made the solution simpler, if perhaps a bit less efficient. $\endgroup$
    – Jiminion
    Apr 13, 2015 at 13:45
10
$\begingroup$

I think Jiminion has a good solution, but if I wanted to add a little more security/obscurity to it I would do the following:

  • Each lady selects 3 numbers (one is her correct age and two random numbers)
  • They pass the calculator around 5 times.
  • On each pass the lady must do one of the following (in any order as long as each lady does each item only once)
    1. Add her real age
    2. Add the first random value
    3. Add the second random value
    4. Subtract the first random value
    5. Subtract the second random value

After the last pass is complete they will end up with their total age and can divide by 4.

Note that you could theoretically do this with any number of random numbers so long as you subtract all of the random numbers you add in and the order of performing the actions is irrelevant since x = x + y - y = y + x - y = x - y + y, etc...

Improve this answer
$\endgroup$
5
$\begingroup$

A wrote just a part of her age, B and C did the same. Then, A added the remaining part of her age, as well as B and C.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is essentially the same answer as the accepted (Part of A's age is Age - random number) which is the same as "Add random number" only the random number is negative. - But you can also skip this step for B,C and D. Only A puts in part of her age, B,C,D add their whole Age and A adds the rest of hers and divides by 4 $\endgroup$
    – Falco
    Apr 22, 2015 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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