Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

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

share|improve this question

1 Answer

up vote 1 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.