Implementing Cryptographic Pairings Mike Scott Bilinear pairings e(aP,bQ) = e(P,Q)ab bilinearity! The Tate pairing seems best choice. Possible on ordinary elliptic curves of prime characteristic and on supersingular curves. P (of prime order r), and Q are points on E(Fqk). Embedding degree smallest k such that r |(qk-1) Pairing evaluates as element in Fqk Here we concentrate on q=p, and nonsupersingular.

Millers algorithm A lgorit hm 1 e( P ; Q) using M iller's algorithm Input: P 2 E ( F pk ) ; Q 2 E ( F pk ) , P has order r O utput: e( P ; Q) 1: T P , f 1 2: for i blg( r ) c 1 downt o 0 do 3: f = f 2:l T;T ( Q) =v2T ( Q) 4: T = 2T 5: if r i = 1 t hen 6: f = f :l T ;P ( Q) =vT + P ( Q)

7: T = T +P 8: end if 9: end for k 1)=r (p 10: f f 11: ret urn f Elliptic Curves (point doubling case) Line of slope j

j = (3xj2+A)/2yj xj+1 = j2-2xj xj,yj yj+1 = j(xj-xj+1)-yj xj+1,yj+1 The Pairing Algorithm Q(xq,yq) Line of slope j l(Q) = (yq-yj) j(xq-xj)

yq-yj xj,yj xq-xj v(Q) =xq-xj+1 xj+1,yj+1 Millers algorithm As described, it may fail (the line may pass through Q!) Traditionally solved by introducing a random R, which doesnt change value of

the pairing. If algorithm fails, choose another R. Will not be needed later, so omitted here First optimizations Choose low Hamming weight r (if possible) If not possible (MNT curves?) windowing algorithms, also idea of Eisentrager et al. Choose P from E(Fp) (Solinass Miller Light), now use projective coordinates. NOT choose p of low Hamming weight! (Schirokauer) Restriction k=2d is always even. Final exponentiation considered in 2 parts.

First optimizations A lgorit hm 1 e(P ; Q) with some optimizations Input: P 2 E ( F p); Q 2 E ( F pk ), P has order r O utput: e(P ; Q) 1: T P , f 1 2: for i blg( r)c 1 downt o 0 do 3: f = f 2:l T;T (Q)=v2T (Q) 4: T = 2T 5: if r i = 1 t hen 6:

f = f :l T;P ( Q)=vT + P (Q) 7: T = T+P 8: end if 9: end for d 10: f f p 1 d 11: f f (p + 1)=r 12: ret urn f Extension field arithmetic Considered before for crypto use ( XTR,

OEFs). k=2 case is the simplest Irreducible polynomial x2+1 for p=3 mod 4 Element in Fp2 is (a+xb), where a and b are in Fp . Consider x=i as root of irreducible polynomial, so i=-1 Just like complex arithmetic! Extension field arithmetic Multiplication (Karatsuba) (a+ib)(c+id) = ac-bd +i[(a+b)(c+d)-ac-bd] 3 modmuls? But better to use lazy reduction, e.g. calculate (ac-bd) mod p (2

muls and one reduction) Cost ~ 2.5 modmuls Squaring (a+ib)(a+ib) = (a+b)(a-b)+i.2ab Cost ~ 2 Modmuls Cubic Extension? Irreducible polynomial x3+n Karatsuba or Toom-Cook for multiplication (6 or 5 Modmuls resp.). Toom-Cook has tricky divisions by constants Final exponent has factor of p-1.. So divisions can be replaced by multiplications thank you Fermat!

Lazy reduction applies again. Squaring 4 Modsqrs and 1 Modmul (Chung & Hasan) recent result! Square roots For quadratic extension, irreducible x2+n p r a + ib = q

(a r a2 + nb2)=2+ xb=(2 (a q a2 + nb2)=2) Can you find simple solution for cubic extension? A Tower of Extensions

For a sextic extension field x6+n, could use a cubic extension on top of a quadratic extension squaring requires only 11 modmuls using Chung-Hasan Always use pairing-friendly irreducible polynomials. For example for k=12, maybe use X6+(1+-2) and a sextic extension on top of a quadratic, which uses x2+2 as the irreducible. Frobenius The Frobenius is very useful for extension field arithmetic (a+ib)p = (ap+ipbp) = (a-ib)

When raising an extension field element to a power, you never have to use an exponent greater than p. Types of pairing-friendly curves #E=p+1-t

|t| 2p r|#E = lg(p)/lg(r) = lg(r)/lg(t) In general small is good ( = 1 is ideal) Large is also good. Example - BN Curves

k=12 p(x) = 36x4+36x3+24x2+6x+1 #E(x) = 36x4+36x3+18x2+6x+1 t(x) = 6x2+1 = 1 (ideal!) = 2 (not bad but = 4 possible for k=12) In general the smaller the harder to find a low hamming weight r. For Cocks-Pinch curves = 2, free choice for r. Where were we? k=2d so assume that Fpk is built as a

quadratic extension on top of Fpd. So now consider an element of Fpk as (a+ib). So (a+ib)pd = (a-ib) (1/(a+ib))pd-1 = (a-ib)pd-1 Which means that following exponentiation to the power of pd-1, inversions cannot be distinguished from conjugates. Further optimizations A lgorit hm 1 e( P ; Q) with further optimization Input: P 2 E ( F p) ; Q 2 ( F pk ) , P has order r O utput: e( P ; Q) 1: T P , f 1 2: for i blg( r ) c 1 downt o 0 do

3: f = f 2:l T ;T ( Q) :v2T ( Q) 4: T = 2T 5: if r i = 1 t hen 6: f = f :l T ;P ( Q) :vT + P ( Q) 7: T = T + P 8: end if 9: end for d

10: f f p 1 d 11: f f ( p + 1) =r 12: ret urn f What about Q? Choose Q to best advantage. Q is point (xQ,yQ), where xQ = (a+ib), yQ = (c+id) Now restrict to the case where b=c=0 The vertical line functions are now in Fpd and so get wiped out - denominator elimination. If Q(a,id) is a point on E(Fpk), then Q(-a,d)

is a point on the quadratic twist E(Fpd). Denominator elimination A lgorit hm 1 e( P ; Q) denominator elimination Input: P 2 E ( F p) ; Q 2 E 0( F pd) , P has order r O utput: e( P ; Q) 1: T P , f 1 2: for i blg( r ) c 1 dow nt o 0 do 3: f = f 2:l T ;T ( Q) 4: T = 2T 5: if r i = 1 t hen

6: f = f :l T ;P ( T ; Q) 7: T = T + P 8: end if 9: end for d 10: f f p 1 d 11: f f ( p + 1) =r 12: ret urn f Yet more optimization

The group order will always be odd, but the effect of the last line addition which takes T to the point-at-infinity will be wiped out by the final exponentiation. Final exponentiation can be further divided into 3 parts, pd-1 (pd+1)/k(p) k(p)/r Yet more optimization For example for k=6, 6(p)=p2-p+1 p6-1 = (p3-1)(p+1)(p2-p+1) r|p2-p+1, from definition of the embedding

degree. Exponentiation by p3-1 and p+1 will be easy using Frobenius and one extension field inversion Exponentiation by (p2-p+1)/r is the hard part Yet more optimization A lgorit hm 1 e( P ; Q) yet more optimization Input: P 2 E ( F p) ; Q 2 E 0( F pd) , P has order r O utput: e( P ; Q) 1: T P , f 1 2: s = r 1 3: for i blg( s) c 1 dow nt o 0 do

4: f = f 2:l T ;T ( Q) 5: T = 2T 6: if si = 1 t hen 7: f = f :l T ;P ( Q) 8: T = T + P 9: end if 10: end for 11: f f ( pd 1)

d 12: f f ( p + 1) =k ( p) 13: f f k ( p) =r 14: ret urn f Hard part of final exponentiation Express hard exponent to base p xe = xe0+e1.p+e2.p2 = xe0.(xp)e1.(xp2)e2 . Now use Frobenius and multiexponentiation. Exploit fact that inverses can be treated as conjugates for fast NAF-based exponentiation.

Compression Alternatively for k8, use Lucas or XTR exponentiation, which uses the full sized exponent, but over smaller fields Fpk/2 and Fpk/3 respectively. Also compresses pairing to one half or one-third size Probably useful to compress the pairing anyway, even after multi-exponentiation. Precomputation In many cases the first parameter P may be fixed it may be an IBE private key. In which case it makes sense to

precompute the values of T which are multiples of P In this case use Affine coordinates Big speed-up for smaller k. For larger k extension field arithmetic dwarfs elliptic curve point addition/doubling. Trick #1 Often in a pairing-based protocol there is a requirement to further raise the value of the pairing to a power v

Powering for free! Curve dependent Optimizations There are families of curves for which >1. For the MNT curves =2. In these cases a truncated loop variant of the pairing is possible the Ate pairing. Here P is chosen from E(Fpd) and Q from E(Fp) Now we get a bilinear pairing with a much shorter loop! Ate pairing A lgorit hm 1 e( P ; Q) A te pairing

Input: P 2 E 0( F pd) ; Q 2 E ( F p) , P has order r O utput: e( P ; Q) 1: T P , f 1 2: s = t 1 3: for i blg( s) c 1 dow nt o 0 do 4: f = f 2:l T ;T ( Q) 5: T = 2T 6: if si = 1 t hen 7: f = f :l T ;P ( Q) 8:

T = T + P 9: end if 10: end for 11: f f ( pd 1) d 12: f f ( p + 1) =k ( p) 13: f f k ( p) =r 14: ret urn f Low CM Discriminant curves For non-supersingular curves, must use Complex Multiplication (CM) method to find curve parameters.

Many pairing-friendly curves have a CM discriminant of -1 or -3. In these cases quartic and sextic twists also exist. For BN curves, D=-3, k=12, and so curve over sextic twist E(Fpk/6) can be used. Low CM Discriminant curves So Q 2 E(Fpk/c) for c=4 or 6 is possible for Tate pairing. Or P 2 E(Fpk/c) for Ate pairing Works particularly well with Ate pairing For a k=6 D=-3 curves both P and Q can be on curves over Fp !

(Unfortunately no such curves are known with <2 ). Trick #2 Consider MNT k=6 curve, r = #E a prime. Hard part of final exponentiation is to the power of (p2-p+1)/r = (p2-p+1)/(p+1-t) = p+, where ~ t So hard part of exponentiation is fp.f Which is one Frobenius and one halflength exponentiation (not a multiexponentiation). The Wider Context Pairings are not calculated in isolation They are part of a wider context.

The protocol may also require variable point multiplications faster if P and Q are over smaller fields. Or it may only also require fixed-point multiplications (B&F IBE), in which case the pairing will be the dominant computation. The Wider Context Compare (a) k=2, p=512 bits with (b) k=6, p=160 bits Similar security levels. But pairing for (a) is much faster (especially with precomputation)

Variable point multiplication (over E(Fp)) much faster on (b). Short signature scheme must use (b). I could go on Scaling security ..much debated Code for higher extensions is much fussier. Spends more time hopping in and out of functions, function overhead an issue. Small instruction cache more cache misses with fussier code.

Scaling security Symmetric key size 80 128 256 Group size 160 256 512 E xtension eld size 960 { 1280

3000 { 5000 12000 { 18000 E mbedding degree 2{8 12{18 24{36 Products of Pairings For example e(P,Q).e(R,S) Implicit multiplication of P and R take place in lock-step. Use affine coordinates and Montgomerys trick. Share the Miller variable f between both

pairings, and only square it once .. And of course share the final exponentiation. Some timings All code in C and assembly, P4 3GHz Compare with 1024-bit RSA decryption on the same platform. Group size of 160-bits, Field size of 1024bit equivalent. Precomputation allowed. Three pairings timings in milliseconds T pairing E(F2379), k= 4 Tate pairing E(Fp), 512 bit p, k=2 Ate pairing E(Fp), 256 bit p, k=4, =2

Timings E ( F 2379 ) T pairing E ( F p) T ate pairing E ( F p) Ate pairing P airing 3.88 2.91 3.10 P oint M ult. 1.82

3.08 1.17 F ield exp. 1.14 0.54 0.62 R SA decryption

1.92 Questions ?? Full paper ftp.computing.dcu.ie/pub/crypto/ pairings.pdf Thank you! [email protected]