5
$\begingroup$

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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you so much for your in-depth answer; really appreciate the clarity of your example along with the generalization of the solution. Really makes me wish I was also in a position to be able to answer questions on Stack Exchange - hopefully, I will get there one day! $\endgroup$ – Rahul Mathur Oct 24 '18 at 23:21
  • 2
    $\begingroup$ (500,1000) is "rather large" he says... 1.35144120472718284758e+299 to be approximate. I wish we had an understatement badge. Either that or I'm gonna need a poncho for all the sarcasm dripping off that statement. $\endgroup$ – Ken Goss Oct 25 '18 at 1:24
  • $\begingroup$ @poncho would you know of a way for your suggestion to be implemented in practice? I tried constructing a (3,4) scheme by hand but I cannot gather is there is a known algorithm to automate the share distribution and inform parties about which shares they possess need to be combined to recover the secret. $\endgroup$ – Rahul Mathur Oct 25 '18 at 11:28
  • 1
    $\begingroup$ @RahulMathur: it ought to be straight-forward; it's easy enough to generate all the $k$-sized subsets out of $n$ in a deterministic order; that's all you need for the share distribution. As for informing the parties about the shares, you could either explicitly list with each subshare which subset it corresponds to, or make that implicit (by telling them their position out of $n$, and having them reconstruct the subshare ordering based on the $k$ out of $n$ ordering you used. $\endgroup$ – poncho Oct 26 '18 at 14:25
  • $\begingroup$ @poncho would you be able to answer my question about the generalized algorithm to implement the above? I've asked that question here $\endgroup$ – Rahul Mathur Nov 3 '18 at 11:07

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.