7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – not2savvy Jul 17 at 16:34
  • $\begingroup$ So in other words, you're asking about equivalent keys in asymmetric crypto? $\endgroup$ – forest Jul 18 at 0:59
  • $\begingroup$ @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? $\endgroup$ – Juam12 Jul 18 at 4:12
  • 1
    $\begingroup$ @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. $\endgroup$ – not2savvy Jul 18 at 4:41
  • 1
    $\begingroup$ 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). $\endgroup$ – fgrieu Aug 28 at 18:42
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, this works and will satisfy the single message constraint, however it looks like have two ciphertexts here. It would be nicer if we can have a single ciphertext which two private keys can decrypt, without having to send additional messages. $\endgroup$ – Juam12 Aug 29 at 3:11

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.