Comment on page

# 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.Last modified 5mo ago