Elliptic-Curve Cryptography (ECC)

Abhijit Das

Department of Computer Science and Engineering

Indian Institute of Technology Kharagpur

Talk presented in the

Second International Conference on Mathematics and Computing (ICMC 2015)
Haldia, 5–10 January, 2015
Elliptic Curves and Cryptography

Koblitz (1987) and Miller (1985) first recommended the use of

elliptic-curve groups (over finite fields) in cryptosystems.
Use of supersingular curves discarded after the proposal of the
Menezes–Okamoto–Vanstone (1993) or Frey–Rück (1994) attack.
ECDSA was proposed by Johnson and Menezes (1999) and adopted as a
digital signature standard.
Use of pairing in new protocols
Sakai–Ohgishi–Kasahara two-party key agreement (2000)
Boneh–Franklin identity-based encryption (2001)
Joux three-party key agreement (2004)
Boneh–Lynn–Shacham short signature scheme (2004)

Numerous other applications of pairing after this.

Supersingular curves are frequently used in these pairing-based protocols.
Organization of the Talk

Part 1: Arithmetic of Elliptic Curves (over Finite Fields)

Part 2: Classical Elliptic-Curve Cryptography

Part 3: Efficient Implementation

Part 4: Introduction to Pairing

Part 5: Pairing-Based Cryptography

Part 6: Sample Application—ECDSA Batch Verification

 PART 1
ARITHMETIC OF ELLIPTIC CURVES
Elliptic Curves

Let K be a field.

An elliptic curve E over K is defined by the Weierstrass equation:

E : y2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 , ai ∈ K.

The curve should be smooth (no singularities).

Special forms
char K 6= 2, 3: y2 = x3 + ax + b, a, b ∈ K.
char K = 3: y2 = x3 + b2 x2 + b4 x + b6 , bi ∈ K.
char K = 2:
Non-supersingular or ordinary curve: y2 + xy = x3 + ax2 + b, a, b ∈ K.
Supersingular curve: y2 + ay = x3 + bx + c, a, b, c ∈ K.
Real Elliptic Curves: Example

y y

x x

(a) y2 = x3 − x + 1 (b) y2 = x3 − x
The Elliptic-Curve Group

Any (x, y) ∈ K 2 satisfying the equation of an elliptic curve E is called a

K-rational point on E.

Point at infinity:
There is a single point at infinity on E, denoted by O.
This point cannot be visualized in the two-dimensional (x, y) plane.
The point exists in the projective plane.

E(K) is the set of all finite K-rational points on E and the point at infinity.

An additive group structure can be defined on E(K).

O acts as the identity of the group.

The Opposite of a Point

Ordinary Points Special Points

P Q
−Q −P

Q P
−P −Q

(a) (b)
Addition of Two Points

Chord and tangent rule

R Q
Q
R

P P+Q
P
P+Q
(a) (b)
Doubling of a Point

Chord and tangent rule

2P P R

P 2P
R

(a) (b)
Addition and Doubling Formulas

Let P = (h1 , k1 ) and Q = (h2 , k2 ) be finite points.

Assume that P + Q 6= O and 2P 6= O.
Let P + Q = (h3 , k3 ) (Note that P + Q = 2P if P = Q).

E : y2 = x3 + ax + b

−P = (h1 , −k1 )
h3 = λ 2 − h1 − h2
k3 = λ (h1 − h3 ) − k1 , where
k2 − k1 , if P 6= Q,

 h2 − h1


λ =
2
 3h1 + a , if P = Q.


2k1
Addition and Doubling in Non-Supersingular or
Ordinary Curves

E : y2 + xy = x3 + ax2 + b (with char K = 2).

−P = (h1 , k1 + h1 ),
 
k1 + k2 2 + k1 + k2 + h + h + a, if P 6= Q,


1 2

 h1 + h2
 h1 + h2
h3 =
b
 h21 + 2 ,


 if P = Q,
h1
k1 + k2 (h + h ) + h + k , if P 6= Q,
  
1 3 3 1

 h1 + h2

k3 =  
 h2 + h1 + k1 + 1 h3 ,

if P = Q.

1 h1
Addition and Doubling in Supersingular Curves

E : y2 + ay = x3 + bx + c (with char K = 2).

−P = (h1 , k1 + a),
 
k1 + k2 2 + h + h , if P 6= Q,


 h1 + h2

 1 2
h3 =
 h41 + b2 ,



2 if P = Q,
  a
k1 + k2 (h + h ) + k + a, if P 6= Q,

1 3 1

 h1 + h2


k3 =  2 
 h1 + b
(h1 + h3 ) + k1 + a, if P = Q.

a


Size of the Elliptic-Curve Group

Let E be an elliptic curve defined over Fq = Fpn .

Hasse’s Theorem:
√ √
|E(Fq )| = q + 1 − t, where −2 q 6 t 6 2 q.
t is called the trace of Frobenius at q.
If t = 1, then E is called anomalous.
If p|t, then E is called supersingular.
If p6 | t, then E is called non-supersingular or ordinary.
Let α , β ∈ C satisfy 1 − tx + qx2 = (1 − α x)(1 − β x). Then,
|E(Fqm )| = qm + 1 − (α m + β m ).

Note: E(Fq ) is not necessarily cyclic.

Example of Elliptic-Curve Arithmetic
E : y2 = x3 − 5x + 1 defined over F17 .
Take the finite points P = (3, 8) and Q = (10, 13) on E.
Opposite: −P = (3, 9), and −Q = (10, 4).
Point addition
The line L joining P and Q has slope λ ≡ 13−8
10−3 ≡ 8 (mod 17).
L has equation L : y = 8x + c. Since L passes through P, we have c = 1.
Substitute this in the equation for E to get (8x + 1)2 ≡ x3 − 5x + 1 (mod 17), that
is, x3 + 4x2 + 13x ≡ 0 (mod 17), that is, x(x − 3)(x − 10) ≡ 0 (mod 17).
The third point of intersection is (0, 1), so P + Q = −(0, 1) = (0, 16).

Point doubling
2
−5
The tangent T to E at P has slope 3×3
2×8 ≡ 12 (mod 17).
The equation for T is y = 12x + 6.
Substitute T in E to get x3 + 9x2 + 4x + 16 ≡ 0 (mod 17), that is,
(x − 3)2 (x − 2) ≡ 0 (mod 17).
The third point of intersection is (2, 13), so 2P = −(2, 13) = (2, 4).
 PART 2
CLASSICAL ELLIPTIC-CURVE CRYPTOGRAPHY
The Classical Intractable Problems
Let G be a finite cyclic additive group with a generator P. Let r = |G|.

Discrete Logarithm Problem (DLP): Given Q ∈ G, find x such that

Q = xP.
Diffie–Hellman Problem (DHP): Given aP, bP ∈ G (but not a and b),
compute abP.
Decisional Diffie–Hellman Problem (DDHP): Given aP, bP, zP ∈ G (but
not a, b and z), decide whether zP = abP, that is, whether z ≡ ab (mod r).

For elliptic-curve groups of suitable sizes, these problems are assumed to

be intractable.
We use the terms ECDLP and ECDHP to highlight the case of
elliptic-curve groups.
Elliptic-curve groups are not necessarily cyclic, so we usually work in
sufficiently large cyclic subgroups with known generators.
How Easy Is It to Solve ECDLP/ECDHP?
ECDLP and ECDHP are believed to be equivalent.
The DLP for finite fields can be solved by subexponential algorithms (like
NFS and FFS).
For general elliptic curves, subexponential algorithms are neither known
nor likely to exist.
Only the square-root methods work (Baby-Step-Giant-Step, Pollard rho
and lambda, Pohlig–Hellman). For a group of size n, these methods run in
√
O˜( n) time.
The ECDLP on a curve over Fq can be mapped to the finite-field DLP over
Fqk (MOV or FR reduction).
In general, k ≈ n. For supersingular curves, k ∈ {1, 2, 3, 4, 6}.
For anomalous curves, a linear-time algorithm is known for the ECDLP.
Supersingular and anomalous curves are not used in classical ECC.
ElGamal Encryption
Let G be an additive cyclic group of size r and with a generator P.
Permanent key pair (of Bob)
Private key: A random integer d ∈ {2, 3, . . . , r − 1}.
Private key: The group element Y = dP.
Encryption
Alice wants to encrypt the message M ∈ G.
Alice generates a random session private key d′ ∈ {2, 3, . . . , r − 1}.
Alice computes S = d′ P and T = M + d′ Y (where Y is Bob’s public key).
Alice sends (S, T) to Bob.
Decryption
Bob recovers M = T − dS using his private key d.
Correctness: dS = d′ Y = dd′ P.
Security
An eavesdropper knows dP and d′ P.
Computing the mask dd′ P is equivalent to solving an instance of the DHP in G.
Elliptic Curve Digital Signature Algorithm (ECDSA)
Let G be an additive cyclic group of size r and with a generator P.
Key pair: Private key d ∈ {2, 3, . . . , r − 1}, and public key Y = dP.
Signature generation
Bob maps the message M to a representative m ∈ {0, 1, 2, . . . , r − 1}.
Bob generates a random session key d′ ∈ {2, 3, . . . , r − 1}.
Bob computes S = d′ P, s ≡ x(S) (mod r) and t ≡ (m + ds)d′−1 (mod r).
Bob’s signature on M is the pair (s, t).

Signature verification
Compute w ≡ t−1 (mod r), u ≡ mw (mod r), and v ≡ sw (mod r).
Compute V = uP + vY ∈ G (here, Y is Bob’s public key).
Accept the signature if and only if x(V) ≡ s (mod r).

Correctness
d′ ≡ (m + ds)t−1 ≡ (mw + dsw) ≡ u1 + u2 d (mod r).
S = d′ P = uP + vdP = uP + vY.
 PART 3
EFFICIENT IMPLEMENTATION
What to Implement?

A good finite-field library is the basic necessity. We assume that such a

library is available.
Elliptic-curve point addition and doubling are governed by fixed formulas.
The most time-consuming operation in classical ECC is elliptic-curve
scalar multiplication: Given an integer n and an elliptic-curve point P,
compute nP.
It is easy to find the opposite of a point, so we assume n > 0.
Scalar multiplication is the inverse of ECDLP (given P and nP, compute n).
Scalar multiplication behaves like a one-way function.
A lot of optimization techniques apply to scalar-multiplication
implementations.
Here, we deal with software implementations only.
Left-to-Right Scalar Multiplication
We are given a point P on an elliptic curve E defined over some Fq .
We assume that the arithmetic functions of Fq are already available.
Let r be the order of P.
Our task is to compute nP for some integer n ∈ {1, 2, . . . , r − 1}.

Let n = (1ns−1 ns−2 . . . n1 n0 )2 be the binary representation of n.

Initialize S = P.
For i = s − 1, s − 2, . . . , 1, 0, repeat:
Set S = 2S. /* Doubling */
If (ni = 1), then set S = S + P. /* Conditional adding */

Return S.

s doubling operations.
At most s addition operations. s/2 additions on an average.
s ≈ log2 n.
Left-to-Right Scalar Multiplication: Example
Consider the curve E : y2 = x3 + 4x + 3 modulo p = 607.
Take P = (234, 121), and n = 410 = (110011010)2 .
[Init] S = P = (234, 121).
[i = 7] Dbl: S := 2S = (65, 216), Add: S := S + P = (2, 176).
[i = 6] Dbl: S := 2S = (223, 283), Add: skipped.
[i = 5] Dbl: S := 2S = (485, 464), Add: skipped.
[i = 4] Dbl: S := 2S = (484, 76), Add: S := S + P = (573, 25).
[i = 3] Dbl: S := 2S = (31, 196), Add: S := S + P = (403, 378).
[i = 2] Dbl: S := 2S = (461, 250), Add: skipped.
[i = 1] Dbl: S := 2S = (389, 228), Add: S := S + P = (170, 25).
[i = 0] Dbl: S := 2S = (541, 197), Add: skipped.

Therefore, nP = (541, 197). Requires 8D + 4A.

Windowed Scalar Multiplication
Choose a small window size w.

Precompute aP for a = 0, 1, 2, . . . , 2w − 1.
Let n = (Nt Nt−1 Nt−2 . . . N1 N0 )2w be the 2w -ary representation of n.
Initialize S = Nt P (use the precomputed table).
For i = t − 1, t − 2, . . . , 1, 0, repeat:
For j = 0, 1, 2, . . . , w − 1, set S = 2S.
Set S = S + Ni P (use the precomputed table).

Return S.

s doubling operations.
About s/w additions at the cost of 2w additions during precomputation.
Practical choice of window size: w = 4.
Windowed Scalar Multiplication: Example
Consider the curve E : y2 = x3 + 4x + 3 modulo p = 607.
Take P = (234, 121), w = 3, and n = 410 = (110 011 010)2 = (632)8 .
[Precomputation] 2P = (65, 216), 3P = (2, 176), 4P = (368, 523),
5P = (14, 539), 6P = (223, 283), and 7P = (96, 385).
[Init] S := 6P = (223, 283).
[i = 1] Dbl: S := 2S = (485, 464)
Dbl: S := 2S = (484, 76)
Dbl: S := 2S = (431, 45)
Add: S := S + 3P = (403, 378)
[i = 0] Dbl: S := 2S = (461, 250)
Dbl: S := 2S = (389, 228)
Dbl: S := 2S = (402, 361)
Add: S := S + 2P = (541, 197)

Requires 6D + 2A in the loop. Precomputation requires 1D + 5A.

For large exponents, the precomputation overhead is insignificant.
Windowed Method with Reduced Precomputation

We represent n = (Nt Nt−1 Nt−2 . . . N1 N0 )2w for a w-bit window.

Precompute only the odd multiples P, 3P, 5P, . . . , (2w − 1)P.
Express each Ni = 2ri νi with νi odd.
Earlier, we had w doubling operations followed by one addition.
Now, we have:
w − ri doubling operations (S := 2S)
One addition (S = S + νi P)
ri doubling operations (S := 2S)

The counts of doubling and addition operations do not change in the loop.
Precomputation effort is almost halved.
Windowed Method: Example
Consider the curve E : y2 = x3 + 4x + 3 modulo p = 607.
Take P = (234, 121), w = 3, and n = 410 = (110 011 010)2 = (632)8 .
[Precomputation] 2P = (65, 216), 3P = (2, 176), 5P = (14, 539), and
7P = (96, 385).
[Init] S = O.
[i = 2] Dbl: S := 2S = O
Dbl: S := 2S = O
Add: S := S + 3P = (2, 176)
Dbl: S := 2S = (223, 283)
[i = 1] Dbl: S := 2S = (485, 464)
Dbl: S := 2S = (484, 76)
Dbl: S := 2S = (431, 45)
Add: S := S + 3P = (403, 378)
[i = 0] Dbl: S := 2S = (461, 250)
Dbl: S := 2S = (389, 228)
Add: S := S + P = (170, 25)
Dbl: S := 2S = (541, 197)
Sliding (Non-Adjacent) Window Method
Precompute only the odd multiples of P.
Skip 0’s after a window (do doubling operations only).
The next window starts at the first 1 located after the last window.
The next window is handled as in the windowed method with reduced
precomputation.

Example: Take n = 410 = (110011010)2 .

The windows are: 110 0 110 10.
Now, the sequence of operations is:
Init S to O.
First window: Dbl, Dbl, Add (3P), Dbl.
Skip: Dbl.
Second window: Dbl, Dbl, Add (3P), Dbl.
Third window: Dbl, Add (P), Dbl.
Signed Binary Representation

Allow negative digits.

Represent n as (nt nt−1 nt−2 . . . n1 n0 )2 = ∑ti=0 ni 2i with each ni ∈ {−1, 0, 1}.
If no two consecutive digits are non-zero, this representation is called a
non-adjacent form (NAF).
It is easy to precompute −P.
Replace runs of consecutive 1’s.
. . . 0111110 . . . can be replaced by . . . 100001̄0 . . . , where 1̄ = −1.
Signed-binary representation of n is not unique. For example,
23 = 16 + 4 + 2 + 1 = (10111)2 = 16 + 8 − 1 = (11001̄)2 = 32 − 8 − 1 =
(101̄001̄)2 .
The NAF representation is unique and has the least possible number of
signed digits.
Computation of NAF
Let n = (ns ns−1 ns−2 . . . n1 n0 )2 .
We add n with 2n. The sum may have a bit-size two more than that of n.
n 0 0 ns ns−1 ... n2 n1 n0
2n 0 ns ns−1 ns−2 ... n1 n0 0
3n ds+1 ds ds−1 ds−2 ... d1 d0 n0
Output carry cs+2 cs+1 cs cs−1 ... c2 c1 c0
We have ci+1 = ⌊(ni + ni+1 + ci )/2⌋, and di = ni + ni+1 + ci − 2ci+1 .
Now, we subtract n from 3n and discard the rightmost zero bit. We do not
do any borrow adjustment here, that is, 0 − 1 is retained as 1̄ = −1.
3n ds+1 ds ds−1 ds−2 . . . d1 d0 n0
n 0 0 ns ns−1 . . . n2 n1 n0
2n ms+1 ms ms−1 ms−2 . . . m1 m0 0
Therefore, mi = di − ni+1 = ni + ci − 2ci+1 .
di need not be computed. ci+1 and mi can be computed from ni , ni+1 , ci
alone. Table lookup can be used (only eight cases).
Computation of NAF: The Algorithm
Let n = (ns ns−1 ns−2 . . . n1 n0 )2 . We take ns+1 = ns+2 = 0.
To compute the NAF (ms+1 ms ms−1 . . . m1 m0 ) of n.

Initialize c = 0.
For i = 0, 1, 2, . . . , s + 1, repeat: /* You may use table lookup */
Set cnext = ⌊(ni + ni+1 + c)/2⌋.
Set mi = ni + c − 2cnext .
Set c = cnext .
Return (ms+1 . . . m1 m0 ).

The digits are generated in the right-to-left order.

The expansion must be stored for use in left-to-right scalar-multiplication
algorithms.
Algorithms for left-to-right generation of optimal signed binary
representation are also known.
Computation of NAF: Examples
Take n = 23 = (10111)2 .
n = 23 0 0 1 0 1 1 1
2n = 46 0 1 0 1 1 1 0
Computation of n + 2n:
3n = 69 1 0 0 0 1 0 1
Output carry 0 1 1 1 1 1 0
3n = 69 1 0 0 0 1 0 1
Computation of 3n − n: n = 23 0 0 1 0 1 1 1
2n = 46 1 0 1̄ 0 0 1̄ 0
Therefore, n = 23 = (101̄001̄)2 = 25 − 23 − 20 .
The NAF for 410 is 101̄0101̄010.
For a 3-bit sliding window, we need to precompute ±P, ±3P, ±5P, ±7P.
Now, the odd-valued windows are 101̄ 0 101̄ 0 1 0
The NAF property guarantees that at least one zero exists between two
consecutive windows.
Width-w Non-Adjacent Form (wNAF or NAFw )
Take an integer width w > 2.
Represent n in the base 2.
The signed digits are zero or odd integers with absolute values < 2w−1 .
Among any w consecutive digits, at most one is non-zero.
The wNAF representation is unique and optimal.
The average density of non-zero digits in the wNAF representation is
1/(w + 1).
The basic NAF corresponds to w = 2.

Some other variants based on addition chains

Signed fractional window method
Mixed radix
τ -NAF (applicable to Koblitz curves)
Computation of the wNAF

Set i = 0.
While (n > 0), repeat:
If n is even, set mi = 0,
else set r = n rem 2w , if r > 2w−1 , set r = r − 2w , set mi = r and n = n − r.
Set n = n/2 and increment i.

Return (mi−1 mi−2 . . . m2 m1 m0 ).

This expansion is from right to left.

If n is even, then we get the next digit as 0.
If n is odd, we compute the next (odd) remainder r of n modulo 2w . It is
ensured that r lies in the range [−(2w−1 − 1), +(2w−1 − 1)].
When this r is subtracted from n, it is guaranteed that the next w − 1 digits
are all 0.
Computation of the wNAF: Example
Let us compute the width-4 NAF of n = 1234567.
i n mi n − mi (n − mi )/2
0 1234567 7 1234560 617280
1 617280 0 308640
2 308640 0 154320
3 154320 0 77160
4 77160 0 38580
5 38580 0 19290
6 19290 0 9645
7 9645 −3 9648 4824
8 4824 0 2412
1234567 = (1000300005̄0003̄0000007)
9 2412 0 1206
= 220 + 3 × 216 + (−5) × 211 +
10 1206 0 603
(−3) × 27 + 7.
11 603 −5 608 304
12 304 0 152
13 152 0 76
14 76 0 38
15 38 0 19
16 19 3 16 8
17 8 0 4
18 4 0 2
19 2 0 1
20 1 1 0 0
Multiple Scalar Multiplication
Let P, Q be elliptic-curve points, and m, n positive integers of the same
bit-size. We can compute mP + nQ in a single loop.

Precompute the point P + Q.

Let m = (ms ms−1 ms−2 . . . m1 m0 )2 be the binary representation of m.
Let n = (ns ns−1 ns−2 . . . n1 n0 )2 be the binary representation of n.
Initialize S = O.
For i = s, s − 1, s − 2, . . . , 1, 0, repeat:
Set S = 2S.
If (mi , ni ) = (1, 0), set S = S + P,
else if (mi , ni ) = (0, 1), set S = S + Q,
else if (mi , ni ) = (1, 1), set S = S + (P + Q) (use precomputed value).

Return S.
Multiple Scalar Multiplication (Contd)
Comparison with two scalar multiplications
The number of doubling operations is halved.
On an average, the number of addition reduces from s to 34 s.

Windowed adaptation
Precompute aP + bQ for all a, b ∈ {0, 1, 2, . . . , 2w − 1}.
w = 2 is a practical choice.
w > 3 calls for too much precomputation.

Generalization to the sum of three (or more) scalar products

To compute lP + mQ + nR.
Precompute P + Q, P + R, Q + R, and P + Q + R.
Depending upon the bits li , mi , ni , add P, Q, R or one of the precomputed
points to S.
Fixed-Base Scalar Multiplication

We want to compute nP for some n ∈ {0, 1, 2, . . . , r − 1}.

Let the bit size of r be s.
Precompute and store P, 2P, 4P, 8P, . . . , 2s−1 P.
Express n = 2i1 + 2i2 + · · · + 2ik .
Add the precomputed points 2ij P.
No doubling required.
Huge permanent storage overhead.
Efficient only when P does not change frequently.
Fixed-Base Multiple Scalar Multiplication
To compute mP + nQ with s-bit scalars m and n.
P and Q are assumed to be fixed.
Precompute and store the points 2i P, 2i Q and 2i (P + Q) for all
i = 0, 1, 2, . . . , s − 1.
Let the i-th bits of m and n be mi and ni .
If (mi , ni ) = (0, 0), do nothing.
If (mi , ni ) = (1, 0), add 2i P.
If (mi , ni ) = (0, 1), add 2i Q.
If (mi , ni ) = (0, 1), add 2i (P + Q).

No doubling needed.
Huge permanent storage.
If P is fixed, but Q changes frequently, the amortized cost of the
precomputations of 2i Q and 2i (P + Q) may be high.
Affine Curves
K is a field.
K is the algebraic closure of K.
It is often necessary to assume that K is algebraically closed.
Affine plane: K 2 = {(h, k) | h, k ∈ K}.
For (h, k) ∈ K 2 , the field elements h, k are called affine coordinates.
Affine curve: Defined by a polynomial equation:

C : f (X, Y) = 0.

It is customary to consider only irreducible polynomials f (X, Y). If f (X, Y)

admits non-trivial factors, the curve C is the set-theoretic union of two (or
more) curves of smaller degrees.
Rational points on C: All points (h, k) ∈ K 2 such that f (h, k) = 0.
Rational points on C are called finite points.
Affine Curves: Examples

Straight lines: aX + bY + c = 0.
Circles: (X − a)2 + (Y − b)2 − r2 = 0.
Conic sections: aX 2 + bXY + cY 2 + dX + eY + f = 0.
Elliptic curves: Defined by the Weierstrass equation:
Y 2 + (a1 X + a3 )Y = X 3 + a2 X 2 + a4 X + a6 .
If char K 6= 2, 3, this can be simplified as Y 2 = X 3 + aX + b.
Hyperelliptic curves of genus g: Y 2 + u(X)Y = v(X) with deg u 6 g,
deg v = 2g + 1, and v monic.
If char K 6= 2, this can be simplified as Y 2 = w(X) with deg w = 2g + 1 and
w monic.
Parabolas are hyperelliptic curves of genus 0.
Elliptic curves are hyperelliptic curves of genus 1.
Projective Plane

Define a relation ∼ on K 3 \ {(0, 0, 0)} as (h, k, l) ∼ (h ′ , k ′ , l ′ ) if h ′ = λ h,

k ′ = λ k and l ′ = λ l for some non-zero λ ∈ K.
∼ is an equivalence relation on K 3 \ {(0, 0, 0)}.
The equivalence class of (h, k, l) is denoted by [h, k, l].
[h, k, l] can be identified with the line in K 3 passing through the origin and
the point (h, k, l).
The set of all these equivalence classes is the projective plane over K.
The projective plane is denoted as P2 (K).
h, k, l in [h, k, l] are called projective coordinates.
Projective coordinates are unique up to multiplication by non-zero elements
of K.
The three projective coordinates cannot be simultaneously 0.
Relation Between the Affine and the Projective Planes
P2 (K) is the affine plane K 2 plus the points at infinity.
Take P = [h, k, l] ∈ P2 (K).
Case 1: l 6= 0.
P = [h/l, k/l, 1] is identified with the point (h/l, k/l) ∈ K 2 .
The line in K 3 corresponding to P meets Z = 1 at (h/l, k/l, 1).
P is called a finite point.
Case 2: l = 0.
The line in K 3 corresponding to P does not meet Z = 1.
P does not correspond to a point in K 2 .
P is a point at infinity.
For every slope of lines in the X, Y-plane, there exists exactly one point at
infinity.
A line passes through all the points at infinity. It is the line at infinity.
Two distinct lines (parallel or not) in P2 (K) always meet at a unique point.
Through any two distinct points in P2 (K) passes a unique line.
Passage from Affine to Projective Curves
A (multivariate) polynomial is called homogeneous if every non-zero term
in the polynomial has the same degree.
Example: X 3 + 2XYZ − 3Z 3 is homogeneous of degree 3. X 3 + 2XY − 3Z is
not homogeneous. The zero polynomial is homogeneous of any degree.
Let C : f (X, Y) = 0 be an affine curve of degree d.
f (h) (X, Y, Z) = Z d f (X/Z, Y/Z) is the homogenization of f .
C(h) : f (h) (X, Y, Z) = 0 is the projective curve corresponding to C.
For any non-zero λ ∈ K, we have f (h) (λ h, λ k, λ l) = λ d f (h) (h, k, l). So
f (h) (λ h, λ k, λ l) = 0 if and only if f (h) (h, k, l) = 0.
The rational points of C(h) are all [h, k, l] with f (h) (h, k, l) = 0.
Finite points on C(h) : Put Z = 1 to get f (h) (X, Y, 1) = f (X, Y). These are
the points on C.
Points at infinity on C(h) : Put Z = 0 and solve for f (h) (X, Y, 0) = 0. These
points do not belong to C.
Examples of Projective Curves
aX+bY+c=0

aX+bY=0

Straight Line Circle

Straight line: aX + bY + cZ = 0.
Finite points: Solutions of aX + bY + c = 0.
Points at infinity: Solve for aX + bY = 0.
If b 6= 0, we have Y = −(a/b)X. So [1, −(a/b), 0] is the only point at infinity.
If b = 0, we have aX = 0, that is, X = 0. So [0, 1, 0] is the only point at infinity.
Circle: (X − aZ)2 + (Y − bZ)2 = r2 Z 2 .
Finite points: Solutions of (X − a)2 + (Y − b)2 = r2 .
Points at infinity: Solve for X 2 + Y 2 = 0.
For K = R, the only solution is X = Y = 0, so there is no point at infinity.
For K = C, the solutions are Y = ±iX, so there are two points at infinity: [1, i, 0]
and [1, −i, 0].
Examples of Projective Curves (contd.)
Y=−X Y=X

Y= 0
X 2−Y 2=1
2
Y =X

Parabola Hyperbola

Parabola: Y 2 = XZ.
Finite points: Solutions of Y 2 = X.
Points at infinity: Solve for Y 2 = 0.
Y = 0, so [1, 0, 0] is the only point at infinity.

Hyperbola: X 2 − Y 2 = Z 2 .
Finite points: Solutions of X 2 − Y 2 = 1.
Points at infinity: Solve for X 2 − Y 2 = 0.
Y = ±X, so there are two points at infinity: [1, 1, 0] and [1, −1, 0].
Examples of Projective Curves (contd.)

y y

x x

Elliptic curve: Y 2 Z + a1 XYZ + a3 YZ 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 .

Finite points: Solutions of Y 2 + a1 XY + a3 Y = X 3 + a2 X 2 + a4 X + a6 .
Points at infinity: Solve for X 3 = 0.
X = 0, that is, [0, 1, 0] is the only point at infinity.
Elliptic-Curve Arithmetic in Projective Coordinates
Consider the simple Weierstrass equation E : y2 = x3 + ax + b.
Let P = [h1 , k1 , l1 ] and Q = [h2 , k2 , l2 ] in projective coordinates.
We want to compute P + Q = [h, k, l] and 2P = [h′ , k′ , l′ ].
The slope of the line passing through P and Q is
k2
− kl11 k2 l1 − k1 l2
λ=
l2
h2 h1
= .
l2 − l1
h2 l1 − h1 l2

Therefore,
h h1 h2 l1 l2 (k2 l1 − k1 l2 )2 − (h2 l1 − h1 l2 )2 (h1 l2 + h2 l1 )
= λ2 − − = ,
l l1 l2 l1 l2 (h2 l1 − h1 l2 )2
and  
k h1 h k1
=λ − − .
l l1 l l1
Substituting the values of λ and h/l gives an explicit expression for k/l.
These expressions are too clumsy.
Elliptic-Curve Addition in Projective Coordinates

Practical solution: Collect common subexpressions.

T1 = k2 l1 − k1 l2 ,
T2 = h2 l1 − h1 l2 ,
T3 = T22 ,
T4 = T2 T3 ,
T5 = l1 l2 T12 − T4 − 2h1 l2 T3 ,
h = T2 T5 ,
k = T1 (h1 l2 T3 − T5 ) − k1 l2 T4 ,
l = l1 l 2 T 4 .

Further optimization possible by storing h1 l2 , k1 l2 and l1 l2 in temporary

variables.
Elliptic-Curve Doubling in Projective Coordinates

The projective coordinates h′ , k′ , l′ of 2P can be computed by the following

formulas.

T1 = 3h21 + al12 ,
T2 = k1 l1 ,
T3 = h1 k1 T2 ,
T4 = T12 − 8T3 ,
T5 = T22 ,
h′ = 2T2 T4 ,
k′ = T1 (4T3 − T4 ) − 8k12 T5 ,
l′ = 8T2 T5 .
Projective Coordinates and Scalar Multiplication

Computing the affine coordinates requires a division in the field. (Recall

the computation of the slope λ .)
Division could be much costlier than multiplication and squaring in the
field.
Projective addition and doubling formulas do not use any division.
At the end of the loop, the sum is converted from [h, k, l] to (h/l, k/l) by a
single division.
Projective coordinates increase the number of multiplication and squaring
operations substantially.
In some situations, speedup is reported with projective coordinates.
Mixed Coordinates

The left-to-right multiplication conditionally adds P to S.

The windowed variant adds aP to S for a small a.
P is available in affine coordinates.
The small multiples of P can be computed in affine coordinates.
Adding S = [h1 , k1 , l1 ] and aP = (h2 , k2 ) is same as adding [h1 , k1 , l1 ] and
[h2 , k2 , 1].
Since l2 = 1, the addition algorithm can be simplified, and many operations
can be saved.
For example,
T1 = k2 l1 − k1 l2
now becomes
T1 = k2 l1 − k1 .
Generalized Projective Coordinates

Let c, d be positive integers. Assume that gcd(c, d) = 1.

Define an equivalence relation on K 3 \ {(0, 0, 0)} as (h, k, l) ∼ (h′ , k′ , l′ ) if
and only if h′ = λ c h, k′ = λ d k, and l′ = λ l for some non-zero λ ∈ K.
Call the equivalence class of (h, k, l) as [h, k, l]c,d .
Identify the finite point (h, k) with [h, k, 1]c,d .
Identify the finite point [h, k, l]c,d with (h/lc , k/ld ).
Homogenization requires replacing x by X/Z c and y by Y/Z d .
Give the weight c to X, the weight d to Y, and the weight 1 to Z.
Each non-zero term in the homogenization is of the same total weight.
Generalized Projective Coordinates: Examples

The standard projective coordinates correspond to c = d = 1.

Jacobian Coordinates: The weights are c = 2 and d = 3.
López–Dahab Coordinates: The weights are c = 1 and d = 2.
For certain curves, generalized coordinates reduce the operation counts for
point addition and doubling.
The use of mixed coordinates can produce further speedup.
Montgomery Ladders
A modification of the left-to-right scalar multiplication.
Two points S and T are computed in the loop.
Invariance: T = S + P.

Initialize S = O and T = P.
For i = s, s − 1, s − 2, . . . , 1, 0, repeat:
If (ni = 0) /* Update (S, T) to (2S, 2S + P) = (2S, S + T) */
Assign T = S + T and S = 2S.
else /* Update (S, T) to (2S + P, 2S + 2P) = (S + T, 2T) */
Assign S = S + T and T = 2T.

Return S.

The Montgomery ladder is resistant to side-channel attacks.

The Montgomery ladder is unlikely to be adaptable to windowed variants.
Montgomery Ladders (Contd)
Consider the curve E : y2 = x3 + ax + b.
Let P = (h1 , k1 ), Q = (h2 , k2 ), P + Q = (h3 , k3 ), and P − Q = (h4 , k4 ).
Suppose P 6= Q. The addition formula gives

(h1 − h2 )2 h3 = (h1 + h2 )(h1 h2 + a) + 2b − 2k1 k2 ,

(h1 − h2 )2 h4 = (h1 + h2 )(h1 h2 + a) + 2b + 2k1 k2 .

Multiply these two formulas and substitute k12 = h31 + ah1 + b and
k22 = h32 + ah2 + b to get

h3 h4 (h1 − h2 )2 = (h1 h2 − a)2 − 4b(h1 + h2 ).

Given h1 , h2 , h4 alone, one can compute h3 .

The x-coordinate h5 of 2P can be computed from h1 alone:

4h5 (h31 + ah1 + b) = (h21 − a)2 − 8bh1 .

Montgomery Ladders (Contd)
We always have S − T = −P. Moreover, x(−P) = x(P).
There is no need to compute any y-coordinate in the Montgomery ladder.
Denote kP = (xk , yk ). Therefore, P = (x1 , y1 ) is known.
The Montgomery loop computes xn = x(S) and xn+1 = x(T). From these,
the y-coordinate of S = nT is computed as
(x1 + xn )(x1 xn + a) + 2b − (x1 − xn )2 xn+1
yn = .
2y1

Each iteration needs one addition and one doubling.

Montgomery ladders are particularly attractive for curves of the form

By2 = x3 + Ax2 + x.

Projective coordinates help for these curves.

Every curve of the form y2 = x3 + ax + b (like a curve of large prime order)
cannot be converted to the Montgomery form.
 PART 4
PAIRING ON ELLIPTIC CURVES
Weil Pairing
Let E be an elliptic curve defined over a finite field K = Fq .
Take a positive integer m coprime to p = char K.
Let µm denote the set of m-th roots of unity in K̄.
We have µm ⊆ Fqk , where k = ordm (q) is called the embedding degree.
Let E[m] be those points in E = E(K̄), whose orders divide m.
Weil pairing is a function em : E[m] × E[m] → µm .
Bilinearity:
em (P + Q, R) = em (P, R)em (Q, R),
em (P, Q + R) = em (P, Q)em (P, R).

Alternation: em (P, P) = 1.
Skew symmetry: em (Q, P) = em (P, Q)−1 .
Non-degeneracy: If P 6= O, then em (P, Q) 6= 1 for some Q ∈ E[m].
If m is a prime and P 6= O, then em (P, Q) = 1 if and only if Q lies in the
subgroup generated by P (that is, Q = aP for some integer a).
Line Functions
To compute the equation of the line LP,Q or the vertical line LR,−R .

If P = Q = O, return 1. Q R
If P = O, return x − x(Q). P

If Q = O, return x − x(P). −R
If P = −Q, return x − x(P).
Now, let P = (h1 , k1 ) and Q = (h2 , k2 ).
3h21 + a k2 − k1
If P = Q, take λ = , else take λ = .
2k1 h2 − h1
Set µ = λ h1 − k1 .
Return y − λ x + µ .
The Functions fn,P (n ∈ Z, P ∈ E(K̄))
These are rational functions unique up to multiplication by elements of K̄ ∗ .
fn,P satisfy the recurrence relation:
f0,P = f1,P = 1,
 
LP,nP
fn+1,P = fn,P for n > 1,
L(n+1)P,−(n+1)P
1
f−n,P = for n > 1.
fn,P
The rational functions fn,P also satisfy
 
LnP,n′ P
fn+n′ ,P = fn,P fn′ ,P × .
L(n+n′ )P,−(n+n′ )P
In particular, for n = n′ , we have  
2 LnP,nP
f2n,P = fn,P × .
L2nP,−2nP
The function fn,P is usually kept in the factored form.
The value of fn,P at some point Q is usually needed.
Miller’s Algorithm for Computing fn,P
Input: A point P ∈ E and a positive integer n.
Output: The rational function fn,P .
Steps
Let n = (ns ns−1 . . . n1 n0 )2 be the binary representation of n with ns = 1.
Initialize f = 1 and U = P.
For i = s − 1, s − 2, . . . , 1, 0, do the following:
/* Doubling */  
L U
Update f = f 2 × L2U,U,−2U and U = 2U.
/* Conditional adding */  
LU, P
If (ni = 1), update f = f × L and U = U + P.
U+P, −(U+P)

Return f .
Note: One may supply a point Q ∈ E and wish to compute the value fn,P (Q)
(instead of the function fn,P ). In that case, the functions LU,U /L2U,−2U and
LU,P /LU+P,−(U+P) should be evaluated at Q before multiplication with f .
Weil Pairing and the Functions fn,P

Let P, Q ∈ E[m], and we want to compute em (P, Q).

Choose a point T not equal to ±P, −Q, Q − P, O.
fm,Q (T) fm,P (Q − T)
We have em (P, Q) = .
fm,P (−T) fm,Q (P + T)
fm,P (Q)
If P 6= Q, then we also have em (P, Q) = (−1)m .
fm,Q (P)
Miller’s algorithm for computing fn,P (Q) can be used.
All these invocations of Miller’s algorithm have n = m.
So a single double-and-add loop suffices.
For efficiency, one may avoid the division operations in Miller’s loop by
separately maintaining polynomial expressions for the numerator and the
denominator of f . After the loop terminates, a single division is made.
Miller’s Algorithm for Computing em (P, Q)
If (P = Q), return 1.
Let m = (1ms−1 . . . m1 m0 )2 be the binary representation of m.
Initialize fnum = fden = 1, U = P, and V = Q.
For i = s − 1, s − 2, . . . , 1, 0, repeat:
/* Doubling */
Update numerator fnum = fnum 2 ×L
U,U (Q) × L2V,−2V (P).
2
Update denominator fden = fden × L2U,−2U (Q) × LV,V (P).
Update U = 2U and V = 2V.
/* Conditional adding */
If (mi = 1), then execute the following three lines:
Update numerator fnum = fnum ×LU,P (Q)×LV+Q,−(V+Q) (P).
Update denominator fden = fden ×LU+P,−(U+P) (Q)×LV,Q (P).
Update U = U + P and V = V + Q.
/* End of for loop */
Return (−1)m fnum /fden .
Weil Pairing: Example

Take E : Y 2 = X 3 + 3X defined over F43 .

This is supersingular with |E(F43 )| = 44, and E(F43 ) ∼
= Z22 ⊕ Z2 .
Take m = 11. The embedding degree for this choice is k = 2.
We work in the field F432 = F1849 = F43 (θ ), where θ 2 + 1 = 0.
F∗432 contains all the 11-th roots of unity: 1, 2 + 13θ , 2 + 30θ , 7 + 9θ ,
7 + 34θ , 11 + 3θ , 11 + 40θ , 18 + 8θ , 18 + 35θ , 26 + 20θ , and 26 + 23θ .
= Z44 ⊕ Z44 contains E[11] ∼
E(F432 ) ∼ = Z11 ⊕ Z11 .
P = (1, 2) and Q = (−1, 2θ ) generate E[11].
Let us compute em (P, Q) for P := P = (1, 2) and Q := 4P + 5Q =
(15 + 22θ , 5 + 14θ ).
11 = (1011)2 .
Initialization: f = fnum /fden = 1/1, U = P, and V = Q.
Miller Iteration for i = 2

Doubling
y + 20x + 21
Λ1 = LU,U /L2U,−2U =
x + 32
x + (36 + 21θ )
Λ2 = L2V,−2V /LV,V =
y + (12 + 35θ )x + (26 + 14θ )
Λ1 (Q) 34 + 37θ
f = f2× =
Λ2 (P) 28 + θ
U = 2P = (11, 26) and V = 2Q = (7 + 22θ , 28 + 7θ )
Addition
m2 = 0, so addition is skipped.
Miller Iteration for i = 1
Doubling
y + 31x + 20
Λ1 = LU,U /L2U,−2U =
x+7
x + (2 + 26θ )
Λ2 = L2V,−2V /LV,V =
y + (18 + 22θ )x + (29 + 2θ )
Λ1 (Q) 12 + 15θ
f = f2× =
Λ2 (P) 25 + 18θ
U = 4P = (36, 18) and V = 4Q = (41 + 17θ , 6 + 6θ )
Addition
y + 2x + 39
Λ1 = LU,P /LU+P,−(U+P) =
x + 33
x + (41 + 8θ )
Λ2 = LV+Q,−(V+Q) /LV,Q =
y + (28 + 9θ )x + (31 + 9θ )
Λ 1 (Q) 25 + 15θ
f = f2× =
Λ2 (P) 28 + 20θ
U = 5P = (10, 16) and V = 5Q = (2 + 35θ , 30 + 18θ )
Miller Iteration for i = 0
Doubling
y + 8x + 33
Λ1 = LU,U /L2U,−2U =
x + 42
x + (28 + 21θ )
Λ2 = L2V,−2V /LV,V =
y + (19 + 16θ )x + (19 + 16θ )
Λ1 (Q) 10 + 22θ
f = f2× =
Λ2 (P) 12 + 28θ
U = 10P = (1, 41) and V = 10Q = (15 + 22θ , 38 + 29θ )
Addition
x + 42
Λ1 = LU,P /LU+P,−(U+P) =
1
1
Λ2 = LV+Q,−(V+Q) /LV,Q =
x + (28 + 21θ )
Λ1 (Q) 12θ
f = f2× =
Λ2 (P) 18 + 32θ
U = 11P = O and V = 11Q = O
Weil Pairing: Example

12θ
 
We have em (P, Q) = (−1) 11
= 26 + 20θ . This is indeed an
18 + 32θ
11-th root of unity.

If P, Q are linearly dependent, we have em (P, Q) = 1.

The Miller loop may encounter a division by zero error in this case.
Use the alternative formula
fm,Q (T) fm,P (Q − T)
em (P, Q) =
fm,P (−T) fm,Q (P + T)

for a randomly chosen point T.

Tate Pairing
Let E be an elliptic curve defined over K = Fq with p = char K.
Let m be a positive integer coprime to p.
Let k = ordm (q) (the embedding degree), and L = Fqk .
Let E[m] = {P ∈ E(K̄) | mP = O}, and mE(L) = {mP | P ∈ E(L)}.
Let (L∗ )m = {am | a ∈ L∗ } be the set of m-th powers in L∗ .
Let P be a point in E[m], and Q a point in E(L).
The Tate pairing is a function

h , im : E[m] × E(L)/mE(L) → L∗ /(L∗ )m

that maps a pair of points P, Q to hP, Qim .

Q should be regarded as a point in E(L)/mE(L).
The value of hP, Qim is unique up to multiplication by an m-th power of a
non-zero element of L, that is, hP, Qim is unique in L∗ /(L∗ )m .
Properties of Tate Pairing
Bilinearity:
hP + Q, Rim = hP, Rim hQ, Rim ,
hP, Q + Rim = hP, Qim hP, Rim .

Non-degeneracy: For every P ∈ E[m], P 6= O, there exists Q with

hP, Qim 6= 1. For every Q ∈
/ mE(L), there exists P ∈ E[m] with hP, Qim 6= 1.
The Weil pairing is related to the Tate pairing as
hP, Qim
em (P, Q) =
hQ, Pim
up to m-th powers.
Let k = ordm (q) be the embedding degree. The Tate pairing can be made
unique by exponentiation to the power (qk − 1)/m:
qk −1
êm (P, Q) = (hP, Qim ) m

êm (P, Q) is called the reduced Tate pairing. The reduced pairing
continues to exhibit bilinearity and non-degeneracy.
Computing the Tate Pairing

Take a point T 6= P, −Q, P − Q, O.

fm,P (Q + T)
We have hP, Qim = .
fm,P (T)
If P and Q are linearly independent, then hP, Qim = fm,P (Q).
Miller’s algorithm is used to compute hP, Qim .
A single double-and-add loop suffices.
For efficiency, the numerator and the denominator in f may be updated
separately. After the loop, a single division is made.
If the reduced pairing is desired, then a final exponentiation to the power
(qk − 1)/m is made on the value returned by Miller’s algorithm.
Weil vs. Tate Pairing
The Miller loop for Tate pairing is more efficient than that for Weil pairing.
The reduced Tate pairing demands an extra exponentiation.
Let k = ordm (q) be the embedding degree, and L = Fqk .
Tate pairing requires working in the field L.
Let L′ be the field obtained by adjoining to L the coordinates of all the
points of E[m].
Weil pairing requires working in the field L′ .
L′ is potentially much larger than L.
Special case: m is a prime divisor of |E(K)| with m6 | q and m6 | (q − 1).
Then, L′ = L. So it suffices to work in the field L only.
For cryptographic applications, Tate pairing is used more often that Weil
pairing.
One takes Fq with |q| about 500–2000 bits and k 6 12. Larger embedding
degrees are impractical for implementation.
Distortion Maps
Let m be a prime divisor of |E(K)|.
Let P be a generator of a subgroup G of E(K) of order m.
Goal: To define a pairing of the points in G.
If k = 1 (that is, L = K), then hP, Pim 6= 1.
Bad news: If k > 1, then hP, Pim = 1.
But then, by bilinearity, hQ, Q′ im = 1 for all Q, Q′ ∈ G.
A way out: If k > 1 and Q ∈ L is linearly independent of P (that is, Q ∈
/ G),
then hP, Qim 6= 1.
Let φ : E(L) → E(L) be an endomorphism of E(L) with φ (P) ∈
/ G.
φ is called a distortion map.
Define the distorted Tate pairing of P, Q ∈ G as hP, φ (Q)im .
Since φ (P) is linearly independent of P, we have hP, φ (P)im 6= 1.
Since φ is an endomorphism, bilinearity is preserved.
Symmetry: We have hQ, φ (Q′ )im = hQ′ , φ (Q)im for all Q, Q′ ∈ G.
Distortion maps exist only for supersingular curves.
Twists
Let E be defined by the short Weierstrass equation Y 2 = X 3 + aX + b.
Let d > 2, and v ∈ F∗q a d-th power non-residue.
Consider the curve E′ : Y 2 = X 3 + v4/d aX + v6/d b (defined over Fqd ).
If d = 2, then E′ is defined over Fq itself.
E′ is called a twist of E of degree d.
E and E′ are isomorphic over Fqd . An explicit isomorphism is given by the
map φd : E′ → E taking (h, k) 7→ (v−2/d h, v−3/d k).
Let m be a prime divisor of |E(Fq )|, G a subgroup of order m in E(Fqk ), and
G′ a subgroup of order m in E′ (Fqk ). Let P, P′ be generators of G and G′ .
Suppose that φd (P′ ) is linearly independent of P.
For d = 2 (quadratic twist), a natural choice is G ⊆ E(Fq ) and
G′ ⊆ E′ (Fq ).
Define a pairing of points Q ∈ G and Q′ ∈ G′ as hQ, φd (Q′ )im .
This is called the twisted Tate pairing.
Pairing-Friendly Curves

Requirement for efficient computation: Small embedding degree k.

For general curves, k is quite high (|k| ≈ |m|).
Only some specific types of curves qualify as pairing-friendly.
Supersingular curves
√
By Hasse’s Theorem, |E(Fq )| = q + 1 − t with |t| 6 2 q.
If p|t, we call E a supersingular curve.
Curves of the form Y 2 + aY = X 3 + bX + c are supersingular over fields of
characteristic 2.
Supersingular curves have small embedding degrees. The only possibilities are
1, 2, 3, 4, 6.
If Fq is a prime field with q > 5, the only possibility is k = 2.
Non-supersingular curves are called ordinary curves.
It is difficult to locate ordinary curves with small embedding degrees.
Supersingular Curves: Examples
E : Y 2 = X 3 + a defined over Fp with an odd prime p ≡ 2 (mod 3).
Embedding degree: k = 2.
E : Y 2 = X 3 + aX defined over Fp with an odd prime p ≡ 3 (mod 4).
Embedding degree: k = 2.
E : Y 2 + Y = X 3 + X + a with a = 0 or 1 defined over F2d with odd d.
Embedding degree: k = 4.
E : Y 2 = X 3 − X ± 1 defined over F3d with 2, 3 6 | d.
Embedding degree: k = 6.
E : Y 2 = X 3 + a defined over Fp2 with a prime p ≡ 5 (mod 6) and with
a ∈ Fp2 a square but not a cube.
Embedding degree: k = 3.
Let E be a supersingular curve defined over Fp with p > 5. Then, E as a
curve over Fpn with even n is again supersingular.
Embedding degree: k = 1.
 How to Find Ordinary Pairing-Friendly Curves
Let k be a positive integer, and ∆ a small positive square-free integer.
Search for integer-valued polynomials t(x), m(x), q(x) ∈ Q[x] to represent a
family of elliptic curves of embedding degree k and discriminant ∆. The
triple (t, m, q) should satisfy the following:
1 q(x) = p(x)n for some n ∈ N and p(x) ∈ Q[x] representing primes.
2 m(x) is irreducible with a positive leading coefficient.
3 m(x)|q(x) + 1 − t(x).
4 m(x)|Φk (t(x) − 1), where Φk is the k-th cyclotomic polynomial.
5 There are infinitely many integers (x, y) satisfying ∆y2 = 4q(x) − t(x)2 .

If y in Condition 5 can be parametrized by a polynomial y(x) ∈ Q[x], the

family is called complete, otherwise it is called sparse.
For obtaining ordinary curves, we require gcd(q(x), m(x)) = 1.
The complex multiplication method is used to obtain specific examples of
elliptic curves E over Fq with E(Fq ) having a subgroup of order m.
Some Families of Ordinary Pairing-Friendly Curves

Some sparse families of ordinary pairing-friendly curves are:

MNT (Miyaji–Nakabayashi–Takano) curves: These are curves of prime
orders with embedding degrees 3, 4 or 6.
Freeman curves: These curves have embedding degree 10.

Some complete families of ordinary pairing-friendly curves are:

BN (Barreto–Naehrig) curves: These curves have embedding degree 12 and
discriminant 3.
SB (Scott–Barreto) curves
BLS (Barreto–Lynn–Scott) curves
BW (Brezing–Weng) curves
Efficient Implementations of Pairing
Denominator elimination: Applicable to Tate pairing.
Let the embedding degree k = 2d be even.
fn,P (Q) is computed by Miller’s algorithm, where Q = (h, k) with h ∈ Fqd .
The denominators L2U,−2U (Q) and LU+P,−(U+P) (Q) correspond to vertical
lines, evaluate to elements of Fqd , and can be discarded.
The final exponentiation guarantees correct computation of Tate pairing.

BMX (Blake-Murty-Xu) refinements use 2-bit windows in Miller’s loop.

Loop reduction: With clever modifications to Tate pairing, the number of

iterations in the Miller loop can be substantially reduced.
A typical reduction is by a factor of 2.
Examples
η and ηT pairings (for supersingular curves)
Ate pairing (for ordinary curves)
R-ate pairing
 PART 5
PAIRING-BASED CRYPTOGRAPHY
Intractable Problems (Contd)

Let G be a finite cyclic additive group with a generator P, and G′ a finite

cyclic multiplicative group. We assume that |G| = r is a prime. Suppose
that e : G × G → G′ is an efficiently computable pairing.
Decisional Diffie–Hellman Problem (DDHP): Given aP, bP, zP ∈ G (but
not a, b and z), decide whether zP = abP, that is, whether z ≡ ab (mod r).
The existence of the pairing function e makes the DDHP in G easy. In fact,
z ≡ ab (mod r) if and only if e(aP, bP) = e(P, zP). In this case, G is called
a Gap Diffie–Hellman (GDH) group.
In a GDH group, given aP, bP, it is easy to compute e(P, P)ab = e(aP, bP).
The Problems That Are Intractable in Presence of
Pairing
Bilinear Diffie–Hellman Problem (BDHP): Given P, aP, bP, cP ∈ G,
P 6= 0, compute e(P, P)abc .
Decisional Bilinear Diffie–Hellman Problem (DBDHP): Given
P, aP, bP, cP, zP ∈ G, P 6= 0, decide whether e(P, P)abc = e(P, P)z , that is,
z ≡ abc (mod r).
Bilinear Diffie–Hellman Assumption: The pairing map does not make
these problems computationally easy.
However, we require the DLP/DHP to be difficult in G.
If one of a, b, c is known, e(P, P)abc = e(bP, cP)a = e(aP, cP)b = e(aP, bP)c can
be computed.
If one of bcP, acP, abP is known, e(P, P)abc = e(aP, bcP) = e(bP, acP) =
e(cP, abP) can be computed.
Example: Elliptic-curve groups with Weil pairing.
Extensions possible for e : G1 × G2 → G3 (Co-BDHP, Co-DBDHP).
Identity-Based Encryption (IBE)
Original concept proposed by Shamir in 1984.
The first realization proposed in 2001 by Boneh and Franklin.
The Boneh–Franklin IBE uses pairing.

Conventional encryption and signature schemes (like RSA, DSA) use

public-key certificates.
Every use of a public key requires validating the public key using a
certificate from a trusted Certification Authority (CA).
An identity-based scheme uses a public identity (like e-mail ID) of an
entity as the public key, which does not require validation.
A trusted authority is still needed as a Key Generation Center (KGC) or
Public Key Generator (PKG).
The KGC is needed only once during the registration of an entity.
Boneh–Franklin IBE: Setup Phase
Domain parameters
Groups G, G′ of prime order r
A generator P of G
An efficiently computable bilinear map e : G × G → G′

Keys of PKG
Master Secret Key (MSK): s ∈R Z∗r
Public Key: PPKG = sP.

Hash functions
H1 : {0, 1}∗ → G
H2 : G′ → {0, 1}n for some suitable n

r, G, G′ , e, P, PPKG , n, H1 , H2 are made public

s is kept secret
s cannot be retrieved from PPKG = sP (DLP assumption)
Boneh–Franklin IBE: Key-generation Phase

The KGC sets up keys for an entity Bob.

Bob’s public identity: bob@p.b.cr
Bob’s public key: PBob = H1 (bob@p.b.cr).
Bob’s private key: DBob = sPBob .

The KGC transfers DBob to Bob securely.

Anybody can compute PBob .
Bob cannot compute s from DBob (DLP assumption).
Boneh–Franklin IBE: Encryption Phase

Alice plans to send an n-bit message M to Bob.

Alice computes Bob’s hashed identity PBob = H1 (bob@p.b.cr) ∈ G.
Alice computes g = e(PBob , PPKG ) ∈ G′ .
Alice chooses a random element a ∈ Z∗r .
Alice computes the ciphertext C = (aP, M ⊕ H2 (ga )) ∈ G × {0, 1}n .

a is the session secret.

H2 (ga ) is used as a mask to hide the message.
Anybody can send messages to Bob.
No certificates are required.
Boneh–Franklin IBE: Decryption Phase
Bob plans decrypts a ciphertext C = (U, V) ∈ G × {0, 1}n .
Bob computes the element g′ = e(DBob , U) ∈ G′ .
Bob computes the mask H2 (g′ ).
Bob retrieves the message M = V ⊕ H2 (g′ ).

Correctness
g′ = e(DBob , U) = e(DBob , aP) = e(sPBob , aP) = e(PBob , P)sa =
e(PBob , sP)a = e(PBob , PPKG )a = ga

Security
An eavesdropper knows P, U = aP, PBob = bP and PPKG = sP.
The mask is e(P, P)abs .
Intractability of the BDHP guarantees security against eavesdroppers.
Alice knows a and can compute the mask.
Bob knows bsP and can compute the mask.
SOK Two-Party Key Agreement
Proposed by Sakai, Ohgishi and Kasahara (2000).
Setup phase: As in Boneh-Franklin IBE (r, G, G′ , P, s, PPKG , e, n, H1 )
Key-generation phase:
Alice: Public key PAlice = H1 (alice@p.b.cr), private key DAlice = sPAlice .
Bob: Public key PBob = H1 (bob@p.b.cr), private key DBob = sPBob .
Key-agreement phase:
Alice computes SAlice = e(DAlice , PBob ).
Bob computes SBob = e(PAlice , DBob ).

Correctness: SAlice = e(DAlice , PBob ) = e(sPAlice , PBob ) = e(PAlice , PBob )s =

e(PAlice , sPBob ) = e(PAlice , DBob ) = SBob .
Security: P, PAlice = aP, PBob = bP and PPKG = sP are known to
everybody. The task is to compute e(P, P)abs . Alice knows DAlice = asP and
Bob knows DBob = bsP, so they can compute e(P, P)abs . An eavesdropper
cannot compute this quantity (BDHP assumption).
One-Round Three-Party Key Agreement

Proposed by Joux (2004).

Setup phase: Same as before (r, G, G′ , P, e).
Key-agreement phase:
Alice chooses a ∈R Z∗r and broadcasts aP to Bob and Carol.
Bob chooses b ∈R Z∗r and broadcasts bP to Alice and Carol.
Carol chooses c ∈R Z∗r and broadcasts cP to Alice and Bob.
Alice computes e(bP, cP)a = e(P, P)abc .
Bob computes e(aP, cP)b = e(P, P)abc .
Carol computes e(aP, bP)c = e(P, P)abc .

Security: A passive eavesdropper knows P, aP, bP, cP only and cannot

compute e(P, P)abc (BDHP assumption).
Paterson’s Identity-Based Signatures

First IBS scheme was proposed and realized by Shamir (1984).

Many pairing-based IBS schemes are known.
Paterson’s IBS scheme (2002) is an adaptation of ElGamal signatures.
Setup phase: Domain parameters r, G, G′ , P, e and PKG’s keys s and
PPKG = sP are as earlier. Hash functions: H1 = {0, 1}∗ → G,
H2 : {0, 1}∗ → Zr and H3 : G → Zr .
Key-generation phase:
Bob’s public key is PBob = H1 (bob@p.b.cr)
Bob’s private key is DBob = sPBob
Paterson’s Identity-Based Signatures (Contd)
Signing: Bob’s signature on message M is (S, T), where:

d ′ ∈R Zr ,
S = d′ P,
T = d′−1 (H2 (M)P − H3 (S)DBob ).

Verification: Bob’s signature (S, T) on M is verified if and only if

e(P, P)H2 (M) = e(S, T)e(Ppub , PBob )H3 (S) .

Correctness: H2 (M)P = d′ T + H3 (S)DBob = d′ T + H3 (S)sPBob , so

e(P, P)H2 (M) = e(P, H2 (M)P) = e(P, d′ T + H3 (S)sPBob )

= e(P, d′ T)e(P, H3 (S)sPBob ) = e(d′ P, T)e(sP, PBob )H3 (S)
= e(S, T)e(Ppub , PBob )H3 (S) .

Security: Similar to ElGamal signatures.

BLS Short Signatures
Proposed by Boneh, Lynn and Shacham (2004).
Uses pairing, but not identity-based.
Smaller signatures than DSA or ECDSA at the same security level.
Setup phase:
Groups G1 , G2 , G3 of prime order r (with G1 6= G2 )
Pairing map e : G1 × G2 → G3
A generator Q of G2
Hash function H : {0, 1}∗ → G1
Key-generation phase:
Bob’s private key: d ∈R Zr
Bob’s public key: Y = dQ ∈ G2
Notes:
Does not involve a PKG
G1 = G2 may fail to give same security as DSA
BLS Short Signatures (Contd)

Signing: Bob’s signature on M is S = dH(M).

Verification: Check whether e(S, Q) = e(H(M), Y).
Correctness: e(S, Q) = e(dH(M), Q) = e(H(M), dQ) = e(H(M), Y).
Security:
Signature verification is easy, since the Co-DDHP is easy for G1 , G2 .
Signature forging is difficult, since the Co-DHP is difficult.
Any pair of gap Diffie–Hellman (GDH) groups G1 , G2 can be used to implement
the BLS scheme.
References
Blake, Seroussi and Smart, Advances in Elliptic Curve Cryptography, Cambridge, 2005.
Boneh and Franklin, Identity Based Encryption from the Weil Pairing, Crypto 2001.
Boneh, Lynn and Shacham, Short Signatures from the Weil Pairing, Jl of Cryptology, 2004.
Das, Computational Number Theory, CRC Press, 2013.
Charlap and Robbins, An Elementary Introduction to Elliptic Curves, CRD Report, 1988.
Charlap and Coley, An Elementary Introduction to Elliptic Curves II, CCR Report, 1990.
Cohen, Frey, Avanzi, Doche, Lange, Nguyen and Vercauteren, Handbook of Elliptic and Hyperelliptic
Curve Cryptography, CRC Press, 2006.
Enge, Elliptic Curves and Their Applications to Cryptography, Kluwer, 1999.
Freeman, Scott and Teske, A Taxonomy of Pairing-Friendly Elliptic Curves, Jl of Cryptology, 2010.
Hankerson, Menezes and Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.
Joux, A One-Round Protocol for Tripartite Diffie–Hellman, ANTS-4, 2004.
Martin, Introduction to Identity-Based Encryption, Artech House, 2008.
Miller, The Weil Pairing, and Its Efficient Calculation, Jl of Cryptology, 2004.
Paterson, ID-Based Signatures from Pairings on Elliptic Curves, Electronics Letters, 2002.
Sakai, Ohgishi and Kasahara, Cryptosystems Based on Pairing, SCIS 2000.
Thanks for Your Attention!

For future: abhij@cse.iitkgp.ernet.in

 PART 6
ECDSA BATCH VERIFICATION
ECDSA Revisited: Parameters

We work over the prime field Fq .

E : y2 = x3 + ax + b is an elliptic curve defined over Fq .
Assume that n = |E(Fq )| is prime.
P is an arbitrary point of order n in E(Fq ).
√
|n − q − 1| 6 2 q.
If n < q, an integer reduced modulo n may have two modulo q values. The
fraction of such integers is very small. So we ignore this.

Signer’s permanent key

Private key d ∈R Zn .
Public key Q = dP.
DL assumption: It is infeasible to compute d from P and Q.
ECDSA Signatures Revisited

Signature generation
k ∈R [1, n − 1] (the session key)
R = kP
r = x(R) (mod n)
s = k−1 (m + dr) (mod n), where m = H(M)
(M, r, s) is the signed message

Signature verification
w = s−1 (mod n)
u = mw (mod n)
v = rw (mod n)
R = uP + vQ ∈ E(Fq )
Accept if and only if x(R) = r (mod n)
ECDSA Signatures: Examples

For illustration, we work with an artificially small example.

q = 991
E : y2 = x3 + x + 23 defined over F991
n = |E(F991 )| = 997
P = (1, 5) ∈ E(F991 ) is a point of order 997

Private key d = 737

Public key Q = dP = (272, 437)
ECDSA Signatures: Examples
Example 1 Example 2 Example 3
m1 = 123 m2 = 561 m3 = 288
Signature generation
k1 = 523 k2 = 755 k3 = 593
R1 = k1 P = (476, 617) R2 = k2 P = (183, 212) R3 = k3 P = (149, 56)
r1 = 476 r2 = 183 r3 = 149
s1 = 549 s2 = 528 s3 = 569
Signature verification
w1 = s−1
1 = 385 w2 = s−1
2 = 338 w3 = s−1
3 = 198
u1 = m1 w1 = 496 u2 = m2 w2 = 188 u3 = m3 w3 = 195
v1 = r1 w1 = 809 v2 = r2 w2 = 40 v3 = r3 w3 = 589
R1 = u1 P + v1 Q = (476, 617) R2 = u2 P + v2 Q = (183, 212) R3 = u3 P + v3 Q = (149, 56)

Signature generation needs one scalar multiplication.

Signature verification needs two scalar multiplications.
Practical improvements:
Use double scalar multiplication.
P is a system-wide fixed parameter.
If Q is fixed too, use double fixed-base scalar multiplication.
Batch Verification

Verify multiple signatures together at a time less than the total individual
verification time
Applicable when most of the available signatures are valid
Useful in resource-constrained and/or real-time systems
Security issue: One or more invalid signatures in a batch may go unnoticed
The attacker may inject carefully crafted forged signatures in a batch
Safeguards needed against such attacks

To verify a batch of t ECDSA signatures (r1 , s1 ), (r2 , s2 ), . . . , (rt , st ).

Ri = (xi , yi ), so ri = xi (mod n). We assume that xi = ri for all i.
Q is fixed in a batch but varies across different batches, so precomputations
based on Q may be ineffective, particularly for small batches
The Problem in ECDSA Batch Verification

The i-th verification equation is Ri = ui P + vi Q.

These equations can be combined as
! !
t t t
∑ Ri = ∑ ui P+ ∑ vi Q.
i=1 i=1 i=1

This boils down to only two scalar multiplication for a batch of any size t.
But how do we compute the left hand side ∑ti=1 Ri ?
ECDSA signatures present only the x-coordinates xi = ri = x(Ri ).
ECDSA∗ : A non-standard variant of ECDSA in which the entire points Ri
are included (instead of only ri ) in the signatures.
For ECDSA∗ , the above algorithm works without any problem.
A Naive Approach to Solve the Problem
y2i = xi3 + axi + b (mod q).
yi is a modular square root of the right hand side.
Square-root computations are costly.
In general, there are two square roots of xi3 + axi + b.
Try all of the 2t combinations of the signs of the square roots. If any of the
combinations satisfies the verification equation, accept.
Checking 2t−1 combinations actually suffices. There are 2t−1 possibilities
of the x-coordinates of ±R1 ± R2 ± · · · ± Rt .
ECDSA# : A non-standard variant of ECDSA in which an extra bit is
appended to an ECDSA signature for identifying the correct square root.
For ECDSA# , only one of the 2t combinations need to be checked.
The naive approach is usually the fastest batch-verification algorithm for
ECDSA# .
The Naive Algorithm: Example

Consider the three signatures (476, 549), (183, 528), (149, 569).
The square roots of 4763 + 476 + 23 are 374, 617. Take R1 = (476, 374).
The square roots of 1833 + 183 + 23 are 212, 779. Take R2 = (183, 212).
The square roots of 1493 + 149 + 23 are 56, 935. Take R3 = (149, 56).
The right hand side of the verification equation is (539, 347).
We have the following elliptic-curve sums:
R1 + R2 + R3 = (117, 895).
R1 + R2 − R3 = (342, 505).
R1 − R2 + R3 = (990, 608).
R1 − R2 − R3 = (539, 644) = −(539, 347).

Therefore, −R1 + R2 + R3 = (539, 347), and the batch is verified.

What about Standard ECDSA Signatures?

To avoid the time for t modular square-root computations

Replace this by something faster
Eliminate the unknown y-coordinates yi = y(Ri )
Three elimination possibilities
Linearization
Algebraic elimination
Use of summation polynomials

The first two methods are based on symbolic manipulations, where

y1 , y2 , . . . , yt are treated as symbols satisfying y2i = xi3 + axi + b (mod q)
The third method is based on resultant computations
Analyses and experiments reveal significant practical improvements
Open question: Can we make elimination faster than O(2t ) time?
Algorithm S1: Elimination by Linearization
The verification equation is ∑ti=1 Ri = (∑ti=1 ui ) P + (∑ti=1 vi ) Q.
Stage 1: Compute the right hand side numerically by a double scalar
multiplication (fixed-base if applicable). Let this point be (α , β ).
Stage 2: Compute the left hand side symbolically, and express the
symbolic sum as a pair (Rx , Ry ) of polynomials in y1 , y2 , . . . , yt . The largest
yi -degree in both Rx and Ry is 1 (since y2i can be substituted by the explicit
value xi3 + axi + b). Moreover, Rx consists non-zero terms of even total
degrees, and Ry consists of non-zero terms of odd total degrees.
Stage 3: We have Rx (y1 , y2 , . . . , yt ) = α . By successively squaring this
equation or multiplying by even-degree monomials, generate a system of
equations, each linear with respect to the even-degree monomials.
Stage 4: Solve the system to get the values of all even-degree monomials.
Stage 5: Use Ry (y1 , y2 , . . . , yt ) = β to solve for individual yi values.
Stage 6: Check whether y2i = xi3 + axi + b (mod q) for all i.
Algorithm S1: Example
The verification equation is (476, y1 ) + (183, y2 ) + (149, y3 ) = (539, 347).
First compute (h3 , k3 ) = (476, y1 ) + (183, y2 ):
λ = (y2 − y1 )/(183 − 476) = 115y1 + 876y2 .
λ 2 = 342y21 + 307y1 y2 + 342y22 = 307y1 y2 + 478.
h3 = λ 2 − x1 − x2 = 307y1 y2 + 810.
k3 = λ (x1 − h3 ) − y1 = 371y21 y2 + 620y1 y22 + 238y1 + 752y2 = 580y1 + 42y2 .
Then compute (h4 , k4 ) = (h3 , k3 ) + (149, y3 ):
λ = (y3 − k3 )/(149 − h3 ) = (411y1 + 949y2 + y3 )/(684y1 y2 + 330)
= (411y1 + 949y2 + y3 )(684y1 y2 − 330)/(6842 y21 y22 − 3302 )
= 987y1 y2 y3 + 904y1 + 57y2 + 906y3 .
h4 = λ 2 − h3 − x3 = 16y21 y22 y23 + 696y21 y2 y3 + 632y21 + 535y1 y22 y3
+ 680y1 y2 y23 + 676y1 y2 + 916y1 y3 + 276y22 + 220y2 y3 + 288y23 + 32
= 524y1 y2 + 332y1 y3 + 58y2 y3 + 497.
k4 = λ (h3 − h4 ) − k3 = 342y1 y2 y3 + 227y1 + 491y2 + 152y3 .
Thus, we have:
524y1 y2 + 332y1 y3 + 58y2 y3 + 497 = 539.
342y1 y2 y3 + 227y1 + 491y2 + 152y3 = 347.
Algorithm S1: Example (Contd)

First equation: 524y1 y2 + 332y1 y3 + 58y2 y3 = 82.

Generate the second equation:
Multiplying by y1 y2 gives 524y21 y22 + 332y21 y2 y3 + 58y1 y22 y3 = 82y1 y2 .
This simplifies to 949y1 y2 + 422y1 y3 + 572y2 y3 = 158.

Generate the third equation:

Multiplying by y1 y3 gives 949y21 y2 y3 + 422y21 y33 + 572y1 y2 y23 = 158y1 y3 .
This simplifies to 82y1 y2 + 833y1 y3 + 847y2 y3 = 445.
    
524 332 58 y1 y2 42
The linearized system is:  949 422 572   y1 y3  =  158 .
82 833 847 y2 y3 445
The solution of this system is: y1 y2 = 983, y1 y3 = 858, y2 y3 = 971.
Algorithm S1: Example (Contd)

We also have 342y1 y2 y3 + 227y1 + 491y2 + 152y3 = 347.

Multiply by y1 to get 342y21 y2 y3 + 227y21 + 491y1 y2 + 152y1 y3 = 347y1 .
Simplification gives 347y1 = 43, that is, y1 = 617.
y2 = (y1 y2 )/y1 = 212.
y3 = (y1 y3 )/y1 = 56.
Therefore, y21 = 145, y22 = 349, and y23 = 163.
Moreover, x13 + x1 + 23 = 145, x23 + x2 + 23 = 349, and x33 + x3 + 23 = 163.
Algorithm S1: Remarks

This is perhaps not too impressive.

This is too much computation.
We have to deal with all even-degree monomials in y1 , y2 , . . . , yt .
There are 2t−1 − 1 of them.
Solving the dense linearized system needs O(23t ) field operations.
But this is the beginning.
We at least have an understanding of the potentials of symbolic
computations.
Algorithm S1′ : Reduction in Monomial Count
Need to reduce the number of monomials in the linearized system.
Numerically compute the right hand side of the batch-verification equation.
Let this point be (α , β ).
Let τ = ⌈t/2⌉. Rewrite the verification equation as:
τ t
∑ Ri = ( α , β ) − ∑ Ri .
i=1 i=τ +1

Compute both sides of the rewritten equation symbolically.

Linearize by successive squaring.
The variables in the linearized system are all even-degree square-free
monomials in y1 , y2 , . . . , yτ , and all square-free monomials in
yτ +1 , yτ +2 , . . . , yt .
Does O(t3/2 ) field operations—still poorer than naive exhaustive search.
Algorithm S1′ : Example

Rewrite the verification equation as

(476, y1 ) + (183, y2 ) = (539, 347) + (149, −y3 ).
Compute the left hand side as (h3 , k3 ) as in S1. We have:
h3 = 307y1 y2 + 810, and
k3 = 580y1 + 42y2 .

Compute the right hand side as (h4 , k4 ):

λ = (347 + y3)/(539 − 149) = 836y3 + 720.
λ 2 = (2 × 836 × 720)y3 + (8362 y23 + 7202 ) = 766y3 + 741.
h4 = λ 2 − 539 − 149 = 766y3 + 53.
k4 = l(149 − h4 ) + y3 = 801y23 + 453y3 + 741 = 453y3 + 492.

Equate the two sides:

307y1 y2 + 810 = 766y3 + 53.
580y1 + 42y2 = 453y3 + 492.
Algorithm S1′ : Example (Contd)

Now, we have two variables y1 y2 and y3 .

First equation: 307y1 y2 + 810 = 766y3 + 53.
Second equation: Square the first equation to get
849y1 y2 + 768 = 925y3 + 645.
    
307 225 y1 y2 234
The linearized system is: = .
849 66 y3 868
Solve this to get y1 y2 = 983 and y3 = 56.
We also have 580y1 + 42y2 = 453y3 + 492. Multiply both sides by y1 to get
(453y3 + 492)y1 = 580y21 + 42y1 y2 , that is, y1 = 617.
y2 = (y1 y2 )/y1 = 212.
Algorithm S2: Algebraic Elimination

The verification equation is ∑ti=1 Ri = (∑ti=1 ui ) P + (∑ti=1 vi ) Q.

Stage 1: Compute the right hand side (α , β ) numerically.
Stage 2: Compute the left hand side symbolically as a pair
(Rx (y1 , y2 , . . . , yt ), Ry (y1 , y2 , . . . , yt )) of polynomials with square-free
monomials.
Stage 3: Set φ = Rx − α . For i = 1, 2, . . . , t, repeat:
Write φ = u(yi+1 , yi+2 , . . . , yt ) + yi v(yi+1 , yi+2 , . . . , yt ).
Set φ to (u − yi v)φ = u2 + y2i v2 .
Substitute all y2j for j = i, i + 1, . . . , t.

Accept the batch if and only if φ is reduced to zero.

Algorithm S2: Example

Consider the same example (476, y1 ) + (183, y2 ) + (149, y3 ) = (539, 347).

As in Algorithm S1, the left hand side has the x-coordinate
524y1 y2 + 332y1 y3 + 58y2 y3 + 497.
Set φ = 524y1 y2 + 332y1 y3 + 58y2 y3 + 497 − 539 =
524y1 y2 + 332y1 y3 + 58y2 y3 + 949 = (524y2 + 332y3 )y1 + (58y2 y3 + 497).
Update φ to (524y2 + 332y3 )2 y21 − (58y2 y3 + 497)2 =
600y22 y23 + 95y22 + 809y2 y3 + 623y23 + 218 = 809y2 y3 + 324.
Update φ to (809y3 )2 y22 − 3242 = 0.
Algorithm S2′ : Faster Variant of S2

Compute (α , β ) as in Algorithm S2.

Let τ = ⌈t/2⌉. Rewrite the verification equation as
∑τi=1 Ri = (α , β ) − ∑ti=τ +1 Ri .
Compute the two sides of the rewritten equation symbolically. Let
(1) (2)
Rx (y1 , y2 , . . . , yτ ) and Rx (yτ +1 , yτ +2 , . . . , yt ) be the x-coordinates of the
two sides.
(1) (2)
Set φ = Rx − Rx .
Eliminate y1 , y2 , . . . , yt from φ as in Algorithm S2.
Accept the batch if and only if φ is reduced to zero.
Algorithm S2′ : Example

Rewrite the verification equation as

(476, y1 ) + (183, y2 ) = (539, 347) + (149, −y3 ).

Symbolic computation gives the x-coordinates of the two sides as

307y1 y2 + 810 and 766y3 + 53.
Start with

φ = (307y1 y2 + 810) − (766y3 + 53) = (307y2 )y1 + (225y3 + 757).

Update φ to

(307y2 )2 y21 −(225y3 +757)2 = 215y22 +907y23 +254y3 +740 = 254y3 +641.

Update φ to 2542 y23 − 6412 = 0.

Algorithms S2 and S2′ : Remarks

Elimination stage is made efficient.

Much faster than Algorithms S1 and S1′ .
Practical for batch sizes up to six or seven.
Theoretically poorer than naive exhaustive search by a factor of t2 .
(Algorithm S1′ is poorer by a factor of 2t/2 .)
Algorithm SP
This achieves a running time of O(2t ) field operations.
Summation polynomials (introduced by Semaev) are recursively defined as:

f2 (x1 , x2 ) = x1 − x2 ,
f3 (x1 , x2 , x3 ) = (x1 − x2 )2 x3 2 − 2((x1 + x2 )(x1 x2 + a) + 2b)x3 +
((x1 x2 − a)2 − 4b(x1 + x2 )),
ft (x1 , x2 , . . . , xt ) = ResT (ft−k (x1 , . . . , xt−k−1 , T), fk+2 (xt−k , . . . , xt , T))
for t > 4 and for any k in the range 1 6 k 6 t − 3.

ResT is the resultant of two polynomials with respect to the variable T.

Let x1 , x2 , . . . , xt ∈ Fq . Then, ft (x1 , x2 , . . . , xt ) = 0 if and only if there exist
y1 , y2 , . . . , yt ∈ F p such that (xi , yi ) lie on the curve for all i = 1, 2, . . . , t, and
we have the following sum in the elliptic-curve group E(F p ):

(x1 , y1 ) + (x2 , y2 ) + · · · + (xt , yt ) = O.

Algorithm SP (Contd)
Write the verification equation as ∑ti=1 (xi , yi ) + (α , −β ) = O.
This is true if and only if ft+1 (x1 , x2 , . . . , xt , α ) = 0.
Recursion tree for t = 5:

f6 (x1 , x2 , x3 , x4 , x5 , α )
→ f4 (x1 , x2 , x3 , T)
→ f3 (x1 , x2 , T1 )
→ f3 (x3 , T, T1 )
→ f4 (x4 , x5 , α , T)
→ f3 (x4 , x5 , T2 )
→ f3 (α , T, T2 )

Practical for batch sizes up to ten.

Replace the last resultant calculation by a gcd computation for practical
benefits.
Algorithm SP: Example

Write the verification equation as

(476, y1 ) + (183, y2 ) + (149, y3 ) + (539, −347) = O.

Compute

f4 (476, 183, 149, 539)

= ResT (f3 (476, 183, T), f3 (149, 539, T))
= ResT (623T 2 + 569T + 114, 477T 2 + 970T + 658)
= 0.

In fact, gcd(623T 2 + 569T + 114, 477T 2 + 970T + 658) = T + 655.

Security Issues
An attacker capable of forging ECDSA∗ (or ECDSA# ) batches can trivially
forge ECDSA batches too.
Suppose that the attacker is capable of forging ECDSA batches that pass
our batch-verification algorithms.
The attacker can uniquely reconstruct the missing y-coordinates.
The naive, S1 and S1′ algorithms indeed do so.
S2 and S2′ can be extended to do the same task.
For small batch sizes, these algorithms are feasible.
So the attacker can forge ECDSA∗ (or ECDSA# ) batches.
Our algorithms do not compromise security—relative to straightforward
ECDSA∗ batch verification.

The security concerns do not end here.

Need for Randomization

An attacker can inject k faulty signatures in a batch of size t.

The attacker needs to arrange the following:
R1 + R2 + · · · + Rk = O.
m1 s−1 −1 −1
1 + m2 s2 + · · · + mk sk = 0 (mod n).
r1 s−1 −1 −1
1 + r2 s2 + · · · + rk sk = 0 (mod n).

The effect of these k forged signatures on both sides of the verification

equation is zero.
For example, the attacker may take m1 = m2 , r1 = r2 and s1 = −s2 . This
corresponds to R2 = −R1 .
In general, the attacker first chooses R1 , R2 , . . . , Rk , and fixes r1 , r2 , . . . , rk .
The attacker then chooses m1 , m2 , . . . , mk . The attacker finally arranges any
solution of the above two modulo n congruences for s−1 −1 −1
1 , s2 , . . . , sk .

Randomization destroys the above three relations with high probability.

What is Randomization?

Choose random multipliers ξ1 , ξ2 , . . . , ξt during batch verification.

Now, the attacker must arrange the following three relations a priori.
ξ1 R1 + ξ2 R2 + · · · + ξk Rk = O.
ξ1 m1 s−1
1 + ξ2 m2 s2 + · · · + ξk mk sk = 0 (mod n).
−1 −1

ξ1 r1 s−1
1 + ξ2 r2 s2 + · · · + ξk rk sk = 0 (mod n).
−1 −1

If l-bit randomizers are used, the probability of a successful attack is 2−l .

One can take l = |q|/2 since square-root methods for solving the ECDLP
imply only this much security.
Another possibility: l = 128.
Randomization of ECDSA Batches

The verification equation now modifies to:

! !
t t t
∑ ξi Ri = ∑ ξi ui P+ ∑ ξi vi Q.
i=1 i=1 i=1

The right hand side again poses no difficulty.

The left hand side appears to be irreparably affected, because only the
x-coordinates of Ri are available.

Rescue: Given only x(R) and a multiplier ξ , the x-coordinate x(ξ R) can be
uniquely determined and efficiently computed.
Replace the points Ri by ξi Ri , and run the batch-verification algorithms.
Now, the symbols yi are y(ξi Ri ).
We need good algorithms to compute x(ξ R) from x(R) and ξ .
Montgomery Ladders Revisited

Suppose that x(P1 ) = h1 , x(P2 ) = h2 and x(P1 − P2 ) = h4 are known.

We can compute h3 = x(P1 + P2 ) and h5 = x(2P1 ) as:

h3 h4 (h1 − h2 )2 = (h1 h2 − a)2 − 4b(h1 + h2 ).

4h5 (h31 + ah1 + b) = (h21 − a)2 − 8bh1 .

Montgomery ladder for computing x(ξ R):

Initialize x(S) := x(R) and x(T) := x(2R).
For (i = l − 2, l − 3, . . . , 1, 0) {
If (ξi = 0), assign x(T) := x(T + S) and x(S) := x(2S),
else assign x(S) := x(T + S) and x(T) := x(2T).
}
Return x(S)

Loop invariance: T = S + R.
Montgomery Ladders: Example

Take R = (476, y) and ξ = 97 = (1100001)2 .

Montgomery iterations:

Bit position Bit value S T x(S) x(T)

6 1 R 2R 476 467
5 1 3R 4R 676 544
4 0 6R 7R 679 441
3 0 12R 13R 875 447
2 0 24R 25R 218 200
1 0 48R 49R 962 740
0 1 97R 98R 514 140
Seminumeric Randomization

Let R = (r, y) with r known and y unknown.

Any non-zero multiple uR of R can be expressed as (h, ky), where h and k
are field elements fully determined by r and u.
For R itself, h = r and k = 1.
−(h, ky) = (h, (−k)y).
Let P1 = (h1 , k1 y) and P2 = (h2 , k2 y) with P1 6= ±P2 . Then, P3 = (h3 , k3 y):
 2  
k1 − k2 3 k1 − k2
h3 = (r + ar + b) − h1 − h2 , and k3 = (h1 − h3 ) − k1 .
h1 − h2 h1 − h2

We have P4 = 2P1 = (h4 , k4 y):

2
3h21 + a
   2  
1 3h1 + a h1 − h4
h4 = − 2h1 , and k4 = − k1 .
2k1 r3 + ar + b 2k1 r3 + ar + b

Represent the multiple (h, ky) of R by the pair (h, k) of field elements.
Seminumeric Randomization: Algorithm

Precompute the field elements r3 + ar + b and (r3 + ar + b)−1 .

Initialize S := (r, 1).
For (i = l − 2, l − 3, . . . , 1, 0) {
Assign S := 2S using seminumeric doubling.
If (ξi = 1), assign S := S + R using seminumeric addition.
}
Return S (or the first component of S).

This is slightly slower than scalar multiplication.

Seminumeric Randomization: Example

Take R = (476, y) and ξ = 97 = (1100001)2 .

Seminumeric iterations:
Bit position Bit value Operation S h k
6 1 Init R 476 1
5 1 Double 2R 467 553
Add 3R 676 704
4 0 Double 6R 679 348
3 0 Double 12R 875 82
2 0 Double 24R 218 834
1 0 Double 48R 962 57
0 1 Double 96R 692 513
Add 97R 514 643
Comparison of Randomization Methods

Montgomery ladders use one doubling and one addition in each iteration.
The seminumeric method does addition only for one bits.
No effective windowed variant is known for Montgomery ladders.
The seminumeric method readily adapts to any windowed variant.
Montgomery ladders are robust against simple side-channel attacks.
Neither the Montgomery-ladder method nor the seminumeric method is
known to have an effective multiple-scalar-multiplication algorithm.
The seminumeric method is practically faster than Montgomery ladders
except for very small randomizers.
Overheads of Randomization
Let SM be the time of one unwindowed full-length scalar multiplication.
Randomization requires roughly t half-length scalar multiplications.
2
4-NAF seminumeric half-length scalar multiplication takes 5 SM time.
7
Double scalar multiplication takes 6 SM time on an average.
2
Preparing each fixed-base precomputation table takes 3 SM time.
1
Double fixed-base scalar multiplication takes 2 SM time on an average.
Let BV denote the batch-verification time.
Verification type Time for verifying t signatures
7t


Individual (no fixed-base) 6 SM
4 t


Individual (fixed-base) 3 + 2 SM
7


Batch without randomization 6 SM + BV
2t 7


Batch with randomization 5 + 6 SM + BV
Final Remarks

For ECDSA# , it is preferable to use arbitrarily scalable naive batch

verification, particularly for large batch sizes.
For standard ECDSA, Algorithm SP with the seminumeric randomization
method gives the best practical performance for t 6 10.
If enough memory is available, individual verification using fixed-base
double scalar multiplication may outperform batch verification except for
small batch sizes.

It is fairly straightforward to adapt the batch-verification algorithms to

other types of curves, like Koblitz curves and Edwards curves.

It remains unsolved whether batch verification can be done in o(2t ) time.

No proposed batch-verification algorithm supplies speedup in the case of
multiple signers, particularly when randomization is used.
References for Part 6

Sabyasachi Karati, Abhijit Das, Dipanwita Roychowdhury, Bhargav Bellur, Debojyoti Bhattacharya
and Aravind Iyer, Batch Verification of ECDSA Signatures, 5th International Conference on Cryptology
in Africa (AfricaCrypt 2012), Lecture Notes in Computer Science #7374, pp 1–18, Jul 10–12, 2012,
Ifrane, Morocco.
Sabyasachi Karati, Abhijit Das, Dipanwita Roychowdhury, Bhargav Bellur, Debojyoti Bhattacharya
and Aravind Iyer, New Algorithms for Batch Verification of Standard ECDSA Signatures, Journal of
Cryptographic Engineering, DOI: 10.1007/s13389-014-0082-x, Volume 4, Issue 4, pp 237–258,
Springer-Verlag, November 2014 (online publication dated 26 July 2014).
Sabyasachi Karati and Abhijit Das, Faster Batch Verification of Standard ECDSA Signatures Using
Summation Polynomials, 12th International Conference on Applied Cryptography and Network
Security (ACNS 2014), Lecture Notes in Computer Science #8479, pp 438–456, Jun 10–13, 2014,
Lausanne, Switzerland.
Sabyasachi Karati, Abhijit Das and Dipanwita Roychowdhury, Randomized Batch Verification of
Standard ECDSA Signatures, 4th International Conference on Security, Privacy, and Applied
Cryptography Engineering (SPACE 2014), Lecture Notes in Computer Science #8804, pp 237–255,
Oct 18–22, 2014, Pune, India.
Sabyasachi Karati and Abhijit Das, Batch Verification of EdDSA Signatures, 4th International
Conference on Security, Privacy, and Applied Cryptography Engineering (SPACE 2014), Lecture Notes
in Computer Science #8804, pp 256–271, Oct 18–22, 2014, Pune, India.
Thanks for Your Attention!

For future: abhij@cse.iitkgp.ernet.in