Twisted elliptic curves

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 curve

Suppose p is an odd prime and let E be the elliptic curve with equation

y^2 = x^3 + ax^2 + bx + c

where 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^2 - d is divisible by p. Then the curve E' with equation

dy^2 = x^3 + ax^2 + bx + c

is 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 is

y^2 = x^3 + 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 by

3y^2 = x^3 + 3x + 2

is a twist of E.

Twisted curve

There'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 form

dy^2 = x^3 + ax^2 + bx + c

where 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^2 is 1 and a form in which the coefficient is a non-square. Specifically,

dy^2 = x^3 + ax^2 + bx + c

and

y^2 = x^3 + dax^2 + d^2bx + d^3c

specify 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 coordinates

For a given x, f(x) = x^3 + ax^2 + bx + c is either a square or a non-square. If it is a square, then

y^2 = f(x)

has a solution and

dy^2 = f(x)

does not. Conversely, if f(x) is not a square, then

dy^2 = f(x)

has a solution and

y^2 = 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 cryptography

In 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 posts

• What is an elliptic curve?
• Discriminant of a cubic
• Naming elliptic curves used in cryptography