EC-ElGamal Encryption

We use the EC-ElGamal encryption as a backing encryption because it is an additively homomorphic encryption.

We use the curve defined in Ed25519 for our implementation because this curve is well battle-tested and efficient.

The decrypted message of the EC-ElGamal encryption is the scalar multiplication between the original plaintext and the base point G. Thus we should solve the discrete logarithm problem (DLP) to retrieve the original plaintext.

The DLP is generally difficult to solve, but if we limit the message size in some range n (say 0-2^24), we can solve the DLP by brute force. For this purpose we pre-generate [O, G, 2G, ..] array as the filename mG.bin for fast lookup for the solution. Pre-generation takes some time (O(n)) which is one-time, and if we utilize binary or interpolation search to the pre-generated points, we can efficiently solve the DLP with complexity O(log(n)) for each decryption process.