1
$\begingroup$

I'm a lowly web dev / programmer of 10 years who's never tried to wrap his brain around the high concept stuff, so apologies is this is a stupid question (or if it belongs in programmers.stackexchange.com)

I started wondering the other day, is it possible to encrypt something and have it decryptable by two different keys?

Suppose you wanted to have a user's data encrypted by a user-defined key, but you also wanted a safely stored "backup" key in case the user forgot their key. Is that even theoretically possible?

$\endgroup$
  • 2
    $\begingroup$ If the user's key and the backup key functionally equivalent, then why do you see an advantage in this application for there to be there two key? That is twice as many keys for an adversary to guess. $\endgroup$ – Tyson Williams Dec 10 '14 at 13:09
  • $\begingroup$ I was just curious as to whether or not it was possible $\endgroup$ – roryok Dec 10 '14 at 15:39
  • $\begingroup$ Ideas along these lines usually make people upset: see the Clipper chip controversy. An easy implementation of this scheme is to separately encrypt the message first with the one key, then with the other, and send both ciphertexts together. (This is not in itself a good scheme because it is subject to various kinds of attacks.) Also, the folks over at crypto.SE might be more interested in this question. $\endgroup$ – András Salamon Dec 16 '14 at 20:53
0
$\begingroup$

This is possible, for instance using the following straight-forward approach (where $E(\cdot,\cdot)$ is some encryption function and $H(\cdot)$ is a cryptographic hash function):

  • Input: A message $m$ and a set of keys $\{k_1,\dots,k_n\}$.
  • Generate a random ephemeral key $k_e$ that is used to encrypt $m$ only.
  • Output (for instance): $$(H(k_e), n, (E(k_1,k_e),\dots,E(k_n,k_e)), E(k_e,m))\text.$$

A message's recipient can subsequently decrypt all the encrypted keys $E(k_1,k_e)$ to $E(k_n,k_e)$ using his key $k$ and check whether the result's hash matches $H(k_e)$. If it does, he (highly likely) found the right $k_e$ and can proceed to decrypt $m$.

On the other hand, an adversary who does not have one of the keys $k_1,\dots,k_n$ learns nothing about $k_e$ from the hash $H(k_e)$ (as long as $H$ is not broken) nor any of the encryptions of $k_e$ (as long as $E$ is not broken), so he can't decrypt the message $m$ (as long as $E$ is not broken).

Drawbacks:

  • This approach leaks the number of keys for which a message is encrypted, which may not be desirable.
  • The method doesn't scale well if you need to support a larger number of keys, but it should do for as few as two. A possibility to avoid having to decrypt all encryptions of $k_e$ until one matches is to add some key ID (for example, a hash of the corresponding recipient's key) to each encrypted key that a recipient can compare to a hash of his own key, at the expense of a slightly longer ciphertext and potential correlation of the recipients' identities.
$\endgroup$

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.