0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gilles♦ Aug 29 '18 at 6:35
  • $\begingroup$ 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? $\endgroup$ – Gilles♦ Aug 29 '18 at 6:38
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Aug 29 '18 at 7:16
  • $\begingroup$ Also, surely the practical implementation of RSA with small exponent $e$ is not considered here. $\endgroup$ – Thinh D. Nguyen Aug 29 '18 at 7:17
2
$\begingroup$

Any RSA variant that goes beyond textbook RSA (which is insecure) will probably not have symmetric encryption/decryption.

Examples are RSA + OAEP or RSA used to encrypt an AES key which is used to actually encrypt the message.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for giving a try. We are interested in the determinism. For otherwise, the ciphertext is longer than the message, and there is no symmetry left. $\endgroup$ – Thinh D. Nguyen Aug 29 '18 at 7:23
  • $\begingroup$ @ThinhD.Nguyen Determinism can not be secure. An attacker can simply use the public key to encrypt his/her guess of the plaintext and compare to the ciphertext to verify the guess was correct. $\endgroup$ – orlp Aug 29 '18 at 7:25
  • $\begingroup$ But Eve may have to guess exponentially many plaintext in average then. Textbook RSA is only insecure in more realistic adversary models. While those more realistic models have been formally theorized. We are not interested in them. $\endgroup$ – Thinh D. Nguyen Aug 29 '18 at 7:28
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Aug 29 '18 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.