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.
