2
$\begingroup$

I understand that an elliptic curve $E$ over a field $K$ has an associated twist, that is another elliptic curve which is isomorphic to $E$ over an algebraic closure of $K$.

Which cryptographic benefits do twists of elliptic curves bring?

$\endgroup$
3

1 Answer 1

3
$\begingroup$

A short answer;

We want fast and secure arithmetic and sometimes the twist of a curve may produce secure and faster arithmetic;

  • EdDSA : Ed25519 : twisted Edwards curve :

    High-speed high-security signatures - 2011 Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang

    • Fast
      • fast single-signature verification
      • Even faster batch verification.
      • Very fast signing
      • Fast key generation
    • Secure
      • No secret branch conditions
      • No secret array indices
      • Uses a twisted Edwards curve that is birationally equivalent to the curve Curve25519 implied ECDLP is equivalent to Curve25519

From rfc8032 : Edwards-Curve Digital Signature Algorithm (EdDSA)

The Edwards-curve Digital Signature Algorithm (EdDSA) is a variant of Schnorr's signature system with (possibly twisted) Edwards curves.

So, whenever there is a benefit, the twist can be used.


A note on the birationally equivalence

Birationally equivalence is the relaxation of the isomorphism where we want some of the points not mapped with the forward and backward birational maps.

Now, we know that Discrete Logarithms are random self-reducibility. What this tells us; if we can solve Dlog in one base then we can solve any base. (Solve for base $G$ the find $P = [a]G$ for base $P$ and see $S = [t]P = [ta]G$..)

By using this and birationally equivalence we can argue that if Dlog hard in Curve25519 then DLog is hard in the twisted Edwards curve. too. If easy then it is easy there too. Just map the points and solve them. If the points are not mappable then use some other as a base use random self-reducibility.

$\endgroup$
4
  • $\begingroup$ Could be enhanced by indicating if using the twisted curve would create fully compatible results. $\endgroup$
    – Maarten Bodewes
    Oct 20, 2023 at 23:02
  • $\begingroup$ @MaartenBodewes do you mean the points are not mapped due to birationally equivalence? they are finite, however, the main point of birational equivalence is Our recommended curve for EdDSA is a twisted Edwards curve birationally equivalent to the curve Curve25519 from [12]. Any efficiently computable birational equivalence preserves ECDLP difficulty, so the well-known difficulty of computing ECDLP for Curve25519 immediately implies the difficulty of computing ECDLP for our curve. Not really mapping the points... Otherwise we need to consider the to exclude the non-mapping points! $\endgroup$
    – kelalaka
    Oct 20, 2023 at 23:27
  • $\begingroup$ @kelalaka how do twists bring faster arithmetic in comparison with protocols that don't use them (asking because unified addition is also available for Edward curves that are not twisted)? $\endgroup$
    – pacman
    Oct 21, 2023 at 7:23
  • 1
    $\begingroup$ There is no magic but deep study there. When you get the quadratic twist, you need to see what you get get this from this twist. This requires looking from the coordinate systems to protocols that can benefit from this. For study, you can generate a random Edward's curve ( possibly large ) and see what this twist can be useful or not. $\endgroup$
    – kelalaka
    Oct 21, 2023 at 9:32

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.