Additive Homomorphism for ElGamal

[eNipu]

I have tried to check if this implementation can be used for Additive homomorphism available in ElGamal.

For example, to achieve sometime like this this ADD(X,Y) = Enc(plain_text_1+plain_text_2)

where

X=(C1, C2)
Y=(C3, C4)

pri_key, pub_key = gen_keypair(Curve25519)
cipher_elg = ElGamal(Curve25519)
plain_text_1 = bytes([3])
plain_text_2 = bytes([4])
X=C1, C2 = cipher_elg.encrypt(plain_text_1, pub_key)
Y=C3, C4 = cipher_elg.encrypt(plain_text_2, pub_key)
C5 = Curve25519.add_point(C1,C3)
C6 = Curve25519.add_point(C2,C4)
result = cipher_elg.decrypt(pri_key, C5, C6)

Then the output is expected to be 7.

Seems cipher_elg.decrypt(pri_key, C5, C6) will not work. Maybe it can be done as future improvements.

[lc6chang]

@eNipu Sorry, the master branch now has no interface for Additive Homomorphism. Actually, "Additive Homomorphism" should be for the Point on the Curve, but not for the bytes of the plain text.

I mean, the input (plain text to be encrypted) should be two points M1 and M2, instead of two bytes (as you mentioned above).

So, I made a fix on this commit https://github.com/lc6chang/ecc-pycrypto/commit/0526d93461bfc7940cf9e47ab33337e01655b534 (done in a hurry, the code will be improved in the future):

@dataclass
class ElGamal:
    curve: Curve

    ...

    def encrypt_raw(self, plaintext: Point, public_key: Point,
                    randfunc: Callable = None) -> Tuple[Point, Point]:
        randfunc = randfunc or urandom
        # Base point
        G = self.curve.G
        M = plaintext

        random.seed(randfunc(1024))
        k = random.randint(1, self.curve.n)

        C1 = k * G
        C2 = M + k * public_key
        return C1, C2

    def decrypt_raw(self, private_key: int, C1: Point, C2: Point):
        M = C2 + (self.curve.n - private_key) * C1
        return M

With these two interfaces, you could achieve it. And I gave you an example here:

from ecc.curve import Curve25519, Point
from ecc.cipher import ElGamal
from ecc.key import gen_keypair

pri_key, pub_key = gen_keypair(Curve25519)
cipher_elg = ElGamal(Curve25519)
plain_text_1: Point = Curve25519.G * 999  # magic number 999, just an example
plain_text_2: Point = Curve25519.G * 777  # magic number 777, just an example
X=C1, C2 = cipher_elg.encrypt_raw(plain_text_1, pub_key)
Y=C3, C4 = cipher_elg.encrypt_raw(plain_text_2, pub_key)
C5 = Curve25519.add_point(C1,C3)
C6 = Curve25519.add_point(C2,C4)
result = cipher_elg.decrypt_raw(pri_key, C5, C6)

print(result == plain_text_1 + plain_text_2)

# >> True

[eNipu]

@lc6chang Thank you for the quick update. Just curious to know if it is possible to remap the result: Point to an Integer. Seems it related to solving ELDLP. i.e. simial to finding 999 given plain_text_1: Point and Curve25519.G But how about making a lookup table for small integers of 4 bytes. Is it practical and will not make the system insecure?

[lc6chang]

1. Yes, it should be The Elliptic Curve Discrete Logarithm Problem. And it is infeasible to find it on a secure elliptic curve.

2. I feel, it depends on the point you choose. For example, if you use Curve25519.G, then a hacker could easily enumerate it. But if you find a true random point, then it should be okay. (sorry, just speaking from my experience. Since I'm just a software engineer, not a mathematician lol 🤣)

[eNipu]

@lc6chang 👍🏾
Yes, the same goes here. By the way, maybe it is possible to encode any random integer less than the order of the curve to a point on the curve without multiplying it to the base point Curve25519.G * 999. right?

I found some answers to it. https://crypto.stackexchange.com/questions/76340/how-to-create-an-ec-point-from-a-plaintext-message-for-encryption

Seems the encode_point function is iterating until it finds a y for a given message x in the curve.

[eNipu]

This paper shows a good method https://eprint.iacr.org/2014/043.pdf

[lc6chang]

@eNipu Thanks for letting me know. Yes, my encode_point just like a toy, using a simplest and unreliable way. You can inherit and override it. Hopefully I can improve it in the future when I have time😊.