Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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. –  mikeazo Feb 11 at 12:52
1  
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. –  tylo Feb 11 at 16:23
2  
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. –  tylo Feb 11 at 18:03

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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