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