Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing

Question

Are there any examples of practical attacks on cryptosystems set over elliptic curves which utilize the easiness of DDH for certain choices of curves $E(\textbf{F}_q)$, and as such their lack of semantic security? I'm looking for something along the lines of using the Jacobi symbol to narrow the set of possible plaintexts (and therefore cards) against the SRA algorithm in the original Mental Poker proposal.

For instance, Elliptic Curve ElGamal Encryption doesn't seem to omit one. As the ciphertext is $(rP, M + rQ)$, where $r \in \mathbb{Z}$ is random and private, $M \in E(\textbf{F}_q)$ is the plaintext, and $P, \, Q \in E(\textbf{F}_q)$ are public, even if an attacker who can solve the DDH can distinguish elements of the ciphertext, the randomness of $r$ would seem to prevent them from narrowing the search space.

My inclination is no, since the relevance of semantic security predates the advent of ECC and so such an attack would likely have at least been considered heuristically, but I figured I'd see if anyone was aware of anything.

Answer 1

Proposition One-wayness of ElGamal encryption holds under the Computational Diffie-Hellman (CDH), and conversely.

CDH Problem (informally) Given $(P, [r]P, [s]P)$ find $[rs]P$.

Let the public key be $Q = [s]P$ where $s$ is the corresponding secret key. Let also a ciphertext $C = (C_1, C_2)$ with $C_1 = [r]P$ and $C_2 = M + [r]Q$ for a message $M$ (viewed as a point on an elliptic curve).

Proof (of the proposition):

1. If you can solve the CDH then you can break the one-wayness of the encryption.
   Suppose you are given a ciphertext $C = (C_1, C_2)$, the goal is to recover the corresponding plaintext. On input $(P,C_1,Q)$, you first obtain $[rs]P$ by solving the CDH. Next you recover the plaintext as $M = C_2 - [rs]P$.
2. If you can break the one-wayness of the encryption then you can solve the CDH.
   Suppose you are given a DH triple $(P,[r]P,[s]P)$, the goal is to obtain $[rs]P$. You define the ciphertext $C = (C_1,C_2)$ where $C_1 = [r]P$ and $C_2$ is a random point. You define the public key as $Q := [s]P$. You recover the corresponding message $M$ (because you can break the one-wayness) and find $[rs]P$ as $[rs]P = M - C_2$.