1
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jul 24, 2012 at 6:50
  • $\begingroup$ @DavidSchwartz Thanks, but Shamir's Secret Sharing is exactly 100% what I was looking for in this case. $\endgroup$
    – Dave
    Jul 24, 2012 at 13:58

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ In particular, Shamir's secret sharing sounds like a good fit for the OP's task. $\endgroup$ Jul 23, 2012 at 16:58
  • $\begingroup$ In particular, there are several open-source implementations of this algorithm, such as ssss-split and ssss-combine and Life, Death, and Splitting Secrets. $\endgroup$
    – David Cary
    Jul 24, 2012 at 19:12
  • $\begingroup$ 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. $\endgroup$
    – maaartinus
    Aug 20, 2012 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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