Secret sharing over reals - constructing a (k,n) threshold scheme

Question

After following a discussion that Shamir's Secret Sharing scheme cannot be used to share a real number as secret, I came across the paper "Secret Sharing Over Infinite Domains" - B. Chor and E. Kushilevitz The above paper describes a method for sharing a real number as a secret, I quote from Section 4 (note: this paper may be accessed freely)

We first introduce a (k,k) secret-sharing scheme which distributes a secret a taken from the interval [0,1). We use the Lebesgue measure on [0,1) Choose independently, with a uniform distribution, k-1 real numbers, {$s_1$,.., $s_{k-1}$} in the interval [0,1). 2) Choose $s_k$ $\in$ [0,1) which satisfies $s_1$ +...+ $s_{k-1}$ +$s_{k}$ = a (mod 1). The proof that this is indeed a secret-sharing scheme is similar to the proof of its analogue in the finite case.
For introducing a (k ,n) secret-sharing scheme for every k $\leq$ n, we observe that the same technique described in [BL] works here as well.

I can see how this (k,k) threshold scheme works. However, I am having some issues with the (k,n) threshold scheme - I've tried to look at Generalized Secret Sharing and Monotone Functions which is referred to above as BL (note - this paper can also be accessed freely.) I don't see how this paper helps me construct a (k,n) threshold scheme.
Any help would be appreciated!

Answer 1

This $(k,n)$ scheme works, but isn't very interesting.

Effectively, it is:

• For each set of $k$ participants out of $n$, construct a $(k,k)$ threshold scheme, and distribute those shares to the participants in the set.

For example, in a $(2, 3)$ scheme, if $z$ is the secret, we'd generate $\binom{3}{2} = 3$ indepedent $(2,2)$ threshold schemes $(r_1, z-r_1 \bmod 1), (r_2, z-r_2 \bmod 1), (r_3, z-r_3 \bmod 1)$, and distribute to the three share holders the shares:

$$(r_1, z-r_2 \bmod 1)$$ $$(r_2, z-r_3 \bmod 1)$$ $$(r_3, z-r_1 \bmod 1)$$

It works, as:

• For any set of $k$ share holders, they can reconstruct the secret, as there is a $(k,k)$ threshold scheme with those share holders with all the shares. In the above example, the first two share holders jointly know both $z-r_2 \bmod 1$ and $r_2$, allowing them to reconstruct $z$.

• For any set of $k-1$ share holders, they learn nothing of the secret; for any of the $(k,k)$ threshold schemes, there will always be at least 1 missing share, and so they can learn nothing.

It's quite straight-forward; the biggest issue is that this requires distributing $\binom{n-1}{k-1}$ independent values to each share holder; this is rather large if you're trying to implement a $(500,1000)$ access structure.