# Single Ciphertext which can decrypt with multiple keys

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

• I‘d say it’s not possible because it would require the multiple decryption keys to have sone kind of mathematical relation which would make them vulnerable to an attack. Any specific reason for not using the common way you already described? – not2savvy Jul 17 '19 at 16:34
• So in other words, you're asking about equivalent keys in asymmetric crypto? – forest Jul 18 '19 at 0:59
• @not2savvy Honestly its just for a personal project im doing where i am looking for ways to reduce the communication overhead and this would be a small optimization. I thought this too, if the two keys have a relationship how much weaker is that system,do you think i can increase the size of the keys to makeup for that weakness? – Juam12 Jul 18 '19 at 4:12
• @Juam12 I don’t think so because it doesn’t change the connection between the keys. But I am not a crypto expert. However, if you want to reduce communication overhead, I‘d say hybrid encryption, as used in S/MIME or PGP, is your best option. – not2savvy Jul 18 '19 at 4:41
• Modern public-key encryption (that is, public-key encryption with strong a security argument) is hybrid, including RSA even for small messages: RSAES-OAEP internaly uses a PRF built from a hash, which is essentially symmetric crypto. Thus the question is ill-formulated, and I vote to close it as unclear (the nearest available match). – fgrieu Aug 28 '19 at 18:42

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