Single Ciphertext which can decrypt with multiple keys

Question

Say we have a public key system where we have 2 users, Alice, and Bob each has a public and private key. We also have a publicly available server which stores a message.

I want to encrypt this message (M) for Alice and Bob only once. such that either Alice or Bob can decrypt the message with their private key.

The easy and well-studied way to do this is to generate a random symmetric key and encrypt the message with that key, then I can encrypt a small message (SM) For Alice and Bob with their public keys which gives them the symmetric key, with this they can now both decrypt the Message M available on the server.

However is there any known way that I can encrypt the message M, where both Alice and Bob can decrypt M without needing an additional symmetric key? I have looked briefly into double trapdoor encryption and Broadcast encryption but I don't think these schemes suit the purpose?

TL;DR One Ciphertext that can be decrypted by multiple Public, Private keypairs, without deriving an additional symmetric key

Answer 1

One trivial solution is to let the message be: $$M = (c_{\text{Alice}}, c_{\text{Bob}}) = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m))$$ Whether this counts as a "single message" or not is difficult to say. Even if it does, it has the (unfortunate) property that Alice/Bob can't distinguish between: $$M = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m)),\quad M' = (Enc_{k_{pub,A}}(m), Enc_{k_{pub,B}}(m'))$$ for $m'\neq m$ (so an adversary could "encrypt" something different to each of them, and provided the underlying scheme is CPA secure neither Alice nor Bob will be able to detect the adversarial behavior).

If you want to reduce the communication overhead of your scheme, hybrid encryption (encrypting the private key under both public keys) is likely the best choice, because after this initial "setup" phase you can switch to solely symmetric crypto under this new key. Symmetric crypto tends to have a lower communication overhead than asymmetric crypto (the term to look at here is the "rate" of the encryption scheme).

That all being said, it's unclear precisely what your threat model is, and even hybrid encryption could easily allow for an adversary to encrypt different keys under Alice/Bob's public keys (so they initially disagree on their secret keys). How this could be leveraged to mount a larger attack I don't know, but without fixing a particular threat model it's difficult to discuss what security would even mean.