Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I am trying to find information on how to encrypt something in such a way that there are n keys, and k of them are needed for decryption. However, I have been searching Google for half an hour but because I do not know what this is called (and am apparently bad at searching), I cannot find it.

EDIT: preferably such that the keys can be chosen, if this exists under a special name.

share|improve this question
    
please thank the answerer by accepting their answers. it is a nice thing to do. –  user917279 Aug 30 at 13:48

2 Answers 2

To complete @Terry's answer:

Shamir's secret sharing works on values in a given field (the mathematical concept). In practice, if you accept that you won't make more than 255 shares (i.e. 1 < k ≤ n ≤ 255) then it is convenient to work in GF(256), the field with 256 elements. This would mean that you actually do the sharing on each byte independently of the others, and thus that you can "share" any secret which fits in a sequence of bytes (so, really, anything which fits in a computer). And it is quite efficient.

Since each share has the same length as the secret data, you may want to optimize things a bit with encryption. This means that if you want to share a big secret value S (e.g. a 3 gigabytes video), then you:

  • Create a random 128-bit key K.
  • Encrypt S with K and a good symmetric cipher; the encrypted value is stored in a common area where every participant can retrieve it.
  • Applies Shamir's secret sharing on K.

This way, each share holder only has to remember something which is the size of K (16 bytes, easily fits in various places, e.g. a smartcard or even a human brain), while the secret value S can be arbitrarily large and efficiently stored and distributed (since it is encrypted, it can be shown to the public at large, e.g. transferred with a peer-to-peer network).


Now for the choosing the share values, that's an interesting problem. If you have n shares and a threshold of k, the normal description of Shamir's scheme implies that each share is essentially random. The secret splitting outputs the shares, and the share holders can only get them.

The computations can be trivially extended into a scheme where at most k-1 shares are chosen arbitrarily. So some shares must still be random.

User-chosen shares make sense when shares must be remembered, i.e. are passwords. But passwords are subject to brute force. For instance, if an attacker obtained k-1 shares and knows that one of the other shares is a password, then he can run a dictionary attack on that extra share, namely trying out potential passwords (for each password, recomputing the shared secret with that password as extra share, and see if the result "makes sense"). This unfortunately weakens the whole system.

Indeed, a great property of Shamir's scheme is that it is unconditionally secure, meaning that it resists attackers with arbitrary computing power, including computers which have not been invented yet (as long as the source of randomness used in the splitting is really random). This simplifies security analysis, in particular for long-term storage, where you have to predict how much computing power attackers will have decades from now. But if you insert passwords in the mix, this unconditional security vaporizes as dew under the morning Sun.

share|improve this answer

You are probably thinking of the Shamir's Secret Sharing algorithm.

From the wikipedia article,

Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret. Counting on all participants to combine together the secret might be impractical, and therefore sometimes the threshold scheme is used where any k of the parts are sufficient to reconstruct the original secret.

share|improve this answer
    
Secret sharing with threshold scheme is what I was looking for, thanks! –  user31890 Oct 12 '13 at 11:49
    
@user31890 No problem, be sure to click the little arrow on the left side of an answer if you think it's the correct one. –  Terry Chia Oct 12 '13 at 11:51
    
I know :-) But it's telling me to wait a few more minutes –  user31890 Oct 12 '13 at 11:54

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.