# Are Koblitz curves paring friendly?

I want to implement an identity based encryption scheme using Koblitz curves as scalar multiplication is faster due to Frobrenius endomorphism.

How can I tell if a curve over $\operatorname{GF}(2^m)$ is pairing friendly or not?

I have found this paper called "Elliptic Curves Suitable for Pairing Based Cryptography" but I think it talks about curves over $\operatorname{GF}(p)$.

• It is highly unlikely a usable bilinear map could be implemented on a random curve. One would choose a curve having such a map. Take a look at curves list known to have this map. Mar 11 '17 at 11:25

## 2 Answers

Let $q$ be the base field cardinal; in your case, $q = 2^m$ for some integer $m$. We need $m$ to be prime for a Koblitz curve, otherwise the curve would also be defined on non-trivial sub-fields, allowing for faster discrete logarithm. For a "pairing-friendly curve", we need the curve order to be a multiple of a prime $r$, and the pairing produces outputs in $\mathbb{F}_{q^k}$ for some integer $k$ which is the embedding degree.

That degree $k$ is the smallest $k\gt 1$ such that $r$ divides $q^k-1$. For a random curve, that degree is very high, on the same order of magnitude as $q$ itself, so computing the pairing would entail using values that cannot fit on an existing computer (or in the whole universe, for that matter). This is the case for all "standard" Koblitz curves (K-163, K-233, and so on).

Moreover, since a pairing transforms discrete logarithm on a curve into discrete logarithm in a finite field, you would need that finite field to be large enough for discrete logarithm to be hard. It has been recently shown that discrete logarithm in fields with small characteristic, in particular binary fields, is much easier than the discrete logarithm modulo a big prime; current records include fields of more than 9000 bits in size. Therefore, if you want to use binary fields for pairings, and still retain some decent security, then you need to use a destination field so large that computations will be very slow, thereby voiding any computational advantage from the curve being binary (Koblitz or not).

K-163 curve is not a pairing friendly curve. It can't be used in IBE that needs pairing operations.

• Are all koblitz curves not pairing friendly?how to know if a curve over GF(2^m) is pairing friendly or not? i have found this [link] (researchgate.net/profile/Annegret_Weng/publication/…) but i think it talks about curves over GF(p) Mar 13 '17 at 18:01
• I am not sure if all Koblitz Curves are not pairing friendly, but if you got it from NIST standards then it should be so, as I am not aware NIST issued standards for pairing-friendly curves. I can't open the link, not sure why. It is complex to construct a pairing friendly curve, this paper (eprint.iacr.org/2006/372.pdf) provide a good summary, you can refer to page 9.
– Tan
Mar 15 '17 at 1:27