# Interchangeable role of public/private key pair and encoding/decoding algorithms

In designing a public-key cryptosystem, there are often two desirable properties:

1. Public/private key pair of each participant can be exchanged. Meaning that whenever a participant has generated a key pair $(a, b)$, it is free up to him to choose to public either $a$ or $b$ (but not both, of course)
2. Encoding/decoding algorithms $(E, D)$ are interchangeable. It is up to all participants to choose either $E$ or $D$ to be the encoding algorithm, then automatically, $D$ or respectively, $E$ will be the decoding algorithm. But the choice must be made prior to any communication.

Note that if $D$ and $E$ are identical, for e.g. $\mathrm{RSA}$, then the property 2 is vacuously true.

The question is: Assume that $E$ and $D$ are different, is there any known public-key cryptosystem that satisfies property 1 but violates property 2.

Informally, the cryptosystems that we are interested are the ones in which the key generation is in some sense symmetric, but the encoding and decoding algorithms are not.

EDIT: We only consider deterministic encryption scheme. To be meaningful, we assume $\mathrm{M} = \mathrm{C}$ and $\mathrm{PU} = \mathrm{PR}$ where $\mathrm{M}$ is the message space, $\mathrm{C}$ is the ciphertext space, $\mathrm{PU}$ and $\mathrm{PR}$ are public and private key space.

• Obviously it's an interesting theoretical problem to study, but why would these properties be “often desirable”? As an implementer, I've yet to encounter a case where this would be useful. Even RSA doesn't have property 1 in practice because the public key almost always uses a small, guessable exponent. – Gilles Aug 29 '18 at 6:35
• Also what do you call “encoding” and “decoding”? Asymmetric schemes can be used for multiple purposes, the most common ones being encryption and signature. It isn't clear to me that these can be broken up into an “encoding/decoding” step and another step of — what would it be? padding? – Gilles Aug 29 '18 at 6:38
• I've made some edit to better narrow down the intended terms. We only consider theoretical aspects of deterministic encryption scheme. There is NO non-trivial adversarial model here. In fact, the adversary has nothing except the public key, but he does not need to recover the private key, only aims at successful decryption of non-negligible amount of ciphertext. – Thinh D. Nguyen Aug 29 '18 at 7:16
• Also, surely the practical implementation of RSA with small exponent $e$ is not considered here. – Thinh D. Nguyen Aug 29 '18 at 7:17

• For example, OAEP is introduced to solve the following problem: if $c$ is the ciphertext of the plaintext $m$, then $cr^e$ is the ciphertext of $mr$. The plaintext is still not revealed to Eve. But she gains some control to the output ciphertext. – Thinh D. Nguyen Aug 29 '18 at 7:35