What differences between Menezes–Vanstone ECC and ElGamal ECC?

Question

After researching ECC encryption, I found that we can use ElGamal cryptosystem with elliptic curve and can we use Menezes-Vanstone cryptosystem with elliptic curve. What is the essential difference between the two systems? Which one is better with regards to complexity/performance?

Answer 1

The essential difference between these two encryption schemes is that for standard ElGamal encryption on elliptic curves the plaintext space is the set of points in your elliptic curve group while in Menezes-Vanstone (which can be considered as a variant of ElGamal) the plaintext space is $F_p^*\times F_p^*$ where $F_p$ is the field over which your curve is defined. So what does this mean?

This means that when using ElGamal over elliptic curves you have to map the message to an elliptic curve point before encryption, while when using Menezes-Vanstone you can take your message string, split it up into to halves and interpret these two strings as elements of $F_p$ each.

Alternatively, you can use other "encoding free" variants of ElGamal such as "hashed ElGamal" that avoid the task of mapping messages to points on the curve. In standard ElGamal on elliptic curves you would compute the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the message $m$ mapped to a point on the curve, $Y$ the public key and $P$ the generator point.

In hashed ElGamal, the ciphertext is $(C_1,C_2)=(kP,m\oplus H(kY))$ where $H:G\rightarrow \{0,1\}^n$ is a hash function that maps points on the curve to $n$ bit strings. Consequently, you can encrypt $n$ bit messages, for instance 256 bit if you use SHA-256 for $H$. For the input to $H$ you need to encode the points of the curve in a suitable way.

Regarding performance, standard ElGamal on elliptic curves costs two scalar multiplications and one point addition, where Menezes-Vanstone costs you two scalar multiplication and two multiplications in $F_p$. So Menezes-Vanstone will be cheaper from a computational point of view.

Regarding ciphertext expansion, to encrypt a message (mapped to a point on the curve) with ElGamal, the ciphertext will contain 2 elements of the curve group (which in affine coordinates will be four elements of $F_p$ - and you can bring it down to ~ 2 elements of $F_p$ when using point compression). In Menezes-Vanstone to encrypt a message (which fits into two elements of $F_p$) the ciphertext will contain one element of the curve group (2 elements of $F_p$) and another two elements of $F_p$ (so you have four elements of $F_p$ and using point compression you come down to ~ 3 elements of $F_p$).

When using ElGamal on elliptic curves you can prove that it provides indistinguishability under chosen plaintext attacks (IND-CPA security), where Menezes-Vanstone does not provide IND-CPA security (this paper shows that it is not a probabilistic encryption scheme and thus not IND-CPA secure). So you should definitely not use the Menezes-Vanstone scheme.

Alternatively, a standardized scheme for public key encryption on elliptic curves is ECIES, which provides stronger security guarantees (IND-CCA security) than ElGamal does (there are ElGamal variants such as Cramer-Shoup wich are IND-CCA secure, but not that efficient as ECIES).