True asymmetric ciphers beside RSA

Question

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).

EDIT:

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.

EDIT2:

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?

Answer 1

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.

Answer 2

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.

EDIT:

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. ...

and

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)$.