# 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.ellipticpir.com/technology/ec-elgamal-encryption.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.