4 ms·

what is the difference between reed solomon erasure codes and shamir secret sharing? i.e. if I just split the secret into a number of reed solomon error correc

what is the difference between reed solomon erasure codes and shamir secret sharing? i.e. if I just split the secret into a number of reed solomon error correcting blocks (where n blocks are sufficient to recover the full data), is that fundamentally different?

ScottEvtuch 6y ago
Presumably the secret sharing algorithm is more resistant to brute forcing if you have one less than the required pieces. They solve opposite problems
- myself248 6y ago
  Could you make one equivalent to the other, by R-S encoding a key? And if you have less than the whole key (assuming it's large enough that the missing portion is still bruteforce-resistant), then even a partial reconstruction of the key still gives you none of the data.
  - lowercase1 6y ago
    Yes you can! Apply an All or Nothing Transform before RS encoding so that you need all of the original data to decrypt. Then you can only decrypt if you have k of n pieces. You save by a factor of k in piece size over SSS. http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf
OskarS 6y ago
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.
- compsciphd 6y ago
  hmm, googling around after my Q found this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.2829&rep=rep1&type=pdf 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.
  - lowercase1 6y ago
    You could also look at http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf 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.
- deleted 6y ago
  [deleted]
- pxx 6y ago
  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.

ScottEvtuch 6y ago

Presumably the secret sharing algorithm is more resistant to brute forcing if you have one less than the required pieces. They solve opposite problems

myself248 6y ago
Could you make one equivalent to the other, by R-S encoding a key? And if you have less than the whole key (assuming it's large enough that the missing portion is still bruteforce-resistant), then even a partial reconstruction of the key still gives you none of the data.
- lowercase1 6y ago
  Yes you can! Apply an All or Nothing Transform before RS encoding so that you need all of the original data to decrypt. Then you can only decrypt if you have k of n pieces. You save by a factor of k in piece size over SSS. http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf

OskarS 6y ago

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.

compsciphd 6y ago
hmm, googling around after my Q found this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.2829&rep=rep1&type=pdf 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.
- lowercase1 6y ago
  You could also look at http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf 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.
deleted 6y ago
[deleted]
pxx 6y ago
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.