Generating bilinear pairing parameters - running time of finding member of p-torsion group

Question

Update: Question completely rephrased.

I want to create the parameters for a bilinear pairing (the Tate pairing in this case).

In case you're interested I'm following this thesis, specifically the type $F$ curves (page 61) which has embedding degree $k = 12$. But it's probably not necessary to refer to the thesis to answer this question, since my question is likely elementary.

Using the method I've so far generated a finite field of size q where q is prime, an elliptic curve over $F_q, E(F_q)$, a prime of size $p$ so that $p | (q^{12} - 1)$ and a point $P$ on $E(F_q)$ of order $p$. Now the last step is to generate a point $Q$ which must also have order $p$ over the curve $E(F_{q^k})$ which must not be on $E(F_q)$. I've searched around and found the following suggested algorithm (where n is the number of points on $E(F_{q^k})$):

1) Generate a random point $R$ on $E(F_{q^k})$

2) Calculate $Z :=(n/p) R$

3) If $Z != O$, return $Z$ - otherwise, go to 1.

I.e. keep generating random points, scaling them by $(n/p)$ and repeating this until one gets a point different from the point-in-infinity, in which case the result should be a point of order $p$.

My question is - what is the running time of this algorithm? I.e. what is the per-iteration probability of getting $Z != O$ in step 3? I've tried to let it run but it doesn't find any points, it just keeps getting $O$ in step 2. Now, since calculation over $E(F_{q^k})$ are quite slow, I've only tried a few hundred iterations.

In this case $p$ and $q$ are primes of size 256 bits and $k = 12$. This means that $n$ is of the order of $2^{3072}$ (since n is the number of points on $E(F_{q^k})$). The p-torsion group has size $p^2$ meaning that such points are extremely rare and would be impossible to find by "random checking". But in this case, the algorithm doesn't operate by just generating a random point and checking if $p R$ is O. Rather, it generates a random point and multiplies by $(n/p)$. So it could be this increases the probability of finding a point.

But still, it seems to take forever! So it would be nice to know what the expected number of iterations is. Thanks!

Answer 1

Given the number of points #E on the curve over the base field $p$, then the number of points (np) over the k-th extension is given by the iteration (due to Weil)

trace=p+1-#E;
t[0]=2;
t[1]=trace;
for (int i=1;i<k;i++)
    t[i+1]=trace*t[i] - p*t[i-1];

np= pow(p,k)+1-t[k]; 

Answer 2

In your step 2 replace $p$ by $p^2$. That should do it.

But you should really be looking for points Q on the sextic twist. See the original Barreto-Naehrig paper.

Answer 3

a point in a $p$-torsion group doesn't have necessarily order $p$. It is of order $p^s$ for some $s \geq 1$.

If you know that the $p$-torsion of your (abelian) group has $p^2$ elements. It is either the cyclic group of order $p^2$ or the product of two copies of the cyclic group of order $p$. In the latter case it has $p-1$ points of order $p$ and $p^2-p$ points of order $p^2$, in the former all points but $O$ are of order $p$.

Now consider your algorithm: Say $p^2$ divides $n$, but $p^3$ does not, i.e. $n = p^2m$.

Lets assume you pick a point $R$ with order $p$. You will get $\frac{n}{p}R=pmR=O$. So in step 3, you will discard $R$. The same holds for all points $R$ with an order which divides $pm$. However assume $R$ has order $p^2$ (or $p^2$ divides the order), then $Z := \frac{n}{p} R\neq O$. You know $Z$ has order $p$ as desired. But it may be that you will never find a point which order is divided by $p^2$.

You can extend the algorithm to:

1. Choose $R$ at random
2. Calculate $Z = pR$
3. If $Z = O$ return $R$
4. Calculate $Z = \frac{n}{p} R$
5. If $Z \neq O$ return $Z$