1
$\begingroup$

I asked a question recently regarding the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz which describes a secret sharing scheme for real numbers in the interval $[0,1]$. I got a fantastic answer as to how to construct a $(k,n)$-scheme.

However, I am struggling to implement the recommended scheme for a general case - I would like to believe there is an algorithm to do this; however, I was unable to do so. Below is a summary of where I am stuck -

For the case $(k,n) = (3,5)$, I used a "2-space diagonal assignment" technique which I have described below:

We have 10 independent $(3,3)$ schemes to construct denoted by
$$r_{j,1}, r_{j,2}, S - r_{j,1} - r_{j,2} \pmod 1 \;\;\forall j \in \{1,\ldots,10\}$$

let $r_{j,3}$ denotes $S - r_{j,1} - r_{j,2} \pmod 1$

My assignments were as follows;

$1 \rightarrow (r_{1,1},r_{2,2},r_{3,3},r_{6,1}, r_{7,2} ,r_{8,3} $)
$2 \rightarrow (r_{2,1},r_{3,2},r_{4,3},r_{7,1}, r_{8,2} ,r_{9,3} $)
$3 \rightarrow (r_{3,1},r_{4,2},r_{5,3},r_{8,1}, r_{9,2} ,r_{10,3}$)
$4 \rightarrow (r_{4,1},r_{5,2},r_{6,3},r_{9,1}, r_{10,2},r_{1,3} $)
$5 \rightarrow (r_{5,1},r_{6,2},r_{7,3},r_{10,1},r_{1,2} ,r_{2,3} $)

I hypothesized that this assignment technique which appears correct is either re-usable for other (k,n) schemes or depends on the difference (n-k).

I tried the both a 2 and 3- space diagonal assignment for a $(3,6)$ scheme..

However, I was unable to work out an assignment technique for the said (and general) case.

Would appreciate any help in finding a general assignment to progress further with my investigation into this scheme. Thanks in advance.

$\endgroup$
3
$\begingroup$

Recall the definition of a $(k,n)$-threshold secret sharing scheme is that any group of at least $k$ players (out of $n$ total players) can recover the secret given their shares. The naive method for constructing a threshold scheme out of a non-threshold scheme (which was recommended in your previous question's answer) is giving every possible $k$-combination of the $n$ players a fresh $(k,k)$ sharing of the secret. (I'll note that this is only practical for small values of $n$.)

It seems that you are stuck on the question of how to enumerate all of the possible combinations. A good reference is this comprehensive answer on Stack Overflow, which mentions several algorithms.

Here is a quick Python script that will calculate all of the combinations for $k=3, n=5$:

import itertools

players = {1, 2, 3, 4, 5}
k = 3
for subset in itertools.combinations(players, k):
    print(subset)

With the resultant subsets:

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

This is of course a general algorithm that will work for any values of $k$ and any set of players.

$\endgroup$
  • 2
    $\begingroup$ Just to make it clear for anyone who might stumble across this thread, this naive method is not a practical way to construct a $k$-out-of-$n$ threshold secret sharing scheme. Sure, it works, but the shares will be huge. Even for your example of $k=3$, $n=5$, you'll end up with shares that are about 10 times as big as for an equivalent instance of e.g. Shamir's scheme. $\endgroup$ – Ilmari Karonen Dec 11 '18 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.