6
$\begingroup$

Snow White needs to send a message to Prince Charming. She considers telling this message to each of the Seven Dwarves, then sending them to deliver it to the Prince. However, the road to the castle is treacherous, and there is risk that agents of the evil Queen might intercept some of the dwarves. So, Snow White wants to say something to the dwarves so that...

  • As long as any 4 dwarves reach Prince Charming, they can tell him the message, but
  • If at most 3 are captured, the Queen cannot learn anything about the message, no matter how hard she interrogates the poor dwarves.

What should Snow White tell the dwarves?

Remarks: Think of the message as a number. Snow White has access to a fair coin. You don't need any fancy cryptography protocols to solve this: there are several elegant solutions using very basic math.

$\endgroup$
  • 1
    $\begingroup$ Does 'not learning anything about the message' include meta-information such as the fact that it exists, its probable length, its sender and intended recipient, etc? $\endgroup$ – A E Apr 10 '15 at 7:51
  • 1
    $\begingroup$ @AE Let's say that the queen already knows all this meta-information, so it doesn't matter whether she can learn this form the dwarves. $\endgroup$ – Mike Earnest Apr 10 '15 at 7:59
  • 1
    $\begingroup$ Wouldn't this be equivalent to a Hamming code of length 7? $\endgroup$ – qzx Apr 10 '15 at 8:19
7
$\begingroup$

This is a classic problem in cryptography, known as:

The secret sharing problem - how can we divide a secret among n people so that selected subsets, eg: any group of at least r people - can reconstruct the secret, but ZERO information is contained in other subsets.

A standard solution to this problem is:

Snow White calls the secret A and picks 3 random numbers B,C,D as well as 7 different random numbers $X_1,X_2,\ldots,X_7$, one for each dwarf. To dwarf $i$, she gives the value of the polynomial $A+BX+CX^2+DX^3$, evaluated at $X_i$. Any four dwarves can recover the coefficients $A,B,C,D$ knowing the values at four different points, but knowing the values at 3 different points reveals no information about any coefficient. I believe this solution was first given by Adi Shamir.
Instead of using polynomials, we could have also chosen 7 random and linearly independent vectors in $R^4$ and given their inner product with $(A,B,C,D)$ to the dwarves.

Another known solution to this is:

http://en.wikipedia.org/wiki/Visual_cryptography

$\endgroup$
  • $\begingroup$ Very elegant! Does the polynomial one also work over a finite field, instead of $\mathbb R$? Because that would make the "choose a random number part" much more friendly. $\endgroup$ – Mike Earnest Apr 10 '15 at 15:42
  • $\begingroup$ Yes, it also works over a finite field, which I guess should be chosen to be large. $\endgroup$ – Aravind Apr 10 '15 at 19:54
3
$\begingroup$

Encode the message as a binary string. Decompose this string into 4 parts that can be xored bitwise together to get back the original, using the coin to generate randomness (three flips are needed for each bit). Like so:

original: 1000111011110011...

part 1:   0000111011010100...

part 2:   1010111001100000...

part 3:   1111100011001010...

part 4:   1101011010001101...

Note that each three parts are worthless without the fourth one. Also note that the probabilities of finding 0s and 1s in all parts are 50%, regardless of the value of the original bit.

Now take four dwarves and give each of them one part.

There are 35 possible combinations of 4 different dwarves out of 7, so repeat the process described above 35 times.

The final output is highly redundant, but no information can be deduced from any incomplete decomposition that could be used to infer the missing information in another incomplete decomposition.

$\endgroup$

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.