2
$\begingroup$

I'm trying to find a Python library that implements Elgamal Encryption on the Elliptic curve i.e X25519 or P-256.

My purpose is to use the additive homomorphic property of Elgamal. I'm using https://github.com/data61/python-paillier Python library for Paillier to have additive homomorphism. However, since I'm only encrypting small integers(32bit). Therefore, I think Elgamal will be faster for encryption and will have a shorter key and cipher size than Paillier [If my conceptual understanding is correct].

Hope someone already implemented and using such a library. Looking forward to knowing such a production-grade library.

I found a library that says they implemented Lifted-Elgamal (not sure what Lifted means here) https://github.com/herumi/mcl However, it seems they use Type-3 pairing to achieve multiplicative homomorphism in Elgamal. To my understanding pairing operation is expensive since the underlying operations are carried over the extension over the prime field.

$\endgroup$
6
  • 2
    $\begingroup$ Welcome to crypto-SE! "Lifted" refers to Hensel lifting, Importantly, our site does not do software recommendations, see whats on-topic. I suggest reformulating the question to state your objective from a crypto standpoint independently of a programming language (a Python library is not an objective worth discussion here; it's a mean). $\endgroup$
    – fgrieu
    Mar 10, 2021 at 5:56
  • $\begingroup$ You should check out PyCryptodome: pycryptodome.org/en/latest/src/public_key/public_key.html. It's a well-known library and is a dependency for thousands of Github projects. PyNaCl also implements Curve25519: pynacl.readthedocs.io/en/latest/public/#nacl.public.PrivateKey $\endgroup$
    – Evan Su
    Mar 10, 2021 at 14:23
  • $\begingroup$ @HACKERALERT, thank you. Will check the links if they support the Elgamal for additive homomorphism. $\endgroup$ Mar 10, 2021 at 14:57
  • 1
    $\begingroup$ @fgrieu I have two objectives. 1st is to reduce the ciphertext size that I'm doing with Paillier. 2nd is to improve the encryption operation. The alternative which came into my mind is Elgamal that supports additive homomorphism. Since Elgamal can be implemented using the Elliptic curve over the prime Field, then I thought it will reduce the ciphertext size since the prime modulus will be 265bit (compared to |n^2|=4096bit if the primes are 1024bit in Paillier). Then, posted here to make sure if my understanding is valid and if anyone already implemented such thing in python or not. $\endgroup$ Mar 10, 2021 at 16:58
  • $\begingroup$ I suggest moving the above in the question. But what matters most (and remains untold) is why/if you need homomorphic encryption in the first place; or perhaps just the maximum $m$ for integers of the ciphertext after straight homomorphic addition, if that's the application. Problem is translating back the deciphered result into an integer. For Pailler that's part of the decryption; for ElGamal in $\mathbb Z_p^*$ there are standard ways. But for ElGamal in P-256, AFAIK, the cost is going to raise like $O(\sqrt m)$, and highly specific code is required. $\endgroup$
    – fgrieu
    Mar 10, 2021 at 17:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Actually, if you have a large precomputed table, you can perform baby-step/giant-step in fewer than $\Theta(\sqrt{a})$ operations (not counting the one-time computation of the precomputed table); for example, if you precompute $256i \cdot G$ for $0 \le i < 2^{24}$, you can find $a \in [1, ..., 2^{32}]$ given $aG$ in 256 steps by computing $aG+jG$ for $j=0, .., 255$, and searching for the common value in the lists... $\endgroup$
    – poncho
    Mar 11, 2021 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.