Posted by: dbrown
Date: 25 September 2007 18:12
I think this paper makes a valid point (see below).
I plan to update standards X9.62/63 and SEC1 accordingly. I may submit a comment to have IEEE 1363 amended in its upcoming schedule revision.
* * *
I now paraphrase my understanding of the point, mainly because it took me a few tries to get it.
Background: Pairings map elliptic curve points (actually, pairs thereof) to field elements. Useful pairings are bilinear and non-degenerate, which implies that the order of the inputs are the outputs are the same, say some prime n. If the elliptic curve is defined over a field of order q, the output of the pairing is defined over a field of order q^k, where k is called the embedding degree, which is the smallest value of k such that n|q^k-1.
Main result of paper: If q=p^m for a prime p, then we may have also have n|p^t-1, where t|km. If t<km, then the output of the pairing actually falls into a smaller subfield of order p^t inside of the field of order q^k. The discrete logarithm problem DLP in the field of p^t could be easier than in the field of order q^k. The DLP in the elliptic curve group is therefore no harder than than the DLP is no harder than in the field of order p^t which is potentially easier than in the field or order q^k, which was the previous measure of what q and k were acceptable. Therefore, one has to watch for this and make sure that p^t is large enough, not just q^k.
Incidentally, one may say that the effective embedding degree is actually t/m, since n|q^(t/m)-1. Other authors have considered such "fractional embedding degrees", but mainly in the context of supersingular curves with p large and m small (e.g. 2). This paper focusses on the case of p=2 and 162<m<572.
I'm pretty sure that the NIST curves pass this revised test, but I will investigate.