Comparatively, simple puzzle today. Again, thanks to ramprasad.

A king was dying. (There is something about puzzles woven into a story, it makes it more dramatic 🙂 ) He alone knew the key to the secret treasure. He had N sons ( anything can happen in a puzzle! ). He wanted to pass on this secret key to his sons. Passing the key in its entirety may become reason of a quarrel. Let us say that key is a very large number ( or a large binary string ).

1) He want to make sure that only when all of his sons combine their part of the key, can they open the treasure.

2) He want to make sure that any k out of N can combine their keys to open the treasure, but any set of k-1 keys can not open the treasure.

Solution :

1) First is extremely simple. Let us say string S is the secret. Generate N-1 random strings of the same length as S. Create Nth key such that XOR of all the keys gives S. Done. Without all N keys, treasure can not be opened as they have to find S from possible strings.

2) Second is also easy. It was an aha moment, when ramprasad told me the general strategy to design such a secret sharing mechanism. Let us say, you want to make sure that any k out of N son can open the treasure. Let us say the number S is the secret. Generate a random polynomial f(x) of k-1 degree such that f(0) = S. Or in other words, S is the constant in the polynomial. Now the part of the keys are nothing but evaluation of the polynomial at some random points ( of course, not at 0 ). Given any k-1 points, there can be infinitely many k-1 degree polynomial which can pass through these points. However, for any given k points, a unique k-1 degree polynomial can be determined.

Well, there you go, so easy eh?

### Like this:

Like Loading...

*Related*

Tags: math, polynomial, puzzle, secret sharing

This entry was posted on January 30, 2010 at 1:02 pm and is filed under math, puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 31, 2010 at 3:27 am |

Nice problem..

I suggest an extension to the problem. This extension would also show how beautiful cryptography and mathematics is.

Suppose it wasn’t a secret string. Suppose we had locks and keys to the box of gold coins. How many locks have to be put and how should keys should be made for each lock and be distributed to N sons so that he can make sure that any k out of N can combine their keys to open the treasure, but any set of k-1 keys can not open the treasure.

Beautiful combinatorics problem. Problem also posted on my blog. 🙂

November 25, 2010 at 8:03 am |

[…] have already talked about secret sharing in one of the earlier post. Funny thing happened recently, Ramprasad came up with a question which is a little bit modified. […]

November 26, 2010 at 10:32 am |

[…] element of the tuple ( that is for each set Si) you can use the XOR method that we mentioned in the first post of the […]