13 ms·

Double-Odd Elliptic Curves

Sniffnoy 5y ago
"Double-odd" is a confusing term. Makes it sound like it's odd in two ways. A more common term for a number that's 2 mod 4 is "singly even" (because 2 only divides it once).
- rdpintqogeogsaa 5y ago
  Let's just do the same we do with other classes of curves: Name them after the person who either came up with or popularized them. Thus, we might as well just call them Pornin curves (in line with Edwards curves and Montgomery curves and [short] Weierstrasse curves and Koblitz curves).
  - a1369209993 5y ago
    Edwards, Montgomery, and Weierstrasse are actually representations for elliptic curves (eg curve25519 is usually represented as a Montgomery curve, but a Edwards representation for the same curve is used in ed25519 ECDSA).
ljhsiung 5y ago
Slightly tangential-- to my knowledge, many common curves (e.g. secp256k1 i.e. bitcoin) use order == 3 mod 4 because it enables usage of quick Tonelli-Shanks shortcuts [1],[2]. Perhaps the claim that the selection of the curve has no cofactor, and thus doesn't require the validation cost of e.g. clearing the cofactor, ensuring torsion safety. Not sure what other performance tricks this type of curve may enable. I'm still reading and understanding how precisely they select the curves to have no cofactor, but that's definitely interesting. There's more desirable security considerations than just a low cofactor, however; but going through the paper, they definitely check a lot of other boxes. [1] https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorit... [2] https://go-review.googlesource.com/c/go/+/11522/ https://go-review.googlesource.com/c/go/+/11522/
- tromp 5y ago
  > the curve has no cofactor The groups do have a cofactor of 2 ("Curve order must be equal to 2r for a prime integer r"). When they say "There is no cofactor to deal with", they mean they pick a generator that's divisible by 2 (like G=(2,2) in do255e) and use curve point representations that only allow multiples of G.
gerdesj 5y ago
The article is proscriptive. Would someone please tell me as a civilian, what these things actually mean and why they are important.
- segfaultbuserr 5y ago
  My reading of the report: this is a new type of elliptic curve for cryptography and it's 20%+ faster than Curve25519 - which previously set the standard of a good elliptic curve, with comparable security.
lanecwagner 5y ago
For anyone that needs an intro to ECC in general: https://qvault.io/cryptography/elliptic-curve-cryptography/ https://qvault.io/cryptography/elliptic-curve-cryptography/

"Double-odd" is a confusing term. Makes it sound like it's odd in two ways. A more common term for a number that's 2 mod 4 is "singly even" (because 2 only divides it once).

rdpintqogeogsaa 5y ago
Let's just do the same we do with other classes of curves: Name them after the person who either came up with or popularized them. Thus, we might as well just call them Pornin curves (in line with Edwards curves and Montgomery curves and [short] Weierstrasse curves and Koblitz curves).
- a1369209993 5y ago
  Edwards, Montgomery, and Weierstrasse are actually representations for elliptic curves (eg curve25519 is usually represented as a Montgomery curve, but a Edwards representation for the same curve is used in ed25519 ECDSA).

ljhsiung 5y ago

Slightly tangential-- to my knowledge, many common curves (e.g. secp256k1 i.e. bitcoin) use order == 3 mod 4 because it enables usage of quick Tonelli-Shanks shortcuts [1],[2]. Perhaps the claim that the selection of the curve has no cofactor, and thus doesn't require the validation cost of e.g. clearing the cofactor, ensuring torsion safety. Not sure what other performance tricks this type of curve may enable. I'm still reading and understanding how precisely they select the curves to have no cofactor, but that's definitely interesting. There's more desirable security considerations than just a low cofactor, however; but going through the paper, they definitely check a lot of other boxes. [1] https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorit... [2] https://go-review.googlesource.com/c/go/+/11522/ https://go-review.googlesource.com/c/go/+/11522/

tromp 5y ago
> the curve has no cofactor The groups do have a cofactor of 2 ("Curve order must be equal to 2r for a prime integer r"). When they say "There is no cofactor to deal with", they mean they pick a generator that's divisible by 2 (like G=(2,2) in do255e) and use curve point representations that only allow multiples of G.

gerdesj 5y ago

The article is proscriptive. Would someone please tell me as a civilian, what these things actually mean and why they are important.

segfaultbuserr 5y ago
My reading of the report: this is a new type of elliptic curve for cryptography and it's 20%+ faster than Curve25519 - which previously set the standard of a good elliptic curve, with comparable security.

lanecwagner 5y ago

For anyone that needs an intro to ECC in general: https://qvault.io/cryptography/elliptic-curve-cryptography/ https://qvault.io/cryptography/elliptic-curve-cryptography/