9
$\begingroup$

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.

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

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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