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?

$\endgroup$
  • 1
    $\begingroup$ McEliece code-based encryption. $\endgroup$ – SEJPM Jun 23 at 18:05
  • $\begingroup$ ElGamal, Cramer-Shoup, pretty much anything else based on DL/CDH/DDH. Any of the generic constructions. $\endgroup$ – Maeher Jun 23 at 18:09
  • $\begingroup$ Also hash based signing algorithms $\endgroup$ – Natanael Jun 23 at 19:12
  • $\begingroup$ If you summarize the comments as answers, I can accept them... $\endgroup$ – vy32 Jun 23 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 Jun 24 at 9:57
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...

$\endgroup$
  • 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 Jun 24 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 Jun 24 at 10:12

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.