13
$\begingroup$

There are several well-known techniques to generate pairing-friendly curves of degrees 1 to 36 on prime fields GF(p): Cocks-Pinch, MNT, Brezing-Weng, and several others.

In extension fields GF(p^n), however, one is confined to supersingular curves. In characteristic 2, embedding degrees are <= 4, and in characteristic 3 they are <= 6. In general, they are <= 2.

The question is: is there any known method to generate ordinary pairing-friendly curves over small characteristic fields, with a reasonable (say, 3-20) embedding degree?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

To my knowledge the answer is no.

Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little constraints on its number of points.

(If you're interested in more precise statements and explicit examples, I suggest looking at Lay and Zimmer, Constructing elliptic curves with given group order over large finite fields, which despite its title covers both aspects. Article behind a pay wall unfortunately.)

This works well to find pairing-friendly curves in large characteristic because you have plenty of room to let the cardinal of the base field vary. But it doesn't work well at all over small characteristic fields, because you put both huge constraints on the cardinal of the base field (it has to be a power of the characteristic) and on the number of points on the curve (to achieve a small embedding degree).

In fact, I'd be curious to see even a single example of an ordinary curve with small embedding degree over a not too large binary field, like $\mathbb{F}_{2^{31}}$ say.

Note that this problem is entirely unrelated with the question of constructing ordinary pairing-friendly curves of higher genus over large prime fields, which Freeman's article mentioned above addresses.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I marked the above reply correct because I failed to specify genus in my question --- Freeman does seem to provide pairing-friendly curves in $J(F_{q^k})$ for genus 2. In genus 1, what you say makes sense. $\endgroup$
    – Samuel Neves
    Commented Jan 17, 2012 at 19:45
  • $\begingroup$ If you check the output of Algorithms 4.2 and 5.1 in Freeman's paper, you'll find that all of his curves (and hence their Jacobians) are defined over prime fields. The $J(\mathbb{F}_{q^k})$ in the abstract is about finding where the full r-torsion of the Jacobian in contained. $\endgroup$
    – Mehdi Tibouchi
    Commented Jan 18, 2012 at 1:11
  • $\begingroup$ I should perhaps note, however (and sorry for commenting twice), that in principle, it might be possible to construct pairing-friendly curves over extension fields of a form like $\mathbb{F}_{p^2}$ with the CM method (see e.g. the discussion in 4.1 of Barreto and Naehrig's paper). But $p$ still has to be large and you cannot fix it in advance, so it doesn't solve the problem in small characteristic. $\endgroup$
    – Mehdi Tibouchi
    Commented Jan 18, 2012 at 1:23
  • $\begingroup$ Understood. Should not have just skimmed the paper... $\endgroup$
    – Samuel Neves
    Commented Jan 18, 2012 at 1:51
2
$\begingroup$

What I think your looking for is this paper. It's a modficiation of Cocks-Pinch that was published by Stanford last year. It allows for it to be defined for most k's inside of your extension field.

Improve this answer
$\endgroup$

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.