> It is perfectly possible to encrypt a message such that two different keys can decrypt it. There is nothing in modern encryption that makes that impossible.

Not really, any more than it's possible to write a message that says the same thing whether you read it in English or Swahili. You might be able to do it once as a novelty, but the approach won't generalize.

There are multiple-recipient schemes, but they don't rely on using two different keys to decrypt the same message. Instead, you encrypt the message (once) using a (single) symmetric key, and you prepend a bunch of different messages saying "the symmetric key is xxxxxxxxxxx", one for each intended recipient. Those are encrypted with keys specific to each recipient, and each recipient has to attempt to decrypt them all and select the one that decrypted successfully.

The paper you link appears to be discussing an entirely different problem: its definition of a "multi-recipient encryption scheme" does not contemplate sending the same message to several different recipients:

> There are n receivers, numbered 1, ..., n. Each receiver i has generated for itself a secret decryption key sk_i and corresponding public encryption key pk_i. The sender now applies a multi-recipient encryption algorithm to pk_1, ..., pk_n and messages M_1, ..., M_n to obtain ciphertexts C_1, ..., C_n.

> Each receiver i can apply to sk_i and C_i a decryption algorithm that recovers M_i.

> We refer to the primitive enabling this type of encryption as a multi-recipient encryption scheme (MRES).

Note that there is no requirement for anyone other than recipient i to be able to understand message M_i. As described, all encryption schemes are multi-recipient encryption schemes, because you can just consider each message M_k individually and encrypt it to recipient k using a single-recipient scheme.