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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
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 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 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 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 at 0:11

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

share|improve this answer
    
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. – tolstikh Feb 1 at 16:48

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.