2
$\begingroup$

Is elliptic curve point multiplication semantically secure? I'd like to know if there are some sets of elliptic curve parameters (e.g. NIST curves) that are proved to be semantically secure or that are not disproved.

By "elliptic curve point multiplication is semantically secure", I mean the following:

Suppose an elliptic curve over a finite field $\mathbb{F}_p$ where $p$ is a prime number. The equation is $y^2 = x^3 + ax + b$. $G$ is a base point and it generates all the points $E = \{G, 2G, ..., (q-1)G, \mathcal{O}\}$ in the curve. Here $q$ is prime and it is the order of the curve. We have the following cryptosystem:

  • The encryption of a point $P$ ($P \ne \mathcal{O}$) is $sP$ where $s$ is a random secret key and $1 \le s < q$.
  • The decryption of a point $Q$ is $s^{-1}Q$ where $ss^{-1} \equiv 1 \mod q$

Suppose there is a set of $n$ distinct points $\{P_1, P_2, ..., P_n\}$ and their encryptions $\{Q_1, Q_2, ..., Q_n\}$ with a secret key $s$. The orders are not necessarily the same, i.e. $Q_1$ might or might not be the encryption of $P_1$. If it is infeasible to determine which encryption belongs to which point better than random guessing, then this cryptosystem is semantically secure.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

If an attacker can choose the points $P_i$, than this system is not semantically secure. For example, they may choose $P_2=2P_1$, and the corresponding encryption $Q_2$ would be equal to $2Q_1$.

If the points are chosen at random, this system is semantically secure if decisional Diffie-Hellman assumption holds for the curve. This assumption is presumed to hold for elliptic curves typically used in cryptography, unless the curve is chosen to have a bilinear pairing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! The points are indeed chosen randomly. It seemed to me that this looked like semantically secure but I had no proof to back up. Your mention of DDH will be helpful. But it is distinguishing $(g^a, g^b, g^{ab})$ and $(g^a, g^b, g^c)$ in the original DDH, and my problem is finding which is which between $(g^a, g^b)$ and $(g^{as}, g^{bs})$. Are these two problems equivalent? I can see that solving my problem leads to solving the DDH, but I'm not sure how the opposite can be true. $\endgroup$
    – Chungmin Lee
    Commented Sep 22, 2014 at 3:23
  • $\begingroup$ If you set $h=g^a$, you see that you can't even distinguish $(h,h^{b/a},h^s,h^{(b/a)s})$ from four random points, which means you also can't determine if the last two points are swapped. $\endgroup$
    – abacabadabacaba
    Commented Sep 22, 2014 at 3:29

Your Answer

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

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