Pairing-unfriendly curves

A couple days ago I wrote about two pair of closely related elliptic curves: Tweedledum and Tweedledee, and Pallas and Vesta.

In each pair, the order of one curve is the order of the base field of the other curve. The curves in each pair are used together in cryptography, but they don't form a pairing" in the technical sense of a bilinear pairing, and in fact none of the curves are pairing-friendly" as described below.

An elliptic curve E/F_q is said to be pairing-friendly if r divides q^k - 1 for some small k. Here r is the size of the largest prime-order subgroup of the curve, but since our curves have prime order p, r = p.

As for what constitutes a small value of k, something on the order of 10 would be considered small. The larger k is, the less pairing-friendly the curve is. We will show that our curves are extremely pairing-unfriendly.

Since q is not a multiple of p in our examples, there must be some power of q such at

q^k = 1 mod p.

The question is whether k is large, i.e. whether the order of q mod p is large. We could try successive values of k, but that won't get us very far. To be more clever, we use Lagrange's theorem that says the order of an element divides the order of the group. So k must be one of the factors of p - 1. (We subtract 1 because we're looking at the multiplicative group mod p, which removes 0.)

Finding the divisors of n - 1 requires factoring n - 1, which isn't easy, but isn't insurmountable either. The previous post reports the time required to do this in Python and in Mathematica for each of the following values ofn.

p= 2²⁵⁴+ 4707489544292117082687961190295928833
q= 2²⁵⁴+ 4707489545178046908921067385359695873
r= 2²⁵⁴+ 45560315531419706090280762371685220353
s= 2²⁵⁴+ 45560315531506369815346746415080538113

Tweedledum has order p and its base field has orderq.

k = 28948022309329048855892746252171976963322203655954433126947083963168578338816

Tweedledee has order q and its base field has orderp.

k = 28948022309329048855892746252171976963322203655955319056773317069363642105856

Vesta has orderr and its base field has order s.

k = 14474011154664524427946373126085988481681528240970780357977338382174983815168

Pallas has orders and its base field has orderr.

k = 14474011154664524427946373126085988481681528240970823689839871374196681474048

It's safe to say in each casek is not a small number.

The post Pairing-unfriendly curves first appeared on John D. Cook.