I am curious why people use elliptic curve in cryptography. I know the main requirement is DLP, but elliptic curve is not the only curve with such property. Some of curves seem to be even simpler.

As an example, we can consider a circle given by the equation:

$$ x^2 + y^2 = 1 (mod p) $$

where $ x, y $ in $ Z_{p} $, $ p $ is prime. And the rule for addition is:

$$ (x_1, y_1) + (x_2, y_2) = (x_1 x_2 - y_1 y_2, x_1 y_2 + x_2 y_1) $$

that can be also written as:

$$ P_1 = (x_1, y_1) $$ $$ P_2 = (x_2, y_2) $$ $$ P_{1+2} = P_1 + P_2 = (x_{1+2}, y_{1+2}) $$ $$ x_{1+2} = x_1 x_2 - y_1 y_2 $$ $$ y_{1+2} = x_1 y_2 + x_2 y_1 $$

I think the circle has some benefits towards elliptic curve:

  1. Easier to understand and to interpret.
  2. Better performance, because we have fewer operations in the addition rule.
  3. Easier to research for "good" primes $ p $ in cryptography tasks, because the number of points on the circle can be calculated much easier than using Schoof's algorithm.

As far as I know, the presence of DLP is an unprovable fact. So we can only prove that there is no DLP, and if we haven't found this prove we can think that there is DLP. I have made a research and haven't found that there is no DLP for the circle, that makes me think it is a good curve to use in cryptography.

On the other hand, it is obvious that circle looks simpler than elliptic curve, that makes me think people tried to use circle in cryptography but left this idea because of something. Does anybody have some thoughts about why people don't use circle? Or perhaps, is there some literature about it?

  • 2
    $\begingroup$ Firstly, prove that your addition law yields a group. $\endgroup$ – fkraiem May 10 '19 at 9:40
  • $\begingroup$ @fkraiem It does. $\endgroup$ – Fomalhaut May 10 '19 at 9:57
  • 2
    $\begingroup$ Welcome to Crypto.SE! There's a a nice answer here: crypto.stackexchange.com/a/11524/58690. P.S: Maybe the "it does" proof needs some elaboration. ;) $\endgroup$ – Marc Ilunga May 10 '19 at 10:02
  • $\begingroup$ @MarcIlunga Thank you, it is nice note. I've had a look at the answer. Perhaps, "the discrete logarithm in this group is no stronger than the discrete logarithm over the underlying field" is the answer I need. $\endgroup$ – Fomalhaut May 10 '19 at 10:25