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

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.

• Well there's the MOV attack which breaks the discrete logarithm in subexp time, but it only works for a negligible amount of curves. – fkraiem Jun 5 '16 at 15:02

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).
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$.
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$.