It is very interesting to see @tylo's answer on ElGamal with elliptic curves. Instead of mapping the message to the elliptic curve point it just reduces an elliptic curve point to its $x$ coodrinate. The scheme now becomes like this:

function $x^P$ denotes the $x$ coordinate of a point.

Encryption: choose random $k\in F_q$ , then calculate $C=kP$ and $c=x^{kY}$. The ciphertext is the point $C$ and the product $c\cdot m \bmod{q}$.

Decryption: From a point $C$ and a value $d$ calculate $c'=x^{xC}$. Retrieve the message with $m=d/c' \bmod{q}$.

Could anyone please clarify if the above scheme is additive homomorphic even if we set the ciphetext to be $c+m \bmod{q}$.

  • $\begingroup$ What is Y in c=x^(kY)? Also, FYI, if you are familiar with latex, you can write equations in latex format so they look nicer. Here is a basic tutorial. I went ahead and updated with the math formatting. If I made any mistakes, feel free to correct. $\endgroup$
    – mikeazo
    Commented Feb 11, 2014 at 12:52
  • 1
    $\begingroup$ ouch... I just noticed an error in my answer back there. It should not be "mod $q$", but it should be done in $\mathbb{F_q}$. It's just a formal mistake, but it is a difference if $q$ is not a prime itself but a prime power. $\endgroup$
    – tylo
    Commented Feb 11, 2014 at 16:23
  • 2
    $\begingroup$ the short answer is: no it's not. Even the multiplicative one is not homomorphic, because projecting the elliptic curve point to its x-coordinate is not a homomorphism. Right now I can't think of any structure preserving functions between elliptic curves and their underlying finite field, except pairings. But in pairing friendly group this encryption scheme will probably not work anyway. $\endgroup$
    – tylo
    Commented Feb 11, 2014 at 18:03
  • $\begingroup$ This might be a bit late, but the encryption you mention is apparently not semantically secure. See this answer: that is an invalid way of combining the point which is the result of the DH exchange with the plaintext. $\endgroup$
    – user45323
    Commented Mar 26, 2017 at 4:50

1 Answer 1


As @tylo says, projecting the point to the $x$ coordinate does not give you a homomorphism. So this version is not useful if you want to have additively homomorphic ElGamal.

However, you could use the "exponential" version of standard ElGamal on elliptic curves, i.e., instead of encrypting a message $m$ somehow mapped to a point $M$ on the curve (using an injective efficiently invertible encoding), to encrypt a message $m$ straightforwardly mapped as $M=m\cdot P$ to a point on the curve where $P$ is your generator and $m$ an integer in the order of the group. This will give you an additive homomorphic encryption scheme. However, as discussed below, this encoding is not efficiently invertible.

Let $P$ be the generator of your elliptic curve group of prime order $q$ and $Y=xP$ be your public key ($x$ the private key). Then given two ciphertexts for messages $m_1,m_2\in Z_q$:

$C_1=(k_1P,m_1P+k_1Y)$ and $C_2=(k_2P,m_2P+k_2Y)$, then by componentwise point addition you receive

$$C=((k_1+k_2)P,(m_1+m_2)P+(k_1+k_2)Y)$$ which is a valid ciphertext for message $m_1+m_2 \mod q$.

You can decrypt $C$, but this obviously gives you $M=(m_1+m_2)P$ and in order to recover $m_1+m_2 \mod q$, you have to compute $\log_P M$, i.e., you have to compute discrete logarithms after encryption. If your messages $m_i$ come from a small set, this, however, is quite efficiently feasible. However, this clearly depends on your application, i.e., which values from which range the $m_i$'s can take.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.