Is there an algorithm to securely split a message into x parts requiring at least y parts to reassemble?

views:

195

answers:

+10 Q:

Is there an algorithm to securely split a message into x parts requiring at least y parts to reassemble?

Is there an algorithm to securely split a message into x parts requiring at least y parts to reassemble? Obviously, y <= x.

An example:

Say that I have a secret message that I only want to be read in the event of my death. As a way to ensure this, I give a fraction of the message to ten friends. Now, I can't guaranty that all my friends will be able to put their messages together to recover the original. So, I construct each message fraction in such a way so as to only require any 5 friends to put their parts together to reconstruct the whole. However, owning less than 5 parts will not give anything away about the message, except possibly the length.

My question is, is this possible? What algorithms might I look at to accomplish this?

Clarification edit: The important part of this is the cryptographic strength. An attacker should not be able to recover the message, either in whole or in part with less than y parts.

Sounds like RAID 5, which is x disks requiring y<x to reassemble a partition. The Reed-Solomon error correction algorithm is one implementation of this type of fault tolerance.

Josh McFadden 2010-03-07 04:00:52

Do you know if this is strong cryptographically? I.E. if a person has less then y parts, is information leaked about the original message, or is it otherwise plausible to recover the original message, either in whole or in part?

Aaron 2010-03-07 04:09:41

Ya know... this came to mind when I read the question... but I really don't think this has anything to do with cryptography... I don't know the details though so I can't really say... but AFAIK, this has to do with redundancy and protecting against data loss... so keeping the data secret isn't a goal...

Tom 2010-03-07 04:15:18

Oh. Yeah, I don't thiiiink it's that strong cryptographically but perhaps you could 1) encrypt the payload using a large key 2) split the payload and key separately into *x* parts 3) give everyone one part of each. If the key is large enough that any one fraction of it would be sufficient to reassure you cryptographically then I think you're good to go. Take a crypto nerd to know for sure.

Josh McFadden 2010-03-07 04:30:07

Looking at Mitch's answer, he's totally right that once you're encrypting you have no reason to split up the encrypted payload. Whoops. Just split the key. But you'd still need an error-correction-like algorithm to split the key for the *x* < *y* requirement.

Josh McFadden 2010-03-07 04:51:54

Yes, this is possible. It is called Forward error correction. See http://en.wikipedia.org/wiki/Forward_error_correction

Larry K 2010-03-07 04:02:12

Can you be a bit more specific. In principle reusing Error Correction algorithms seems like a good idea, but the difficulty may be to select the right algorithm, i.e. : one that tolerates a mighty noisy channel (P(error) = 50%) and yet one which guaranties that _no fewer_ than 5 parts be _necessary_ to rebuild the original message (and of course that such 5 parts be also sufficient). AFAIK (which is not much ;-) ), the emphasis in telco and information theory is on the _sufficient_ not so much the _necessary_.

mjv 2010-03-07 04:12:22

+3 A:

Check http://parchive.sourceforge.net/. There is a specification and software based in Reed-Solomon Code to split an archive in x parts and create y parity files.

For example. You split one 5mb archive in five 1mb "data" files and create another five 1mb "parity" files. You can recover your original file using any combination of data and parity files, for example 1 data file and 4 parity files, or 5 parity files.

Maybe you can apply this.

EDIT: The application would be to split your archive into X parts and create (X-Y) parity files, then give one part and all the parity files to each recipient. Then any Y of them could put their parts together, plus the parity files that they all share, to produce the desired output.

Carlos Gutiérrez 2010-03-07 04:56:15

Example Reed Solomon FEC code, from Luigi Rizzo and updated by the UDPcast team, from bytes to gigabytes,

http://koders.com/c/fidD435475ABA35C752BC554D7D3E04208B2896D06C.aspx?s=fec#L3

Smaller scale, counting in bits, from tape to audio controllers,

http://koders.com/cpp/fidF6CF3C208FBFE2EF0DAAD9CBFEC777068A81595D.aspx

Steve-o 2010-03-07 05:09:23

+15 A:

Shamir Secret Sharing and Blakley's scheme are two well-established, provably secure means of sharing a secret so that it can be recovered only when a pre-determined number of "shares" are combined.

erickson 2010-03-07 05:11:53

Are they practical algorithms?

Mitch Wheat 2010-03-07 05:17:08

Yes, they are fairly widely used for exactly the sort of application the poster describes. There are some open source implementations available (in C, as far as I found) and an even an online demonstration at http://point-at-infinity.org/ssss/demo.html

erickson 2010-03-07 05:20:08

+1. BTW, That's an excellent demo.

Mitch Wheat 2010-03-07 05:22:52

Perfect! This is exactly what I was looking for! Thank you!

Aaron 2010-03-07 05:23:45

+1. Shamir's scheme is really clever - it wouldn't hurt to include a short description in the answer. As crypto schemes go, it's remarkably straightforward and understandable for anyone who knows a little linear algebra.

Nick Johnson 2010-03-07 11:06:43

+1 A:

What you are looking for is the "Information Dispersal Algorithm" by Rabin. There is a good explanation and example code here: http://bryanmills.net/archives/2007/09/information-dispersal-algorithms/

uk 2010-03-07 05:26:18

I feel that, instead of splitting message into x parts, you can actually encrypt the message and split the key among y people.

Similar problem in real world will be the Voting. El gamal encryption is used with re-randomization to solve this problem.

-- Bala

Algorist 2010-03-07 06:01:48

ansaurus

tags:

views:

answers:

Is there an algorithm to securely split a message into x parts requiring at least y parts to reassemble?

related questions