# 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. – Vadym Fedyukovych Mar 11 '17 at 11:25

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).