ElGamal encryption over elliptic curves

ElGamal encryption is a public key encryption system over an elliptic curve that encodes ciphertext encryptions of messages as curve points. The Findora implementation uses the Ristretto group over Curve25519. The “basepoint” G is a fixed element in the Ristretto group used by the implementation. As an optimization, it is the same basepoint used in the Pedersen commitment setup parameters.

ElGamal_keygen() → s, PK

An ElGamal public key is a curve point PK = sG = ec_scalar_multiply(s, G). The secret key is the 256-bit integer s.

ElGamal_embed(m) → M

The message m is embedded into a curve point as M = mG.  

ElGamal_encrypt(M, PK) → (E1, E2)

The ciphertext encryption of M is a pair of curve points E1 = rG = ec_scalar_multiply(r, G) and E2 = rPK + M = ec_add(rPK, M)

ElGamal_decrypt(E1, E2, s) → M

The secret key is s and allows recovery of M = E2 – sE1. The integer value of m may be recovered from M by brute force, which is practical for a 32-bit integer. A 64-bit integer will be split into two 32-bit components that are each encrypted separately.