Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

Sorry if this question's a bit basic, but I don't know of any way to ask it concisely enough for a search... What I'm looking for is a proven means of doing the following:

Create x number of strings so that any combination of at least y of those x can be used to recreate a message.

For example: if I have "this is my message" (the message), I'd like to split it up in some way where I can give 10 people (x) part of the message, but ensure that the message can be reconstructed accurately as soon as any 7 of those people (y) combine their individual components.

In reality this message would be a public key for encryption, although I don't see how that would really matter. Ideally, both x and y would be as variable as possible (one algorithm/approach which works when x=10 and y=7, as well as when x=50 and y=1, as well as when x=5 and y=5, etc).

share|improve this question
It makes a huge difference what the threat model is. Is it vital that x-1 people not be able to find out anything about the data? Because there are simple, efficient algorithms used for storage (erasure codes) that work only if that's not a requirement. – David Schwartz Jul 24 '12 at 6:50
@DavidSchwartz Thanks, but Shamir's Secret Sharing is exactly 100% what I was looking for in this case. – Dave Jul 24 '12 at 13:58

1 Answer

up vote 3 down vote accepted

What you are looking for is called secret sharing. It is a well studied problem and you should be able to find lots of information now that you know what to search for.

share|improve this answer
2  
In particular, Shamir's secret sharing sounds like a good fit for the OP's task. – Ilmari Karonen Jul 23 '12 at 16:58
In particular, there are several open-source implementations of this algorithm, such as ssss-split and ssss-combine and Life, Death, and Splitting Secrets‌​. – David Cary Jul 24 '12 at 19:12
For implementation, I'd suggest using GF(256) over prime fields. It has no size limitations, works bytewise, need no padding, no multiple precision arithmetic, and is probably faster and easy to program (even I did it:D). It limits the number of shares to 255, which should suffice. – maaartinus Aug 20 '12 at 17:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.