Posts Tagged ‘non linear classification’

Secret Sharing – 2

November 25, 2010


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 🙂