Score:2

Different secret sharing schemes instead of Shamir's?

ua flag

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?

Score:3
sa flag

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.

Hunger Learn avatar
ua flag
thank you for your answer, but I think i need to open a new question now...
kelalaka avatar
in flag
Yes, that is what actually a good researchers do, rediscover when need, as [Peter Shor did](https://cstheory.stackexchange.com/a/25513/50778)
Score:3
ng flag

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.

Hunger Learn avatar
ua flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.