# tower of extension field

while working on tate pairing, i have to implement towering technique. like i have point p on F(q) and point Q(F(q^k)) (here embedding degree k=12 for BN curve).

instead of taking a point Q on F(q^12), i take this point on twisted curve E'(q^2).

finally i need to map this point to F(q^12),how can i use this towering technique (2-2-3), because output of tate pairing for BN curve should be F(q^12). i have studied different articles but still confused, any numerical example would be very helpful. thanks in advance

-

Are you sure you want 2-2-3, not 2-3-2? The latter is more common in my experience.

None the less, the first step is almost always done with a quadratic extension where i^2=-1. So you just need to implement complex numbers over your field of choice.

Multiplying complex numbers is simple if you just treat them as (x+iy) - I hope that's basic.

For inversion see See "Implementing cryptographic pairings", M. Scott, section 3.2. (ftp://136.206.11.249/pub/crypto/pairings.pdf)

And here's my code for this step: https://code.google.com/p/go/source/browse/bn256/gfp2.go?repo=crypto

For the cubic extension see http://eprint.iacr.org/2006/471.pdf. I used τ^3=i+3. The multiplication is little more complex, but still just an application of basic algebra. For inversion, I'll have to point you at the comments that I wrote in my code: https://code.google.com/p/go/source/browse/bn256/gfp6.go?repo=crypto#242

Now you're at q^6 you can work in the twisted curve.

Lastly, the quadratic extension to q^12 is similar to the original extension. After the cubic, it should be easy! I used ω²=τ because I was following http://cryptojedi.org/papers/dclxvi-20100714.pdf.

For exactly how you get from the twist over q^6 to the curve over q^12 depends on the exact homomorphism in question.

-
if i take a numerical example let's assume that two points are there one on orignal curve and other on twisted curve, point P(10,15) and point Q(21,31), how do i map this point Q to F(q^12) using the towering technique like (2-3-2). – malik Dec 19 '12 at 14:42
Your twisted curve is over $q^6$, no? So a point on it would be expressed in the form ((a,b),(c,d),(e,f)), ((g,h),(i,j),(k,l)). (That is, an (x,y) pair of triplets of pairs). The function that maps a point on the twist curve to the point on the normal curve over $q^{12}$ is the group homomorphism. The homomorphism in the paper above is (x,y) -> (ω²x, ω^3y), but yours may vary. – agl Dec 19 '12 at 16:13
for example, if a point on Fp is (x,y) and we want to do Fp^2 and than using Fp^2 to reach at Fp^4, that is quadratic over quadratic, would you please consider any values for x and y and do it for me. – malik Dec 21 '12 at 15:24
we all know that BN curve has a sextic twist. for Pairing we take one point on orginal curve and other on twisted curve. first build filed extension (2-3) than it is on (Fp^6). now using homomorphism map from Fp^6 to Fp^12. – malik Dec 21 '12 at 15:29
it is my understanding, i need your comments. – malik Dec 21 '12 at 15:30