Suppose you have a file that you want to divide between $n$ users. Now the division should be such that whenever any $k$ of the $n$ persons collaborate they know the complete file otherwise they must not have any information about the file.
Interestingly the solution to this problem is related to the solution to the following problem :
Thirteen pirates go on an extended voyage, pillaging and plundering from Africa to Asia. By the end they have quite a stash--too much to take back with them. They decide to lock it in a chest, leave the chest on an island, and come back for it a year later. Of course, not being terribly trusting, they want to ensure that none of them can come back early and claim the treasure for himself. They could just put 13 locks on it and each take a key, but a pirate's life is dangerous--they may not all be around in a year. What they want is for any majority of the original thirteen to be able to open the chest, while any fewer will be locked out. How many locks will it take for them to achieve this? The locks they are using are quite simple. Each key opens only one lock (no master keys), but keys can be duplicated, so multiple pirates can have keys to the same lock.
Solution1:
For the pirate problem you should choose ${n \choose {k-1}}$ locks and distribute the keys such that for every group of ${k-1}$ users there is a lock that they do not have the key for.
This solution easily extends to the first problem. Let the data file be $x \in \mathbb{F}_q$. Now generate ${n \choose {k-1}}$ random variables $R_i, i \in \{1, \ldots, {n\choose {k-1}}\}$ and give each user the information $x + \sum_{i=1}^{n \choose {k-1}} R_i$. Now, the values of the random variables can be distributed like the keys of the lock in the previous puzzle, and we are done.
Solution2:
This is the solution proposed by Adi Shamir (the guy behind Bitcoins), here.
Basic Idea : If you are given any $k$ points of a $k-1$ degree polynomial $f(x)$, you can determine the polynomial. So,
secret := polynomial coefficients
user data := $n$ points of the polynomial
Ofcourse, the polynomial is over a finite field. You need only $k$ random variables in this scheme to share one bit ($a_0 = [x^0] f(x)$) instead on ${n \choose (k-1)}$ in the previous scheme.
Interestingly the solution to this problem is related to the solution to the following problem :
Thirteen pirates go on an extended voyage, pillaging and plundering from Africa to Asia. By the end they have quite a stash--too much to take back with them. They decide to lock it in a chest, leave the chest on an island, and come back for it a year later. Of course, not being terribly trusting, they want to ensure that none of them can come back early and claim the treasure for himself. They could just put 13 locks on it and each take a key, but a pirate's life is dangerous--they may not all be around in a year. What they want is for any majority of the original thirteen to be able to open the chest, while any fewer will be locked out. How many locks will it take for them to achieve this? The locks they are using are quite simple. Each key opens only one lock (no master keys), but keys can be duplicated, so multiple pirates can have keys to the same lock.
Solution1:
For the pirate problem you should choose ${n \choose {k-1}}$ locks and distribute the keys such that for every group of ${k-1}$ users there is a lock that they do not have the key for.
This solution easily extends to the first problem. Let the data file be $x \in \mathbb{F}_q$. Now generate ${n \choose {k-1}}$ random variables $R_i, i \in \{1, \ldots, {n\choose {k-1}}\}$ and give each user the information $x + \sum_{i=1}^{n \choose {k-1}} R_i$. Now, the values of the random variables can be distributed like the keys of the lock in the previous puzzle, and we are done.
Solution2:
This is the solution proposed by Adi Shamir (the guy behind Bitcoins), here.
Basic Idea : If you are given any $k$ points of a $k-1$ degree polynomial $f(x)$, you can determine the polynomial. So,
secret := polynomial coefficients
user data := $n$ points of the polynomial
Ofcourse, the polynomial is over a finite field. You need only $k$ random variables in this scheme to share one bit ($a_0 = [x^0] f(x)$) instead on ${n \choose (k-1)}$ in the previous scheme.
No comments:
Post a Comment