Geometric interpretation of an Edwards curve
Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:
(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)
To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.
A curve in Edwards form might look like this:
(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)
However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = left(frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}right).$$
When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).
Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?
elliptic-curves
add a comment |
Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:
(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)
To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.
A curve in Edwards form might look like this:
(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)
However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = left(frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}right).$$
When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).
Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?
elliptic-curves
add a comment |
Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:
(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)
To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.
A curve in Edwards form might look like this:
(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)
However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = left(frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}right).$$
When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).
Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?
elliptic-curves
Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:
(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)
To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.
A curve in Edwards form might look like this:
(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)
However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = left(frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}right).$$
When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).
Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?
elliptic-curves
elliptic-curves
asked yesterday
Ruben De SmetRuben De Smet
812215
812215
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
The normal form (later Edwards form) of an elliptic curve was first introduced by Harlod Edwards in his AMS bulletin by its addition law but gave no geometric interpretation. To give an interpretation of the addition law of two points $P$ and $Q$ you need a function $g_{P,Q}=frac{f_1}{f_2}$ with $div(g_{P,Q})=(P)+(Q)-(mathcal{O})-(P+Q)$ where $mathcal{O}=(0,1)$ is the neutral element. The curve has degree 4, so it has $4times deg(f)$ intersection points with the function $f$. We can choose $f_i$ to be quadratic functions to offer enough freedom of cancellation (8 intersections). Quadratic functions (conic sections) are determined by 5 points. Observing that points at infinity $Omega_1 = (1:0:0)$ and $Omega_2 = (0:1:0)$ are singular and have multiplicity 2, let us determine the conic by passing through $P$, $Q$, $(0,-1)$, $Omega_1$ and $Omega_2$. This let only one more intersection point $P+Q$.
(addition and doubling over $mathbb{R}$ for $d<0$)
This was the first suggestion by Arène, Lange, Naehrig and Ritzenthaler to give a geometric interpretation of the addition law.
add a comment |
The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.
The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).
You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66325%2fgeometric-interpretation-of-an-edwards-curve%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
The normal form (later Edwards form) of an elliptic curve was first introduced by Harlod Edwards in his AMS bulletin by its addition law but gave no geometric interpretation. To give an interpretation of the addition law of two points $P$ and $Q$ you need a function $g_{P,Q}=frac{f_1}{f_2}$ with $div(g_{P,Q})=(P)+(Q)-(mathcal{O})-(P+Q)$ where $mathcal{O}=(0,1)$ is the neutral element. The curve has degree 4, so it has $4times deg(f)$ intersection points with the function $f$. We can choose $f_i$ to be quadratic functions to offer enough freedom of cancellation (8 intersections). Quadratic functions (conic sections) are determined by 5 points. Observing that points at infinity $Omega_1 = (1:0:0)$ and $Omega_2 = (0:1:0)$ are singular and have multiplicity 2, let us determine the conic by passing through $P$, $Q$, $(0,-1)$, $Omega_1$ and $Omega_2$. This let only one more intersection point $P+Q$.
(addition and doubling over $mathbb{R}$ for $d<0$)
This was the first suggestion by Arène, Lange, Naehrig and Ritzenthaler to give a geometric interpretation of the addition law.
add a comment |
The normal form (later Edwards form) of an elliptic curve was first introduced by Harlod Edwards in his AMS bulletin by its addition law but gave no geometric interpretation. To give an interpretation of the addition law of two points $P$ and $Q$ you need a function $g_{P,Q}=frac{f_1}{f_2}$ with $div(g_{P,Q})=(P)+(Q)-(mathcal{O})-(P+Q)$ where $mathcal{O}=(0,1)$ is the neutral element. The curve has degree 4, so it has $4times deg(f)$ intersection points with the function $f$. We can choose $f_i$ to be quadratic functions to offer enough freedom of cancellation (8 intersections). Quadratic functions (conic sections) are determined by 5 points. Observing that points at infinity $Omega_1 = (1:0:0)$ and $Omega_2 = (0:1:0)$ are singular and have multiplicity 2, let us determine the conic by passing through $P$, $Q$, $(0,-1)$, $Omega_1$ and $Omega_2$. This let only one more intersection point $P+Q$.
(addition and doubling over $mathbb{R}$ for $d<0$)
This was the first suggestion by Arène, Lange, Naehrig and Ritzenthaler to give a geometric interpretation of the addition law.
add a comment |
The normal form (later Edwards form) of an elliptic curve was first introduced by Harlod Edwards in his AMS bulletin by its addition law but gave no geometric interpretation. To give an interpretation of the addition law of two points $P$ and $Q$ you need a function $g_{P,Q}=frac{f_1}{f_2}$ with $div(g_{P,Q})=(P)+(Q)-(mathcal{O})-(P+Q)$ where $mathcal{O}=(0,1)$ is the neutral element. The curve has degree 4, so it has $4times deg(f)$ intersection points with the function $f$. We can choose $f_i$ to be quadratic functions to offer enough freedom of cancellation (8 intersections). Quadratic functions (conic sections) are determined by 5 points. Observing that points at infinity $Omega_1 = (1:0:0)$ and $Omega_2 = (0:1:0)$ are singular and have multiplicity 2, let us determine the conic by passing through $P$, $Q$, $(0,-1)$, $Omega_1$ and $Omega_2$. This let only one more intersection point $P+Q$.
(addition and doubling over $mathbb{R}$ for $d<0$)
This was the first suggestion by Arène, Lange, Naehrig and Ritzenthaler to give a geometric interpretation of the addition law.
The normal form (later Edwards form) of an elliptic curve was first introduced by Harlod Edwards in his AMS bulletin by its addition law but gave no geometric interpretation. To give an interpretation of the addition law of two points $P$ and $Q$ you need a function $g_{P,Q}=frac{f_1}{f_2}$ with $div(g_{P,Q})=(P)+(Q)-(mathcal{O})-(P+Q)$ where $mathcal{O}=(0,1)$ is the neutral element. The curve has degree 4, so it has $4times deg(f)$ intersection points with the function $f$. We can choose $f_i$ to be quadratic functions to offer enough freedom of cancellation (8 intersections). Quadratic functions (conic sections) are determined by 5 points. Observing that points at infinity $Omega_1 = (1:0:0)$ and $Omega_2 = (0:1:0)$ are singular and have multiplicity 2, let us determine the conic by passing through $P$, $Q$, $(0,-1)$, $Omega_1$ and $Omega_2$. This let only one more intersection point $P+Q$.
(addition and doubling over $mathbb{R}$ for $d<0$)
This was the first suggestion by Arène, Lange, Naehrig and Ritzenthaler to give a geometric interpretation of the addition law.
edited yesterday
answered yesterday
Youssef El HousniYoussef El Housni
43438
43438
add a comment |
add a comment |
The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.
The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).
You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
|
show 1 more comment
The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.
The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).
You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
|
show 1 more comment
The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.
The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).
You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange
The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.
The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).
You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange
edited yesterday
answered yesterday
ddddavideeddddavidee
2,57611429
2,57611429
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
|
show 1 more comment
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
Sometimes I do actually wonder why people even bother with Weierstrass curves. These Edwards curves seem so much more elegant!
– Ruben De Smet
yesterday
1
1
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
probably because Weierstass curves have been studied at the beginning and maybe we were less aware of the exploitability of timing side channels? (just a supposition)
– ddddavidee
yesterday
3
3
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@ddddavidee I am not sure about the "angles addition" on Edwards curves. This is only an analogy with the circle case but not a geometric interpretation of the addition law. For Weierstrass equations, I think that the interpretation stands for finite fields as well but the line passing through the points to add is $pmod p$ (see 3rd figure: andrea.corbellini.name/2015/05/23/…).
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
@RubenDeSmet another reason for some people not choosing Edwards curves is that they cannot have a prime number of rational points over the base field, and they are therefore incompatible with the prime-order Weierstrass curves used in all of the current cryptographic standards.
– Youssef El Housni
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
I'll undo the accept until I've studied both a bit more myself. Thanks for both answers!
– Ruben De Smet
yesterday
|
show 1 more comment
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66325%2fgeometric-interpretation-of-an-edwards-curve%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown