Posts Tagged ‘secret sharing’

Secret Sharing-3

November 26, 2010

As promised in the last post,  I am back with the solutions to the problem we left. There are  couple of solutions when collection of sets is given explicitly. If for example, sets S1 to Sn are given with the constraint that all and only members together from any set should be able to unlock the secret. Given n such sets, there are two solution which are similar in some sense.

First solution, can make the unlocking as hard as possible. That is, there is a brute force way to unlock, even if you are not authorized. In this, we share a secret as n tuple, each co-ordinate in the tuple is of length 1024 ( making it 2^{1024} possibilities ). That is for each set, you have 1024 bit. Choose a secret S and make n copies of it. Now, for each 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 series.

Second solution, again uses tuples, but instead of using the XOR one can use the polynomials. Choose, different polynomial for each co-ordinate of the tuple such that the polynomial constant is secret S. This is again described in the first post.
However, when sets are not given explicitly, the size of the tuple becomes very large if one goes on to enumerate all possible sets which can unlock. The solution which ramprasad had in mind is using circuit with threshold gates. Th_k is a k-threshold gate which becomes one when k or more of the inputs are set to one.

Now, let us see how the circuit for the counter example mentioned in the last post would look like.

The example was as follows. group of 8 persons. 5 or more should be able to unlock the secret. If there are 4, then they would be able to unlock only if there are even of them from the first half ( in turn, there are even of them from each half 🙂 ).

The circuit would look like this

Th_5 \;OR\; (LTh_4)\; OR\; (LTh_2\; AND\; RTh_2)\; OR\; (RTh_4) where LTh and RTh denotes threshold gates for the left and the right half. Note that if we want to enumerate the sets there are {8 \choose 5} + {4 \choose 2}{4 \choose 2} + 2{4 \choose 1} sets. In comparision, having such a circuit is a very efficient solution 🙂

Secret Sharing – 2

November 25, 2010

Well,

We 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. He had a different answer in mind, but I came up with a very simple solution.

Problem : Given a secret S, you have to divide it amongst p1,\dots,p6 such that p1 and p2 together should unlock the secret. Alternatively, p1 or p2 along with three of the other four ( p2 to p6 ) should be able to unlock the secret. However, p2 to p6 together should not be able to unlock the secret.

Solution : I came up with a very simple solution. Take any random polynomial of degree 5 such that the constant term is our secret. Evaluate this polynomial at 10 nonzero random points. Now, give 3 points each to p1 and p2 along with their values. Similarly, distribute one point each to the remaining four persons. See that to construct the original polynomial and hence evaluate it at zero, you need at least 6 points.

For this concrete example this solution is perfectly valid. I was tempted to generalize it as follows.

Let us say that we are given collection of sets. In this case, sets are {1,2},{1,3,4,5},{1,3,4,6} ….. and so on. Meaning, you should be able to unlock the secret when all the members of any set are present. I was tempted to generalize the solution I gave earlier, as follows.

Write it in form of constraints such that we will give each person pi weight wi

So now the constraints will be

\forall i w_i > 0 ( we will give some positive number of points of polynomials to each of them )

\forall _{S_i \in C} \sum _{j \in S_i} w_j \geq 1 ( when all members of any set is present it should unlock the secret ( threshold is 1 )

\forall _{S_i \in C} \forall _{x \in S_i} \sum _{j \in S_i - x} w_j < 1 ( if not all members of the set are present, they should not be able to unlock the secret )

The reason why threshold is taken as 1 is because once we get any feasible solution to this system of inequalities, we can always scale it up, so that all w_i are positive integers and accordingly we will choose threshold T  ( degree T-1 polynomial ). So when collectively when they have T points, they can construct the polynomial and hence, can unlock the secret.

How do we know that the system of inequalities always have the solution? ( if it does, it has infinitely many of them ). Apparently, it is not always possible to have the solution for such a system. Here, any solution defines a hyperplane in n-dimension ( n being total number of people ) such that all the points above it are acceptable and all the points below it are not.

So for collection of sets which demands non-linear surface, this method will not work. Here is a counter-example that ramprasad came up with.

Let us say that there ar 8 persons. You are supposed to divide the secret in the following manner.

  1. If there are 5 or more together, they can unlock
  2. If there  are exactly 4 of them, then if there are even number of them from the first half ( p1 to p4 ) then they should be able to unlock the secret.
  3. Should not be able to unlock in all other cases.

Observe that this gives rise to non-linear partitioning surface.

There are many different generic solution  to this kind of problem. Will talk about it sometime later 🙂

Puzzle : Secret Sharing

January 30, 2010

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?