39

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?

Rand al'Thor
  • 116,845
  • 28
  • 322
  • 627
Mohit Jain
  • 3,628
  • 24
  • 43
  • 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? – Jabe Apr 13 '15 at 17:00
  • @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. – Mohit Jain Apr 14 '15 at 01:13

4 Answers4

39

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.

lipeiran
  • 543
  • 4
  • 16
Jiminion
  • 1,952
  • 14
  • 19
  • 5
    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. – Peter B Apr 10 '15 at 14:43
  • 1
    @Dropeter, But then Ana couldn't look at the calculator after B, because then she'd know B's age, right? And in general, if C saw the calculator before and after B added to it, then she'd know B's age as well. Depending on the 'rules', I think they all have to add a random amount. – Jiminion Apr 10 '15 at 15:07
  • 4
    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. – DHall Apr 10 '15 at 15:15
  • Right. I guess the puzzle says the only lady n+1 sees the calculator after lady n has added to it. – Jiminion Apr 10 '15 at 15:29
  • 1
    @Jiminion Yes, you are right – Mohit Jain Apr 10 '15 at 17:12
  • @MohitJain I'm not sure what the best answer is. Maybe only Ana has to add a random number. – Jiminion Apr 10 '15 at 18:58
  • 5
    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.) – Ilmari Karonen Apr 10 '15 at 19:37
  • 2
    a,b,c and d could be positive / negative number, which you couldn't guess the age at all just by looking at the Sum? – Alex Apr 10 '15 at 20:22
  • 3
    Great idea, it won't work for 2 people though. – K1. Apr 11 '15 at 01:09
  • Third lady will know sum of ages of first two, but, probably it is the best possible way to do it. – Yola Apr 11 '15 at 08:04
  • @IlmariKaronen you just have a huge (relatively speaking) number as your random number, something like 34982 is unlikely to give away anything. – enderland Apr 11 '15 at 15:22
  • 1
    @enderland: Well it does now, you just told us what it is. ;) But, seriously, I agree that the weakness I described is more theoretical than practical. If Ana picks her random number uniformly between, say, 0 and 99999, then the probability that Barbara can learn anything about her age (assumed to be between 0 and 100 years) is less than 0.2%. If that's still too much, she can just widen the range even further. – Ilmari Karonen Apr 11 '15 at 15:34
  • 30
    @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. – Ilmari Karonen Apr 11 '15 at 15:36
  • 1
    @IlmariKaronen Oh, yes you're absolutely right, that's one degrees of freedom. – K1. Apr 11 '15 at 15:43
  • You don't need that last step. Put X of random numbers into a hat that add up to exactly 0, where X is the exact number of people. Have everyone pick a random number. Have everyone tell you their (age+random number). Divide by X. – Jonathon Apr 11 '15 at 19:18
  • 1
    @JonathonWisnoski how many "random numbers" that add up to 0 can you fit inside a hat? 4 unique numbers at best? so the chance of you guessing a person's age based on the knowledge of the four random numbers (and your own age) would be 1/3? doesn't seem quite right.. – user2813274 Apr 12 '15 at 05:59
  • 1
    @JonathonWisnoski: That sounds like a sensible scheme, but it requires a trusted outsider to generate the random numbers. (If whoever gets to generate the numbers isn't trustworthy, they can pick the numbers to be far enough apart that they can simply tell everyone's age from the sums they report.) If you do have such a trusted outsider, you might as well just have all the ladies whisper their age to her, and have her announce the average. – Ilmari Karonen Apr 12 '15 at 12:54
  • 1
    @Ilmari Karonen Well the numbers can be known by everyone so everyone can be involved in creating them and everyone can verify their integrity and correctness. – Jonathon Apr 12 '15 at 13:09
  • 1
    @JonathonWisnoski: I don't see how that would work. If the four numbers are, say, 957, 305, -32 and -1230, and everyone knows that, it'll be pretty obvious from the results who got which number. (You can make it harder by choosing smaller random numbers, but then they're no longer as effective in actually masking the ages.) – Ilmari Karonen Apr 12 '15 at 13:22
  • 1
    @JonathonWisnoski: For a worst-case scenario, imaging that all the ladies already know that they are, say, between 44 and 46 years old -- except Diana, who only knows the others online, and has no idea if they're 15 or 95. If you publicly pick large random numbers (say, between -100 and +100), then A, B and C will almost surely learn each others' exact age; if you pick small ones (say, between -5 and +5), Diana will learn that all the others are in their forties. Pick medium-sized numbers (say, between -20 and 20), and you'll probably get both leaks. – Ilmari Karonen Apr 12 '15 at 13:25
  • 1
    Well considering we are using a physical method instead of log into a server and anonymously enter your age, I was sort of thinking that they all already had a pretty good idea of the ages of everyone else (and were using small numbers). So you have a range but they already had a pretty decent range because they were in the same room as each other.

    How about distributing the number generation? Half the group picks two medium sized numbers that add up to 0. So any single person only knows for example that one person will pick 20 and another -20, but not if 23 or 18 are also available or not?

     – Jonathon Apr 12 '15 at 17:33
20

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.

Community
  • 1
Ilmari Karonen
  • 3,209
  • 1
  • 14
  • 20
  • 2
    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. – Warlord 099 Apr 10 '15 at 21:05
  • 0..99 would be a better pick. If anyone is over 100, they wouldn't care about hiding their age anyways. – BlueBuddy Apr 10 '15 at 22:43
  • 5
    @Warlord099 In some circles, learning about something secret one time out of five is an astronomically (and unacceptably) large percentage of the time. – Daniel Wagner Apr 10 '15 at 22:54
  • @DanielWagner What is your point and what does it have to do with me? – Warlord 099 Apr 11 '15 at 23:35
  • If we label the ladies 1,2,3,4,5 and then have each lady add her age plus a random number the first time they have the calculator, then subtract it the second time they do, and pass the calculator in the order: 1,2,3,4,5,1,3,5,2,4 (so no pair of ladies can know both numbers trivially), I think the only collusion of three ladies we could get would be 2, 3, and 5 discovering 4's age. (and I suspect if we had a third round, we could make no collusion possible, except the trivial 4 lady collusion) – Milo Brandt Apr 12 '15 at 18:07
  • @Meelo: You know there are only 4 ladies in the scenario, right? – Ilmari Karonen Apr 12 '15 at 18:19
  • @IlmariKaronen I do now! Then the order of $1, 2, 3, 4, 1, 3, 2, 4$ probably eliminates all nontrivial collusion. – Milo Brandt Apr 12 '15 at 18:22
  • 1
    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. – Jiminion Apr 13 '15 at 13:45
10

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...

Warlord 099
  • 1,784
  • 1
  • 11
  • 13
5

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.

leoll2
  • 12,590
  • 3
  • 39
  • 83
CarmeloS
  • 159
  • 2
  • 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 – Falco Apr 22 '15 at 11:28