# Secret sharing over reals - Difficulty with Computer implementation

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.

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.

• 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. – Ilmari Karonen Dec 11 '18 at 14:06