6
$\begingroup$

In recent studies on elliptic curve cryptography, Edwards curves are remarkable examples on this field. Studies show that this kind of elliptic curves provide faster computation compared to Weierstrass form.

The following equation is called an Edward Curve $$x^2 + y^2 = 1 + d\cdot x^2\cdot y^2$$ or $$x^2 + y^2 = c^2 \cdot (1+d\cdot x^2y^2)$$

If $(x_1, y_1)$ and $(x_2, y_2)$ are points on an Edwards curve, then new point calculated by addition formula would be still on the curve as illustrated below.

$$(x_1, y_1) + (x_2, y_2) = (x_3, y_3)$$ where:

$$\begin{align} x_3 &= \frac{(x_1\cdot y_2+x_2\cdot y_1)}{(1+d\cdot x_1\cdot x_2\cdot y_1\cdot y_2)}\\ y_3 &= \frac{(y_1\cdot y_2-x_1\cdot x_2)}{(1-d\cdot x_1\cdot x_2\cdot y_1\cdot y_2)}\\ \end{align}$$

Proofs of addition formulas for conventional Weierstrass form exist. However, I cannot find any proof for Edwards curve addition formulas. Where do they come from?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "proof of addition formula"? The proof that the resulting operation gives an abelian group? $\endgroup$ – yyyyyyy Jan 31 '17 at 8:44
  • 1
    $\begingroup$ In other words, how x3 and y3 equations retrieved / extracted? $\endgroup$ – johncasey Jan 31 '17 at 10:20
  • $\begingroup$ Did you check wikipedia [en.wikipedia.org/wiki/Edwards_curve]? It has all the references you are looking for. $\endgroup$ – 111 Jan 31 '17 at 23:57
6
$\begingroup$

I think this is a good question, but not one with an easy answer. Let me give it a go anyway.

First of all, let's focus on the classic Weierstrass case. The points on an elliptic curve $E$ in this shape form a group. We can do this by the standard way (in most cases): draw a line between two points $P$ and $Q$, intersect at a unique third point, and invert across the $x$-axis. The resulting point $R$ is defined to be $P+Q$. Many standard texts indeed provide proofs that the points with this operation form a group.

Now, as you may have noticed, this way of defining the group depends very much on the way we represent the elliptic curve. That is, it assumes that we write $E$ as the set of solutions to $y^2=x^3+ax+b$. Can we also define the group law without making this assumption? The answer is yes.

How to do this, is quite complicated. Think of an elliptic curve $E$ as a very abstract object, not even assuming how to represent its points. It can be shown, that there exist some group attached to $E$, which is the degree-0 group of something called the Picard group. We denote it by $\operatorname{Pic}^0(E)$. Even more, it can be shown that there is a bijection between the points of $E$ and elements of $\operatorname{Pic}^0(E)$. Because $\operatorname{Pic}^0(E)$ is a group, so are the points on $E$.

So, we know that the points on $E$ form a group. How do we compute it? Well, it depends on how we represent points on $E$. If we choose to write points as $(x,y)$, where $y^2=x^3+ax+b$, then it is the classical way. If we choose to write points on $E$ as $(u,v)$ where $u^2+v^2=1+du^2v^2$, then it is done in the way you described.

TLDR How do we prove that your $x_3$ and $y_3$ are correct? As above, we need to prove that they correspond to a point on $E$ such that it corresponds exactly to the group law defined by $\operatorname{Pic}^0(E)$. For this specific case, your best bet is the original paper or the cryptographic application paper. In particular I would look at section 3 of the latter paper.

$\endgroup$
  • 1
    $\begingroup$ I just have to ask: Did you e-mail subscribe / RSS-subscribe to the elliptic-curves tag? $\endgroup$ – SEJPM Jan 31 '17 at 20:58
  • $\begingroup$ @SEJPM No I did not. But I cant deny preferring it over other tags (my username kind of gives it away). $\endgroup$ – CurveEnthusiast Jan 31 '17 at 21:04
  • $\begingroup$ @CurveEnthusiast suppose we have a new model of EC and want to derive an explicit addition law. Can we derive it directly from its Picard group or the best way to proceed would be to derive an equivalence with a Weierstrass curve and walk the Weierstrass addition law backwards to the target model ? $\endgroup$ – Ruggero Feb 1 '17 at 12:22
  • $\begingroup$ @Ruggero Probably depends on how you derived your model. If you derived it from the Weierstrass model, you may want to show equivalence of their respective addition laws. If you did it differently, there may be a nice interpretation of the group law (for example, by intersecting with planes instead of lines). For example, iirc you can look at an elliptic curve as an intersection of two quadrics, and then the addition law can be interpreted by intersecting these quadrics with planes. $\endgroup$ – CurveEnthusiast Feb 1 '17 at 17:20
2
$\begingroup$

This is actually a reference request, anyway: according to Edwards "A Normal Form for Elliptic Curves", this addition law was introduced by Gauss with reference to Euler.

http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf

$\endgroup$
  • $\begingroup$ Yes, you are definitely right! But I wonder the proof of Gauss or Euler. I cannot find these proofs anywhere. $\endgroup$ – johncasey Nov 26 '18 at 10:34
1
$\begingroup$

Another very good reference is here. In these slides, there is a very good (and intuitive) explanation for the addition formula you are looking for. The proof consist from three steps.

  1. Prove that the initial curve is elliptic (has genus 1)

  2. Find exactly the birational map from the initial Edward's curve to the Weierstrass model. and finally,

  3. Use the well known addition formula over the Weierstrass model and transfer (via the birational map) to the Edward's curve.

$\endgroup$
1
$\begingroup$

I have been working on understanding Edwards addition formula and finally, I found an answer. In the paper A normal form for elliptic curves, Harold Edwards proves the correctness of the addition formula by mathematical induction. He showed that new point $P_3(x_3, y_3)$'s exact value derived from the known points $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$ must satisfy the elliptic curve equation only if addition formula is valid.

I also study on Euler's and Gauss's work but they are really confusing.

$\endgroup$
0
$\begingroup$

Hales proposed and verified a proof for the group law of elliptic curves in Edwards form. It does not use sophisticated tools. I'm currently porting his proof fully into a proof assistant.

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