# Elliptic curve ElGamal with homomorphic mapping

I am interested in ElGamal due to the fact that you can achieve some degree of homomorphic properties. I became interested in applying ElGamal to elliptic curves, and found this other question with an answer that shows 2 different ways to apply ElGamal to elliptic curves, but from what I can tell neither approach has the additive homomorphic property.

So are there any other ways to apply ECEG that give us the additive homomorphic property?

The only thing I was able to come up with is using a message-point mapping function that encodes the message with scalar point multiplication, ie the cipher text $(kP, mkY)$

It seems to work because with $(\sum k_iP, \sum m_i k_i Y)$ we can solve $\sum m_i = \frac{\sum m_i k_i Y}{x \sum k_i P}$, but this is solving the ECDLP so is very difficult. Are there any other options?

EDIT: I'm looking for the additive homomorphic property over integers, not points.

• Actually, if you're dealing with small integers, the ECDLP problem isn't that tough. If you know that $0 < k < N$, you can recover $k$ from $kG$ in $O(\sqrt{N})$ time; if (say) $N = 1000000$, this may be reasonable (perhaps 2,000 point additions...) – poncho Mar 2 '16 at 19:22
• As a matter of fact I am using small integers, likely 16-bit or so. Can you explain your technique? I only know the naive approach that would test all $k \in [0,N-1]$ one at a time. – tolstikh Mar 3 '16 at 22:42
• I came across the Baby-step_giant-step algorithm which has the desired $O(\sqrt(N)$ time, but requires a rather large chuck of memory to implement. I am dealing with a memory constrained system (embedded). Is there any thing else like this with low memory requirements? – tolstikh Mar 3 '16 at 23:08
• With Baby/Giant step, if you have $M$ memory locations, you can find $k$ in $max( M, N/M )$ time. Even if $M = \sqrt{N}$ is too big, is there a smaller value of $M$ which you could live with, and which would be fast enough for you? – poncho Mar 4 '16 at 0:11

One way to use ECEG to encrypt a point $M$ is to have the encrypted value be the pair of points $(kP, M + kY)$
That way, if you have the encryption of the points $M, M'$ as $(kP, M + kY)$ and $(k'P, M' + k'Y)$, you can add each element in the pair to form $( kP + k'P, M + kY + M' + k'Y) = ((k + k')P, M + M' + (k + k')Y)$, which is a valid encryption of the point $M + M'$