To encrypt a group element $P$ with public key $K$ and randomness $r$ using ElGamal on elliptic curves with base point $G$ we do the following $(c_1, c_2) = (r\cdot G; P+r\cdot K)$.

When we want to encrypt a free-form message $m$, we have to convert it to a group element $P$ first. For that, we can either use scalar multiplication $P=m\cdot G$ (additively homomorphic) or map the message $P = map(m)$ (multiplicative homomorphic). The former gives not just a point, but a group element. The latter is more complicated.

All methods I found map a message to a curve point (Koblitz's approach, its variant, injective encoding article). However, there is no guarantee that the resulting point belongs to the cyclic group (i.e. has the right order).

So using encoding to just EC point results in not semantically securing ElGamal. It's basically similar to leaking if the message is a quadratic residue or not when using $G_q$ over finite fields with $p = 2q+1$ and messages from $Z_p^*$ without encoding (details about why the leakage happens are here or here).

Is there any way to encode a random message to the EC point of the correct order (i.e. group element)? Is there a way to convert EC point to a group element?

  • 1
    $\begingroup$ The encoding $P=m\cdot G$ has a drawback: it makes decryption computationally intractable. $\endgroup$
    – fgrieu
    Nov 15, 2021 at 16:52
  • 1
    $\begingroup$ Elligator 1 and Elligator 2 $\endgroup$
    – kelalaka
    Nov 15, 2021 at 18:56
  • 1
    $\begingroup$ @fgrieu, true. It works only for a very small message space, plus requires precomputing a table for decryption or many iterations to "recover" $m$ from $m\cdot G$ i.e. break dlog. But so far I don't see any other way to get semantically secure ElGamal while keeping its homomorphic properties. $\endgroup$
    – pintor
    Nov 16, 2021 at 10:14
  • $\begingroup$ @kelalaka, thank you! I'll take a closer look. From the first glance, it seems like an improvement of injective encoding by Fouque et. al. Thus I'm afraid, it's again encoding to a point of the curve and not to its large prime order subgroup (i.e. correct point order is not guaranteed). $\endgroup$
    – pintor
    Nov 16, 2021 at 10:24
  • $\begingroup$ @kelalaka, unfortunately, Elligator doesn’t always give points with the right order. Seems like an open problem in ECC $\endgroup$
    – pintor
    Nov 18, 2021 at 11:06


Your Answer

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