Split encryption into two steps

Question

Are there two step encryption systems that - given the same plain text - support choosing two keys ($k_{A_1}, k_{A_2}$) for a first encryption so, that you can calculate another pair of keys ($k_{B_1}, k_{B_2}$) resulting in equal cipher texts?

$E(k_{B_1}, E(k_{A_1}, m)) = E(k_{B_2}, E(k_{A_2}, m))$ with $k_{A_1} \neq k_{A_2}$

A one-time-pad encryption is one of these systems, if you choose the keys like this $k = k_{A_1} \oplus k_{B_1} = k_{A_2} \oplus k_{B_2}$. Are there other systems that don't suffer from key re-usage?

Answer 1

There's always the old Polig-Hellman system, with:

$$C = M^k \bmod p$$

where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$), and $p$ is a large public prime.

Decryption can be done as:

$$M = C^{k^{-1} \bmod p-1} \bmod p$$

To address your requirement, given $k_{A_1}, k_{A_2}$, you can select a random $k_{B_1}$ (relatively prime to $p-1$), and then compute $k_{B_2} = k_{A_1} k_{B_1} k_{A_2}^{-1} \bmod p-1$, and Bob's your uncle.