Score:2

# ElGamal with elliptic curves and semantic security

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?

The encoding $P=m\cdot G$ has a drawback: it makes decryption computationally intractable.
[Elligator 1 and Elligator 2](https://elligator.cr.yp.to/)
@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.
@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).
@kelalaka, unfortunately, Elligator doesn’t always give points with the right order. Seems like an open problem in ECC