8 of 8
added 2 characters in body

True asymmetric ciphers beside RSA

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?