1
$\begingroup$

Consider the solutions of the equation $y^2 = x^3 \pmod p$ for some prime $p=6k+1$. When considered as an elliptic curve, it has a cusp at $(0, 0)$, and addition involving this point doesn't work out. Let's remove this point. It seems that what remains is a cyclic group of order $p$, satisfying the regular elliptic curve addition (and hence also scalar multiplication).

To verify the size, notice that the points form $(p-1)/6$ packs of size 6 given by $\pm A_i ,\pm B_i, \pm C_i$ satisfying $A_i + B_i + C_i = \mathcal O$ and each has the same $y$ coordinate. When we consider the identity element $\mathcal O$ also, we get to exactly $p$ points.

Questions:

  1. Is this really a cyclic group of order $p$ under regular EC addition?
  2. Is DLP (discrete logarithm problem) easy in this group?

Update: I'm starting to think there should be a very easy DLP algorithm for this curve.

This elliptic curve satisfies the ideal pairing property: If $aG = (x_1, y_1)$ and $bG = (x_2, y_2)$ then $abG = (x_1x_2, y_1y_2)$. Namely given $aG$, $bG$, we can efficiently find $abG$

This means that if DLP was hard on this curve, we would get simple fast FHE. So almost certainly there is a very simple algorithm to perform point to point division in this curve (aka DLP). Please let me know how this can be done.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ If you exclude the cusp, the set of points form a group under the usual group operation. This group is isomorphic to the field under addition. See Proposition III.2.5 in Silverman's The arithmetic of elliptic curves 2nd ed. Which means, (1) yes, (2) yes. $\endgroup$
    – K.G.
    Commented Sep 26 at 21:31

1 Answer 1

Reset to default
2
$\begingroup$

Fix the generator $G=(1,1)$. Given a point $kG = (x,y)$ on this curve, one can calculate $k=x/y$.

So there is a very simple algorithm to perform point to point division.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I realize this is a self-answer, but I'm wary of Answers that are significantly shorter than the Question being addressed. I think there are a number of aspects of the computation that could be fleshed out, perhaps with a succinct summary of information to be found elsewhere on StackExchange or the Internet at large. $\endgroup$
    – hardmath
    Commented Sep 26 at 2:07
  • $\begingroup$ @hardmath Thank you, this is fair. I don't have an elegant enough derivation yet. I'm working on it though! $\endgroup$
    – MERTON
    Commented Sep 26 at 2:48

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.