Puzzle : Secret Sharing

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 2^{|S|} 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?

Advertisements

Tags: , , ,

3 Responses to “Puzzle : Secret Sharing”

  1. Pratik Poddar Says:

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

  2. Secret Sharing – 2 « Me, Myself and Mathematics Says:

    […] 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. […]

  3. Secret Sharing-3 « Me, Myself and Mathematics Says:

    […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: