Talk:Shamir's secret sharing

Example using arithmetic on finite field

Assume the secret is D=148

Let’s take p=997 (prime), a1=59 (random), a2=340(random) so that g(x)=148 + 59x + 340x2

We compute 5 fragments

D1 = g(1) mod 997= 547

D2 = g(2) mod 997 = 1626 mod 997 = 629

D3 = g(3) mod 997 = 3385 mod 997 = 394

D4 = g(4) mod 997 = 5824 mod 997 = 839

D5 = g(5) mod 997 = 8943 mod 997 = 967

We give to each user a fragment among (1,547), (2,629), (3,394), (4,839), (5,967)

Assume users with fragments 1,3,4 want to reconstruct the secret

They compute q(0)

𝑞(0)=547((−3)/(1−3) (−4)/(1−4))+394((−1)/(3−1) (−4)/(3−4))+839(1/(4−1) 3/(4−3))

𝑞(0)=547∗2−394∗2+839=1145

𝑞(0) 𝑚𝑜𝑑 997=148

Arnaud.legout (talk) 20:05, 28 October 2010 (UTC)

Shouldn't this example be moved out to the main page? It also is a nice example of how to simplify the math by dropping the x variables from the equation. — Preceding unsigned comment added by Jeremiah.jahn (talk • contribs) 13:48, 2 November 2011 (UTC)

Reconstruction phase flawed

There isn't a single computation that is correct in the reconstruction phase!

l0 = 1/6x^2 -3/2x+10/3

l1=-1/2x^2 +7/2x-5

l2=1/3x^2 -2x + 8/3

Moreover, as the goal is to compute f(0), the computation of the li can be simplified by considering x=0.

f(0) = 1942 * 10/3 -3402*5 + 4414*8/3 = 1234

Arnaud.legout (talk) 16:56, 28 October 2010 (UTC)

Indeed the calculations are incorrect, though I see where it has gone wrong:

-3/2 = -(1+1/2)

3/10 = 3+1/3

...

So I guess there's just the +'s missing.

Jpjacobs (talk) 10:51, 2 March 2011 (UTC)

Practical implementation considerations

In the reconstruction phase, aren't there potential issues with approximation errors when interpolating? 128.178.252.14 (talk) 20:12, 5 September 2009 (UTC)

Not when you work in finite fields, as you should in a proper implementation of Shamir's method. 01:51, 30 January 2013 (UTC)

Citations

Citations should be available in the paper that this page is about. There is a link to it under "References". Vulturejoe 23:10, 22 May 2007 (UTC)

I removed the notice about improving references. Most of the material in the article stands for itself and there are good references. While it would be very nice with inline references, I do not think we should keep the ugly template at the head of the article. ❝Sverdrup❞ 23:06, 23 January 2008 (UTC)

Information-theoretic security

Is this how Shamir originally described it, or is it a paraphrase? For example, the method as described appears not to be information theoretic secure. (If polynomial coefficients are restricted to integers, with k = 3, a person who had f(1) and f(2) could determine whether f(0) was even or odd; if they are not restricted to integers, there are possible roundoff errors.) A finite-difference based method seems better; are there any problems with it? Ralphmerridew (talk) 17:14, 19 April 2008 (UTC)

See this blog post and this reply. -- De Guerre (talk) 07:17, 20 April 2008 (UTC)

As some of the comments in the blog post state, this does not reveal a flaw in Shamir's scheme, which specifies that the arithmetic be done in FINITE FIELDS.

So it was a case of the paper being misstated. Good.Ralphmerridew (talk) 10:04, 23 April 2008 (UTC)

It's not that misleading, when you consider that it's only an example to give the idea of the method. The example is correct, it's just that the method isn't information-theoretically secure when you use a field of characteristic zero. -- De Guerre (talk) 12:20, 25 April 2008 (UTC)

Lagrange Operations correct ?

Are the lagrange operations correct ? I mean, 1942 - 3402 * 5 + 4414 * 4/3 doesn't goes into 1234.. —Preceding unsigned comment added by 158.109.1.15 (talk) 14:34, 20 January 2010 (UTC)

• 1942 * 3,(3) - 3402*5 + 4414*2,(6) = 1219... hmm... Vlsergey (talk) 16:44, 18 August 2010 (UTC)
• 1942 * 3,(3) - 3402*5 + 4414*2,(6) = 6473,(3) - 17010 + 11770,(6) = 1234 Y Vlsergey (talk) 16:47, 18 August 2010 (UTC)

Link to erasure code?

It seems to me that Shamir's Secret Sharing is an example of an erasure code, with additional security properties not necessarily shared by other erasure codes. It might be useful to have cross-references back and forth, and ideally also a discussion of how Shamir's algorithm is different (or has additional properties) vs. other erasure codes. Paul Koning (talk) 18:25, 31 August 2011 (UTC)

David McGrew's variant

David McGrew created a version of Shamir's algorithm that has some useful practical benefits: [1]. It might be worth minimally a reference and perhaps some description. The main difference is that it processes the input as a sequence of bytes which are then shared over GF(256) instead of treating the input as a large integer shared over GF(prime). Paul Koning (talk) 18:31, 31 August 2011 (UTC)

What about a section called "Variants and Alternatives" to cover this, and also variants of multisig? Dan Shearer (talk) 06:48, 27 September 2022 (UTC)

Incorrect python code

The code for joining the shares that is written in python is incorrect. It should use mod inverse. — Preceding unsigned comment added by 108.46.120.106 (talk) 00:57, 10 August 2013 (UTC)

Why the $P$ ?

The article defines the size of $F$ as $0<k\leq n<P$, why don't we use $0<k\leq n$ ? The $P$ is used nowhere else in the article and there is always a prime number bigger than $n$ because it's easy to prove that there is no biggest prime number. — Preceding unsigned comment added by 2001:6F8:14DC:2:E892:D2DB:40C:4132 (talk) 18:35, 19 January 2014 (UTC)

"Not a finite field, therefore not SSS"?

The page currently reads, "Note, however, that calculations in the example are done using integer arithmetic rather than using finite field arithmetic. Therefore the example below does not provide perfect secrecy,[clarification needed] and is not a true example of Shamir's scheme."

But isn't integer arithmetic going to produce the same results as finite field arithmetic in a sufficiently large finite field? If so, then should there be some upper bound on $P$, or is the above wrong?

50.204.20.34 (talk) 17:41, 8 April 2014 (UTC)

$a_{i}\in \mathbb {N}$ ?

Does really have to be $a_{i}\in \mathbb {N}$? What about $\mathbb {Z}$? — Preceding unsigned comment added by Fsdoiudofh (talk • contribs) 12:52, 30 August 2014 (UTC)

Error in javascript example

Throughout the page, the example secret is $1234$. However in the sample implementation, the secret $129$ is used instead (even some of the internal comments still reference 1234). While the results appear correct for that value, it's very confusing. The example should either continue to use the secret 1234 (which, if my results are correct, generates points [(1, 209), (2, 143), (3, 8), (4, 61), (5, 45), (6, 217)] but someone smarter than me should confirm) or have the different secret clearly called out and the comments updated. I'm not confident enough in my implementation to make the change myself. — Preceding unsigned comment added by 71.6.63.210 (talk) 21:15, 27 January 2015 (UTC)

I checked your idea and edited the example correspondingly. Lizziemcguire (talk) 17:59, 15 September 2017 (UTC)

Error 2 in javascript example

I tried the javascript example with different settings for "needed". Therefore I enabled the random coefficients line. I observer a rather strange result:

• for split(129,6,2), I need 3 shares to reconstruct (which should not be the case)
• for split(129,6,3), I need 3 shares (ok)
• for split(129,6,4), I need 5 shares (wrong!)
• for split(129,6,5), I need 5 shares (ok)
• for split(129,6,6), I need 7 shares (i.e. 129,7,6 works, 129,6,6 doesn't)

I've looked at the code for half an hour, but i don't see the problem.

So it looks like this only works for odd values of "needed". Lizziemcguire (talk) 17:45, 15 September 2017 (UTC)

Errors in JavaScript example (and new example details)

As seen above, the JavaScript example had some recurring issues. Tracked this down to some issues with the floating point math. I'll be posting an example implementation with the following improvements:

• Prime is of secure length (~128 bit) - JavaScript's built-in integer math limits the current example to 1237, meaning all results of the current implementation will be brute-forceable. Justification for the prime is also provided.
• No math.floor() or possible loss of accuracy
• Shorter - fewer lines of code for increased readability
• Tested. This code is released into the public domain from a working industry implementation of Shamir. This greatly improves security in the event that someone copies and pastes the code into a production use case.

Here's to no more bugs in examples! --MahmoudHashemi (talk) 23:02, 16 December 2017 (UTC)

Security with high $p$

The page claims that setting $p$ "too high" can result in reduced security "because Eve knows that the chance for f(x)\pmod{p}=f(x) increases with a higher p and she can use the procedure from the original problem to guess S (although now, instead of being sure of the 150 possible values, they just have a increased chance of being valid compared to the other natural numbers)". I see no evidence that this is true. The integer attack fails completely, since the parameters $a_{i}$ should be drawn uniformly at random from $\mathbb {Z} _{p}$, and therefore "positive" numbers are just as likely as "negative" numbers. In fact Shamir provides a constructive proof of security in his paper, so I am convinced that this warning is spurious. 118.209.99.238 (talk) 02:17, 28 February 2015 (UTC)

Merge with Secret sharing using the Chinese remainder theorem

The only difference between the two secret sharing schemes is the choice of the underlying ring. Shamir's secret sharing uses a polynomial ring with moduli of degree 1 while the other article uses the integers. Merging the two schemes would simplify the content as well as broaden it. — Preceding unsigned comment added by Jannaston (talk • contribs) 21:15, 5 April 2016 (UTC)

"2 points are sufficient to define a line, 3 points are sufficient to define a parabola"...

" 2 points are sufficient to define a line, 3 points are sufficient to define a parabola"... Really? If by chance it happens that the three points are colinear, then there is no parabola determined by them. I think things need some conditions. — Preceding unsigned comment added by 78.97.133.105 (talk) 06:40, 19 April 2016 (UTC) Three points define a parabola even when colinear. It just happens to be that the coefficient multiplying the square term is zero (every straight line can be interpreted as a higher level polynomial line, but not the other way around). — Preceding unsigned comment added by HomoNomos (talk • contribs) 09:47, 12 February 2018 (UTC)

Links to external projects

With the exception of a research paper, I removed all links in the External Links section as several were dead projects, none appeared to be particularly authoritative, and most appeared to be promotional. A Google search on the topic will turn up currently relevant results. —Waldhorn (talk) 04:55, 26 December 2017 (UTC)

Ambiguous use of order in the scheme

Within the scheme section there is a step which requires the secret S to be less than P but that incorrectly assumes that S is a real number instead of being an element of a finite field F which does not necessarily have an order defined on it. Also P is not necessarily an element of F so even if it did have an order it still doesn't allow the both to be compared. SalimShady (talk) 23:30, 19 August 2019 (UTC)

Suggestions

• In the explanation of solution to the problem, infinite amount of possible values for $a_{1}$ is incorrect, the number of values is still limited to the elements in the finite field. With small enough $p$, standard algorithms like the extended Euclidean algorithm can be used to easily obtain the required result directly.
• More emphasis on what should be private and public, and the level of security should be mentioned. The article seems to overstate the secrecy too much, given current tools available. More emphasis on this being superseded by other schemes (by decades) should be mentioned.
• Relation to Reed-Solomon codes should be emphasised, and generalisations (such as multi-party computation) should be linked.
• More theory on properties should be explained.
• Pseudo-code should be used instead of a particular language like Python.

ZekeTan (talk) 05:17, 26 April 2021 (UTC)

The size of the finite field

The article says

Since everyone who receives a point also has to know the value of p, it may be considered to be publicly known. Therefore, one should select a value for p that is not too low.

Is this correct? It is my understanding that the size of the finite field is only restricted by the size of the message and the number of shares of the secret. --Been-jamming (talk) 20:01, 12 December 2021 (UTC)

SSS flagged as "too technical"

I agree with this template being applied. For example, the article (and this talk page) assumes that the concept of "finite fields" is obvious. That shouldn't be assumed knowledge for SSS, because if someone is wants a conceptual overview of the topic all they need to know is that polynomial interpolation is by default in an infinite field and that this is a vulnerability that needs to be fixed. I'm not sure of the best place to start in simplifying this article, but since it is of "High Important" to the Wikipedia crypto project that does need to be done. Dan Shearer (talk) 15:24, 19 September 2022 (UTC)

I agree that the article could be improved, but I am also not sure where to start. Nuretok (talk) 07:32, 25 September 2022 (UTC)

I have made a start, do please jump in and help!

The introduction is now hopefully much more accessible to readers with no relevant background. There is still a lot more to do. I created a "History" section, and I suspect maybe a new "Variants and Alternatives" section is needed because there are a lot of both.

SSS seems to be quite widely used, but I don't see documented examples here.

The example code seems to be disproportionate at present, in the sense that unless you can make sense of either maths or python or both you don't have much sense of what SSS is and how it works and how it is used. Dan Shearer (talk) 06:52, 27 September 2022 (UTC)

Thank you for starting with the improvement. I have also tried to improve the start of the article a bit.

The long block of code seems out of place in the article, but I am unsure how to handle it. Deleting it seems like a waste. Maybe it is better placed on a source code sharing platform. Nuretok (talk) 13:51, 1 October 2022 (UTC)

There are many other example implementations including others in Python, Rust, PHP and more, and we can link to some of these. I agree with you the code block is not ideal, and that at most some much shorter pseudocode would be better. Let's also find examples of SSS in use.

Dan Shearer (talk) 15:55, 1 October 2022 (UTC)

I agree regarding shorter code. I found some usage examples and added a new section with them. Nuretok (talk) 06:04, 2 October 2022 (UTC)

Great. We're off to a good start. I am looking at the variations of SSS to see if I can find good references. I don't know how the Computer Science project is organised, but perhaps when this article is looking better we should ask for some review since it is marked "High Importance".

Dan Shearer (talk) 07:09, 2 October 2022 (UTC)

Detailed python implementation is original research

On further thought, the python code is not just unhelpful, I think it may be excluded from Wikipedia due to being original research. I was unable to find this exact code anywhere else (which does not mean it doesn't exist, merely that I did not find it.) If correct, that suggests someone wrote it exclusively for Wikipedia. That's a good effort, but I think in this case misguided. I will have a look at who the original author was in the history, but I think this has to go.

... or perhaps not, I later found Category:Articles_with_example_Python_(programming_language)_code . It would be helpful to get review from someone who curates Compsci.

Dan Shearer (talk) 09:30, 3 October 2022 (UTC)

Usage examples

@David Gerard: You removed the following section

Shamir's Secret Sharing is used in:

• Vault password manager by Hashicorp
• Passwordless authentication by Secret Double Octopus
• Key Recovery in PreVeil's email encryption
• Wallet management of cryptocurrencies

with the comments "rm cryptocurrency sites, not RSes on WIkipedia; rm spam magnet" and "No, it's all non-RS nonsense. Find RSes for all of this or it shouldn't be in the encyclopedia at all. [{WP:V]]". WP:V states that "The appropriateness of any source depends on the context", which is more detailed in WP:RSCONTEXT. I understand that the sources for this section vary in quality and none of them are great. However, I don't think they are all useless. Their purpose is not to validate some extraordinary claim, but just to show that Shamir's Secret Sharing is being used by a software or for a given use case. (And only the last of these cases is directly related to cryptocurrencies.) Should we discuss the reliability of the individual sources (for this context) to progress from here or do you have another idea? Nuretok (talk) 18:40, 22 January 2023 (UTC)

References

Find solid RSes and not crypto sites, primary sources, promotional pages or blogs, I would strongly suggest - David Gerard (talk) 23:17, 22 January 2023 (UTC)

I'm not convinced that listing a few specific products that use the technique is useful. It is often undesirable, since it is effectively promotional. Listing some widespread use case types (rather than specific products) is usually sufficient, and if sourcing for that is desired, secondary sources will often exist. —Quondum 23:47, 22 January 2023 (UTC)

@David Gerard: I fully agree that high quality sources are important and to better understand you I have some questions: When you write Crypto what are you referring to? Cryptography or Cryptocurrency? Do you consider Bitcoin Magazine a reliable source (in this case)? Do you consider PCMag a RS (here)? Would the software documentation or a developers blog be a RS for a feature of the software? (While clearly primary sources, WP:PST allows exception)

@Quondum: I understand your point. I only added the names of the companies, because they have Wikipages. I guess the fourth point is already worded as use case and not for specific product. Would you be OK, if we remove the mentions of the specific product from the bullet points 1, 2, and 3? Nuretok (talk) 20:37, 23 January 2023 (UTC)

Cryptocurrency. Bitcoin Magazine is very obviously not an RS - David Gerard (talk) 21:33, 23 January 2023 (UTC)

@David Gerard Would you please share the reason why Bitcoin Magazine is very obviously not an RS? (I read its Wikipedia-page, but could not find any obvious red flags) Nuretok (talk) 17:07, 24 January 2023 (UTC)

All the crypto mags are advocacy outlets. This has long been the consistent consensus at WP:RSN. You could ask again, but I predict you'd get the same answer. They're not good for financial writing nor for technical writing - David Gerard (talk) 17:46, 24 January 2023 (UTC)

Thank you for the link, after going through some discussions I finally found it explicitly stated in Wikipedia:Notability_(cryptocurrencies)#Crypto-centric_news_organizations. Do you consider PCMag a RS for the statement "SSS is used for key recovery on email encryption"? Nuretok (talk) 19:40, 24 January 2023 (UTC)

For inclusion to make any sense, the purpose that a sharing scheme serves in any use-case should be made clear to the reader. For example, in wallet management, it may be used to split a key that is used to access a cryptocurrency wallet, and how this provides protection against certain types of attack should be mentioned. This kind of key-splitting is not specific to this use-case, though, so this use-case in turn would just be one of several examples of key-splitting for local data protection. —Quondum 21:37, 23 January 2023 (UTC)

@Quondum: Sorry, I don't understand. Would you like to add another usage example? (There is already one at the beginning of the article) Nuretok (talk) 17:11, 24 January 2023 (UTC)

The one in the lead has the same problem IMO: it just says that SSS is used for cryptocurrency wallets, which does not help the reader understand what the role of SSS is here. It is unclear whether, for example, the data content of the wallet or the key for accessing the wallet are shared. I don't particularly see the need to give specific instances at all, just as no specific applications are listed in Advanced Encryption Standard.

For clarity, I am just answering some questions and giving opinions because some things seem clear to me and I happened to wander in here. I am not trying to get directly involved with the editing, since my interest is really only the description of its mathematics: I use it as a primitive, but have no interest in where others have applied it. —Quondum 18:34, 24 January 2023 (UTC)

I agree that it would be of more value to the reader if the description of applications would lead to a better understanding. I hope the applications example does that. If not, please feel free to improve it.

The AES article has so many applications that they are part of a dedicated subarticle together with implementations: AES_implementations#Applications.

Thank you for your clarification. I am also mainly interested in SSS, because I like the idea, but at least in my opinion it would also be interesting to read where it is actually used in practice. Nuretok (talk) 19:56, 24 January 2023 (UTC)

To consider your concerns about reliability of sources and advertisement for specific products (I also consider both of them improtant) as well as not to give certain parts undue weight and handle the example in the lead section, I propose to replace the sentence "A standard SSS specification for cryptocurrency wallets has been widely implemented." in the leading section with the following sentence:

Shamir's secret sharing is, for example, used to decrypt the root key of password managers, recover encrypted emails and share cryptocurrency wallets.

References

I am looking forward to constructive criticism. Nuretok (talk) 08:14, 29 January 2023 (UTC)

Your descriptions of the uses are not accurate, and need adjustment. All these use cases are apparently of the same general type: long-term multi-party storage of cryptographic keys to allow recovery in the case of loss, with threshold protection against compromise, as well as robustness against DoS. Thus: The first example is sharing of a key for decrypting the root key, not actually the scheme being used to decrypt anything. Your "recover encrypted emails" is too simplistic, giving the wrong impression, where "recover a user key for encrypted email access" would be more informative and accurate. The third use is sharing of the passphrase used to recreate a master secret, which is in turn used to access a wallet. So again, it is not the wallet that is shared, it is the passphrase used to access it that is shared. (I am appalled at the unnecessary leakage that is built into that last one, but that is not relevant here.) This might sound excessively nit-picky, but in the article body, being so specific would be necessary, and in the lead, it should all rather be summarized as "sharing access keys to a master secret", since that is what these all have in common and frames it adequately for the reader. The lead summary would not need the references; these would belong with the detail such as you have, adjusted, in the body.

Substantiating a claim of the existence of implementation types is less demanding of references than is technical detail, so that is not so much of a concern to me: assess the source for plausibility (and hype, which is only too prevalent in publications for sale or by involved parties). No-one should be directly challenging the veracity of the claims. —Quondum 13:46, 29 January 2023 (UTC)

Ok, thank you for your valid concerns. Here is my next proposal that hopefully covers them all:

Lead: "Shamir's secret sharing is usually used to share access keys to a master secret."

Somewhere in the main text (its own section?):

"Shamir's secret sharing is, for example, used to

• share a key for decrypting the root key of a password manager,
• recover a user key for encrypted email access and
• sharing of the passphrase used to recreate a master secret, which is in turn used to access a cryptocurrency wallet."

Please feel free to post an updated version, if you have further comments. Nuretok (talk) 17:58, 29 January 2023 (UTC)

Close enough: it makes more sense to include this in the article and tweak there than here. I expect the new section would be something along the lines of "Use cases" or the like. —Quondum 21:56, 29 January 2023 (UTC)

OK, I added it to the article. If you don't like where I added the use case section feel free to move it! Nuretok (talk) 19:19, 30 January 2023 (UTC)