Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Shamir’s Secret Sharing Scheme

ericrafaloff.com

Post reply on HN
Print view View original

31–40 of 46 posts

Re: Shamir’s Secret Sharing Scheme

#31

Post by black_puppydog »

alliecat wrote: post #23
nanomonkey wrote: post #22

Dark Crystal[ https://darkcrystal.pw ] is perhaps my favorite implementation of this. It's built on top of Secure Scuttlebutt, and allows you to share private keys with trusted friends, so that you can later rebuild them when they are lost.

The only thing I remember about Secure Scuttlebutt is that it's anything but secure, but I can't for the life of me remember where I read it - can somebody jog my memory?

Might be because it's all written in somewhat hacky and not well-documented JS, making it harder to trust? There's an effort going right now to properly the (grown) protocol and provide reference implementations of the core components in Rust. Obviously, that doesn't make it secure per se, but it should make it much easier to reason about and audit.

Edit: apart from that, nanomonkey is right, if you post something publicly, it will be public. That's to be expected though. And assuming the use of libsodium is done correctly, there shouldn't be much of a problem with the primitives.

Now, the logic implemented on top of the protocol is a whole different story, sort of like most ethereum cautionary tales are not about ethereum being buggy, but people running buggy code on ethereum.

Re: Shamir’s Secret Sharing Scheme

#33

Post by turc1656 »

This math and the key analogy makes me think of the Reed–Solomon error correction algorithm which underlies the parchive sets used to transmit data on systems that are prone to errors in transmission or storage or that don't have any ECC built into the transfer protocols. That's effectively the same result. You are trying to reconstruct the full, original message/file and the checksum for certain pieces show damage so you use the additional data to reconstruct it. The math for the Reed–Solomon is similar in concept to oversampling the points on a line. You only need two points on a line to determine the actual path/slope, etc. so if you take three points, any two will allow you recreate the line.

Re: Shamir’s Secret Sharing Scheme

#34

Post by fusiongyro »

y7 wrote: post #28
pdpi wrote: post #5

Shamir's Secret Sharing is probably my favourite algorithm for showing the deep relationship between algebra and cryptography. The Fundamental Theorem of Algebra is a relatively straightforward result to show to a layperson, and Shamir's is basically as direct an application of it as you could want. Then the part where using integers leaks information, and how to attack that, gets a bit hairier but is still a moderat…

What does Shamir's (or any) secret-sharing scheme have to do with the fundamental theorem of algebra?

The real question is what the fundamental theorem of algebra has to do with algebra.

Re: Shamir’s Secret Sharing Scheme

#36

Post by tialaramex »

philwelch wrote: post #27
alexandernst wrote: post #3

This is very very very old (not the link, but SSSS). I wonder why did it pop in HN today.

It's old, but it's surprisingly not that old. From a cursory glance at Wikipedia, it looks like Shamir's paper was published in 1979, which is stunningly late for a technique that, in principle, could be done with pencil and paper. When I first learned about SSSS, I asked my professor after class why it wasn't invented earlier. He replied that even thinking of trying something like SSSS first requires the insight tha…

"You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century.

His Incompleteness results show that you can essentially write "This statement is false" as a number and blow up the grand project of formalising all of mathematics as a single (edit: typos) infallible, provable monolith.

If that's the key insight you could do SSSS before any actual digital computers were built (those happen very slightly after Kurt Gödel does this work and Turing et al build on it)

Re: Shamir’s Secret Sharing Scheme

#37

Post by [deleted] »

tialaramex wrote: post #36
philwelch wrote: post #27

Earlier quoted context omitted.

It's old, but it's surprisingly not that old. From a cursory glance at Wikipedia, it looks like Shamir's paper was published in 1979, which is stunningly late for a technique that, in principle, could be done with pencil and paper. When I first learned about SSSS, I asked my professor after class why it wasn't invented earlier. He replied that even thinking of trying something like SSSS first requires the insight tha…

"You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century. His Incompleteness results show that you can essentially write "This statement is false" as a number and blow up the grand project of formalising all of mathematics as a single (edit: typos) infallible, provable monolith. If that's the key insight you could do SSSS before any actual digital computers were built (those…

[deleted]

Re: Shamir’s Secret Sharing Scheme

#38

Post by philwelch »

tialaramex wrote: post #36
philwelch wrote: post #27

Earlier quoted context omitted.

It's old, but it's surprisingly not that old. From a cursory glance at Wikipedia, it looks like Shamir's paper was published in 1979, which is stunningly late for a technique that, in principle, could be done with pencil and paper. When I first learned about SSSS, I asked my professor after class why it wasn't invented earlier. He replied that even thinking of trying something like SSSS first requires the insight tha…

"You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century. His Incompleteness results show that you can essentially write "This statement is false" as a number and blow up the grand project of formalising all of mathematics as a single (edit: typos) infallible, provable monolith. If that's the key insight you could do SSSS before any actual digital computers were built (those…

> If that's the key insight you could do SSSS before any actual digital computers were built

The time window between Gödel's incompleteness theorems and the first digital computers seems to be roughly 1931 to 1946 (if you count ENIAC as the first). That very, very closely overlaps with the Second World War--and even the years before the war were treated by many governments as exactly that, years to prepare for war. I suspect that would put a damper on publishing any interesting results in cryptographic techniques, though to be fair, there is also no evidence that anyone secretly, independently invented SSSS during that period or during the 24 years afterward.

Re: Shamir’s Secret Sharing Scheme

#39

Post by pergadad »

This is fascinating but being neither a CS nor Maths graduate I'm having trouble following the maths from the moment modulo operations are introduced.

Would someone be able to suggest a self-learning resource (book, app, ...) that goes into cryptography and the required maths but doesn't demand too much pre-knowledge?

Thanks in advance!

Re: Shamir’s Secret Sharing Scheme

#40

Post by viralpoetry »

atonse wrote: post #14
infamousjoeg wrote: post #10

Earlier quoted context omitted.

Which sucks when it's 2am and you start blowing up a majority of shard holders phones to unseal it because it sealed itself causing a critical outage.

I kid you not, the main reason we haven't implemented vault yet, is not because we're worried about security. It's because we're deathly afraid of locking ourselves out by making a mistake, taking the whole system down. Meaning, this makes Vault more of a "let's really dedicate time to think of every possible scenario" type implementation rather than "let's just keep adding a couple of secrets a week". What has other…

I really do not understand your frustration. We are running 5 node cluster in production with the keepalived and nobody needs to wake up unsealing if one, or two instances fail. Perfectly good to do it in the morning by copy pasting curl oneliner from the keepass.
Post reply on HN