This morning I was sitting at a little bakery thinking about what to do before I check out of my hotel.
I saw that the name of the bakery was Twist Bakery & Cafe, and that made me think of writing about twisted elliptic curves when I got back to my room.
Twist of an elliptic curveSuppose p is an odd prime and let E be the elliptic curve with equationy² = x³ + ax² + bx + cwhere all the variables come from the integers mod p.
Now pick some d that is not a square mod p, i.
e.
there is no x such that x² – d is divisible by p.
Then the curve E‘ with equationdy² = x³ + ax² + bx + cis a twist of E.
More explicit it’s a quadratic twist of E.
This is usually what people have in mind when they just say twist with no modifier, but there are other kinds of twists.
Let’s get concrete.
We’ll work with integers mod 7.
Then the squares are 1, 4, and 2.
(If that last one looks strange, note that 3*3 = 2 mod 7.
) And so the non-squares are 3, 5, and 6.
Suppose our curve E isy² = x³ + 3x + 2.
Then we can form a twist of E by multiplying the left side by 3, 5, or 6.
Let’s use 3.
So E‘ given by3y² = x³ + 3x + 2is a twist of E.
Twisted curveThere’s something potentially misleading in the term “twisted curve”.
The curve E‘ is a twist of E, so E‘ is twisted relative to E, and vice versa.
You can’t say E‘ is twisted and E is not.
But you might object that E‘ has the formdy² = x³ + ax² + bx + cwhere d is a non-square, and E does not, so E‘ is the one that’s twisted.
But a change of variables can leave the curve the same while changing the form of the equation.
Every curve has an equation in which the coefficient of y² is 1 and a form in which the coefficient is a non-square.
Specifically,dy² = x³ + ax² + bx + candy² = x³ + dax² + d²bx + d³cspecify the same curve.
The two curves E and E‘ are not isomorphic over the field of integers mod p, but they are isomorphic over the quadratic extension of the integers mod p.
That is, if you extend the field by adding the square root of d, the two curves are isomorphic over that field.
Partitioning x coordinatesFor a given x, f(x) = x³ + ax² + bx + c is either a square or a non-square.
If it is a square, theny² = f(x)has a solution anddy² = f(x)does not.
Conversely, if f(x) is not a square, thendy² = f(x)has a solution andy² = f(x)does not.
So a given x coordinate either corresponds to a point on E or a point on E‘, but not both.
Application to cryptographyIn elliptic curve cryptography, it’s good if not only is the curve you’re using secure, so are its twists.
Suppose you intend to work over a curve E, and someone sends you an x coordinate that’s not on E.
If you don’t check whether x corresponds to a point on E, you are effectively working on a twist E‘ rather than E.
That can be a security hole if E‘ is not as secure a curve as E, i.
e.
if the discrete logarithm problem on E‘ can be solved more efficiently than the same problem on E.
Related postsWhat is an elliptic curve?Discriminant of a cubicNaming elliptic curves used in cryptography.