9

I want to encrypt data, but make sure that no single user can decrypt the data.

Further, it is important not to require ALL users to be present to decrypt. This will allow for some flexibility and reduce the consequences if/when secrets are lost. It should be enough that 2 out of 3 secrets are provided, or a configurable fraction with a larger number of users.

Does this kind of security scheme exist and have a name? If so, how is it typically implemented?

3 Answers 3

11

It is called threshold encryption (or, here, decryption).

A well-known scheme is Shamir's Secret Sharing. It allows splitting a secret value into n shares, such that any t shares are sufficient to rebuild the secret. n and t can be chosen at will (although you will want to have n greater than t in practice). For the threshold encryption problem, you apply Shamir's scheme on the decryption key. When t share holders meet, they can rebuild the decryption key, and then decrypt the data.

Though Shamir's scheme is fine (in fact, it is provably secure even against attackers with infinite computational abilities -- very few cryptographic algorithms can claim to be similarly secure), it has a limitation which is the following: it rebuilds a secret. This makes it somehow "one shot": if the share holders rebuild the secret, then they have the secret. Each of them will be able to do further decryptions alone by simply remembering the rebuilt secret.

Depending on your context, this may or may not be a problem. For instance, there are voting systems using homomorphic encryption (e.g. with ElGamal), where the encrypted votes are tallied together without decrypting them (that's the point of homomorphism); but the final count must still be decrypted. We want threshold decryption here: several authorities must collaborate with each other to do the decryption. That way, the authorities keep each other in check. However, if they learn the private key itself in the process, then each authority will thereafter be able to decrypt individual votes, which defeats the whole purpose.

If this issues apply to your context, then you must do more mathematics. There are threshold decryption schemes which allow, for instance, a threshold ElGamal decryption, such that t share holder must talk to each other for each decryption instance, exchanging "partially decrypted messages". The private key is never really rebuilt, but its action (the decryption) is gradually reproduced.

There is a lot of theory on threshold cryptosystems, with various characteristics (how many shares, what possible threshold values, does the scheme resist well when some share holder actively cheat, how many messages must be exchanged, and so on). If your problem at hand can be solved with Shamir's scheme, then, by all means, go for it. It is reasonably simple to implement (in particular, sharing files is easy if you do all computations in GF(28)).

5
  • Excellent answer! I accepted Seths answer as he was first with a good answer for what I asked. However, the weakness you describe (that the secret is ultimately exposed) was very useful knowledge. I will probably look into ElGamal first if I can find a good Java implementation. Jan 30, 2014 at 21:24
  • 1
    @KarlIvarDahl Much as I appreciate having an answer accepted, I'd encourage you to accept what you feel is the best answer, rather than the first sufficiently okay answer. Everyone benefits more in the long run if the game rewards quality rather than speed (for example, people may reach this question from Google in the future and only bother reading the accepted answer).
    – Seth
    Jan 30, 2014 at 21:49
  • @Seth You are of course correct. Thank you both for your help, it is really inspiring. Jan 30, 2014 at 22:31
  • @Thomas I have looked into an ElGamal threshold implementation (code.google.com/p/tau-ev-workshop) and it looks like there is a limit to the message size. With a small message I can probably encrypt a key that in turn is used to encrypt the whole message. But does this not mean that the "secret" is exposed in a similar way as Shamir´s? I have also looked into a Paillier Threshold implementation (utdallas.edu/~mxk093120/paillier) with a similar limitation. Is this a limitation of this kind of encryption? How could threshold ElGamal or Paillier be applied to large messages? Feb 3, 2014 at 18:31
  • Threshold cryptography relies on heavy mathematics and objects with a lot of structure, which in turn implies strict size limitations. Using an intermediate secret key and symmetric encryption is "safe" if you take care to always generate a new private key for each message. Feb 3, 2014 at 18:47
5

What you're after is Shamir Secret Sharing. The goal is that given a group of k users, any n of them working together can decrypt the data. On the other hand a group of fewer than n users shouldn't be able to learn any information about the decryption key.

The general idea of how this works uses some geometry. Suppose we want any two users to be able to decrypt. Imagine the standard 2-D plane with a horizontal and vertical axis. To set up the system, you choose a random point on the vertical axis between 0 and, say 2^128; this corresponds to a 128-bit key.

Next, you choose a random line on the plane that intersects that point. You tell each of your users the coordinates of a point on that line (each user learns a different point). Any two users can combine their points to figure out what line you chose --- literally by connecting the dots --- and from there figure out what the key is.

If you want more than two users to need to work together, you choose a higher-order polynomial (like a parabola, for three users) instead of a line.

There's one technical point I'm glossing over here, namely that instead of using standard multiplication and addition, you define these operations in a special way. (Mathematically speaking, you work in a finite field). Informally, the reason for this is so that you can assign users points from a well-defined range (with both x- and y-coordinates between 0 and 2^128 - 1, for example) while still preventing them from eliminating possible key values (unless they work together with the specified number of people).

1
  • This is what I was looking for. Bonus points for actually explaining it in a way I could understand :) Jan 30, 2014 at 21:13
0

I'm sure there is a formal name for this, but it escapes me. One solution would be to generate a 256bit key which 64 hex characters.

Give Alice key characters 1-22 and 22-43. Give Bob key characters 22-43 and 43-64. Give Carol key characters 1-22 and 43-64.

This way any two can perform the decryption, but no one has the full key.

The problem here is that there is only about 22 characters/85 bits of missing data for either Alice, Bob or Carol to brute force. Maybe if you encrypt with something like http://en.wikipedia.org/wiki/Blowfish_(cipher) which has up to a 448 bit key, that would solve that problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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