Cryptographic Pairings on Elliptic Curves
Colin D. Walter
Royal Holloway, University of London,
Egham, Surrey, TW20 0EX, United Kingdom
Colin.Walter@rhul.ac.uk

Abstract. Pairings on elliptic curves provide many interesting new protocols and services that are not available within classical asymmetric
cryptography. These notes provide a more in depth description of themain components necessary for building such systems for those wishingto take the lecture material further. It contains a more detailed discussionof the enhanced arithmetic required.

1

Motivation - Some Applications

A standard problem with asymmetric public key cryptography is the man-inthe-middle attack. He replaces public key parameters of others with his own,
enabling him to read and modify messages which he intercepts. Users therefore
need a guarantee that they have public key parameters correctly. One solution isfor an organisation to use the same parameters throughout its systems. They canbe distributed very securely, once for all, and they take little space. Traditionallya different key is generated and distributed for every new member, revoked for
retiring members, and it takes time and space as well as being less secure.
In order to solve this, suppose the company were to pick a group G on which
all employees are to perform the cryptography, with individual i having public
encryption exponent ei . With classical RSA or ECC, the encrypt/decrypt keys
di , ei satisfy di ei = 1 mod |G|. Then j can deduce i’s private key from ei since
he knows |G|. So this cannot solve the previous problem.
Pairings on elliptic curves enable one to circumvent this problem, the firstsolution (1999) being given by Ohgishi, Sakai & Kasahara [23]. Independently
Boneh & Franklin [7] discovered an almost identical technique (2001) but also
provided a security proof. (A security proof is a proof that breaking the system
is equivalent to solving a mathematical problem which is generally regarded as
being “hard”.) With this solution there are still public parameters which must
be distributed securely to everyone by the KDC (key distribution centre) andindividuals need to obtain their decryption key(s) from the KDC, but it is nolonger possible to deduce decrypt keys from other (d, e) pairs.
Such a scheme must have a sufficiently large number of possible encryption
keys that they can be generated from a random string. This means that, in practice, the organisation can specify formats of e for which the KDC will provide
decryption keys and senders just need to follow those formats. In particular, e
may have to be the recipient’s email address. However, it might include further

2Pairings, C. D. Walter

attributes such as the current date. This would enable the KDC to deny addressees the decrypt key if they have left the company before that date. So a
revocation list which all should access is replaced by recipients regularly renewing their decryption keys. Other attributes can be included to avoid a plethoraof email addresses for different groups of members. This answered positively aquestion posed by Shamir [28] about using one’s identity as a public key1 .
An example would be a national health service. A patient takes his healthcard to a pharmacy, which then signs a request to the patient’s doctor for therequired prescription and that is then sent securely from the surgery to thepharmacy. The three parties may never have met previously, but the process
works (with the right protocols) without each party having to know parameters
for everyone in the health service – which is so huge that the membership iscontinuously changing.

2

Definition of Bilinear Pairing

A bilinear pairing (“pairing” for short) is a map e : G1 × G2 →G0 for abeliangroups G1 , G2 , G0 (here written additively, additively & multiplicatively respectively) 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 . An easy example is to take the finite field Fp with,say p = 7 and generator 3. The multiplicative sub-group of non-zero elements
has p−1 = 6 elements. This is G0 for the example, and G1 and G2 are boththe additive group of integers modulo 6, (which is the group of exponents ofthe generator 3 of F7 .) Then the map e(A, C) = 3AC mod7 provides the pairing.
Properties (i) and (ii) are easily checked. (An exercise for the reader.)For us, G1 and G2 are subgroups or quotient groups of an elliptic curve,
and G0 is a group of roots of unity in a field (the “embedding” field), with
|G1 | = |G2 | = |G0 |. Note thate(A, C) = e(A+0, C) = e(A, C)e(0, C) ,so that e(0, C) = 1 for all C ∈ G2 . Similarly e(A, 0) = 1 for all A ∈ G1 . Alsoe(nA, C) = e(A, C)n = e(A, nC) for n ∈ Z, including n = 0 (which we have justnoted), and e(aA, cC) = e(A, C)ac . We are only interested in pairings with two
additional properties:a) non-degeneracy: e(A, C) 6= 1 for some A ∈ G1 , C ∈ G2 .
b) computability: there is an efficient algorithm to determine e(A, C) from A
and C.
1

In [28] Shamir used RSA to give an identity-based signature scheme.

Lausanne Cryptographic Engineering3

We will not bother about property (a), which is for mathematicians to verify.
One of the main goals here is to describe an algorithm satisfying (b) and covera few special cases where the algorithm becomes more efficient.
For a curve with a pairing, we can translate discrete log problems from a curve
subgroup G1 defined over the field K0 = Fq to the “embedding” field K = Fqk ,i.e. that containing G0 . Thus, suppose Q = αP . Use the non-degeneracy of e
to choose R ∈ G2 with h = e(Q, R) 6= 1. Then h = e(αP, R) = g α whereg = e(P, R). Solving the discrete log problem (DLP) in G0 yields α, whichsolves the DLP in G1 . This can be done using a (sub-exponential) index calculus
method. So we need to know that the DLP is difficult in the embedding field. The
MOV threshold arising from the complexity of this attack (Menezes, Okamoto,
Vanstone [20,16]) means an embedding degree of at least 6 to 9 (depending on
the required security) when the order q of the field over which the curve is definedhas 192 bits. So the pairings are computed in the field GF(q 6 ) or GF(q 9 ) or an
extension of it – at least 1536 bits, say.
However, the computations are increasingly expensive as the embedding degree rises. The need to keep it small severely restricts the curves over which thecryptography is practical because, on average, the embedding degree k has thesame order as the group, i.e. O(q), rather than 6, 9 or 12, say. The usable curves
are called “pairing-friendly” curves (see [13,17]). The earliest to be constructed
were the MNT curves. Given the difficulty of generating curves with large enoughprime subgroups, small enough embedding degree and efficient arithmetic in theembedding field, as well as the work involved in determining the size of theelliptic curve and the potential for selecting an insecure curve, one should only
consider choosing a recommended curve, i.e. a well-documented, well-studied
curve with known properties and which is preferably accepted in some standard
such as P1363.3 [17].
We won’t cover the different families of such curves, but one must be chosen.
Unfortunately, the associated finite fields tend not to have particularly efficientarithmetic known for them. There is essentially just one pairing, but it comesin various different guises: Weil, Tate, Eta, Ate, R-Ate pairings which may or
may not be applicable to the chosen curve family (see [17], §A.13.2.) Here weconcentrate on Tate pairings and MNT curves.

3

Joux’s Three Party Key Agreement

This is another application of bilinear maps, and one that sparked the interestin them for constructive cryptography as opposed to their previous destructiveuse, e.g. in the DLP. In 2000, Joux presented a scheme for one-round, 3-party
key agreement based on bilinear maps [18]. The usual Diffie-Helman scheme isbetween two parties and so takes further rounds to agree a secret key among
more parties. In the Joux scheme, P is a public generator of G = G1 = G2 . The
three parties A, B, C have secrets a, b, c ∈ Zr ∗ respectively where r = |G0 |. The
protocol is as follows:4

Pairings, C. D. Walter

1. A publishes aP , B publishes bP , C publishes cP .
2. 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 have the shared key K = e(P, P )abc ∈ G0 .

4

IBE – Identity-Based Encryption

There are many applications of pairings in modern cryptography. This motivational section provides a brief technical outline of the main one: an identity-based
encryption system. It can be skipped, but it shows what arithmetic components
we need to be able to implement.
There is a standard structure for defining such systems so that “proofs” ofsecurity (i.e. reductions to simpler, standard problems of equivalent complexity
which are generally believed to be “hard”) are clearer:
1. Setup
2. Extract
3. Encrypt
4. Decrypt
These are fairly self-explanatory. Setup chooses the public parameters such as
the curve and a private master key. Extract generates private decrypt keys fordifferent identities from the public and private parameters determined by Setup
and an identity’s public encrypt key. Encrypt and Decrypt are descriptionsof the appropriate functions.
The encryption is best described in two stages, starting with a simplified one
called BasicIdent. Suppose Setup has already generated a suitable curve with
subgroup G1 of prime order r, and given us a pairing e into G0 , also of order r.
Let H, H 0 be two hash functions from Fn2 (i.e. n-bit texts) to G1 and from G0back to Fn2 respectively. Setup also chooses a master secret s ∈ Z of order |G2 |,a random generator P of G2 , and computes the public parameter Ppub = sP .
Let id ∈ Fn2 be the public encryption string associated with an identity.
Extract first computes the hash
QID = H(ID) ∈ G1
and then generates id’s private key
dID = sH(ID) = sQID ∈ G1
where s is the master secret. Encryption starts with computing QID = H(ID)and gID = e(QID , Ppub ) ∈ G0 and choosing a random ρ. The ciphertext of
message M is the pairρρP, M ⊕H 0 (gID)

Lausanne Cryptographic Engineering

5

To decrypt pair (U, V ), computeρV ⊕ H 0 (e(dID , U )) = (M ⊕ H 0 (gID)) ⊕ H 0 (e(dID , ρP ))= M ⊕ H 0 (e(QID , Ppub )ρ ) ⊕ H 0 (e(sQID , ρP ))= M ⊕ H 0 (e(QID , P )ρs ) ⊕ H 0 (e(QID , P )ρs ) = M
Overall, a random number generator is required, computation of pairings (oneper identity by the encrypter, one per message by the decrypter), two hashing
functions, and an exponentiation in G0 by the encrypter.
To obtain a scheme with proven security, this needs the application of atechnique by Fujisaki & Okamoto (see [7] for details.) Let H1 , H2 be two morehash functions on the message space, and EID (M, r) the encryption of M underthe basic scheme. Then the encryption of M under the full scheme requires asecond random, say σ, and is the pair
EID (σ, H1 (σ, M )), H2 (σ) ⊕ M– essentially another blinding of M by a random σ. Decryption is as follows:
Let U, V be the pair EID (σ, H1 (σ, M )) forming the first component and W =H2 (σ) ⊕ M be the second component in the full scheme. As before, the decrypter
first decrypts the EID component by computing V ⊕ H 0 (e(dID , U )) to recoverσ. Then H2 (σ) ⊕ W = M reveals the message.
So there are no new arithmetic requirements in the full scheme, just somefurther hashing. Overall, from previous lectures in this course we know how
to do everything with the possible exception of i) finding suitable curves, andii) calculating the pairing. There are, of course, some small details regarding
hashing to G1 or G0 instead of Bn , but they are straightforward.

5

Elliptic Curve Pairings

5.1

Notation

In line with the introductory sections above, the following (standard) notation
will be used:– p is the characteristic of the finite fields of interest. Usually a small prime
such as 2 or 3, or a large prime of at least 160 bits.
– q = p∗ is the power of p which is the order of the field over which the elliptic
curve cryptography is performed. (Typically 160 or 192 bits but no morethan 256 bits; normally prime or a power of 2 or may be 3.)– K0 = Fq is the finite field of order q in which the curve is normally defined
to lie.
– E(K0 ) is the chosen elliptic curve defined over K0 .
– r the order of the largest prime subgroup of the elliptic curve E(K0 ) overK0 . By the Hasse bound, the curve has order close to q. We want q/r small,ideally q = O(r). Typically q/r < 24.

6Pairings, C. D. Walter– G1 = E(K0 )[r] is the elliptic curve subgroup of points defined over K0 whose
rth multiple is the point O at infinity. This is cyclic of order r because r is
so large.
– k is the embedding degree, the smallest number such that r divides q k − 1.
Also called the security multiplier. It divides r−1, and, for practical purposes,
is typically under 12 in applications, but greater than 1. Often k = 6 ischosen, but the recommended lower bound has risen slowly as theory has
developed.
– K = Fqk is the embedding field. It is the smallest extension of K0 = Fq
containing the rth roots of 1, i.e. K contains an element ζ such that ζ r = 1
but ζ a 6= 1 for all positive a < r.
– G2 = E(K)/rE(K) is the elliptic curve quotient group of points defined overK modulo the rth multiples.
– G0 = µr is the group of rth roots of unity in K = Fqk , i.e. the set of elementsζ ∈ K such that ζ r = 1.
– e : G1 × G2 →G0 is the selected bilinear pairing.

5.2

Divisors

Pairing values are obtained by constructing a function from the elliptic curve
into the embedding field which has a particular set of zeros and poles. (Zeros
are where the function has the value 0, and poles are where it has the value ∞.)The concept of a divisor is straightforward, and simply summarises a function
using just a formal representation of its set of zeros and poles. In order to write
down the definitions correctly, we have to go up to the “algebraic closure” K of
K but all calculations will be done in K or K0 , so that K can be ignored. The
elliptic curves E(K) and E(K0 ), defined over K and K0 respectively, are justsubgroups of the curve E(K).
Definition 1. Divisors arePformal (finite) sums over Z of points on the curve
E(K). For example, D = P ∈E(K) nP (P ) where nP ∈Z for all P ∈E(K). The
P
degree of D is deg(D) = P nP and its support is sup(D) = {P | nP 6= 0}.
Divisors form an additive group (in the obvious way) and (P ) is the way ofwriting the divisor of degree 1 and support P ∈ E(K). The obvious function fcorresponding to divisor D in the definition is the “rational” functionfD (x) =ΠP ∈E(K),nP >0 (x − P )nPΠP ∈E(K),nP <0 (x − P )−nP

This function has zeros of order nP at P when nP > 0 and poles of order −nP
at P when nP < 0.
If f is a function from E(K) to K, then ordP (f ) is the multiplicity of P as azero of f , with negative numbers representing the multiplicity of P as a pole (i.e.
the number of times x−P is a factor inPthe numerator or denominator of f (x)).
This yields a principal divisor (f ) = P ordP (f )(P ). So the principal divisor

Lausanne Cryptographic Engineering

7(fD ) for the example function fD is the divisor D in the definition. Note thata non-zero constant multiple cf of f gives the same divisor: (cf ) = (f ) because∗
the two functions have the same zeros and poles. For c ∈ K , the divisor (c) isthe empty formal sum 0.
Definition 2. Two divisors are equivalent if they differ by a principal divisor,
i.e. D1 ∼ D2 if, and only if, D1 = D2 +(f ) for some function f .
The group of divisors of degree 0 modulo this equivalence is the divisor classgroup of E. Computation of the pairing will be done in this group.
P
Theorem 1. Suppose D = P nP (P ) has degree 0. Then D ∼ 0 if and only ifP
P [nP ]P = O, i.e. D = (f ) for some function f if, and only if, the points in
D (with multiplicity) add to O.
The first sum here is the formal sum defining a divisor, the second sum is a sumof points on the elliptic curve, and O is the point at infinity on the curve. For
example, if `P Q (x, y) is the line through P and Q on E(K), then R = −P −Q isthe third point at which the line meets E(K) and the associated divisor is(`) = (P )+(Q)+(R) − 3(O)since the zero of the curve group, namely O, is a pole of thePline with order 3.2
Finally, for a function f : E(K)→K and divisor D = P nP (P ), we candefine f (D) byY
f (D) =f (P )nP
P

where f (P ) is the value of f at P . This is a well-defined element of K ∗ if the
support of (f ) does not intersect that of D. Clearly, for a non-zero constantc ∈ K, (cf )(D) = f (D) if deg(D) = 0 since all the instances of c cancel.
5.3

The Tate Pairing

Most of this section can be skipped by readers wishing to avoid any mathematicalcomplexity. The key contents to note are the definitions of the Tate pairing inequation (1) and the pairing e(∗, ∗) in equation (2).
For r coprime3 to p = char(K), the cyclic group of rth roots of unity in K
is denoted µr . This is the set of elements ζ ∈ K such that ζ r = 1. There are rof them and φ(r) have order r. This will be the group G0 into which our pairingmaps. The group from which the first argument of the pairing comes is
G1 = E(K)[r] = {P ∈ E(K) | [r]P = O} ,2
3This is not obvious. It uses a theorem of algebraic geometry which says deg((f )) = 0.
Any r > 0 with this property is suitable. Only the applications need r to be a large
prime factor of E(K0 ).

8Pairings, C. D. Walter

i.e. the subgroup of curve points defined over K whose order divides r. The
group
rE(K) = {[r]P | P ∈ E(K)}of rth multiples is used in defining the quotient group
G2 = E(K)/rE(K)from which the second argument of the pairing comes. This group has exponentr, i.e. the rth multiple of an element is the zero of the group. G1 = E(K)[r]and G2 = E(K)/rE(K) have the same order, but are not necessarily isomorphic
although they are for the cases of interest to us.
Pick two points P ∈ E(K)[r] and representative Q ∈ E(K) of a class in
E(K)/rE(K). Since the divisor r(P ) − r(O) has degree 0, there is a function4
f with that as divisor, i.e. an f such that (f ) = r(P ) − r(O). Choose divisorD ∼ (Q) − (O) whose support is disjoint from that of (f )5 . Usually, if S ∈ E(K)is an arbitrary point, then it suffices to take D = (Q+S) − (S). Here f (D) ∈ K ∗because of the definitions of f , D and the support property of D. The Tate
Pairing is defined by
hP, Qi = f (D) ∈ K ∗ /(K ∗ )r(1)
Note that K ∗ /(K ∗ )r is isomorphic to µr in a canonical way6 , so we can view
the pairing as giving us a value in µr . The choice of Q and D from their classes
means that this is only defined up to multiplication by an rth power. The main
evaluation problems are therefore: constructing the function f of divisor r(P ) −r(O), and determining which rth root of unity is in the same class as f (D).
An important observation is that hP, Qi ∼ 1K is trivial if P, Q ∈ E(L) for
any subfield L ⊂ K which does not contain any non-trivial rth roots of unityµr . This is because f and D are defined over L and so f (D) ∈ L ∩ µr = {1}. In
particular, for prime r and P, Q ∈ E(K0 )[r] we have hP, Qi = 1 if the embedding
degree k > 1. This means that we normally choose one argument in E(K0 ) to
simplify the arithmetic but must choose the other properly in E(K) to avoid
everything degenerating to 1.
As |K ∗ | = q k −1, we can raise elements of K to the power (q k −1)/r to obtainan rth root of unity. This gives a canonical element in a coset of K ∗ /(K ∗ )r since
any rth power is killed by raising it to the power (q k −1)/r. It also avoids the
problem of determining which root of unity is in the class of hP, Qi. Hence wedefine the pairing(q k −1)/re(P, Q) = hP, Qi∈ µr .
(2)
Computing the power on the right side is called the final exponentiation. The
bilinearity properties of h∗, ∗i (which we have assumed) are inherited by e(∗, ∗).
Finally, readers interested in the Weil pairing could look at Galbraith’s account in [6], IX.6. There he defines that pairing in terms of evaluating two Tate
4

In the next but one section there is a construction for this using Miller’s algorithm.
We can’t take D = (Q) − (O) since O is then in the support of both D and (f ).
6
The class of ζ ∈ µr is mapped to ζ.

5

Lausanne Cryptographic Engineering

9pairings hP, Qi and hQ, P i. As the Weil pairing already maps into µr , there isno need for the “final exponentiation”. So it appears to require less than twice
the computational effort. However, in the Tate pairing we can usually pick P in
E(K0 ) but not Q in E(K0 ). When we come to Miller’s algorithm for the Tatepairing, hQ, P i is then much more expensive than hP, Qi to compute. So Tate’s
pairing is very much faster and so generally preferred.

6

Computing the Pairing

6.1

ExampleTwo lines are used to describe the addition law P +Q = S on an elliptic curve
over K. The first is that through P and Q, say `P Q . It intersects the curve again
at a point R, say, such that P +Q+R = O. The second, say vR , is the verticalline through R and O, which intersects the curve again at S = −R, making
R+S = O. Specifically, `P Q (x, y) ≡ rx+sy+t for some r, s, t ∈ K such thatrxP +syP +t = 0 and rxQ +syQ +t = 0. Similarly, if the curve has an equationof the form y 2 = f (x) then vR (x, y) ≡ x−xR , which is satisfied by R and
S = −R = (xR , −yR )7 .
If we are using Weierstraß coordinates then lines over K0 have equations of
the form `(x, y) = 0 where `(x, y) = rx+sy+t, say, for some r, s, t ∈ K. The
equation of the line gives a formula for y in terms of x. When this is substituted
into the curve equation it yields a cubic which has three roots, namely xP , xQ
and xR for `P Q . Hence `P Q determines the three points P, Q, R and the divisor(`P Q ) includes (P )+(Q)+(R). The full mathematical definition of divisors ismore complex and some hard work is required to show that there is a balancing
multiple of (O). However, we could eventually show that(`P,Q ) = (P )+(Q)+(R)−3(O)and, similarly, that(vR ) = (R)+(S)−2(O) = (R)+(−R)−2(O)Since the divisor provides the multiplicities of the zeros and poles of a function,
we have (f g) = (f )+(g). Hence(`P Q /vR ) = (P )+(Q)+(R)−3(O) − (R)−(S)+2(O) = (P )+(Q)−(S)−(O)6.2

Miller’s Algorithm

The main step in evaluating the pairing is to construct is a function f such that(f ) = r(P ) − r(O). This is done using a sequence of functions f1 , f2 , ..., fr withthe divisor property(fi ) = i(P ) − ([i]P ) − (i−1)(O) .
7(3)

We cannot always pick the equation to have this form, in which case we can expect
y−R 6= −yR .

10Pairings, C. D. Walter

Using the construction in the example of §6.1, there are two lines `, v which
define a group addition. For a given point P ∈ E(K)[r], let `ij , vi+j be those
associated with the addition [i]P + [j]P . Thus `ij is the line through [i]P and[j]P whereas vi+j is the line through [i+j]P and −[i+j]P . In the same way as
the roots of a polynomial determine the polynomial up to a non-zero multiple, so
a divisor of degree 0 determines a function which is unique up to multiplication
by a non-zero constant. Hence the functions fi are determined up to a constant.
They can be generated iteratively using:Lemma 1. The functions fi satisfy:
f1 = c1 , andfi+j = cij fi fj `ij vi+j −1
for some constants c1 , cij for 1 ≤ i, j ≤ r.
To see this, note first that the divisor (f1 ) = 1(P )−([1]P )−(1−1)(O) = φ is theempty formal sum by eqn. (3). Hence f1 is just a non-zero constant function.
Next, we have(`ij /vi+j ) = ([i]P ) + ([j]P ) − ([i+j]P ) − (O)by the example in the previous sub-section. Thus, by the obvious induction
hypothesis that eqn. (3) holds for all indices less than i+j,
(fi fj `ij /vi+j ) = i(P )−([i]P )−(i−1)(O) + j(P )−([j]P )−(j−1)(O) + (`ij /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 and the preceding remark.
tuObserve that P ∈ E(K)[r] means [r]P = O, so that (fr ) = r(P )−r(O) and
fr = f is the function we seek in order to evaluate the pairing. Note also that forany point S, (Q+S)−(S) ∼ (Q)−(O) by Theorem 1 because {Q+S}−S = Q−O.
Hence, by definition, hP, Qi = f (D) for a divisor D = (Q+S)−(S) where S is arandom point on the curve. So hP, Qi = f (Q+S)/f (S). This means the constants
cij cancel in the iterative computation of f (D):Corollary 1. For a divisor D of degree 0, the values fi (D) satisfy:
f1 (D) = 1, and−1
fi+j (D) = fi (D)fj (D)`ij (D)vi+j (D) .
Since fr is calculated iteratively using lines which compute multiples of P up
to [r]P , this corollary means f can be computed simply by inserting some extra
computation into any scalar multiplication algorithm for computing [r]P . In thefollowing algorithm due to Victor Miller, the variable T holds a multiple of P ,say [j]P where j is given by the leftmost i bits of r, and the variable f contains
the corresponding value fj (D) for D = (Q0 )−(S) = (Q+S)−(S).

Lausanne Cryptographic Engineering

11

ALGORITHM: Miller
Pn−1
INPUTS: Points P, Q ∈ E(K), P of order r = i=0 ri 2i , ri ∈B, rn−1 =1.
OUTPUT: The Tate pairing hP, Qi mod K ∗r .
Choose a random point S ∈ E(K)Q0 ← Q+S
T ←P
f ← 1KFor i ← n-2 downto 0 do{
Determine lines ` and v for doubling T .
T ← [2]Tf ← f 2 `(Q0 )`(S)−1 v(Q0 )−1 v(S)If ri = 1 then{Determine ` and v for the addition T +P .
T ← T +Pf ← f `(Q0 )`(S)−1 v(Q0 )−1 v(S)}}Return f
Recall the assumption in the definition of the pairing that the support of f
had to be disjoint from the divisor Q0 −S at which f is evaluated. This is to
avoid f becoming 0 when it is evaluated at any point in the divisor. f has at
most about 15
2 log2 r zeros or poles besides O. (Three for each line ` and twofor each vertical v for, on average, 23 log2 r cases.) As r is large and there are atleast r choices for S, there is therefore only a negligible chance of a random S
resulting in Q0 or S being part of the support of f . This would be noticed in thealgorithm by an attempt to multiply or divide f by 0. In this case the algorithm
would have to be run again with a different S.
There is, of course, still the final exponentiation by (q k −1)/r to perform toobtain e(P, Q). We know how to do this, but it is a main topic in section 7.
6.3

Other Scalar Multiplication Algorithms

In fact, alternative scalar multiplication algorithms for [r]P can be adapted to
speed up the version of Miller’s Algorithm presented in the previous section. For
example, by using NAF (non-adjacent form) for which there are non-zero digits±1 which are always separated by at least one zero digit, the number of addition
operations is reduced from 12 log2 r to 13 log2 r on average. Almost all efficientscalar multiplication algorithms use an iterative step which involves a number ofdoublings T ←[2]T and an addition T ←T +[d]P of a small, signed digit multiple
dP . The latter uses fd , so [d]P and fd (D) should be pre-computed and stored invariables Pd and fd , say. Then, for positive digits d, the addition step becomes:

12Pairings, C. D. Walter
If d > 0 then{Determine ` and v for the addition T +Pd .
T ←T +Pdf ←f fd `(Q0 )`(S)−1 v(Q0 )−1 v(S)}However, unless d = 1 the insertion of the factor fd increases the cost of theaddition step so much that alternatives to double and add are usually more
expensive! This is confirmed in more detail below.
For negative digits d, the function fd has not been constructed and so fi+d
is obtained from fi and f−d by re-ordering the propertyfi (D) = fi+d (D)f−d (D)`i+d,−d (D)vi (D)−1from Corollary 1 into ([8], eqn.(1))
fi+d (D) = fi (D)f−d (D)−1 `i+d,−d (D)−1 vi (D)Thus, the two lines of interest are associated with the addition of [−d]P and[i+d]P . The line `i+d,−d goes through [i+d]P, −[d]P and so also −[i]P . Thus itis the line `i,d = `−i,−d through the points −[d]P and −[i]P which is complementary to the line `i,d through [d]P, [i]P and so essentially already known as±[d]P was pre-computed and T = [i]P is the current point. If the curve equation has the form y 2 = F (x), then `i,d is just the mirror image in the x-axis of
the line `−i,−d . We can refer to `i,d as the line associated with the subtraction
T −P−d . It is, indeed, one of the two possible lines that can be used to determine
the difference T −P−d and so causes no extra work beyond what is necessary to
determine T +Pd . The required vertical line is vi through [i]P and −[i]P , i.e. T
and −T . So the full addition step becomes:
If d > 0 then{Determine ` and v for the addition T +Pd .
T ←T +Pdf ←f fd `(Q0 )`(S)−1 v(Q0 )−1 v(S)}If d < 0 then{Determine ` for the subtraction T −P−d and v through T .
T ←T −P−df ←f f−d −1 `(Q0 )−1 `(S)v(Q0 )v(S)−1}
In practice, only the digits ±1 are of interest. For these the factor f±d = 1
disappears. So a NAF representation of r or a 2-bit sliding window methodwith digits 0, ±1 would provide some speed-up over the usual double-and-add
methods.

Lausanne Cryptographic Engineering

7

Efficiency Aspects

7.1

The Main Efficiency Issues

13

The largest efficiency saving is from working in K0 = Fq rather than K = Fqk
whenever possible. Representations of elements in K are k times the lengthof representations of elements in K0 so that a multiplication over K0 is k×k
times faster than one over K. Although small values of k such as k = 6 are
typical, the saving is nevertheless considerable if available choices enable many
multiplications to be made over K0 instead of K.
The focus of attention in this sub-section is the evaluation of the line`(x, y) ≡ rx+sy+t(4)

at S and Q0 . In Miller’s algorithm, if P ∈ E(K0 ) then all the lines are over K0
and point additions are performed over K0 . Thus the coefficients of (4) are in
K0 and calculating the coordinates of multiples of P only requires arithmetic in
K0 . Moreover, S can be chosen so that either S or Q0 is defined over K0 . Thenhalf the line evaluations `(S) and `(Q0 ) in the algorithm are at points definedover K0 , and once again all the arithemtic is in K0 . In fact, if K0 is not a prime
field (i.e. char(K) < q) then S might be chosen in a much smaller subfield thanK0 , making multiplication using its coordinates still cheaper.
The cost of one point doubling or point addition step in Miller’s algorithm
is roughly the following, when field additions and multiplications by small constants are ignored. There are typically 12 to 17 field multiplications per point
addition, depending on the coordinate system (see [6], Table V.1), and thisshould yield both lines with little extra work since ` is essentially determinedwhen calculating a point sum. It is comparable but a little less for point doubling – typically 80% of the cost of a point addition. All these should be overK0 . Another 12 multiplications are required to evaluate the two lines at the twopoints when projective coordinates are used. Six of these will be over K0 if S or
Q0 is chosen to be defined over K0 . However, the other six will be mixed multiplications with one argument in K0 and the other in K, making them k times
the cost of a multiplication over K0 . Finally, 4 or 5 multiplications or divisions(for the point addition and doubling respectively) are required to determine ffrom those evaluations. Since f ∈ K, most of these operations are properly inK.
Temporarily counting a division to have the same cost as a multiplication8 ,over half of the multiplications of an addition or doubling step are therefore over
K0 instead of K if P, S ∈ E(K0 ), namely those for the point addition or doubling
and two of the line evaluations, and most of the rest have at least one argumentin K0 . Only 3 or 4 are fully over K. Overall, choosing S ∈ E(K0 ) is useful but
much less significant than choosing P ∈ E(K0 ). Consequently, although one has
to keep K large enough to avoid a DLP attack via K, K0 should be kept down
to the size used in classical ECC applications and P chosen in E(K0 ).
8

Division is treated properly in the following paragraphs.

14Pairings, C. D. Walter

Clearly, field divisions and inversions should be avoided. Any constant multiple of ` or v is acceptable because their contributions to f are via `(D) =`(Q0 )/`(S) and v(D) = v(Q0 )/v(S), so that any extra constant is cancelled.
Hence computing the coefficients of lines ` and v, and determining the values`(Q0 ), `(S), v(Q0 ) and v(S) should not involve any division.
f is computed using a similar approach to that of replacing affine with projective coordinates, viz. adding another variable to store values as ratios: f is split
into numerator and denominator values fN and fD for the main loop. It requires
twice the storage for f , which is little overall increase in memory. Naturally, thetable elements fd (D) would have any divisions performed before storage so theirdenominators would also be 1. Then each division in the computation of f canbe replaced by a single multiplication. Thus, for example, in the addition step
the updating of f becomesfN ←fN `(Q0 )v(S) ;fD ←fD `(S)v(Q0 )(5)which involves two multiplications of elements in K0 by elements in K and two
multiplications properly over K. (The same number of multiplications as wecounted earlier.) Eventually there is a single field division f =fN /fD after theloop terminates.
There are, of course, a number of papers describing how to save one or two
multiplications per double and add step in scalar multiplication algorithms, e.g.
[8,9].
7.2

Alternative Scalar Multiplication Algorithms

This section can be skipped. It is mostly an interesting exercise in understanding
the relative merits of other likely sources of improved efficiency and should be
helpful in developing general skills for tackling this issue in other contexts.
Our aim here is to reduce the total number of multiplications properly overK since this is the most expensive arithmetic operation aside from the single
final division after the loop termination. These multiplications dominate Miller’salgorithm. Alternative point multiplication algorithms which involve digits otherthan 0, ±1 require an extra multiplication by f±d ∈ K in the point addition step.
For example, for d > 1, f is updated usingfN ←fN fd `(Q0 )v(S) ;fD ←fD `(S)v(Q0 )This increases the number of multiplications with both arguments properly in
K from 2 to 3 compared with when d = 1. By comparison, the doubling stepfN ←fN 2 `(Q0 )v(S) ;fD ←fD 2 `(S)v(Q0 )requires two squarings and two multiplications properly over K, which is typically equivalent to about 3.6 such multiplications.
With a prime r of 160 bits, there are on average 159/2 addition steps in thebinary double and add algorithm, requiring 2× 21 ×159 = 159 multiplications over

Lausanne Cryptographic Engineering

15

K. With a NAF representation, one in three digits is non-zero and so the addition
steps require on average only 2× 31 ×159 = 106 multiplications. For a 3-bit sliding
window algorithm, the digits are ±1, ±3 and one in four of the doubling steps
is associated with a non-zero digit. So one in eight involves ±3 and requires
an extra multiplication. The total is ( 28 + 38 )×159 ≈ 99 multiplications for the
addition steps. The saving of under 7 multiplications over NAF is insufficient toperform the extra division necessary when computing f3 (D) for the table. Of
course, the saving is proportional to the bit length of r, and will be more forlarger r. One concludes that only scalar multiplication methods involving digits
0, ±1 are worthwhile for the usual size of r.
7.3

Another Less Efficient Method

This section may also be skipped – it reveals another slight efficiency gain withlittle extra expense in memory use.
Similarly to the splitting of f into numerator and denominator, the field
multiplications for updating f might be separated into those over K0 and thoseover K. Suppose variables f0 = f0N /f0D and f1 = f1N /f1D are used for these,
and they are multiplied together at the end to obtain f = fN /fD . Again ignoring
the inversions, each iterate of the doubling stepfN ←fN 2 `(Q0 )v(S) ;fD ←fD 2 `(S)v(Q0 )is split intof0N ←f0N 2 v(S) ;f0D ←f0D 2 `(S) ;f1N ←f1N 2 `(Q0 ) ;f1D ←f1D 2 v(Q0 )Both require two multiplications and two squarings over K. In addition, the firsthas two mixed multiplications K×K0 →K but the second only two multiplications and two squarings over K0 , which is cheaper for k ≥ 2. However, the saving
is only O(k) per loop iteration in Miller’s algorithm, whereas the total cost isO(k 2 ) per loop iteration. Notice the importance of performing multiplications inan order which keeps successive products in the smallest possible field.
7.4

Affine or Projective Coordinates?

Next to consider is the choice of coordinates. Only S and Q0 appear in thecomputation of f , and, being random, S can easily be chosen over K0 withaffine coordinates. As neither is changed during the computation, it is best also
to put Q0 into affine coordinates initially and stay with affine coordinates for the
calculation of f , thereby making the line evaluations at S and Q0 cheaper.
For the iterative calculation of [r]P it is tempting to use projective coordinates. One of their main uses is to speed up exactly this computation. Observe,
however, that the line v through the point T (which is the variable in Miller’salgorithm holding a scalar multiple of P ) then has x-coordinate given by theratio xT /zT , so that the evaluation of v ≡ zT x − xT z at S or Q0 requires a

16Pairings, C. D. Walter

multiplication which was not required before, the latter case with one argumentin K. These multiplications cause an extra computational effort of O(k) per loop
iteration. However, the additional cost of affine coordinates for T is a divisionin K0 , which, as a function of k, is an O(1) operation. Consequently, according
to Galbraith [6] chap. IX, affine coordinates are empirically faster. Indeed, theanalysis here shows that this is inevitable as k grows larger.

8

The Final Exponentiation

Recall that our aim is to compute e(P, Q) = hP, Qi
rithm only outputs hP, Qi.
8.1(q k −1)/r, and Miller’s algo-Removing the Factors involving S

In many cases, part of the work in calculating the pairing may be saved using
the following theorem.
Theorem 2. [2] For the evaluation of e(P, Q), if r is prime to q−1 and k > 1
then S = O can be chosen in Miller’s Algorithm and the factors `(S) and v(S)deleted from it.
In practice, as we have noted, S is generally chosen in E(K0 )[r] to ensure thecalculations of `(S) and v(S) are entirely within K0 . However, the calculationsof `(Q0 ) and v(Q0 ) are in K and so much more expensive. Hence the saving fromthis theorem is not as great as the half that might be expected at first sight, but
it is one of the improvements that makes other pairings, such as the ate pairing,
attractive.
The main point here is that, in order to calculate e(P, Q), the final exponentiation by (q k −1)/r is by a multiple of q−1. Ignoring any problems regarding the
support of f , by picking S ∈ E(K0 ) we would have `(S) ∈ K0 and v(S) ∈ K0
and so `(S)q−1 = 1 and v(S)q−1 = 1 unless `(S) = 0 or v(S) = 0. So their contribution after the final exponentiation is trivial, and the factors `(S) and v(S)can be safely deleted from the algorithm. Of course, in our case K0 is chosen
small, so k > 1. By the definition of r, r will therefore generally be prime toq−1, so that normally this theorem can be applied.
The restriction on the choice of S is that it is not in the support of any
function f that is used. However, only O(log(r)) points of E(K0 )[r]) occur insuch supports as only that number of functions f are used in the calculation. So
there are points S defined over K0 which could be used legitimately and which
avoid the support of the function f . Unfortunately, we need to be a bit moreclever since we want to take S = O in order to have Q0 = Q, and this is one ofthe points in the support of f . As the course is not about proofs, so we will skip
this tiresome detail.
Theorem 3. [2] When computing e(P, Q), if r is prime to q−1 and k > 1 thenin Miller’s Algorithm all the factors of f , namely fd , `(Q0 ), `(S), v(Q0 ) andv(S), can be replaced by multiples α1 fd , α2 `(Q0 ),... for any α1 , α2 , ... ∈ K0∗ .

Lausanne Cryptographic Engineering

17

The reasoning is the same here – each αj is killed by the final exponentiation.
Since the line ` will normally have a denominator in its gradient, a consequenceof this theorem, in particular, is that the line ` can have any denominators safely
removed to avoid divisions. Generally, the multiples [i]P of P will end up having“rational” coordinates (i.e. a ratio of a numerator and a denominator) so thatthe denominators infect all the calculations. This theorem enables all of them to
be avoided.
8.2

The Frobenius Automorphism

The final exponentiation by r0 = (q k −1)/r can sometimes benefit from the Frobenius automorphism on K. If p = char(K) is the characteristic of K, then the
Frobenius automorphism is the map γ→γ p for γ ∈ K. This is used for fields ofvery small characteristic or those for which the exponent has few non-zero digits
modulo the characteristic.
If Fm is a subfield of K with order m = pj for some j, then elements of
K can
be stored using a representation of K as a vector space over Fm . If
Pn−1
γ = i=0 γi bi , γi ∈Fm , is the representation of γ∈K using basis (b0 , b1 , ..., bn−1 )
Pn−1
Pn−1
Pn−1 mover Fm then γ m = ( i=0 γi bi )m = i=0 γim bmi =i=0 γi bi because, for thesecond equality, all the binomial coefficients of the omitted terms are multiplesof the characteristic p, and, for the third equality, the order m−1 of F∗m meansγim = γi by Lagrange’s theorem. Thus,• Raising to the power of the characteristic requires no general field multiplications, only constant multiplications and additions.
The values of bm
i are pre-computed and used for this – in any application of
pairing-based cryptography the field K is usually fixed and so this is generally
done once in the lifetime of the application. The bm
i are linear combinations of theoriginal basis elements, hence the constant multiplications and additions. With
careful choice of the field representation, such as a normal basis, the constants
are small or even trivial.
To take advantage of the cheap Frobenius automorphism, there is a base manalogue of square-and-multiply, namely m-ary exponentiation. Each iteration
raises the value so far to the power m, and multiplies in the pre-computed value
corresponding to the coefficient:
ALGORITHM: m-ary Exponentiation
Pn−1
INPUTS: γ ∈ K, r0 = i=0 ri mi .
0
OUTPUT: γ r .
Pre-compute and store the occurring values γ riΓ ← γ rn−1
For i ← n-2 downto 0 do
{ Γ ← Γ m ; if ri 6= 0 then Γ ← Γ ×γ ri }Return Γ
For small characteristic and m = char(K) > 2 this is normally cheaper than awindowing method using the base 2 representation of r0 because raising to the18

Pairings, C. D. Walter

power m is so cheap and squaring relatively expensive. Note also, of course, thatsquaring is cheap when char(K) = 2.
The same cheapness is true for larger characteristics providing that only a
few different small digits appear in the base m representation of the exponent
r0 = (q k −1)/r. This turns out to be almost the case for many constructions,√which tend to concentrate pairing-friendly curve sizes at the limits q±2 q+1 or√√at natural division points of Hasse’s bounds q−2 q ≤ |E(K0 )−1| ≤ q+2 q on
the size of the elliptic curve. (All the super-singular curves have this property,
for example – see [6], Thm. IX.20.) Thus a representation of n = |E(K0 )| to√base q or q is often possible with just two or three tiny digits. (Recall that r is
usually a very large prime factor of n.) We can convert the exponentiation to thepower r0 into one to the power n0 = (q k −1)/n if n divides q k −1: for P ∈E(K0 )[r],n = |E(K0 )| dividing q k −1 and the obvious notation, the property(q k −1)/re(P, Q) = hP, Qir(q k −1)/n= hP, Qinholds. (The two Tate pairings are those related to the subgroups of points withorder dividing r and n respectively.) Since the co-factor n/r is preferably verysmall, there is a good chance that n = |E(K0 )| will divide q k −1, so that we can(q k −1)/ncompute hP, Qin
instead. When n/r is small this requires only a few moreiterations in Miller’s algorithm. Moreover, the form of n means n0 = (q k −1)/n
has a good chance of having a sparse representation in base p = char(K), which iswhat is required to obtain the greatest benefit from the Frobenius automorphism.
Example√For q = 3163 there is a super-singular curve of order n = q− 3q+1 = 3163 −382 +1= 7r for a prime r and its embedding degree is 6 since n is a factor of q 2 −q+1
which divides the factor q 3 +1 of q 6 −1. So we can evaluate the pairing using nrather than √r. The final exponentiation is then by n0 = (q 6 −1)/n = (q 3 −1)(q+1)n
for n = q+ 3q+1 = 3163 +382 +1. Hence there is a base 3 representation of n0
with at most 2×2×3 = 12 small non-zero digits. This makes exponentiation by
n0 extremely fast.
Note further that m-ary exponentiation could be used advantageously inMiller’s algorithm. For example, in characteristic 3, direct point tripling is cheaper
than forming [3]P from P +[2]P (see §9.2). Moreover, the scalar r can be written
in base 3 using only the digits 0, ±1. As illustrated in the example, the chosen
number of iterations n may also have almost no non-zero digits in its base 3
representation. So there could be considerable savings.

9

Pairing-Friendly Curves

The need for “pairing-friendly” curves has already been noted. They have asmall embedding degree, and usually a large prime factor in the curve order.
There are now a number of different families of such curves. A good referenceis the “Taxonomy” paper of Freeman, Scott and Teske [13]. Two representativeLausanne Cryptographic Engineering

19

cases are studied here, namely the super-singular curves and the MNT curves.
There are a number of individual curves that have been studied in the research
literature and for which there are speed details and, hopefully, also the necessary
implementation details for achieving the claimed speed. The IACR ePrint libraryis a good source for these, e.g. [5]. There is no obvious reason not to choose such
curves when they belong to families for which there are no security reservations.
9.1

Super-Singular Elliptic Curves

Definition 3. An elliptic curve E defined over a field Fq of characteristic p issuper-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 the characteristic on supersingular curves. A list of popular super-singular curves is given in [6] Table IX.1.
√
Recall that the trace t is bounded by |t| ≤ 2 q according to Hasse’s bound.
However, the only choices for super-singular curves satisfy:
•
•
•
•
•

t = 0 with k = 2,√t = ±2 q with k = 1,√t = ± q if char(F) ≡ 0, 2 (mod 3) with k = 3,√t = ± 2q if char(F) = 2 with k = 4, or√t = ± 3q if char(F) = 3 with k = 6.

√
If r > 4 q is a large prime divisor of the order of a super-singular curve
over 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}. This means that there are
no difficulties between the two arguments E(K)[r] and E(K)/rE(K) of thepairing: by restricting the latter to classes of E(K)[r] we just get E(K)[r] forboth arguments. There is also a nice “distortion” map which maps E(K0 )[r]to another subgroup of E(K) with order r (corresponding to the image of thecurve over a conjugate of K0 ) so that the two generate the full group E(K)[r]on which the pairing is of interest. The advantage of this is that half the work ofa pairing calculation is avoided: all the denominators can be ignored – see §9.3
below and [2].
The most frequently used constructions for these curves are the following:• E : y 2 = x3 +a over Fp , where p ≡ 2 (mod 3).
Here |E(Fp )| = p+1, t = 0, k = 2, and the distortion map is (x, y) 7→ (ζ3 x, y)
where ζ3 is a primitive cube root of 1.
• E : y 2 = x3 +x over Fp , where p ≡ 3 (mod 4).
Here |E(Fp )| = p+1, t = 0, k = 2, and the distortion map is (x, y) 7→ (−x, iy)where i is a primitive fourth root of 1.
• E : y 2 = 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, t = −p, k = 3, and the distortion
map is (x, y) 7→ (γbxp , by p ) where b = a−(p−1)/2 and γ 3 = a−1 for γ ∈ Fp6 .

20

Pairings, C. D. Walter• E : y 2 +y = x3 +x+a √where Fq , q = 2l for odd l and a ∈ F2 .
Here |E(Fq )| = q ± 2q+1 according to the choice of a, k = 4, and the
distortion map is (x, y) 7→ (u2 x+s2 , y+u2 sx+s) where u2 +u+1 = 0 for
u ∈ F4 and s2 +(u+1)s+1 = 0 for s ∈ F16 .
l∗• E : y 2 = x3 −x+a where√ Fq , q = 3 for odd l and a ∈ F3 .
Here |E(Fq )| = q ± 3q+1 according to the choice of a, k = 6, and the
distortion map is (x, y) 7→ (α−x, iy) where i ∈ F9 is a fourth root of 1 andα ∈ F27 satisfies α3 −α−a = 0.
Suitable fields and curves with these parameters are found as follows. First,
systematically choose random numbers p of the required magnitude for the characteristic, applying the Rabin-Miller primality testing algorithm to check primality, and then running it again on r where r is obtained from n = |E(K0 )|using the above formula, and removing all small factors. Note that Rabin-Miller
need only be run initially enough times to give a reasonable chance that p isprime. If r turns out to have a high probability of being prime, then p can bechecked further. Typically a sieve of Eratosthenes is used on a large intervalof numbers p with a given residue mod 210, say, in which all elements with aprime divisor less than 216 , say, have been tagged. Rabin Miller is run a few
times on the surviving elements. The probability of both p and n being prime isO(log(n)−1 log(p)−1 ), and so suitable primes p are not difficult to find. Assuming
you can already construct the field K0 , the embedding field here is given for caseswith char(K0 ) 6= 2, 3 by adjoining the elements α, i, γ and ζ3 , as appropriate.
For char(K0 ) = 2, 3 the choice of fields is very limited: for q = 2l or q = 3l
there are very few reasonable cases where |E(Fq )| has a large enough prime
factor; q = 3163 is a case mentioned above. There are tables of irreducible polynomials for generating finite fields from which F2251 = F2 [t]/(t251 +t7 +t4 +t2 +1),
for example (e.g. [27]). Note that fast multiplication methods, such as KaratsubaOfman and Toom, are useful for typical fields in elliptic curve cryptography.
9.2

Characteristic 2 and 3 fields

This is a brief aside on the connection between P 7→ [p]P on a super-singularcurve with characteristic p and the Frobenius map α 7→ αp when p = 2, 3.
Take char(K)=2 first, with E : y 2 +y = x3 +x+a so that k = 4. Take P =(x1 , y1 ) ∈ E. The tangent at P is ` : y = λ(x−x1 )+y1 where λ = x21 +1. This
intersects the curve again at x2 = λ2 = x41 +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 = (x41 +1, x41 +y14 )if a ∈ F2 , so that doubling requires just four squarings (the Frobenius) and some
additions, and the lines for Miller’s algorithm are a by-product. Obviously also
16[4]P = (x16
1 , y1 +1) .

For char(K)=3 take the curve E : y 2 = x3 +a4 x+a6 and point P = (x1 , y1 )on E. The tangent at P has slope λ = 1/y1 and so is ` : x = y1 y−y12 +x1 . This

Lausanne Cryptographic Engineering

21

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 λ0 = y13 −λ, from which one can deduce[3]P = (x91 +a6 (1−a4 ), −y19 ) .
Again, there are no divisions and the tripling is given by several applicationsof the Frobenius, which is very efficient. So pairing calculations for fields ofcharacteristic 3 should be performed with 3-ary exponentiation.
9.3

Distortion Maps and Vertical Lines

Super-singular curves have “distortion” maps. Suppose E(K) has no points oforder r2 , φ is a non-rational endomorphism of E, and Q ∈ E(K0 )[r]. If φ(Q) ∈/E(K0 ) then e(Q, φ(Q)) 6= 1. Such a φ is called a distortion map, and some werelisted in §9.1. They only exist for super-singular curves, but calculating the Tatepairing at φ(Q) involves only numbers in K0 and its conjugate φ(K0 ). In many
circumstances and the right presentation of the curve equation, these numbers
can be kept sufficiently separate for there to computational savings, particularly
as a result of the final exponentiation killing off elements of K0 in the same way
as noted above. So, for the second parameter in our pairing, using φ(Q) withQ ∈ E(K0 )[r] is cheaper than a more arbitrary choice from E(K)[r] \ E(K0 )[r].
In particular, for the vertical lines v,• The contributions v(φ(Q)), Q∈E(K0 )[r], can be ignored providing the curveparameters are chosen suitably (see [2],Table 2).
This happens mostly because the final exponentiation annihilates v(φ(Q)) in thesame way that it does elements from K0 . This observation saves half the work
before the final exponentiation.
Proof for char 3 (i.e. the case k = 6 with parameters as given above in §9.1).
For the equation y 2 =x3 −x+a, the distortion map is φ(x, y)=(α−x, iy) wheretα, i∈K satisfy α3 −α−a=0, i2 = − 1. By easy induction, α3 =α+a×(t mod 3) fort ≥ 0. The lines v have the form x=c for some c∈K0 , so that v(φ(Q))=α−xQ −c.
tt
As xQ , c ∈ K0 , we have xqQ = xQ and cq = c for t ≥ 0. Sov(φ(Q))q333= αq −xqQ −cq3= α−xQ −c = v(φ(Q)) .

3

Thus v(φ(Q))q −1 = 1. However,
the exponent in the final exponentiation is√(q 6 −1)/r where r divides q ± 3q+1, which is a factor of q 3 +1, not q 3 −1. So the
exponent is a multiple of q 3 − 1. Hence the contribution of v(φ(Q)) to e(P, φ(q))
is 1, and it can be ignored.
tu
9.4

MNT Elliptic Curves

One of the most widely used and oldest of the non-singular pairing-friendly
curves are the MNT curves. “MNT” refers to the authors Miyaji, Nakabayashi

22

Pairings, C. D. Walter

and Takano of these curves [21]. Our main interest is implementing pairings
efficiently on some device, assuming the curve is given, and that has been covered
in previous sections. This section, which may be skipped, outlines the work
involved if one’s own MNT curve has to be generated.
MNT curves are ordinary curves (i.e. not super-singular) with “complex multiplication” and require some effort to generate. In particular, the construction
requires the Weber class polynomial [1,16] which typically has degree up to 103
and coefficients in C of up to 103 bits for the cases here, for which the relevant“discriminant” has a value up to 232 (a single word) in absolute value. To keep
the time complexity reasonable, the use of Karatsuba-Ofman or similar is essential for multiplying both complex numbers and polynomials in these calculations.
Space complexity is also at the limit of reasonable computing because of the sizeof the numbers and polynomials. There are recent improvements by Enge andothers which construct these polynomials modulo a variety of primes and thenapply the Chinese Remainder Theorem to deduce their coefficients modulo thecharacteristic of the chosen K0 , see e.g. [10,11]. The details of both the classicaland the modern construction methods are beyond the scope of this course –generally one should use dedicated computation packages, such as Mike Scott’s
Miracl software [26], to find the desired curve. Then the detail of the calculations
can be avoided. Those interested in the basics can consult section §A.12 of thenumber-theoretic appendix to the IEEE’s P-1363 standard [16,17]9 .
The construction begins with a factorisation of the polynomial xk −1, (k =3, 4, 6) to obtain necessary values for the trace t = q+1−|E(Fq )|. These areparameterised by an integer l:
k
3
4
6

q
12l2 − 1l2 + l + 1
4l2 + 1t
−1 ± 6l−l or l + 1
1 ± 2l√For example, the curve order for k = 6 is q ∓ q−1, which is a factor of q 2 −q+1,
which in turn divides q 3 +1 and q 6 −1, establishing that k = 6. As in the case of
the super-singular curves, l and k are chosen to give fields K0 , K of the desired
size, with the parameter l being varied until q is prime and the curve order
q+1−t has a sufficiently large prime factor r.
However, there is an added complication in selecting l, namely that the discriminant ∆ = t2 −4q must consist of a large square times a small square-free
factor (typically under 232 ) or else the numbers become too large10 and the likelihood of finding solutions of the required size becomes too small. As an example,
consider the case when k = 6. Then ∆ = t2 − 4q = −12l2 ± 4l − 3. Writing∆ = y 2 δ, one has to solve y 2 δ = −12l2 ± 4l − 3, i.e. −3y 2 δ = (6l ∓ 1)2 + 8. So
we require solutions (x, y) to the Diophantine equation x2 + 3δy 2 = −8. These
are given in a similar way to those for Pell’s Equation x2 + 3δy 2 = 1 which come9

The class polynomial section has a hard-to-find sign error at least in the early editionsof this standard.
10
Specifically, the degree of the Weber polynomial and its coefficients become too large.

Lausanne Cryptographic Engineering

23√
from the continued fraction approximation
to −3δ. Of course, this means com√puting a very accurate value for −3δ. One solution to x2 + 3δy 2 = −8 can be
combined with the fundamental solution of x2 + 3δy 2 = 1 to obtain a series ofincreasingly large solutions, among which might be one that yields a value for lin the required range. Typically, many values of ∆ must be tried before a prime
l of the right size is found.
The next problem is to construct the Weber class polynomial w∆ (t). (The
Hilbert class polynomial is too large√ for the applications here.) Its roots are
known complex numbers related to −∆. Details are given in [1,17] and involvethe sine and cosine functions. The roots need to be calculated sufficiently accurately and then the linear factors multiplied together to obtain the polynomialwith sufficient accuracy for its coefficients to be known with an accuracy better
than 12 . Since the coefficients are (huge) integers, the polynomial is then known
exactly. This is now reduced modulo the field characteristic p. A linear or cubic
factor g(t) of the polynomial must now be extracted – there are algorithms forthis. Then the coefficients a, b ∈ Fp of the curve equation y 2 = x3 +ax+b arederived from g(t) with some straight-forward manipulation.
Finally, the curve has only a 50-50 chance of having the right order. The
ambiguity in the curve order is reflected in the ± sign. Only one of the twosigns gives a size divisible by r. The next stage is to check which curve has
been obtained. Choose a random (non-zero) point on the curve. Multiply it by
the intended curve size over r to make sure it is not killed by a small factor of
the group order. Then multiply it by the group order. If the result is O, thenthe right curve has been found. Otherwise, return to the factor g(t) to make adifferent choice of coefficients a, b.

10

Elliptic Curves Coordinates

This section just contains a few remarks on the representation of the curve. The
choice of coordinate system can make a substantial difference to the efficiency
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. However, the difference in speeds between the fastest and the slowest
curve additions is within a factor of about 2. So at best the pairing will bedone at twice the speed with another choice. A useful list of the various main
addition and doubling formulae is given by Bernstein & Lange [4]. They aremostly just variations on a theme, with the Weierstraß affine coordinates as astandard example – see Prof. Koç’s lecture.
The usual equation over Fp , p odd, is the short Weierstraß form11
y 2 = x3 + ax + b
for which the addition and doubling formulae for (x1 , x2 )+(x2 , y2 ) = (x3 , y3 )and [2](x1 , y1 ) = (x2 , y2 ) are given byx3 = λ2 − x1 − x2
11

2

3

2

where λ = (y2 −y1 )/(x2 −x1 )E : y + xy = x + a2 x + a6 for F2n .

24Pairings, C. D. Walter
y3 = λ(2x1 +x2 ) − λ3 − y1andx2 = (3x21 +a)2 /(2y1 )2 − x1 − x1y2 = (2x1 +x1 )(3x21 +a)/(2y1 ) − (3x21 +a)3 /(2y1 )3 − y1
Note that the addition formula cannot work for doubling since it gives the value
0/0. Note also the cost is made up of general field multiplications, field additions
and subtractions, multiplications by small constants, and an inversion. This is
the cost that is normally used to compare most alternatives, but be aware that
communication costs between processor and memory may also be significant, as
may be the costs of moving data between registers.
When there are points of order three, an elliptic curve has points (x, y) satisfying the following Hessian form equation:
x3 + y 3 + 1 = 3dxy
The addition and doubling formulae are, respectively,
x3 = (y12 x2 −y22 x1 )/(x2 y2 −x1 y1 )y3 = (x21 y2 −x22 y1 )/(x2 y2 −x1 y1 )andx2 = y1 (1−x31 )/(x31 −y13 )y2 = x1 (y13 −1)/(x31 −y13 )The (additive) inverse is given by −(x1 , y1 ) = (y1 , x1 ). There is a strong symmetry between the x and y coordinates here, as can be seen immediately fromthe equation. Again, just one inversion appears, being the result of computing
the gradient of the chord or tangent on the curve. Counting the other field operations shows this to have about two thirds of the cost of the Weierstraß form.
Most other representations fall between these two in terms of efficiency.
As noted in §7.4, Galbraith has compared affine and projective coordinatesand found the latter not to provide a noticeable advantage despite claims in theliterature. Although the requirement for speed is perhaps most acute in embedded systems, side-channel leakage may be a problem there, primarily enablingadds and doubles to be distinguished. Of course, the curve parameters, including
the scalar r and final exponent r0 , are public, but P is the private key in decryption for the Boneh-Franklin scheme. So its value must not be leaked during
the execution of Miller’s algorithm. There are many different solutions to suchleakage. We could, for example, note that the projective representation of the
Hessian form uses the same formula12 for both addition and doubling, and sochoose that. These issues are covered elsewhere in this course, often by ensuring
12

The formula is [2](X1 , Y1 , Z1 ) = (Z1 , X1 , Y1 ) + (Y1 , Z1 , X1 ).

Lausanne Cryptographic Engineering

25

that adding and doubling formulae execute the same sequence of field operations.
This means, in particular, that the above formulae do not have quite enough detail for us. Specifically, the order of executing the various field operations andread and write operations needs to be given also... This is another story.

11

Finite Field Construction

Constructing finite fields is an important topic. This has been covered by Prof.
Koç in his presentations. One of the problems is that curves chosen for theefficiency of their arithmetic, such as those in the standards produced by NIST
and Certicom [12], are not generally suitable for pairing-based cryptography as
the embedding degree k is far too large. Therefore one has to generate one’s own
field. There are two main cases: very small or very large characteristic.
For small characteristics, there is a choice between polynomial and normalbases. The frequent use of the Frobenius in the final exponentiation and, indeed,
its appearance in point multiplication by the characteristic should be borne inmind when deciding between the two. This suggests that a normal basis would
be better. There are tables of irreducible polynomials and techniques to obtainnormal bases for such cases [27]. The polynomials are generally sparse (typicallyno worse than pentanomials), so that a polynomial basis is also not so expensive
to implement.
For larger characteristics p, the standard classical technique is to choose p tohave low Hamming weight (in a suitable representation such as binary of NAF)
so that field multiplications are cheap. This is the exact analogy of choosing
a sparse polynomial in the low characteristic case. Unfortunately, in pairingbased cryptography, we do not generally have the luxury of a choice of p as itis essentially random. The extension degree of K over Fp is generally small –usually a divisor of 24. Hence the generating polynomial for K/Fp has small
degree and it is feasible to search for a suitable irreducible polynomial with verysmall coefficients (one computer word), hopefully with many being zero.

12

Appendix: Other Essential Algorithms

There are a number of other basic but necessary algorithms which there has beenno time to cover. They are generally mostly straightforward. Many are found in
the very readable IEEE P1363 [17]13 . Here’s a list of them:– The Rabin-Miller Primality Test. This is needed in checking for prime characteristic when generating MNT curves, and for finding large prime factors
in the order of any curve.
13

P1363.3 begins with a brief overview of the main definitions, terminology and algorithms. It is a useful proof-free summary which is easily read by those with amathematical background. It is comprehensive, starting with modular arithmetic
and finite fields.

26

Pairings, C. D. Walter– Square Root Algorithm. This is used when generating random or other points
on a curve when only the x-coordinate is present, as in point compression.
Using the curve equation, the y-coordinate is the square root of a polynomial
in x. (A point can be represented by its x-coordinate and a bit to determine
which of the two values of the y-coordinate to select.)– The SEA Point Counting Algorithm. Named after the originator Schoof andsubsequent developers Elkies and Atkin, this is for finding the order of anelliptic curve. It is a complex and time-consuming algorithm. By picking
curves with complex multiplication, it can be avoided. Usually one only has
to check the order against a claim, and this can be done by verifying theorder of a random point, as observed in §9.4.
Generally speaking, there is no need to implement algorithms such as SEA
or Rabin-Miller. These are available in many software packages, such as Scott’s
Miracl [26].

References
1. A.O.L. Atkin & F. Morain, Elliptic Curves and Primality Proving, Math. Comput.
61(203), July 1993, pp. 29–68.
2. P.S.L.M. Barreto, H.Y. Kim, B. Lynn & M. Scott, Efficient Algorithms for PairingBased Cryptosystems, Crypto 2002, LNCS 2442, pp. 354–368.
3. P. Barreto, Pairing Based Crypto Lounge, at
http://www.larc.usp.br/∼pbarreto/pblounge.html
4. D. Bernstein & T. Lange, Explicit-Formulas Database, at
http://hyperelliptic.org/EFD/index.html
5. J.-L. Beuchat, J.E.G. Daz, S. Mitsunari, E. Okamoto, F. Rodrguez-Henrquez &T. Teruya, High-Speed Software Implementation of the Optimal Ate Pairing over
Barreto-Naehrig Curves, ePrint 2010/354, IACR.
6. I.F. Blake, G. Seroussi & N.P. Smart, Advances in Elliptic Curve Cryptography:
Further Topics, LMS Lecture Note Series 317, Cambridge Univ. Press, 2005.
7. D. Boneh & M. Franklin, Identity-Based Encryption from the Weil Pairing, SIAM
J. Computing 32(3), pp. 586–615, 2003. (See also Crypto 2001, LNCS 2139, pp.
213–229.)
8. K. Eisenträger, K. Lauter & P.L. Montgomery, Fast Elliptic Curve Arithmetic and
Improved Weil Pairing Evaluation, CT-RSA 2003, LNCS 2612, Springer-Verlag
2003, pp. 343–354.
9. K. Eisenträger, K. Lauter & P.L. Montgomery, Improved Weil and Tate Pairings
for Elliptic and Hyperelliptic Curves, ANTS VI, LNCS 3076, Springer-Verlag 2004,
pp. 169–183.
10. A. Enge, The Complexity of Class Polynomial Computation via Floating Point
Approximations, Math. Comp. 78(2009), pp. 1089–1107.
11. A. Enge & A.V. Sutherland, Class Invariants by the CRT Method, ANTS IX, LNCS
6197, Springer-Verlag 2010, pp. 142–156.
12. Digital Signature Standard (DSS), FIPS Pub 186-3, National Institute of Standards
and Technology (NIST), June 2009.
13. D. Freeman, M. Scott & E. Teske, A Taxonomy of Pairing-Friendly Elliptic Curves,
IACR ePrint 2006/372.

Lausanne Cryptographic Engineering

27

14. S. Galbraith, Elliptic Curve Cryptography, http://www.isg.rhul.ac.uk/∼sdg/ecc.html(for a good overview of the best books in the area.)
15. S. Galbraith, K. Harrison & D. Soldera, Implementing the Tate Pairing, HPL2002-23, HP Labs, 2002. Also ANTS 2002, LNCS 2369, Springer-Verlag, 2002,
pp. 324–337.
16. IEEE P1363-2000 IEEE Standard Specifications for Public-Key Cryptography, Annex A: Number-Theoretic Background, §A.12.1, IEEE 2000.
http://grouper.ieee.org/groups/1363/P1363/index.html
17. IEEE P1363.3 Standard for Identity-Based Cryptographic Techniques Using Pairings, http://grouper.ieee.org/groups/1363/IBC/
18. A. Joux, A One Round Protocol for Tripartite Diffie-Hellman, Algorithmic Number
Theory, LNCS 1838, Springer-Verlag 2000, pp. 385-394. and J. Cryptology 17(4),Sept 2004, pp. 263–276.
19. M. Joye, The Montgomery Powering Ladder, CHES 2002, LNCS 2523, SpringerVerlag 2003, pp. 291-302.
20. A. Menezes, T. Okamoto & S. Vanstone, Reducing Elliptic Curve Logarithms to
Logarithms in a Finite Field, IEEE Trans. Inform. Thy. 39, 1993, pp. 1639–1646.
21. A. Miyaji, M. Nakabayashi & S. Takano, New explicit conditions of elliptic curve
traces for FR-reductions, IEICE Trans on Fundamentals, E84-A(5), pp. 1234–
1243, 2001.
22. P.L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization,
Mathematics of Computation, 48(177) Jan 1987, pp. 243-264.
23. K. Ohgishi, R. Sakai & M. Kasahara, Notes on ID-based Key Sharing Systems
over Elliptic Curve, IEICE Technical Report, ISEC 99(414) Nov. 1999, pp. 37–42.
(Available at http://ci.nii.ac.jp/naid/110003298699/.)
24. R. Sakai, K. Ohgishi & M. Kasahara, Cryptosystems based on Pairing, SCIS ’2000,
Okinawa, Japan, Jan. 2000, pp. 26–28.
25. M. Scott, The Tate Pairing, http://www.computing.dcu.ie/∼mike/tate.html
26. M. Scott, Multiprecision Integer and Rational Arithmetic C/C++ Library (Miracl),
Shamus Software, Ireland.
27. G. Seroussi, Table of Low-Weight Binary Irreducible Polynomials, HPL-98-135, HP
Labs, 1998.
28. A. Shamir, Identity-based Cryptosystems and Signature Schemes, Crypto ’84,
LNCS 196, pp. 47–53.
29. J.H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics
106, Springer-Verlag, 2nd ed., 2009.