4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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...) $\endgroup$
    – poncho
    Commented Mar 2, 2016 at 19:22
  • $\begingroup$ 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. $\endgroup$
    – tolstikh
    Commented Mar 3, 2016 at 22:42
  • $\begingroup$ 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? $\endgroup$
    – tolstikh
    Commented Mar 3, 2016 at 23:08
  • $\begingroup$ 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? $\endgroup$
    – poncho
    Commented Mar 4, 2016 at 0:11

1 Answer 1

Reset to default
5
$\begingroup$

There is a way to use ECEG that gives us an additive homomorphic property, however the addition in this case is Elliptic Curve point addition, not addition over the integers.

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'$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, I understand this, but I am interested in the additive homomorphic property over the integers/plaintext, should probably clarify. This approach can still work, assuming there is a mapping of plaintext to points that has the additive homomorphic property as well. $\endgroup$
    – tolstikh
    Commented Feb 1, 2016 at 16:48
  • $\begingroup$ relevant article to understand how ECEG works in this case: medium.com/asecuritysite-when-bob-met-alice/… $\endgroup$
    – Erik Aronesty
    Commented Jan 24, 2023 at 16:36

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.