Cryptographic Pairings on
Elliptic Curves
Colin D. Walter
Royal Holloway, University of London,
Egham, Surrey, TW20 0EX, United Kingdom
Colin.Walter@rhul.ac.uk
Outline• Motivation – some examples• Bilinear Pairings• Tate & Weil Pairings• Miller’s Algorithm• Other Scalar Multn Algorithms• Efficiency: Ground vs. Extension Field• Divisions and Denominators• Frobenius & Final Exponentiation• Pairing Friendly Curves: super-singular & MNT• Curve & Field Representations

1/44

Preliminary Remarks• Only about half these slides will be covered.
The remainder are for future study.
• The first half of the slides are introductory togive you a feel for the topic.
• The second half sketches some of the main
implementation issues.
• There are additional notes which give much
more detail. These are primarily for when you
really have to learn the subject in order toimplement pairings.
• There is a lot of deep mathematics behindpairings, but it can all (or mostly) be avoided.
• For those who have not seen pairings before,
the key things to master are:
1. The notation
2. Miller’s Algorithm
3. The Final Exponentiation

2/44

Motivation – Some Applications• Pairings provide new protocols and services
not available in classical cryptography.
We would like identity-based encryption where allusers share common public parameters – thiswould reduce key distribution problems.
Classical RSA doesn’t work. The keys di, ei satisfy
diei = 1 mod N.
Then j can deduce i's private key from ei since heknows N and inversion mod N is “easy”.
• Are there systems where j cannot deduce i’s
private key from his own keys?
Ohgishi, Sakai & Kasahara (1999) andBoneh & Franklin (2001)
solved this with pairings on elliptic curves.
The public identity-based encryption key of an
identity (person) may contain, for example:• the identity's email address• the current date• a subject or security level• a department/group name.
An example would be a national health service.
3/44

Definition of Bilinear Pairing
A bilinear pairing (“pairing” for short) is a map
e: G1 × G2 → G'
for abelian groups G1, G2, G' such thati) e(A+B,C) = e(A,C) e(B,C),andii) e(A,C+D) = e(A,C) e(A,D)
for all A,B ∈ G1, C,D ∈ G2.
• G1 and G2 will be subgroups or quotientgroups of an elliptic curve (written additively),• G' is a group of roots of unity in a field(the “embedding” field), with |G1| = |G2| = |G'|.
• Note that e([r]A, [s]C) = e(A,C)rs.
Our pairings require two additional properties:i) non-degeneracy: e(A,C)≠1 for some A∈G1, C∈G2ii) computability: there is an efficient algorithm todetermine e(A,C) from A and C.
Example e(u,v) = uMvT for vectors u,v and matrix M.
4/44

The DLP – Discrete Log Problem
Notation:• Elliptic curve group G1 defined over K0• Pairing e into the “embedding” field K(the field containing the necessary roots of unity, i.e. of 1.)

Suppose Q = αP for P ∈ G1.
• The discrete log problem (DLP) for G1 is to find α.
Choose R∈G2 with h = e(Q,R) ≠ 1.
Then h = e(αP,R) = gα where g = e(P,R).
Solving DLP in K yields α, so solves DLP in G1.
• We want Q and P public and α private.
So we need to the DLP to be difficult in K.
The MOV threshold from this attack means anembedding degree of at least 6 to 9 when theorder q of K0 has 192 bits,
i.e. K has an order qk of at least 1536 bits, say.
• Computations over K are expensive, so theembedding degree k = [K:K0] must be kept down.

5/44

Joux's Three Party Key Agreement
In 2000, Joux presented a scheme for one-round,
3-party key agreement based on bilinear maps,
the first constructive use of these maps in crypto.
(The usual Diffie-Helman scheme is between two
parties and so takes more rounds for more parties.)
In the Joux scheme,• P is a public generator of G = G1 = G2.
• The three parties A, B, C choose random
integer secrets a, b, c.
The protocol is as follows:• A publishes aP
B publishes bP
C publishes cP• A computes e(bP,cP)a = e(P,P) abc
B computes e(aP,cP)b = e(P,P) abc
C computes e(aP,bP)c = e(P,P)abc
All parties now possess the shared secret key
s = e(P,P) abc ∈ G'.
An attacker cannot deduce a from P and aP as the
DLP is too hard.
6/44

IBE – Identity-Based Encryption
There are four parts to this:• SETUP chooses the public parameters such as
the curve and a private master key.
• EXTRACT generates private decrypt keys fromthe public and private parameters determinedby SETUP and a public encrypt key.
• ENCRYPT is a description of encryption.
• DECRYPT is a description of decryption.
Here is BasicIdent in the Boneh-Franklin scheme.
The full scheme is a “minor” extension.
Given:• A curve with subgroup G1 of prime order r,• A pairing e into G', also of order r.
• H a hash function from n-bit texts to G1• H' a hash function from G' to n-bit texts.

7/44

SETUP• choose a master secret s,• choose a random generator P of G2,• publish P and Ppub = sP.
EXTRACT for public identity ID• compute the hash QID = H(ID) ∈ G1
• generate ID’s private key dID = sH(ID) = sQID
ENCRYPT message M for identity ID• compute QID = H(ID) ∈ G1
• compute gID = e(QID,Ppub) ∈ G'
• choose random ρ ∈ Z• output ciphertext pair ρP, M⊕H'(gIDρ) .
DECRYPT (U,V):V ⊕ H'(e(dID,U))= (M ⊕ H'(gIDρ))⊕ H'(e(dID, ρP))

= M ⊕ H'(e(QID,Ppub)ρ) ⊕ H'(e(sQID,ρP))= M ⊕ H'(e(QID,P)ρs)
= M
8/44

⊕ H'(e(QID,P)ρs)The arithmetic requirements are:• a random number generator• four hashing functions (for the full scheme)• determining suitable fields & curves• computing the pairing• exponentiation in G'
Next, we must fill in the missing arithmetic detail.

9/44

Notation (for reference)• p the field characteristic. Usually a small
prime (2 or 3), or a large prime of 160+ bits.
• q the order of the field K0 containing theelliptic curve. Typically 160 or 192 bits.
• K0 = GF(q) the field in which the curve lies.
• E(K0) the chosen elliptic curve over K0.
• r the prime order of a large subgroup of E(K0).
Ideally q/r is small, typically q/r < 24.
• G1 = E(K0)[r] the group of points whose
rth multiple is the point O at infinity.
This is cyclic (because r is so large).
• k the embedding degree, the smallest number
such that r divides qk–1.
k divides r–1, and typically divides 12.
• K = GF(qk) the embedding field, the smallest
extension of K0 containing the rth roots of 1.
• G2 = E(K) / rE(K), the quotient group of points
defined over K modulo the rth multiples.
• G' = µr, the group of rth roots of 1 in GF(qk)• e: G1×G2 → G' the selected bilinear pairing.
10/44

Divisors
Divisors summarise a function’s main properties
using a formal representation of its zeros & poles.
Definition. A divisors is a formal sum over Z ofpoints on the curve E(K), e.g.
D = ∑P∈E(K) nP(P) where nP∈Z for all P∈E(K).
Terminology:• The degree of D is deg(D)= ∑PnP .
• Its support is sup(D) = {P | nP ≠ 0}.
• (P) is the divisor of degree 1 and support
P ∈ E(K).
• ordP(f) is the multiplicity of P as a zero of fwhere f : E(K) → K.
• (f) = ∑P ordP(f) (P) is a principal divisor.
Properties• (cf) = (f) for non-zero c∈K*.
• (c) = 0 is the empty sum for c ∈ K*.
• (fg) = (f) + (g),(f / g) = (f) – (g) .

• deg((f)) = 0 and ∑P [ordP(f)] P = O .
11/44• deg((f)) = 0 and ∑P [ordP(f)] P = O .
For example, if lPQ(x,y) is the line through P and Q
on E(K), then R = –P–Q is the third point at which
the line meets E(K) and the associated divisor is(l) = (P) + (Q) + (R) – 3(OO) .
So O is a pole of order 3.
Definition For f : E(K) → K and D = ∑PnP(P), definenf(D) = ∏P f(P) P
This extends the definition of f from points on the
curve to any divisor.
For a non-zero constant c∈K,(cf)(D) = f(D) if deg(D) = 0
because the constants c all cancel.
We are only interested in divisors with degree 0.
Definition Two divisors are equivalent if theydiffer by a principal divisor, i.e.
D1 ~ D2 if, and only if, D1 = D2+(f)for some function f.
(We need this for technical reasons but will ignore
related theory.)
12/44

The Tate Pairing
The groups for the pairing e : G1×G2 → G' are• G1 = E(K)[r] = {P∈E(K) | [r]P = O},i.e. the subgroup of curve points defined over K
whose order divides the prime r.
• G2 = E(K) / rE(K) where rE(K) = {[r]P | P∈E(K)}This has exponent r.
• G' = K* / K*r ≅ µr , the rth roots of unity.
Pick P∈E(K)[r] and Q∈E(K). Let f be such that(f) = r(P) – r(O) .
Choose divisor D ~ (Q) – (O) with support disjoint
from (f). Then the Tate Pairing is defined by〈P,Q〉〉 = f(D) ∈ K*/(K*)r
As |K*| = qk–1, we can raise elements of K to thepower (qk–1)/r to obtain an rth root of unity andavoid the ambiguity of the quotient group. Hence
we define the pairingke(P,Q) = 〈P,Q〉〉(q –1)/r ∈ µr .
Note that 〈P,Q〉 = 1K mod K*r if P,Q ∈ E(L) for any
subfield L ⊂ K not containing µr since f(D) ∈ L ∩ µr = {1}.
So we usually pick P∈E(K0)[r] and Q properly in E(K).
13/44

There are a number of other related pairings, e.g.
• The Weil pairing is a ratio 〈P,Q〉 / 〈Q,P〉 ∈ µr
with no “final exponentiation”,
but is too expensive.
• The eta (η), ate, R-ate, optimal ate, etc.
pairings are more efficient,but specific to particular contexts.
We won’t cover these, but the arithmetic
techniques are similar.
In particular, the ate pairing involves a smaller final
exponent and the function f is evaluated at one
divisor, namely Q, not the two implied by D.

14/44

Chords to the Curve
Two lines are used to describe the addition law
P+Q = S on an elliptic curve over K, namely• The chord lPQ through P and Q, and• The vertical line vS through S, –S and O.
The corresponding divisors are(lP,Q) = (P) + (Q) + (–S) – 3(O)and(vS) = (S) + (–S) – 2(O)Consequently,(lP,Q / vS) = (P) + (Q) – (S) – (O)nicely represents the addition.
Computationally, in affine coords,lP,Q(x,y) ≡ rx+sy+t
for some r,s,t ∈ K such that rxP+syP+t = 0 andrxQ+syQ+t = 0. If P,Q ∈ E(K0) then r,s,t ∈ K0.
Similarly, if the curve has form y2 = f(x) thenvS(x,y) ≡ x–xS
which is satisfied by S and –S = (xS,–yS).
15/44

Miller's Algorithm
We need to construct a function f with divisor(f) = r(P) – r(O) .
This is done by constructing f1, f2,..., fr such that(fi) = i(P) – ([i ]P) – (i –1)(O) .
Lemma. Let lij be the chord through [i]P,[j]P andvi+j the vertical line through [i+j]P, –[i+j]P. Then:• f1 = c1, and• fi+j = cij fi fj lij vi+j–1
for some constants c1, cij for 1≤ i, j ≤ r.
Proof.
First, (f1) = 1(P)–([1]P)–(1–1)(O) = 0
is the empty formal sum. So f1 is a constant.
Secondly, (lij / vi+j) = ([i]P) + ([j]P) – ([i+j]P) – (O)gives (fi fj lij / vi+j)= i(P)–([i]P)–(i–1)(O) + j(P)– ([j]P)–(j–1)(O) + (lij/vi+j)= i(P) –(i–1)(O) + j(P) –(j–1)(O) – ([i+j]P) – (O)= (i+j)(P) – ([i+j]P) – (i+j–1)(O)= (fi+j)

which establishes the claim by induction.
16/44

■

〈P,Q〉 requires evaluating f at a divisor D of degree 0.

Corollary. For a divisor D of degree 0,• f1(D) = 1, and• fi+j (D) = fi (D) fj (D) lij (D) vi+j (D)–1.
Thus the constants cancel in the previous lemma,and so can be ignored.

Since (fr) = r(P)–([r ]P)–(r –1)(O) = r(P) – (r)(O) = (f),〈P,Q〉 = fr(D) .
The construction of fr via the formula for fi+j interms of fi and fj shows fr(D) can be computed byinserting some extra computation into an algorithm
for determining [r]P.

17/44

Choose D = (Q+S)–(S) for random point S.
Then D ~ (P) – (O) as required for the Tate pairing.
In the following, T holds a multiple [ j ]P of P, andf contains the corresponding fj (D).
ALGORITHM: Miller
INPUTS:

Points P,Q ∈ E(K),P of order r = ∑i=0n–1 ri2i, ri∈B, rn–1=1.
OUTPUT: The Tate pairing 〈P,Q〉 mod K*r.
{ Choose random S∈E(K)Q' ← Q+S
T ←P
f ← 1KFor i ← n–2 downto 0 do
{ Determine lines l and v for doubling T.
T ← [2]Tf ← f2 l(Q') l(S)–1 v(Q')–1 v(S)If ri = 1 then{ Determine l and v for the addition T+P.
T ← T+Pf ← f l(Q') l(S)–1v(Q')–1v(S)}}Return f}
18/44

• This is the binary left-to-right algorithm for [r]P.
• Pick S in E(K0) so f(S) is cheaper to calculate.
• The support of D must not intersect any fiwhich occurs.
This will be evident by obtaining 0/0.
If this happens, run it again with a different S.

19/44

Other Scalar Multiplication Algorithms
Other scalar multiplication algorithms for [r]P canbe used, e.g. NAF or m-ary, but most are too
expensive. (See additional notes for details.)
Useful cases restrict allowable operations to only:• doublings T ← [p]T or• tuplings

T ← [p]T for very small p = char(K)and• additions T ← T ± P

The main drawback with alternative algorithms isthe cost of an extra multiplication fd(D) for digitsd ≠ ±1 since the addition step becomes:
Determine l and v for the addition T+Pd.
T ← T+Pdf ← f fd l(Q') l(S)–1v(Q')–1v(S)Recall f1(D) =1, so digit d=1 is not a problem.
Otherwise there are extra multiplications in K.

20/44

The Main Efficiency Issues• Work in K0 when possible.
Values in K take k times more space than in K0,
and multiplications take k2-fold more time.
• If P ∈ E(K0) then all the lines are over K0.
• If S ∈ E(K0) then half the evaluations are in K0.
About half the multiplication count is calculating[r]P, the rest determining and evaluating the lines.
So, with lines and S in K0,• Evaluating the lines at Q' dominates the time.
• K0 should be kept down to the size used inclassical ECC.
Clearly,• Divisions & inversions should be avoided.
So f is split into numerator and denominator values
fN and fD. Then, e.g., the addition step becomesfN ← fN l(Q') v(S); fD ← fD l(S) v(Q')
which has the same number of multiplications.
Then there is a single final division f = fN/fD.
21/44

Separating Mults over K0 and K

Field multiplications for updating f might beseparated into
• those over K0 using variables f0N , f0D and• those over K using variables f1N , f1D, say.
By estimating each K×K multn as equivalent to k2
multns over K0, it is clear that only the total numberof K×K multns is significant.
• The multn count is unchanged by the above split.
• Multns should be done in the order which
minimises the number of K×K operations.
The saving is O(k) whereas
the cost of all multiplications is O(k2).
Hence this is significant only for small k.

22/44

Projective or Affine Coordinates?
• Use affine coordinates for Q'.
As Q' ∈ E(K), 3 coordinates for Q' increases thecost of each l(Q') and v(Q') in Miller’s algorithm.
It is cheaper to convert Q' = Q+S to affine coords
once for all when the random S ∈ E(K0) is chosen.
To do this, the Extended Euclidean Algorithm gives
the inverse at the cost of 10 or so multiplications –much less than the number of double & add steps.

• According to Galbraith, empirical evidence
does not justify projective coords elsewhere.
The main extra cost from projective coords is thatthe vertical lines are now in the form zTx – xTz = 0 .
Evaluating this at Q' and S costs another K0×K
multn and another K0×K0 multn, which is more
expensive than the inversion in K0 to put T in affine
coordinates (unless k is exceptionally small).

23/44

Removing the Factors involving S• Recall the “final exponentiation” to obtain e(P,Q)
Pick S ∈ E(K0)[r] in Miller's algorithm to makecalculations of l(S) and v(S) entirely within K0.
• Thenl(S)q–1 = 1 = v(S)q–1.

If r /q–1 then (qk–1)/r is a multiple of q–1, sokkl(S)(q –1)/r = 1 = v(S)(q –1)/r.
So l(S) and v(S) make no contribution toke(P,Q) = 〈P,Q〉(q –1)/r ∈ µr .

Theorem. If r is prime to q–1 and k>1 then S = O
can be chosen in Miller's Algorithm and the factorsl(S) and v(S) deleted from it.

Unfortunately, the calculations of l(Q') and v(Q')
are much more expensive than l(S) and v(S), so
the saving is not so significant.
24/44

Theorem. In Miller's Algorithm, if r is prime to q–1
and k>1 then all the factors of f, namely fd, l(Q'),l(S), v(Q'), v(S) can be replaced by multiples α1fd,
α2l(Q'),... for any α1, α2,... ∈K0*.

The reasoning is the same here – each αj isannihilated by the final exponentiation.
This is useful if denominators have appeared,
e.g. through calculating a gradient and avoiding
the inversion when adding two points.

25/44

The Frobenius Automorphism
Consider the final exponentiationke(P,Q) = 〈P,Q〉(q –1)/rIf p = char(K), the Frobenius automorphismis the map γ → γp for γ ∈ K. Clearly,

γp = γ for γ ∈ Fp
by Lagrange’s theorem on the ×ve group Fp*.
If q = pn then elements of Fq are stored using a
representation of Fq as a vector space over Fp.
If γ = ∑i=0n–1γibi, γi ∈ Fp, is the repn of γ ∈ Fq usingbasis (b0,b1,...,bn–1) over Fp then
p

p

p

p

γ = (∑i=0n–1γI bi ) = ∑i=0n–1γi bi = ∑i=0n–1γI bipbecause all absent terms in the product havebinomial coefficients which are multiples of p.
• Raising to the power p requires
no general field multiplications,only constant multiplications and additions.
p

The bi are pre-computed if p is small.

26/44

With careful choice of the field representation,psuch as a normal basis, the expressions for the bi
are very simple linear combinations of the bj.

To take advantage of a cheap Frobenius
automorphism, use m-ary exponentiation with m=p:
ALGORITHM:
INPUTS:OUTPUT:p-ary Exponentiationγ ∈ K, r' = ∑i=0n–1 ripi.
Γ = γr'.

Pre-compute & store the occurring γriΓ ← γrn–1
For i ← n–2 downto 0 do
Γ ← Γp;if ri ≠ 0 then Γ ← Γ×γri
Return Γ

For small p ≠ 2, this should be cheaper than
exponentiation using a base 2 representation of
the final exponent r' = (qk – 1)/r.

27/44

For large p we want only a few non-zero digits ri,
which is almost the case for many pairing-friendly
curves after this adjustment:
Theorem Suppose r divides n, n divides both qk–1
and |E(K0)|, and P ∈ E(K0)[r]. Thenkke(P,Q) = 〈P,Q〉r(q –1)/r = 〈P,Q〉n(q –1)/nExampleFor q = 3163 take the super-singular curve of ordern = q–√(3q)+1 = 3163–382+1
n = 7r for a prime r. The embedding degree is k=6
since n is a factor of q2–q+1 which divides q3+1
and hence q6–1.
So we can evaluate the pairing using n rather than r.
The final exponentiation is then byn' = (q6–1)/n = (q3–1)(q+1)n''
for n'' = q+√3q+1 = 3163+382+1.
Multiplying out, there is a base 3 representation ofn' with at most 2×2×3 = 12 small non-zero digits.
This makes exponentiation by n' extremely fast.
28/44

Pairing-Friendly Curves
These curves have:• a small embedding degree k,• a large prime factor r in the curve order,• a small co-factor |E(K0)|/r.

There are a number of different families of curves.
P1363 is a bit out of date, but a good reference is
the “Taxonomy” paper of Freeman, et al.

We look at two cases:• Super-singular curves,• MNT curves.

29/44

Super-Singular Elliptic Curves
Definition. An elliptic curve E defined over a field
Fq of characteristic p is super-singular if p | t,where t = q+1–|E(Fq)|. If p / t then E is ordinary.
So the number of finite points is a multiple of thecharacteristic on super-singular curves.
By Hasse's bound, |t| ≤ 2√q for trace t.
The only choices for super-singular curves are:• t= 0with k=2,• t = ±2√qwith k=1,• t = ±√q

if char(F) ≡ 0,2 (mod 3) with k=3,

• t = ±√(2q)

if char(F) = 2 with k=4, and• t = ±√(3q)

if char(F) = 3 with k=6.

If r > 4√q is prime divisor of |E(K0)|, then r2 exactly
divides |E(K)|, E(K)[r] is the direct product of two
subgroups of order r and E(K)[r] ∩ rE(K) = {O}.
So E(K)/rE(K) ≅ E(K)[r]/rE(K) and we caneffectively take both arguments from E(K)[r].

30/44There is also a nice “distortion” map which maps
E(K0)[r] to another subgroup of E(K) with order r.
This is defined over a conjugate of K0 and the twogenerate the full group E(K)[r].
The advantage is that half the work of a pairing
calculation is avoided: all the denominators can beignored as above (page 24) because they areannihilated when raising to the power q–1.

The most frequently used constructions for thesecurves are the following:
1. E : y2 = x3+a over Fp, where p ≡ 2 (mod 3).
Here |E(Fp)| = p+1 and k=2.
2. E : y2 = x3+x over Fp, where p ≡ 3 (mod 4).
Here |E(Fp)| = p+1 and k=2.
3. E : y2 = x3+a over Fp2, where p ≡ 5 (mod 6)
and a∈Fp2 is a square but not a cube.
Here |E(Fp2)| = p2–p+1 and k=3.
4. E : y2+y = x3+x+a where Fq, q=2ℓ for odd ℓ anda∈F2. Here |E(Fq)| = q±√(2q)+1 and k=4.
5. E : y2 = x3–x+a where Fq, q=3ℓ for odd ℓ anda∈F3*. Here |E(Fq)| = q±√(3q)+1 and k=6.
31/44

Suitable fields and curves with these parameters
are found as follows:
1. First, systematically choose random p of therequired magnitude: applying the Rabin-Miller
primality testing algorithm to check primality.
2. Run Rabin-Miller again on r where r is
obtained from n = |E(K0)| using the above
formula, and removing all small factors.
Typically a sieve of Eratosthenes is used for p,
tagging all elements in the table having a prime
divisor less than 216, say.
• The probability of both p and n being prime isO(1/log(np)), and so not difficult.
For char(K0) = 2, 3 the choice of fields is very
limited: |E(Fq)| rarely has a large prime factor forsuitable q. q = 3163 is one example.
There are simple equations provided with these
constructions which define how to build K/K0. Also
there are tables of irreducible polynomials forgenerating K0 , e.g. F2251 = F2[t]/(t251 + t7+ t4+ t +1).
• Fast multiplication methods, such as Toom or
Karatsuba-Ofman, are advisable for K.
32/44

Characteristic 2 – a worked example.
Take super-singular E : y2+y = x3+x+awith a ∈ F2 so that k = 4.

over F2,

The tangent at P = (x1,y1) isl : y = λ(x–x1)+y1
where λ = x12+1. This intersects the curve again at
x2 = λ2 = x14+1
The vertical line through this isv : x–x2 = 0.
So [2]P = (x2,y2) where y2 = 1+λ(x2+x1)+y1.
Then, easily,[2]P = (x14, x14+y14+1)
So doubling requires just four squarings(the Frobenius) and some additions.
The lines for Miller's algorithm are a by-product.

33/44

Characteristic 3 – a worked example.
Take super-singular E : y2=x3+a4x+a6 over F3.
The tangent at P = (x1,y1) isl : x = y1y – y12 + x1
where λ = 1/y1 . This intersects the curve again at(λ2+x1, λ3+y1), giving [2]P = (λ2+x1, –λ3–y1).
The line between P and [2]P has slope λ' = y13–λ,from which[3]P = (x19+a6(1–a4), –y19)
Again, no divisions and the tripling is given by four
applications of the Frobenius, which is very efficient.
So pairing calculations for fields of characteristic 3
should be performed with 3-ary exponentiation forboth scalar point multiplication and final exponentn.

34/44

Distortion Maps and Vertical Lines
Super-singular curves have “distortion” maps:
Definition Suppose E(K) has no points of order r2,
φ is a non-rational endomorphism of E, andQ ∈ E(K0)[r]. If φ(Q) ∉ E(K0) then e(Q,φ(Q)) ≠ 1.
Such a φ is called a distortion map.
They only exist for super-singular curves, but
calculating the Tate pairing at φ(Q) now involves
only numbers in K0 and its conjugate φ(K0).
In many circumstances and the right presentationof the curve equation, these numbers can be kept
sufficiently separate for there to computationalsavings, particularly as a result of the final
exponentiation killing off elements of K0 in thesame way as noted above.
In particular,• The contributions v(φ(Q)), Q ∈ E(K0)[r], can beignored, i.e. removed, providing the curveparameters are chosen suitably.
• This observation saves half the work before
the final exponentiation.
(See the notes for a proof.)
35/44

MNT Elliptic Curves(Miyaji, Nakabayashi & Takano)

One of the most widely used and oldest of thenon-singular pairing-friendly curves are the MNTcurves.

They are ordinary curves (i.e. not super-singular)
with “complex multiplication” and require someeffort to generate. One should use dedicatedcomputation packages, such as Mike Scott's
Miracl software, for this. More construction detail isin the notes and the IEEE P1363 standard.

There are recent improvements by Enge andothers using only local methods & the CRT.

36/44

The construction begins with a factorisation of thepolynomial xk–1, (k = 3,4,6) to obtain possible
values for the trace t = q+1–|E(Fq)|. These areparameterised by an integer ℓ :
k

q

t

3

12ℓ 2–1–1±6ℓ

4ℓ 2+ℓ+1–ℓ or ℓ+1

6

4ℓ2+1

1±2ℓ

E.g. the curve order for k=6 is q±√q–1,
which is a factor of q2–q+1, which divides q3+1
and so also q6–1, establishing that k=6.
ℓ must be chosen to give fields of the required size,and varied until q is prime and the curve orderq+1–t has a sufficiently large prime factor r.
The discriminant ∆ = t 2 – 4q must also consist of alarge square times a small square-free factor(typically under 232) or else the numbers become
too large and the likelihood of finding solutions of
the required size becomes too small.

37/44

Elliptic Curves Coordinates
The choice of coordinate system affects theefficiency of any calculations on it.
The total time for the elliptic curve operations in apairing calculation is proportional to the time taken
for a single elliptic curve operation.
The difference in speeds between the fastest andthe slowest curve additions is within a factor of
about 2. So at best the pairing will be done attwice the speed with another choice.
A useful list of the various main addition anddoubling formulae is given by Bernstein & Lange.
They are mostly just variations on a theme, with
the Weierstraß affine coordinates as a standard
example – see Prof. Koç's lecture.
e(P,Q) will usually have P in E(K0) and Q in E(K).
So the computation of rP will be over K0, making it
relatively cheap, as are the values l(S) and v(S).
The expensive part is l(Q), v(Q) and the final
exponentiation. So Q should be put in affine
coordinates.

38/44

Affine Coordinates.
The usual equation over Fp, p odd, is the short
Weierstraß form
E : y2 = x3 + ax + b
for which the addition and doubling formulae for(x1,x2)+(x2,y2)=(x3,y3) and [2](x1,y1)=(x2,y2) are
x3 = (y2–y1)2/(x2–x1)2–x1–x2
y3 = (2x1+x2)(y2–y1)/(x2–x1)–(y2–y1)3/(x2–x1)3–y1
andx2 = (3x12+a)2/(2y1)2–x1–x1
y2 = (2x1+x1)(3x13+a)/(2y1)–(3x12+a)3/(2y1)3–y1
The addition formula cannot work for doubling
since it gives the value 0/0.
The cost is usually given as a count of generalfield multns, field additions and subtractions, multns
by small constants, and an inversion.
However, be aware that communication costs
between processor and memory may also be
significant, as may be the costs of moving data
between registers.
39/44

Hessian Form
When there are points of order three, an elliptic
curve has points (x,y) satisfying an equation:
x3+y3+1 = 3dxy
The addition and doubling formulae are, respy,
x3 = (y12x2–y22x1)/(x2y2–x1y1)
y3 = (x12y2–x22y1)/(x2y2–x1y1)
andx2 = y1 (1–x13)/(x13–y13)
y2 = x1 (y13–1)/(x13–y13)
The inverse is –(x1,y1) = (y1,x1).
Again, just one inversion appears, a result ofcomputing the chord gradient. This has about two
thirds the multiplication count of the Weierstraßform. Most other representations fall between
these two in terms of efficiency.
Steven Galbraith has compared affine andprojective coordinates and found the latter not toprovide a noticeable advantage.

40/44

Although the requirement for speed is perhaps
most acute in embedded systems, side-channel
leakage may be a problem there, mainly fromdistinguishing adds from doubles.
There are many different solutions to suchleakage.
For
example,theprojective
representation of the Hessian form uses the same
formula for both addition and doubling, viz.
[2](X1,Y1,Z1) = (Z1,X1,Y1) + (Y1,Z1,X1)
and one can choose that.
We don’t need to hide r which is public, but in theBoneh-Franklin IBE scheme, P is the decryption
key, and it must not be leaked.
These issues are covered elsewhere in thiscourse, and solved by adding more detail to theabove formulae, such as specifying the order of
execution.

41/44

Finite Field Construction
Efficient field arithmetic has been covered by Prof.
Koç. Standard curves are chosen using theseprinciples. However, they are not generally
suitable for pairing-based cryptography as theembedding degree is too large.
So one has to generate one's own field. There are
two main cases: small or large characteristic.

For small characteristics, the frequent use of the
Frobenius in the final exponentiation suggests thata normal basis would be better than a polynomial
basis.
There are tables of irreducible polynomials(trinomials and pentanomials for p=2) andtechniques to obtain normal bases for such them.
Being sparse, a polynomial basis is also possible.

42/44

For large p, the classical technique is to choose pwith low Hamming weight so that multiplications
are cheap. Unfortunately, here p is essentiallyrandom and so it is difficult to obtain this property.
Consequently, pairings tend to be computed faster
when the characteristic is very small.
For large p the extension degree of K over Fp isgenerally small – typically 6. Hence the generating
polynomial of K/Fp has small degree. It is feasible
to search for a nice irreducible polynomial withvery small coefficients, with many being zero.

43/44

Appendix: Other Essential Algorithms
Other basic, necessary algorithms include:• The Rabin-Miller Primality Test.
Needed in curve generation to check char(K) andfinding large prime subgroups of E(K0).
• Square Root Algorithm.
Used to find the y-coord of a point from its x-coord.
• The SEA Point Counting Algorithm.
Finds the order of an elliptic curve. Avoid this bypicking curves with known order.
Some attacks modify public parameters. However,the curve order can be checked easily by verifying
the order of a random point.
Most algorithms are detailed in the number theory
appendix A to IEEE P1363.
• Generally, there is no need to implement
algorithms such as SEA or Rabin-Miller.
• They are available in many software
packages, such as Mike Scott's Miracl.
44/44