Does an encryption algorithm exist where encrypted data can be decrypted by multiple private keys?

Question

Suppose I have Company1 with their own Public/Private Key Pairs and another Company2 with their public/private key pairs and yet another Company3 with their public/private key pairs.

Is there any way/algorithm to encrypt a piece of data, given we provide Company1 and Company2 public keys to it, such that the encrypted data can be decrypted by EITHER ONE of their private keys. i.e. upon receiving the encrypted data, Company1 can use their private key to see what it actually is, and so can Company2, without them knowing each other's private keys. Also, Company3 should in no way be able to decrypt that data.

I've also been looking at Shamir's Secret Sharing algorithm. It works somewhat for our use case, assuming we encrypt each share using PGP and share it to the companies. In our specific use case, the bottleneck is that any data sharing between the companies happens on a shared ledger/database -- so by default everyone sees everything. Also not sure what the maximum number of shares are in this case, as its possible the list will grow to hundreds of shares being generated.

Answer 1

Yes, quite easily, with key encapsulation and the appending the symmetric key twice (encrypted for each company):

1. Encrypt the data with a random symmetric key, for instance an AES key;
2. For each recipient, encrypt the symmetric key with the respective public keys of the recipients.

The ciphertext is the combination of the encrypted message and wrapped key for each recipient.

More theoretically, you could use identity-based encryption, which is close to what you describe. That does require a common setup, though, and possibly someone having a master key.

Answer 2

PGP permits this very thing using hybrid encryption. You might want to take a look at how it works.

Here's one article that explains it.