3
$\begingroup$

The RSA public key encryption system has the characteristic that the public key and the private key can be reversed. That is, information encrypted with the public key can be decrypted with the private key, but the keys are themselves symmetric, such that it's also possible to use them the other way around and information encrypted with the private key can be decrypted with the public key.

This is not inherent with public key cryptography, however. The Paillier cryptosystem, for example, does not have this feature: the private key cannot be used to encrypt data that can then be decrypted with the public key.

Are there other public key systems that do not have this property?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ McEliece code-based encryption. $\endgroup$
    – SEJPM
    Commented Jun 23, 2019 at 18:05
  • $\begingroup$ ElGamal, Cramer-Shoup, pretty much anything else based on DL/CDH/DDH. Any of the generic constructions. $\endgroup$
    – Maeher
    Commented Jun 23, 2019 at 18:09
  • $\begingroup$ Also hash based signing algorithms $\endgroup$
    – Natanael
    Commented Jun 23, 2019 at 19:12
  • $\begingroup$ If you summarize the comments as answers, I can accept them... $\endgroup$
    – vy32
    Commented Jun 23, 2019 at 19:54
  • 10
    $\begingroup$ In practice, you cannot switch the public and private keys of RSA either. You've got CRT, small public exponents, libraries that will wrongly apply padding, exponentiation that doesn't protect the public exponent against side channel attacks, etc. . Many libraries don't even except large public exponents, and those are of course a requirement to use the public key as private key. Java's JCA lib simply flat out rejects public keys used instead of private keys, so you don't make this mistake. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 24, 2019 at 9:57

1 Answer 1

Reset to default
15
$\begingroup$

Are there other public key systems that do not have this property?

A more cogent question might be "are there any public key systems other than RSA that does have this property?"

In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public and private keys, and you eschew the CRT optimization on the private key side).

I'm familiar with a number of proposed public key systems, and nothing comes to mind:

  • Other factoring-based systems: Rabin-Miller and Pallier - nope; although Rabin does come close, but with a fixed public exponent of 2, it can't really be used as a private exponent (and it's not quite reversible either).

  • Discrete log; nope. They (in my experience) have a private key as an integer $e$ and a public key as the value $g^e$ (or $eG$, if you're using a group with additive notation). Given that you can compute the public key from the private one, you can't swap them and remain secure.

  • Lattice based systems; nope. They internally have more variants than the discrete log problems, however in general, the private key is some secret sauce that makes solving the lattice problem easy (at least in the cases that the system cares about), hence you can't swap them.

  • Code based systems; nope. The private key is the secret sauce to make the error correction problem easy, hence you can't swap them.

  • Multivariate systems; nope. The private key is the secret sauce to make solving the multivariate equations easy, hence you can't swap them.

  • Isogeny based systems; nope. The private key in this case is a subgroup of the elliptic curve, while the public key is the isogenous elliptic curve that the isogeny maps the curve into (while mapping the subgroup to the neutral element). Again, it doesn't make any sense to swap them.

  • Hash based signatures; nope. In this case, the public key is a hash, while the private key is the series of values that are hashed together (generally in a big tree structure) to ultimately form the hash. It makes no sense to swap the public and private keys.

I can't think of any other public key systems that haven't been broken...

Improve this answer
$\endgroup$
2
  • 9
    $\begingroup$ Warning: "which you can do with RSA, as long as you select large public and private keys": let's be clear: this means a securely generated RSA public key with large exponent. Generally RSA public keys do not fit the bill as they have a small exponent. Furthermore, implementations of RSA have not been designed to keep the public exponent secure. So in practice you will not find secure RSA that uses the public key as private key unless you design it from the ground up. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 24, 2019 at 9:52
  • $\begingroup$ Further for discrete logs: the private key (scalar) may not be in the group, so not even valid as a public key. $\endgroup$
    – user7761803
    Commented Jun 24, 2019 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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