Is there any TRUE public key cipher beside RSA? Most people would answer Elgamal or ECC, but for what is my understanding (and I know cryptography only superficially), those are not true asymmetric ciphers (because both parties can encrypt and decrypy).


I realized that my question needed better explaining.

The following quote is from the Handbook of Applied Cryptography:

Definition 1.50: Consider an encryption scheme consisting of the sets of encryption and decryption transformations $\{E_e : e ∈ K\}$ and $\{D_d : d ∈ K\}$, respectively. The encryption method is said to be a public-key encryption scheme if for each associated encryption/decryption pair $(e, d)$, one key $e$ (the public key) is made publicly available, while the other $d$ (the private key) is kept secret. For the scheme to be secure, it must be computationally infeasible to compute $d$ from $e$.

Now take for instance Elgamal encryption. Bob chooses the parameters, then sends the public key to Alice, Alice computes the mask $K_M$ (the session key) and the ephemeral key $K_E$, encrypts the message $M$ with $K_M$ obtaining $C$, and sends ($C$,$K_E$) to Bob. Bob can compute $K_M$ using $K_E$ and his private key. The quoted definition is not satisfied. Alice and Bob, in the end, both have $K_M$ which is used for encryption and decryption.


The reply I got from fgrieu was very satisfying, I was mistaking a shared secret key for a public key. However this made me reflect on another difference between an Elgamal scheme and an RSA scheme. I'm going start with another quote from HAC (Basic Terminology, p.12):

An encryption scheme consists of a set ${E_e : e ∈ K}$ of encryption transformations and a corresponding set ${D_d : d ∈ K}$ of decryption transformations with the property that for each $e ∈ K$ there is a unique key $d ∈ K$ such that $D_d = E_e^{−1}$; that is, $D_d(E_e(m)) = m$ for all $m ∈ M$. An encryption scheme is sometimes referred to as a cipher.

With this, Elgamal randomized E is not acceptable, because a randomized function can't be the left inverse of another function. Se we can heve $D_d(E_e(m)) = m$ for all $m ∈ M$, but we can't have $D_d = E_e^{−1}$. This is also the reason (I think) why Elgamal cipher can't be usued for digital signatures (Elgamal DS is different from the cipher).

Now my question: is the second quoted definition correct? Or $D_d = E_e^{−1}$ should be "$D_d$ is a left inverse of $E_e$"? Also unicity of $d$ is really necessary?

  • 4
    $\begingroup$ By your logic RSA based encryption isn't asymmetric either. Since Alice knows the message she encrypted, she can also "decrypt". The fact that you can relearn the message you yourself encrypted isn't really surprising. $\endgroup$ – Maeher Nov 27 '19 at 9:24
  • $\begingroup$ This looks like hybrid encryption - KM is typically a key for a symmetric algorithm such as AES. $\endgroup$ – Eugene Styer Nov 27 '19 at 16:52
  • $\begingroup$ I think the part of your own description is lacking depth. The "ephemeral key" $K_E$ doesn't have any meaningful interpretation: You can construct it either if you know the plaintext/ciphertext pair or you know the random coins and the plaintext. That is basically the same as being able to decrypt or to be the one who encrypted a message. For RSA you could call $m^{e-1}$ the ephemeral key, and it works just the same as your ElGamal example. I don't think there exists a proper definition for "true asymmetry" with your thought process. $\endgroup$ – tylo Nov 27 '19 at 19:27
  • $\begingroup$ If anything, you could argue that in ElGamal Bob can not extract the random coin - which does not exist in plain RSA. If you define it like that, RSA is not truly asymmetric, but ElGamal would be. $\endgroup$ – tylo Nov 27 '19 at 19:30
  • $\begingroup$ @maeher I didn't intend the same sender, but somone with his key. That is the message was recoverable by using only the public key. My mistake was considerig $K_M$ a public key beacuse it was shared. Incidentaly this hilighetd the main difference between Elgamal and RSA which I was overlooking. And I'm going to add that to open now. $\endgroup$ – Alex123 Nov 28 '19 at 7:04

Yes, there are true asymmetric (public-key) ciphers beside RSA. Elgamal encryption is an example, and matches the question's definition when we allows that definition's encryption transformation $E_e$ to be randomized (as we must: otherwise, anyone could use the public $E_e$ to verify a guess of the message, which would be a disaster in many practical applications, e.g. enciphering the name of some guy on the class roll).

Using the notation in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984),

  • Parameters are a large prime $p$ with $p-1$ having at least one large prime factor, and a generator $\alpha$ (e.g. with $q=(p-1)/2$ prime, and $\alpha\in[1,p)$ with $\alpha^q\bmod p\ne 1$ ). Parameters are public, or part of individual public keys.
  • The definition's encryption/decryption pair $(e,d)$ is the combination of parameters and long-term public-private key pair $(y_B,x_B)$ used by recipient Bob. More precisely, $e$ is $(p,\alpha,y_B)$ and $d$ is $(p,\alpha,x_B)$, with $x_B$ a random secret and $y_B=\alpha^{x_B}\bmod p$.
  • The definition's encryption transformation $E_e$ accepts as input a message $m$ in $[0,p)$. As part of each invocation of $E_e$, the sender (Alice) draws ephemeral random $k$, computes $K={y_B}^k\bmod p$, $c_1=\alpha^k\bmod p$, $c_2=Km\bmod p$. The ciphertext is $(c_1,c_2)$.
  • The definition's decryption $D_d$ accepts as input a ciphertext $(c_1,c_2)$ in $[0,p)^2$. The receiver (Bob) computes $K={c_1}^{x_B}\bmod p$, and $m=K^{-1}c_2\bmod p$.

Note: In the version described here and in the original paper, ElGamal encryption is not CPA secure. For a start, $m=0\iff c_2=0$. And even if we exclude message $m=0$, the Legendre symbol $\displaystyle\biggl(\frac m p\biggr)$ can be found from $(p,\alpha,y_B,c_1,c_2)$, and that leaks one bit of information about $m$.

Regarding EDIT2 (about as it stands less a few typos):

we can have $D_d(E_e(m))=m$ for all $m\in M$, but we can't have $D_d = E_e^{−1}$.

To my eyes, the two statements are equivalent by any sensible definition of $E_e^{−1}$, which must be a transformation taking the output of $E_e$ and returning what was the input. And the Elgamal cipher matches that. The second quoted definition looks correct to me.

I would agree with "we can't have $E_e= D_d^{−1}$", because multiple inputs of $D_d$ have the same output, making $D_d$ impossible to invert for the classical definition of that. And yes, this is a reason why Elgamal cipher can't be used for digital signatures using the techniques allowing RSA signature.

RSA is not quite the only public-key cipher internally using a trapdoor permutation, usable for both encryption and signature scheme (which turns out to be the meat of the question's introductory phrase). There is at least the Rabin cryptosystem, which can be thought as RSA with even public exponent. I fail to name another which got sizable traction.

Note: RSA as in the original paper and PKCS#1 does not match the "unique key $d$" requirement. For this to hold, we need to reduce $d$ modulo $\lambda(N)$ (where $\lambda$ is the Carmichael function), as in FIPS 186-4.

| improve this answer | |
  • 1
    $\begingroup$ What's the difference to standard ElGamal that would break CPA security in this description? $\endgroup$ – SEJPM Nov 27 '19 at 9:24
  • $\begingroup$ @SEJPM: If you have a description of what standard ElGamal is, I'd appreciate that and would answer more in depth. What I have seen tends to skim at how plaintext is reversibly mapped to some abstract group, or change the definition of $c_2$ to something different from multiplication in the group used for $y=\alpha^x$. $\endgroup$ – fgrieu Nov 27 '19 at 13:13
  • $\begingroup$ Indeed I was referring to ElGamal where the message is mapped into the group, in this case this would be $\mathbb Z^\times_p$. $\endgroup$ – SEJPM Nov 27 '19 at 13:29
  • $\begingroup$ @SEJPM: For the reason in the last sentence of my answer, ElGamal is not CPA secure in the multiplicative subgroup modulo prime $p$, of $p-1$ elements [which I guess is your $\mathbb Z^\times_p$. The notations I know for that are $\Bbb Z_p^*$ and $(\Bbb Z/p\Bbb Z)^\times$ ]. For CPA security we need to further restrict $m$ to the subgroup of quadratic residues, of $(p-1)/2$ elements. We can (but need not) choose $\alpha$ as a generator of that subgroup. How to map actual messages to that subgroup and back is not trivial. Many sources fail to mention that issue. $\endgroup$ – fgrieu Nov 27 '19 at 14:47
  • 1
    $\begingroup$ @Alex123: standard math terminology on functions can't apply when $g$ is not a function ($E_e$ is not a function). So my reading is that $f = g^{-1}$ means $\forall x,f(g(x))=x$. No, I don't think that it is practically necessary to avoid more than one $d$ key for the same $e$ key. My point is that we need such tweak of the definition of $d$ in RSA if we want to have RSA match the second quoted definition. $\endgroup$ – fgrieu Nov 28 '19 at 11:10

As long as the private key is kept secret (as it should be), then both parties cannot both encrypt and decrypt. That would make no sense. Public key is used only for encryption, and you need the private key for decryption.

because both parties can encrypt and decrypt

Have you read this somewhere? Do you have a source? Or is this only what you think? One party knows the private key, and everyone knows the public key. That would mean that everyone can both encrypt and decrypt, which would be the same as not encrypting at all.


Definition 1.50: ...The encryption method is said to be a public-key encryption scheme if for each associated encryption/decryption pair $(e,d)$, one key $e$ (the public key) is made publicly available, while the other $d$ (the private key) is kept secret. ...


Remark 1.51: ...it takes two or more parties to share a secret, but a key is truly private only when one party alone knows it.

Technically, the 1.50 definition doesn't say anything about shared (not private) keys. Otherwise no TRUE asymmetric encryption would satisfy this definition. Of course, I haven't heard the definition of TRUE asymmetric cipher anywhere, so it would be probably useful to properly define it and changes these other definitions accordingly.

1.8.1: ...Consider any pair of associated encryption/decryption transformations $(E_e, D_d)$ and suppose that each pair has the property that knowing $E_e$ it is computationally infeasible, given a random ciphertext $c \in C$, to find the message $m \in M$ such that $E_e(m)=c$. This property implies that given $e$ it is infeasible to determine the corresponding decryption key $d$.

This part holds for ElGamal for both the (public, private) key, and for $(K_E, K_M)$.

| improve this answer | |
  • $\begingroup$ I explained my question better, and added a quote. $\endgroup$ – Alex123 Nov 27 '19 at 7:27

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.