Secret Sharing-3

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

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 sets. In comparision, having such a circuit is a very efficient solution 🙂

Secret Sharing – 2

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

( we will give some positive number of points of polynomials to each of them )

( when all members of any set is present it should unlock the secret ( threshold is 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 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 🙂

Circles and Tangents

Recently I came across a very nice puzzle related to geometry.

Problem : Take any three non-intersecting circles of distinct radii. Common tangents of any two will intersect at a point. Prove that the three intersection points due to three pairs of tangents are co-linear.

Solution : Ramprasad and I came up with a proof but we believe that there should be much simple and elegant proof. If you can throw any light, please comment. Here is the proof.

Let the center of circles A, B and C be denoted by . Also the intersection points be denoted by and radii are .

Given any two circles, say A and B. Following relation holds due to congruence of the triangles formed.

. Now,

Simplifying, we will get . Thus, we have got how far a point will be given the radii of two circles and the distance between their centers. Let .

Now, Let be the origin and with respect to that the vectors of be denoted as .

So, vector for will be .

Similarly, and

For three points to be collinear, following must hold for some .

Therefore, we must prove that for some

Simplifying,

and

 

You can verify that it is indeed the case that

 

Very ugly math, and with very high probability I must have made a typo in the calculation. Please try it yourself and convince that the property holds. I am looking for a better proof!

Logic and games -2

Well,

In the earlier post I mentioned about using games as a mean to prove/disprove expressibility of FO ( First Order Logic ).

Let us modify the game that we saw last time. Now each round consists of the following : The spoiler chooses one of the structure, chooses a subset of elements of that structure, duplicator has to do the same on the other structure. Now, the spoiler puts a pebble on one of the elements of the subset he/she has chosen and duplicator replies by playing it on the other structure. We have seen in the earlier post that it is impossible to distinguish between two graph A (two disconnected 5-cycle )and B ( one 10-cycle ) using only 3 pebbles. In fact, you will need log 2k pebbles to distinguish between two disconnected k-cycles and one 2k-cycle.

However, in this modified game, only 3 pebble suffices for the spoiler to win for any k. Here is the strategy for the spoiler to expose the difference between two structure.

Look at the figure. Spoiler first chooses one of the k-cycle in A and puts a pebble. Duplicator selects k-points in B ( 2k-cycle ) and puts a pebble. Now, the spoiler chooses the second k-cycle and puts a pebble and duplicator replies. For the third round, the spoiler chooses to play on B. It selects the shortest path between two fixed pebbles as subset, and puts a pebble right in the middle of it. Duplicator now has to play it in A ( two disconnected k-cycles ). Now, according to pigeonhole principle one of the k-cycle will have two pebbles. As shown in figure, (1,2) and (2,3) are in different cycles. Now on, spoiler will always play in graph B. it will choose a pair of pebbles belonging to different cycles in A, selects the pair having shortest path in graph B and puts the pebble right in the middle of it. The spoiler always maintain that it divides the path between pebbles images of which are in different cycles in the other graph. it is easy to see that, after some time, duplicator will have no answer to spoiler’s move ( isomorphism implied by pebbles can not be maintained in the other graph ).

 

This game gives rise to a logic which is strictly powerful than FO. However, Ramprasad mentions that due to a recent result one can always construct pairs of graphs that spoiler can not win for any k-pebble game. Also, this game has some connection to graph isomorphism but probably ramprasad will give details in the comment 😉

 

Similar games are designed to prove/disprove the expressibility of temporal logic, but may be some other time 🙂

 

— Saurabh Joshi

Logic and Games

Dear All,

This post is a side effect of a fruitful discussion with Ramprasad, which also refreshed my memories about a course “Logic in Computer science”.

An interesting way to capture the power of First Order logic is in terms of Ehrenfeucht–Fraïssé games. Essentially, it is a two player game. Given two different structures A and B and set of k pebbles the game is played as follows. Spoiler tries to show that A and B are indeed different where as Duplicator will try to hide this fact. Each of them take turn. In every round, spoiler will choose one of the two structure and put a pebble on one of the element of that structure. Duplicator puts a pebble on the other structure so that the two substructures induced by pebbles are isomorphic with respect to the relations specified.

For example, take two graphs A and B. A consists of two disconnected 5-cycles and B be a 10-cycle. One can see that it is impossible to distinguish these two graphs if only 3 pebbles are given. Try the exercise with 4 pebbles and the spoiler wins irrespective of the number of rounds played. Similarly, structures could be bit strings. Given P pebbles, one can always construct two bit strings of length greater than such that one of then has odd parity and another one has even parity yet the spoiler has no way of winning. In general, parity checking or even st-connectivity ( whether there is a path from s to t in a graph ) can not be expressed in any first order logic. Here, pebbles corresponds to variables in the FO ( first order ) formula and a round corresponds to the quantifier depth of a formula. Hence, when we say duplicator wins in 5 pebble 10 round game,  is equivalent of saying that a formula which uses 5 variables and 10 quantifier depth can not express the property in question. When, the rounds are unbounded, it means that FO can not distinguish.

More interesting details/references can be found from wikipedia link given in this post. Thanks to Dr Anil Seth for introducing me to such a wonderful world of logic.

— Saurabh Joshi

Impartial Games

Well,

Today’s post is outcome of a fruitful discussion and puzzle solving with Ramprasad.

Problem : Given two pile of coins (n,m) – denoting that there are n coins in 1st pile and m coin in the second. In this two player game, a player is allowed to take as many coins as he/she wishes from any one pile. He/she has to take at least one coin. If a player does not have a valid move, he loses. Which player has a winning strategy and what is the winning strategy?

 

Solution : It turns out that the first player has a winning strategy if , otherwise the second player has a winning strategy. The strategy is that a player always make the configuration (i,i) and pass it on to the next player. Okay, for two pile this is simple enough. What about 3 piles? Who wins? What is the strategy?

In general, one can ask questions about such impartial games regarding the winning strategy. Grundy numbers and Sprague-Grundy theorem allows one to easily build strategy for wide class of such games.

As we are talking about finite impartial games, the leaves of game tree are assigned grundy number zero ( losing position ). Now for any node in the game tree, assign the smallest non-negative integer which is not equal to the grundy number of any of its child. Hence, in the two pile game, (n,0) configuration has a grundy number n.

So now, for a union game G1+G2 ( one can make a move in either game ), the grundy number of the node ( i , j)  is nothing but XOR of grundy number of i in G1 and the grundy number of j in G2.

 

For example, in the game of three coin piles with configuration ( 3, 4, 5 ) the XOR is 2 ( 011 XOR 100 XOR 101  = 010 ). Hence, any one getting a configuration with grundy number zero loses if the other player is smart enough :-). So, in a 3 pile game, a player’s job is to always make a move such that the grundy number of the resulting configuration is zero. Assume A XOR B XOR C = X. Now, we need to make a move such that A becomes A XOR X, or B becomes B XOR X or C becomes C XOR X so that the resulting configuration always yields a zero grundy number. Because X is non-zero look at the most significant 1-bit. You can choose A or B or C depending upon which of these have 1-bit in the corresponding position.

Not only this, one can have games like, a player is allowed to take at most 3 coins from 1st pile, upto 5 coins from 2nd pile or upto 8 coins from 3rd pile. It is easy to see that now grundy number of G1, G2, G3 is N mod 4, N mod 6, N mod 9 respectively. And resulting grundy number can be found by XORing these mod-ed numbers 🙂

 

Pardon for a not so clear and untidy article. I had to compromise a bit to keep the length tolerable :-). Please see corresponding wikipedia links and other relevant material for more details on games.

 

— Saurabh Joshi

Tournament graph and Hamiltonian Path

Well,

Those of you who are unaware of tournament graph and hamiltonian path, you can look here and here. Ramprasad gave me the following interesting problem to think about.

Problem : Given a tournament ( I will omit the suffix “graph” as it is obvious in the context of graph theory ), construct a hamiltonian path in polynomial time.

Solution : When I first heard the problem, I was even wondering how to prove first that all tournament indeed always have an hamiltonian path. And that too, we need to find it in polynomial time..Phew! But I believe that if you comeup with an algorithm, that itself gives you a proof!!

He gave me a hint : given that you already have explored some path how can you extend it for a given vertex ? That is, of course, if the path has not covered every vertex :-).

If there is a directed edge from to there is a natural extension. You just append to the path. If not, find out two consecutive vertices in the path such that the tournament have edges and in which case the modified path will be .

Suppose no such pair exists!!!! Let’s try to see why this can’t be true. Look at, . It has to be the case that either tournament contains edges or . If it is the second case, that can be just added as a prefix to the path. If it is the first case, than note that tournament must contain because other wise we can have . Similarly, we can argue for giving us the contradiction as we had assumed that edge is absent from the tournament.

Hence, we can always extend the path as long as there is some vertex we have not yet covered.
Ramprasad gave a simple proof of why a pair must exist such that we can extend the path to contain . If we can not add as a prefix or a suffix to the path. Then look at the vertex with the least index j such that is an edge. By the definition of the tournament, one of the two edge must be there. But, because j is the least index having an incoming edge in the path, the second edge can not be there. hence we can extend the path to contain .

Easy to see that algorithm runs in time as we need to search vertex to extend the path and repeat it till we  have covered all vertices.

–Saurabh Joshi