Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yes, it's very different: if you split some error coded thing across several files, each individual file is going to give you some chunk of the data. It's not secret in any way, it's just that you've only got, like, 1/7th of it.

With Shamir's secret sharing, having anything less than the required number of files is useless, you can't decrypt any of the data unless you reach the required number.



I wouldn't say it's "very" different as long as you make the code non-systematic. In a systematic code the first n blocks are the input data, but there's no reason you need to have it this way.

Even the par2 format will let you do what you want here. Just toss out the original input data and give people 1/k the correct amount of parity blocks. Given a large enough file size [1], there is a vanishing probability that you can recover additional bits of the input with fewer blocks than needed. This also allows you to transmit less bits total (each target gets 1/k as many bits).

Of course, if you don't like this argument, you can always just encrypt the par2 blocks and use Shamir to share the key. This reduces the overhead to a multiple of the (hopefully much-shorter) key. EDIT: Commentary further down the thread indicates that a better idea is just to use an all-or-nothing transform.

[1] We have information theoretical security in the sense than you can't recover n bytes from (k-1)n/k bytes, so what I'm saying is that we need large enough n/k.


hmm, googling around after my Q found this

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80....

where the authors explicitly write: "Shamir's scheme for sharing secrets is closely related to Reed-Solomon coding schemes."

now, my eyes glaze over when it comes to the math, so I'll need to look it through a few times before I understand what they are saying.


You could also look at http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf

You can combine the reconstruction properties of Reed Solomon (you need k of n pieces) with the All or Nothing Transform. Encrypting data so that you need all of the data to decrypt.

Then you can essentially do Shamir secret sharing witout storage overhead. A 1 MB file split so you need 5 pieces would have 200 KB pieces instead of 1mb pieces. This is at a cost of exchanging information theoretic security for computational security.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: