Talk:Secret sharing

From Wikipedia, the free encyclopedia

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.

	To-do list for Secret sharing:	edit  · history  · watch  · refresh
Add illustration for Shamir's scheme (maybe something like [1]) Add illustration for Blakley's scheme (maybe something like [2]) Explain "Why is trivial secret sharing not good enough?" Expand or merge sections to avoid one-paragraph-section syndrome Rework "limitations of secret sharing schemes" section to be more rigorous

Contents 1 too minor, too obscure 2 really good! 3 thanks. what for? 4 what is it that's good? 4.1 narrative arc 5 loons at the launch controls 6 good info, some comments 7 good but.. 8 Comments from peer review

[edit] too minor, too obscure

"Seems too minor for its own article. Completely obscure to the layman." GCW

This 1998 bibliography includes 216 academic papers on the subject. — Matt Crypto 15:43, 13 Dec 2004 (UTC)

It's only obscure to someone who's not interested in cryptography. To anyone -- even a "layman" who wants to understand crypto (like myself), this is obviously a key concept. --Kadin2048 20:47, 20 March 2007 (UTC)

[edit] really good!

Just came across this comment. It's understandably obscure to the layman, for which apologies are perhaps due as a perfect article would make clear all. In the case of this subject, I think that there isn't a chance of being that clear. Not in the real world and with real people writing in real langauges.

The article as it stands is superb. Better than that! It's an example of what I hope the crypto coverage in WP will eventually uniformly be; though I trust the less technical articles will be more understandable to the layman. This is regrettably a sort of 'inside baseball' for the non crypto oriented, but let me hasten to assure them that the technique(s) here is(are) of critical importance in real crypto system design.

Superb work all. Highest congratulations.

ww 19:11, 17 Apr 2004 (UTC)

Note that the article was a little different back at the time of thie above comment; Back then it was: [3] — Matt 19:18, 17 Apr 2004 (UTC)

Matt, I looked, I understand that. But still... This is good work, albeit on an obscure topic. Think how far this is from what might have been expected! ww 19:29, 17 Apr 2004 (UTC)

[edit] thanks. what for?

Gee, thanks. (I just now stumbled across your note on my user page.) There's just one problem: Secret sharing is just naturally intuitive. The math touches several fields and tends to be fairly simple in all of them. Nifty generalizations like "two points make a line; three make a parabola" fit nicely here. Try explaining DES that way. The whole point of DES is that the algorithm is so complicated that nobody can figure out how to work backwards. I could imagine basic mathematical concepts being done like this article. Checksums, for example, would lend themselves perfectly to this sort of handling. It would be farfetched, however, to suggest that we could even hope to "uniformly" write intuitive math articles throughout the cryptography section. I appreciate the compliment, though.

C17GMaster 21:33, 19 Apr 2004 (UTC)

C17..., I'm not sure I can agree with your characterization of 'just naturally intuitive'. Shamir is a very subtle thinker, and this is not wholly intuitive to me despite a professional interest in the explanation of not so clear stuff to users and in particular crypto users. Agreed that it can be understood -- even by me -- but then I didn't think it up, Shamir and Blakely did. But even so, we needn't agree on that; my kudos stand. This is good work.

On the question of DES. That's harder, for the gibberish production method must be such (for a good algorithm) as to resist all known attacks and the ones the Oppostion will think up in future. This last is by definition unknowable, and more proofs of invulnerabilty are sorely needed. That's part of the background for such as DES and is tricky stuff. It's not just being so complicated that working backwards can't be worked out.

This crypto stuff is tricky. ww 14:49, 20 Apr 2004 (UTC)

[edit] what is it that's good?

What is it about secret sharing that appeals to you? I personally thought the "pa------" / "----wo--" example, the "three points make a parabola," and the general discussion of coordinates in space instead of abstract numbers and bits. These concepts are quite intuitive, especially in the context of the discussion. Points, parabolas, and words with missing letters make sense to all of us. Now, maybe "s-boxes" and "Feistel schemes" also have simple underlying concepts that I just don't know, but I honestly doubt that there is a good non-technical way to present DES to non-technical people. The "trick" to secret sharing was applying simple linear algebra tricks in a finite field. (The article doesn't make it sound that way, but I spent longer figuring out finite fields than I did learning all of the other details combined.) I don't think DES has a "trick" like that. The same goes for many other cryptographic algorithms. If it isn't just a new way of doing old math, it isn't going to be easy to explain.

I reiterate my original question because it might provide some insight as to what I'm missing. What exactly do you like about the secret sharing article? Is it the broad scope? The references to points, lines, and parabolas? Is it anything that lends itself to other cryptography-related articles?

C17GMaster 21:03 (?), 20 Apr 2004 (UTC)

[edit] narrative arc

C17..., I've not watchlisted this page and so have just noticed your request. Sorry to have taken so long.

The specific reason I think this is so good is the narrative arc it has -- your doing if I read the page history correctly.

There is a definition (with some terminological notes), a brief comment on the easiest (intuitive) but wrong meaning and why it's wrong, (having motivated the reader to find out the right way) a brief account of crypto secret sharing, some variations, and finally uses and applications. The only thing missing, to my mind, is a little levity and Schneier's example of loons at the launch controls is the best I know of. I'll add it if you like. The reader's likely thinking is anticipated, dealt with, satisfied, and the end result is a well informed reader on a somewhat obscure topic. It's not too long (easy to get wrong), it's not too technical (easy to do in crypto), the end result is an informed reader (not too pissed off by being led down one or another garden path), ... This is good writing.

Your comments in re linear algebra in a finite field being intuitive are, I think, a little more than the average reader will find. In any case, whether the reader follows all that or not, he's acquired a sense of what it is (and isn't --- often more important anyway), and may not want to follow the details of the real thing. I will say again that the structure is the elegant bit here, not the details of explication -- mostly. The example under what it's not is so easy to follow (and so tempting) that the details there are significant. But just including the ground is not common, and in this case was helpful. The figure is what most (readers and writers) concentrate on, and doing so can easily make things less easily followed.

Now, that said, I can find nits to gripe about, but that wouldn't be fair. This does something that is hard to do, and does it well. Nits about sentence structure and punctuation and other miss Fidditchie things aren't on that level.

Does this get the idea across?

ww 16:48, 24 Apr 2004 (UTC)

Ah, I understand what you mean when you say "narrative arc." I can accept this as one of the article's key strengths. The style would work easily for broad concepts like "public key-cryptography" or "confusion and diffusion," but I still believe it would be difficult for more specific articles like (my classic example) DES. Still, the "narrative arc" is more applicable than what I thought you were talking about -- the "two points make a line" analogy and its relatives. I agree that it would be nice and feasible to do certain other cryptographical articles in this manner.

I'm ashamed to admit it, but I'm not familiar with most of Schneier's illustrations. I've glanced at his "Crypto-gram" paper every now and then (usually when Slashdot links to it), but I've never read anything about loons and launch controls. If you feel the story is relevant, then by all means, add it.

C17GMaster 16:31, 25 Apr 2004 (UTC)

[edit] loons at the launch controls

C17G..., 'would work easily', 'nice and feasible to do'... Were it only so! Or maybe it's easy for you. It certainly isn't for me since covering the material often interferes with narrative arc type concerns, and getting some sort of narrative arc often slights understanding of the material. It's a tightrope covered with bananna peels. I've tried, in many a crypto article and elsewhere, and found that WP is a particularly difficult place to write as all are 'hostage' to all. Those whose perspective doesn't include such things (or who otherwise values them) can -- and do -- toss in large hand grenade editing. Oh well, ...

The Schneier example is from Applied Crypto (I think both eds, but can't remember). You have a problem. You don't want a single person to launch the ICBMs and incinerate the world. He/she might be a lunatic, after all. Secret sharing allows you to arrange that more than one person must cooperate before launch. You want to be sure that two have to agree before doing so. In fact, secret sharing allows you to ensure that only if three lunatics agree can they launch the ICBMs and incinerate the world.

It's a strenuous sort of humor not universally appreciated, though I find it hilarious (I like WC Fields too), and I expect there may be some objection on POV grounds or non-encyclopedic grounds. What do you think? ww 16:27, 27 Apr 2004 (UTC)

Ah, I've heard examples like that. Should we add it? Probably not. It doesn't add much that the Coca-Cola example doesn't, but as you say it might offend people of certain tastes. On the other hand, the loons story emphasizes the fact that the dealer doesn't trust certain people, while the Coca-Cola story seems to emphasize that the speaker doesn't trust a paper in a safe. Maybe it would be easier to change the Coca-Cola story, but I don't really care. If anyone has a problem with the loon story, he can edit it. I'm not especially defensive, even about the parts of the article I did write. (If you do anything, move the Coca-Cola/loons-at-the-launch-controls story one paragraph up. Either of those stories belongs before the paragraph starting "The players don't have to be different people." I'm too lazy to do it myself; talking is more interesting than doing.)

As for the difficulty of writing to a narrative arc... Your problem might be that you actually understand this stuff. Here's my story: About five years ago, I stumbled across an article about secret sharing, but for some reason I thought it was "Holographic storage." Of course, the concept isn't called holographic storage, so I couldn't find information on it until this February (I believe) when I saw it again in a Scientific American puzzler. I spent the next month learning enough about finite fields and linear algebra to write a simple C program that could process single bytes. I also researched everything else I could think of that had "secret sharing" in the title. I had been disappointed that the Wikipedia only had a stub and also wanted to make sure I could store my information in some place that was safer than my volatile hard drive. To make a long story short, I wrote this article after a little over a month of research, when everything was still fresh on my mind. I remembered the order in which I had to learn everything (the narrative arc) and the intuitive explanations behind the math (three points make a parabola). I also had the advantage of starting with a blank slate -- nobody cares what you do to a stub.

If you don't think you could do something like this with public-key cryptography, you've probably just been around too long. Secret sharing was my first (and only) significant article on the Wikipedia. You have far more experience with this than I do. If you want to do an article with a narrative arc, sit down and try to figure out the math behind the concept. The math is your best bet because you're less likely to remember the details about it. Read every article on the Internet about the public-key algorithms. Try to figure out what the mathematics behind the algorithms have in common, and decide why those patterns seem to be common. Write an article based on your findings, but refer to the actual math as little as possible. Then, think of nifty tricks people add to it (say, "hybrid" systems, like encoding a DES key with RSA) and tack those to the end of the article. I really do suspect that your problem is that the concepts behind all things crypto are so embedded in your thinking that you don't see any of them as "more" or "less fundamental." I'm sure that if I tried to write the secret sharing article today, it wouldn't be as good. Just try to refresh yourself with a bunch of other articles from everywhere, first. It's a slow process, but you can probably refresh yourself more quickly than you can learn it for the first time.

I'm not sure what to do about stubs. I have practically no experience on the Wikipedia. (I spent the last month and a half reading instead of writing.) I don't know how defensive people are about their articles. Walking in and changing Public-key cryptography might offend half a dozen people... Your experience here is probably enough to get around that, I suppose.

C17GMaster Something o'clock, 28 Apr 2004 (UTC) (4:55pm EDT)

C17G..., Interesting how you got to writing this article. All I can suggest with regard to your sense of being 'new' is, do it again! Being around WP a long time isn't sufficient to escape attention from the more primitive / more absolutist amongst us. Some people are defensive about their work, some aren't, it's part of the, ahmmm, 'fun'. The problem, it seems to me, is 'tude. Some folks are convinced that their take on xyz is the ONLY take, and behave accordingly. Others just think it's funny to trash content -- grossly or a little more subtly. I wish most members of both classes great fortune in their quest for a Darwin Award.

I'd love to include loons at the launch controls in the article, but haven't quite figured out how to do it with reduced risk of deletion.

Your idea about how I might go about writing articles here in crypto land is a bit skew to my purpose in contributing to WP (nearly all of which has been on crypto -- one way or another). You're correct in that I seem to be more of a cryptiac than you, but I'm not contributing to advance or even describe the state of the art therein. I'm trying to increase comprehension in the generic reader of an odd corner of human endeavor, one in which ordinary reasoning and tendencies aren't applicable in peculiar and sruprising ways. And one which is increasingly important in any of many political contexts. (See digital rights management for an example).

I find writing about it too often tricky because one cannot be complete (it's a technical field w/ many interconnections, after all) and yet less than complete accounts of <whatever> get sniped at for incompleteness (!), for POV, and for including unnecessary stuff, most of which (if it weren't merely a brain vacation) was deliberatly constructed to induce in the reader a particular perspective or sense of things. Hints and humor draw similar fire. This many objectives end up tripping all over each others' feet, fins, and feathers and leave me annoyed that I'm unable to reach all goals.

Crypto engineering has been stalled for some time as I dither about how quite to address things, for example.

I'll keep plugging away, but I don't have much sense of real accomplishment so far. Improvements certainly, but more incremental than I'd like, and there's a good bit of 3 steps up and 2 back. Still worth doing though.

Keep contributing, please. Especially for crypto stuff, but anywhere will be fine.

ww 17:11, 29 Apr 2004 (UTC)

So be it; I'll start contributing again when finals are over. I'll be sure to keep an eye out for POV issues should I write on anything controversial. I really can't think of anything else to say in this discussion thread, though, and even if I could I wouldn't have time to say it for another week. This was a profitable discussion, though, and it will be foremost in my mind when I next draft something for the Wikipedia. (Oh, sorry for taking so long to say even this much...)

C17GMaster ??:??, 2 May 2004 (UTC)

[edit] good info, some comments

What secret sharing is not -> this current example convolutes the issues of 1.being able to guess the rest of the secret from available information, i.e. getting pass--rd, one could easily guess password and 2.information theoretically secure.

also, the example assumes that the set of possible values are limited to the size of the english alphabet; what if your possible set of values is infinite? wouldn't the level of security be the same then as this scheme using a finite field (which assumes an infinite set of numbers)?

vss -> why would the dealer want to lie/i.e. why would participants want to check if the dealer is lying?--Confuzion 05:32, 7 Aug 2004 (UTC)

What secret sharing is not -> I think you're missing the actual issue. The idea isn't that you can look at pass--rd and think, "Hey, I know what it is!" The idea is that you only have to check passaard through passzzrd to get the solution, rather than aaaaaaaa through zzzzzzzz. I don't think the paragraph, as it stands now, is especially confusing. If you think you have a better idea, go ahead and try it.

More often than not, we're dealing with computers. If your possible set of values is infinite (i.e. the field characteristic is zero), you'll need to do a lot of creative memory-management to get your program to handle it. As for the level of security... Technically, you could improve the security on anything by allowing infinitely large input values. If computers let you use arbitrarily long passwords, you could be more secure than you are now because instead of searching from 00000000 to zzzzzzzz (assuming that only alphanumeric characters are allowed), an attacker would have to search every string of every length, from the one-character 0 to a string of twenty z's and beyond. The problem would go from recursive to recursively enumerable. So in theory, the level of security could rise, but it isn't an issue unique to secret sharing. I am convinced that finite fields are the way to go, and it looks like Shamir agrees with me.

Why would the dealer lie? Suppose someone named Alice owed me money and I wanted her to suffer. I could distribute a secret among a group of people and give Alice a defective share. When the people try to reconstruct the secret and get gibberish, they know that somebody lied. If they can find a few extra people with good shares, they can try various combinations of shares until they realize that they get the same, non-gibberish secret each time they leave Alice's share out. They conclude that she lied to them so she could have access to their shares (and find the secret herself without anybody else's knowing). Alice is tarred and feathered, and the dealer gets away scot-free. I'm open to adding this trick to the main text of the article, if you think it's relevant.

C17GMaster 17:53, 7 Aug 2004 (UTC)

[edit] good but..

Good article, easy readable to me, but I am also pretty much into crypto stuff. Some comments:

"The dealer gives a secret to the players, but only when specific conditions are fulfilled." This is rather unprecise. In literature, we call it that only a "qualified subset of players" can reconstruct a sharing. This is one of my main critism at the article: It only focuses on threshold shemes, which means that a subset of players is qualified if it has size at least t. However, the principle of secret sharing allows more general structures (see my reference).

"Such schemes cannot be computed conventionally; the players must collectively add and multiply numbers without any individual's knowing what exactly is being added and multiplied. Tal Rabin and Michael Ben-Or devised a multiparty computing (MPC) system that allows players to detect dishonesty on the part of the dealer or on part of up to one third of the threshold number of players, ..." This is very inprecise. What means "conventionally"? It sounds like general MPC is needed to get a VSS. It is the other way round: VSS is a neccessary building block for MPC and nothing unconvential happens during the VSS, it is even possible to use the simple Shamir secret sharing and do error correction during reconstruction. (However, if the dealer can be corrupted too, it must be verified that the ditributed shares lie on a degree-t polynomial.)

Side note: (information theoretical secure) VSS and MPC are also possible for t<n/2 if there is additional a broadcast channel available. Of course a seperate article on MPC would be nice.

Reference: Secure Multi-Party Computation Made Simple

Sounds like you have some good contributions to make. Be Bold in making them! Lunkwill 23:59, 12 Feb 2005 (UTC)

Same thing User:Lunkwill just said — thanks (of course) for reviewing the article, and if you've got the time to fix some of the issues you've identified, it would be most welcome. — Matt Crypto 00:09, 13 Feb 2005 (UTC)

[edit] Comments from peer review

Well it doesn't seem to make sense to comment on all 73 articles on the peer review page, so I will comment here. Good article. A few points: 1) The lead should tell why this is important. Just summarize a bit from 'uses and applications' as simply worded as possible. 2) There should ideally be no one or two sentence paragraphs in the article. They are spots that either need to be expanded to stand on their own or merged with similar material. 3) Why is trivial secret sharing not good enough? Seems fine to me from what the description says. 4) Is the verifiable secret sharing the same thing as Byzantine fault tolerance or just similar? In either case it could stand to be compared there. 5) The limitations section second part says random bits are required. However it doesn't prove that very well since the sentence "This information cannot be the secret, so it must be random." seems to be a non sequitur. The information could be arbitrary and not be secret either I would think. 6) I corrected a fact in the uses and applications section. Please make verify my fix. - Taxman 21:36, Mar 2, 2005 (UTC)

Thanks for looking this one over! Re: 1) Agreed. It would also be nice to add some examples, not just of what secret sharing could be used for, but some prominent examples of what it is used for...that is, have any of these ideas been implemented in actual systems? 2) Yes. I think they can be expanded, except "Trivial secret sharing", which might be better merged into another section. 3) I think the problem is that it requires all n out of n shares. Such schemes aren't very robust in practice: if one shareholder gets run over by a bus, the secret is lost. Being able to specify t out of n is a nice property that makes these schemes more attractive in practice -- I'll add this. 4) Similar, I guess: I think the relationship is that "Verifiable Secret Sharing" is secret sharing with Byzantine fault tolerance; there can be other applications which need Byzantine fault tolerance, such as decision-making. 5) I don't think it's worded very clearly at all. I'll try and do some reading on this and see if I can put it more precisely. 6) Looks good. — Matt Crypto 17:39, 3 Mar 2005 (UTC)

I share a lot of the opinions expressed above on the difficulties of explaining cryptography, or any complicated issue, intuitively to non-specialists. In my opinion the wikipedia should provide information for both kind of readers. Now I will come to my point: The example with the coca cola formula, is an example of an access structure. More generally one could think of a scheme, where different numbers of top, middle or lower management personel are required to reconstruct the secret, or one from middle and two from lower management. The access structure would then be the set of all those subsets of managers who can together reconstruct the secret. What I would like to do is write a WP article about access structures, and possible link to it from the secret sharing article, possibly mentioning that threshold secret sharing is in fact only a special case of general secret sharing. I don't want to spoil the sharing article however, as I think that technical information on the wikipedia is fine (it won't be too technical anyway), as long as it doesn't go on the costs of the general public audience.