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 rec开发者_StackOverflowonstruct 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.

---

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.

---

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.

---

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

---

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/

---

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.

---

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

---

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