Elliptic Curves and bilinear pairings

Chapter 3

ELLIPTIC CURVES AND

BILINEAR PAIRINGS

3.1 Introduction

The complexity-theoretic foundation for modern public-key cryptography is based

on a class of hard problems: NP problems. An encryption algorithm should, on

the one hand, provide a legitimate user who is in possession of correct encryp-

tion/decryption keys with efficient algorithms, i.e., polynomial-time, for encryption

and/or decryption, and on the other hand, pose an intractable problem for any

cisional problems which are suitable for, and have been widely used in, the con-

struction of modern public-key cryptographic algorithms and protocols. Most of

the problems listed there, e.g., problems (2-4) in Example 2.14, relate their in-

tractabilities to that of the integer factorization problem or that of the discrete

logarithm problem. In these cases, which we shall call “conventional public-key

cryptographic primitives”, the difficulty of the intractability is a sub-exponential

expression sub

exp(k) given in (2.5.9), here k is the security parameter of the algo-

rithm in question, which is usually the size of the public key parameter.

Thus, for a conventional public-key cryptographic primitive, the computational-

cryptographic primitives. Consequently, legitimate users suffers a high computa-

tional cost.

Miller [?] and Koblitz [?] suggest to construct public-key cryptographic primi-

111

112 Elliptic Curves and Bilinear Pairings Chapter 3

tives using some calculations on elliptic curves.. These calculations will privite us

with a more different asymmetry between legitimate users and non-users because

these calculations run polynomial time for users and exponential time for non-users.

Recently, elliptic curve also finds new and exciting applications in cryptography,

in particular in cryptographic protocols. This is from so-called bilinear pairing

to do many things which were thought impossible not too long ago.

In this chapter we introduce elliptic curves and bilinear pairings. The material

to be provided here has a focus on bilinear pairings and forms a self-contained

foundation for our future study (in this book) of interesting cryptographic protocols

which apply bilinear pairing techniques.

3.1.1 Chapter Outline

§3.2 introduces elliptic curves over finite fields. §3.3 introduces bilinear pairing

techniques.

3.2 Elliptic Curves

Elliptic curves for cryptography are defined over finite algebraic structures such as

where a and b are elements in F

(p > 3) satisfying 4a

+ 27b

6≡ 0 (mod p).

To

have the points on E to form a group, an extra point denoted by O is included.

This extra point is called the point at infinity and can be formulated as

O = (∞, ∞).

We write the set of all such points on E as

This set of points form a group under a group operation which is conventionally

Section 3.2. Elliptic Curves 113

Denote by f (x) the cubic polynomial in the right-hand side of (3.2.1). If f(x)

is reducible over F

then (ξ, 0) ∈ E where ξ ∈ F

is a zero, also called root, of f(x)

(i.e. f (ξ) ≡ 0 (mod p) and this is why f (x) is reducible over F

). We will see in

a moment that these points have order 2 under the group operation “+” . Since

f(x) is a cubic polynomial, there are at most three such points. Depending how

η ∈ F

number modulo p, see §2.11). Indeed, each quadratic residue element in F

has

two distinct square roots modulo p (see Corollary 2.4) and hence if (η,

and (η, −

f(η)) for all ξ, η in F

quadratic residue element in F

and O. Then P “+” Q is the point such that `

intersects E at R, O and P “+” Q.

We can now explain why we have required the coefficients of the cubic polynomial

in (3.2.1) to satisfy 4a

+ 27b

6≡ 0 (mod p). Notice that

∆ = −4a

− 27b

is the discriminant of the cubic polynomial f(x) = x

+ ax + b. If ∆ ≡ 0 (mod p)

=

∂E

= 0.

Fig 3.1 illustrates the Chord-and-Tangent Operation Note, the illustration only

makes sense for a curve defined over R. The top two curves are the case for ∆ < 0;

in this case the cubic polynomial has one real zero and so the curve cuts the real

114 Elliptic Curves and Bilinear Pairings Chapter 3

axis once. The lower two curves are the case for ∆ > 0; in this case the cubic

polynomial has three real zeros and so the curve cuts the real axis three times

(note, with ∆ 6= 0, these three zeros must be distinct).

We remark that any line connecting a finite point F = (X, Y ) ∈ E and “the

point at infinity” O = (∞, ∞) ∈ E is the virtical line x = X. Informally we can

think of O = (∞

, ∞

) ∈ E satisfying

Section 3.2. Elliptic Curves 115

For this equation to hold, ∞

from the finite space, the point O is at the infinitely far distance “in the north

pole direction.” That’s why the line connecting any finite point F and O should be

virtical. In §?? we will see a formal evidence for this informal explanation.

Let us now show that (E, “+” ) does form a group.