Could this "symmetric RSA" scheme provide key compromise resistant communications?

Question

This question, and fkraiem's answer to it, made me wonder about the security and practicality of using "symmetric RSA" to provide a partially compromise-resistant secure channel.

Specifically, assume that Alice and Bob wish to communicate securely over an untrusted network, so that others cannot read or forge their communications. Obviously, assuming that Alice and Bob can establish a shared secret in advance, they can achieve this simply using any standard IND-CCA2 secure symmetric authenticated encryption scheme.

However, let's assume that Alice and Bob also wish to minimize the impact of either party's key material being compromised; specifically, even if an attacker learns Alice's key(s), she should not be able to read messages sent by Alice to Bob or forge messages from Bob to Alice, and vice versa.

As I noted in my answer to the linked question, this can be achieved by combining public-key encryption and digital signatures: basically, Alice and Bob each generate an encryption key pair and a signature key pair (i.e. four key pairs in total, for two-way communication), exchange the corresponding public keys, and encrypt and sign their messages. However, fkraiem gave an alternative suggestion involving just a single RSA key pair, which I interpret as follows:

1. Alice and Bob together generate an RSA modulus $n$, i.e. a product of two large primes $p$ and $q$.

2. They select a random exponent $e_A$ coprime to $\lambda(n) = \operatorname{lcm}(p-1,q-1)$, and let $e_B \equiv e_A^{-1} \pmod{\lambda(n)}$.

3. Alice stores the modulus $n$ and exponent $e_A$, while Bob stores $n$ and $e_B$. Both erase all other intermediate values, including $p$, $q$ and the other exponent.

4. To send a (padded) message $m$ to Bob, Alice encrypts it as $c \equiv m^{e_A} \pmod n$, and transmits $c$ to Bob. To decrypt the message, Bob computes $c^{e_B} \equiv m^{e_A e_B} \equiv m \pmod n$. Similarly, Bob can send messages to Alice in the same way, just swapping $e_A$ and $e_B$.

Obviously, this scheme will not be secure for arbitrary unpadded messages, for the same reasons that textbook RSA isn't secure. That said, it might be possible to combine this with a suitable randomized padding scheme to make it secure, although I'm not sure if any of the standard RSA padding schemes would work here; all the RSA padding schemes I know of are meant for either encryption or signatures, whereas this scheme would seem to effectively require both at once.

Thus, my questions would be:

1. Can this scheme work at all, or is there some generic attack that breaks it regardless of padding?

2. If this scheme can be made secure using a suitable padding scheme, what would such a padding scheme look like?

(I was hoping it might at least be possible to make this system work in key encapsulation mode, but that seems to be trivially vulnerable to bidirectional forgery if one party's key is compromised: if Eve knows Alice's key, she can not only forge messages from Alice to Bob, but can also intercept any message sent by Bob, decrypt it to learn the encapsulated ephemeral key, and then use this key to send any message she likes to Alice. So that, at least, would seem to be a non-starter.)

Answer 1

Yes, this seems to make sense and it is a plausible solution. The KEM approach does not work, unless you use some tricks, like including a hash of the message in the KEM. (That could work, of course.)

Security goal

The type of scheme we are looking at consists of three algorithms $(K,E,D)$. The key generation algorithm $K$ outputs two keys, say $k_0$ and $k_1$. The encryption algorithm $E$ takes as input a key and a message and outputs a ciphertext. The decryption algorithm $D$ takes as input a key and a ciphertext and outputs a message or $\bot$.

We require that for any $(k_0, k_1)$ output by $K$ and any message $m$, $$D(k_{1-\beta}, E(k_\beta, m)) = m \text.$$

There are two goals here, confidentiality and integrity. You want messages encrypted with $k_\beta$ to be confidential to everyone who does not have $k_{1-\beta}$. And someone who does not have $k_\beta$ (but may have $k_{1-\beta})$ should not be able to create ciphertexts that look as if they were created with $k_{\beta}$.

Confidentiality

In the confidentiality game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary chooses two messages $m_0$ and $m_1$. The simulator flips a coin $b$ and creates a ciphertext $c^*$ as $E(k_1, m_b)$. The simulator sends $c^*$ to the adversary, and the adversary eventually sends $b'$ to the simulator. During the entire process, the adversary is allowed to send messages or ciphertexts to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively.

The adversary wins if $b=b'$. He should not win significantly more (or less) often than half the time.

Integrity

In the integrity game, the simulator generates a key pair $(k_0, k_1)$ and gives $k_1$ to the adversary. The adversary is allowed to send ciphertexts and messages to the simulator, and the simulator responds with the result of $E(k_0, m)$ or $D(k_0, c)$, respectively. Finally, the adversary sends a ciphertext $c^*$ to the simulator and the simulator decrypts it using $k_1$.

The adversary wins if the $c^*$ decrypts correctly and it was not created by the simulator. The adversary's success rate should be negligible.

Analysis Proposal

I would try something like OAEP+, but for simplicity, I would "personalize" the hash functions so that we can use different random oracles for the two senders. The confidentiality game looks a lot like the usual RSA-OAEP+ game, but you need to create ciphertexts for the recipient. This becomes much easier when you use separate random oracles.

I suspect it will work out. It may even be possible to "reduce" the security to that of ordinary RSA-OAEP+.