We'll say that asymmetric encryption is homomorphic below $\ell$ when, given the public key and ciphertexts $C_i$ obtained from plaintexts assimilated to integers $a_i\in\mathbb N$ such that $\ell>\sum a_i$, it can be efficiently computed ciphertext $C$ that deciphers to $a=\sum a_i$.
The best known example is Pailler encryption, which when the secret primes are 1024‑bit is homomorphic below $2^{2046}$. That's more than ample for many applications, so the limit $\ell$ is typically unstated.
The question asks an equivalent using ElGamal encryption on a standard Elliptic Curve group such as X25519 or P-256, with the stated goals:
- reduce the ciphertext size
- "improve the encryption operation", which I take as making at least encryption faster.
Both are possible, but as far as I know that comes with a serious limitation: the cost of decryption¹ grows about as $\Theta(\sqrt a)$ where $a$ is the plaintext. That's thus not even a cipher by the modern definition of that, which would require cost polynomial in $\log a$. However the question is "only encrypting small integers (32bit)", thus that might be tolerable.
Using the notation in the definition of P-256 aka secp256r1 in SEC2, that variant of ElGamal encryption goes:
- The curve has a generator $G$ forming an Elliptic Curve group of prime order $n$ with $\log_2(n)\approx256$
- A point on the curve other than the neutral can be defined by it's $x$ coordinate in $[0,p)$ and the parity of it's $y$ coordinate, and fits 257 bits or 33 bytes.
- The private key is a random secret integer $d$ drawn about uniformly randomly in $[1,n)$
- The public key is the point $Q$ of the curve computed as $Q\gets d\,G$. Recall that this scalar multiplication on the Elliptic Curve gives the same $Q$ as would computing $\underbrace{G+G+\ldots+G}_{d\text{ terms}}$, but can be performed with $\approx512$ point additions in the Elliptic Curve group (refer to SEC1).
- Encryption of integer $a\in [0,n)$ goes:
- Draw a random secret integer $k$ about uniformly randomly in $[1,n)$
- Compute $R\gets k\,G$ and $S\gets a\,G\,+\,k\,Q$.
- Output ciphertext $(R,S)$ (it's like 66 bytes).
- Decryption of ciphertext $(R,S)$ goes
- Check that $R$ and $S$ are on the curve
- Compute $A\gets (n-d)R\,+\,S$
- Find integer $a\in [0,n)$ with $a\,G=A$.
It's easy to verify that
- decryption (if we can manage it's last step) recovers the plaintext $a$;
- if $a_i$ has enciphered to $(R_i,S_i)$, and $n>\sum a_i$, then $(\sum R_i,\sum S_i)$ [where the summations are point additions in the Elliptic Curve group] deciphers to $\sum a_i$ [where the summation is ordinary addition]: our modified ElGamal encryption is homomorphic below $n$.
I think security is somewhat reducible to some well-studied problem (is it DDH?).
The catch is: we don't know how to perform the last decryption step for cost¹ less than $\Theta(\sqrt a)$. For plaintext $a$ limited to 32-bit, Baby-Step/Giant-Step is probably the method of choice: it's simple; has predictable runtime; is straightforward to implement in pure Python on a standard PC if we brush aside resistance to side-channel attacks.
The whole endeavor is a useful exercise, and can be done from scratch in like a day for one with a good understanding of Elliptic Curve Cryptography, programming, and some exposition to Python. About half the work is implementation of the code doing point addition and multiplication, which exists in many open-source projects²
Difficulty grows sharply if we want a secure implementation, or acceptable speed for much larger $a$. For the later, we'd want Pollard's Rho with distinguished points, which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.
¹ This is the cost for a single decryption, including precomputations. These precomputations can be performed before the ciphertext is available, and amortized across multiple decryptions, see poncho's comment.
² For NIST's P-256, P-384, P-521 curves, pycryptodome's EccPoint looks like it can be used without re-engineering the interface. This is not a recommendation: I've not used or reviewed that code. And from the perspective of learning crypto (rather than the joys and pitfalls of code reuse), it's better to implement that too.
