Encryption that could have multiple decryption key

Question

The title looks strange but it is to deal with this situation.

The data we have should only be accessible by our end user and data administrators, not anyone else. Ideally, each user should have different encryption key.

Even with administrators, I wish only when two of them agrees, then they could access the data by join two pieces of the key. I could think of doing this by breaking up the key into two half, and each one of them holds half the key.

Is there such a cryptography can achieve this? So the file could be decrypted by more than one key. Or any other recommendations?

Answer 1

What you ask is very well possible.

Let's assume you have a document DATA you want to encrypt. You first randomly generate a symmetric key K and authenticate and encrypt DATA using this one.

In the next step you asymmetrically encrypt K with the end user's public key and store the resulting cipher text along with the encrypted data.
For allowing your administrators to access the file only when at least two collaborate you have two options:

1. Secretely share a private key among the administrators using a threshold of $k=2$ and encrypt K using the corresponding public key. The drawback of this one is, that the admins actually learn the private key and nothing can stop them from decrypting all files without per-file collaboration of two admins.
2. Give each administrator a private key and secretely share a symmetric key (with a threshold $k=2$) that can recover K (on a per-file basis). Encrypt the shares using the admins' keys and store them with the encrypted DATA and when they need to access a file, they first have to recover the symmetric key using secret sharing and then they recover K. The advantage here is that for each file two administrators have to collaborate but the drawback is that you now need to store $n$ ($n$ being the number of admins) asymmetrically encrypted cipher texts instead of $1$.