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

Improve this question
$\endgroup$
3
  • 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
    Commented Apr 10, 2015 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
    Commented Apr 10, 2015 at 7:59
  • 1
    $\begingroup$ Wouldn't this be equivalent to a Hamming code of length 7? $\endgroup$
    – qzx
    Commented Apr 10, 2015 at 8:19

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Apr 10, 2015 at 15:42
  • $\begingroup$ Yes, it also works over a finite field, which I guess should be chosen to be large. $\endgroup$
    – Aravind
    Commented Apr 10, 2015 at 19:54
  • $\begingroup$ IIRC, Shamir's method was slightly different. Call the secret A, choose a modulus M (M > A, M has no small factors), then choose three random numbers B, C, and D, and find the unique cubic polynomial P such that P(0) = A (mod M), P(1) = B (mod M), P(2) = C (mod M), and P(3) = D (mod M). Give the dwarf $i$ the numbers M and $P(i) mod M$. This uses only integers and gives a person no information until they have 4 dwarfs. $\endgroup$
    – ralphmerridew
    Commented Dec 5, 2020 at 1:46
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This was the solution I had in mind, as it bears similarity to lock and key problems. $\endgroup$
    – Mike Earnest
    Commented Apr 10, 2015 at 15:32
  • $\begingroup$ So, I understood how only 4 dwarves can be sent and if 3 or less get caught then the msg cannot be decrypted. But, I didn't understand how we can send all the 7 dwarves. Can you pls explain? $\endgroup$
    – Hemant Agarwal
    Commented May 13 at 23:59

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