Menu
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.
908
The Split algorithm is an essential building block of route-first cluster-second heuristics and modern genetic algorithms for vehicle routing problems. The algorithm is used to partition a solution, represented as a giant tour without occurrences of the depot, into separate routes with minimum cost.
Alice and Bob use a key exchange algorithm such as Diffie-Hellman-Merkle, to securely agree on an ephemeral (short lived) session key. They use the keys from step 1 only to authenticate one another during this process.
If the key is the only secret, keys can be changed cheaply and easily, which makes key-based schemes much more attractive. Ultimately, modern cryptography is based on Kerckhoffs's principle which states that: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
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.
101
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.
36
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
2
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/
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
