2
$\begingroup$

Are there any different secret sharing schemes instead of Shamir's Secret Sharing , that is not based in polynomial interpolation over finite fields? Or is it the most efficient than the others?

$\endgroup$
3
$\begingroup$

You shouldn't think of secret sharing as being (directly) related to polynomials, and instead should see it as being directly related to (usually linear) codes, which are generally related to polynomials.

There are general results on getting secret sharing schemes from linear codes. From this perspective, Shamir's secret sharing is generally the scheme you get if you instantiate the general construction with a particular class of linear codes (usually Reed-Muller codes). Here is a particular paper on the topic, but it is somewhat arbitrarily chosen --- in general, Ronald Cramer writes on this area extensively, so searching his DBLP may be useful for more information.

From this point of view, there is a particularly nice property that Shamir's scheme has that most other schemes don't --- given two sets of Shamir's secret sharing shares, there is a way to "multiply" shares. This "multiplication" protocol suffices to construct Multiparty Computation, and is the basis of the BGW MPC protocol. You can read about this protocol in many places, say here or here.

$\endgroup$
1
  • $\begingroup$ thanks for the answer. I have seen in economic papers using the BGW protocol for the multiparty computation, however I am not aware of the cryptographic protocols and I will open a new question with some references from papers that I have seen. $\endgroup$ Nov 5 '21 at 8:14
3
$\begingroup$

Blakley's scheme was introduced at the same time as Shamir's.

Blakley’s Secret Sharing Scheme (SSS) uses hyperplane geometry to solve the secret sharing problem. The secret is a point in a $t$ dimensional space and the $n$ shares are affine hyperplanes that pass through this point. An affine hyperplane in a $t-$dimensional space with coordinates in a field $F$ can be described by a linear equation of the following form: $$ a_1x_1 + a_2x_2 + \cdots + a_tx_t = b. $$ The intersection point is obtained by finding the intersection of any $t$ of these hyperplanes. The secret can be any of the coordinates of the intersection point or any function of the coordinates.

Appendix:

In fact, Shamir scheme is based on Reed-Solomon not Reed-Muller codes. One could even say that Shamir rediscovered the Reed-Solomon codes, in the context of "erasure of symbols" (missing codeword coordinates).

To make that precise, it is possible to think of Reed-Solomon codewords $c_f,$ in terms of the evaluations of a polynomial over the nonzero elements of a finite field (usually termed Generalized Reed-Solomon formulation): $$ c_f=(f(x_1),f(x_2),\ldots,f(x_n))_{x_i \in \mathbb{F}_q\setminus\{0\}} $$ and if $f$ has degree $k$ then any $k+1$ coordinates are enough to recover the correct polynomial. Then $f(0)$ is used to recover the secret $s$. The polynomial is defined by $f(0)=s,$ and its other coefficients are randomly uniformly chosen.

The point is the collection $$ \{c_f: deg(f)\leq k-1\} $$ is precisely the set of Reed-Solomon codewords for the Reed Solomon code of dimension $k$ and minimum distance $n-k+1$ over $\mathbb{F}_q.$ It's just that one does not transmit the full codeword $c_f$ but use a subcollection $$ \{f(x_1),f(x_2),\ldots,f(x_{k+1})\} $$ as the shares.

$\endgroup$
2
  • $\begingroup$ thank you for your answer, but I think i need to open a new question now... $\endgroup$ Nov 5 '21 at 8:12
  • 1
    $\begingroup$ Yes, that is what actually a good researchers do, rediscover when need, as Peter Shor did $\endgroup$
    – kelalaka
    Nov 5 '21 at 18:42

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.