De¬nition 2.1.2 The number of elements in G, denoted |G|, is called the order of

G. A group G is ¬nite if |G| is ¬nite.

G is said to be cyclic if there is an element g ∈ G such that for each a ∈ G there is

an integer i with a = gi . Such an element g is called a generator of G.

In this book, we let G ‚ Z— be a cyclic group of prime order q, where g is a genera-

p

tor of G. The security parameters, p and q, are de¬ned as the ¬xed form q|p ’ 1 and

ord(g) = q.

2.1.2 Bilinear Maps from Elliptic Curve Pairings

Using the notation of Boneh and Franklin [22], we let G1 be an additive group of

prime order q and G2 be a multiplicative group of the same order q. We assume the

existence of a map e from G1 — G1 to G2 and that elements of G1 and G2 can be

ˆ

represented by bit strings of the appropriate lengths. Typically, G1 will be a sub-

group of the group of points on an elliptic curve over a ¬nite ¬eld, G2 will be a

subgroup of the multiplicative group of a related ¬nite ¬eld, and the map e will be

ˆ

1.

derived from either the Weil or Tate pairing on the elliptic curve

1 Tate pairing appears to be more computationally ef¬cient than Weil pairing [45, 59]. A more

comprehensive description of how these groups, pairings and other parameters should be selected

2.1 Mathematical Background 21

The mapping e must be ef¬ciently computable and has the following properties.

ˆ

For Q,W, Z ∈ G1 , both

Bilinearity.

e(Q,W + Z) = e(Q,W ) · e(Q, Z) e(Q +W, Z) = e(Q, Z) · e(W, Z).

ˆ ˆ ˆ and ˆ ˆ ˆ

Non-Degeneracy. For some elements P, Q ∈ G1 , we have e(P, Q) = 1G2 .

ˆ

Computability. For some elements P, Q ∈ G1 , we have an ef¬cient algorithm to

compute e(P, Q).

ˆ

A bilinear map, e, is said to be an admissible bilinear map if it satis¬es all three

ˆ

properties. Since e is bilinear, the map e is also symmetric.

ˆ ˆ

2.1.3 Computational Problems and Assumptions

We introduce here several computational problems and assumptions, which are

based on number theoretic problems. In other words, these cryptographic problems

and assumptions exist within the framework of complexity theory. We recall the

de¬nitions for three frequently used complexity theory terms: the security param-

eter k, a negligible function (presented in De¬nition 2.1.3), and the de¬nition of a

polynomial time algorithm (presented in De¬nition 2.1.4).

In cryptographic algorithms, the security parameter, k, is important as negligibil-

ity of functions and complexity of algorithms are often parametised by k (e.g., the

size of cryptographic groups and key lengths, within those algorithms). The larger

the value of k is, the more computation is required to run an algorithm. The value

k relates to the bounds on an adversary s success probability (i.e., k is often repre-

sented in unary notation as 1k ). All cryptographic algorithms in this book receive

this value as input and the running time is measured in k.

De¬nition 2.1.3 (A Negligible Function [9]) A function µ(k) : N ’ R in the secu-

rity parameter k, is called negligible if it approaches zero faster than the reciprocal

of any polynomial in k. That is, for every c ∈ N there is an integer kc such that

µ(k) ¤ k’c for all k ≥ kc .

De¬nition 2.1.4 (Polynomial Time Algorithm [9]) A polynomial time algorithm

(also called an ef¬cient algorithm) is an algorithm whose worst-case running time

function is of the form O(kc ), where k is the input size and c is a constant.

In de¬ning assumptions, protocol designers have various degrees of freedom related

to the concrete mathematical formulation of the assumption. For example, what kind

of attackers are considered or over what values the probability spaces are de¬ned.

in practice for ef¬ciency and security is described by recent work of Barreto, Kim, Lynn, and Scott

[8] and Galbraith [45].

22 2 Background Materials

In the following discussion, we will introduce the computational problems and as-

sumptions that will form the basis of security for the schemes discussed in this book.

The general structure of the problems is one of these two types.

Computational. For a given problem instance, a probabilistic, polynomial time

algorithm, F , succeeds if and only if it can solve the problem instance.

Decisional. For a given problem instance, another random problem instance is

chosen with the same structure instance using the corresponding problem in-

stance sampler and a random bit b. The probabilistic, polynomial time algorithm,

F , succeeds if, and only if, it can decide whether a given solution chosen ran-

domly from the solution set of one of the two problem instances corresponds to

the given problem instance.

The respective assumption states that no probabilistic, polynomial time algorithm

has non-negligible advantage in k in solving the corresponding computational / de-

cisional problem as described below for the given parameters. Let

x, y, z, a, b, c, d ∈ Z— ,

• q

g, gx , gy , gxy , gz ∈ G,

•

• P, aP, bP, cP, dP ∈ G1 , and

e(P, P)abc , e(P, P)d ∈ G2 .

• ˆ ˆ

De¬nition 2.1.5 (Computational Dif¬e-Hellman Problem [42])

Instance : (g, gx , gy )

Output : gxy .

If we can solve the Discrete Logarithm Problem (DLP) [23]2 in G, then we can also

(immediately) solve the Computational Dif¬e-Hellman (CDH) problem although

the converse is still an open research problem [23, 70, 79].

De¬nition 2.1.6 (Decisional Dif¬e-Hellman Problem)

Instance : (g, gx , gy , gz )

?

Decide : gz = gxy .

De¬nition 2.1.7 (Bilinear Dif¬e-Hellman Problem [22])

Instance : (P, aP, bP, cP)

Output : e(P, P)abc .

ˆ

The Bilinear Dif¬e-Hellman (BDH) problem is closely related to the Computational

Dif¬e-Hellman (CDH) problem [22, 53]. For example, Horwitz and Lynn [53] show

how the BDH problem (associated with a particular e) can be obtained from the

ˆ

CDH problem with a simple game transformation. A recent survey by Joux [59] is

2 The DLP forms the basis in the security of many cryptographic techniques [54, Chapter 3.6].

2.1 Mathematical Background 23

an excellent starting point for a detailed analysis of the relationship between BDH

and other standard problems.

De¬nition 2.1.8 (Decisional Bilinear Dif¬e-Hellman Problem [21])

Instance : (P, aP, bP, cP, e(P, P)d )

ˆ

?

Decide : d = abc mod q.

Note that the Decisional Bilinear Dif¬e-Hellma (DBDH) problem is easy in the

group G1 [60] but is believed to be hard in the group G2 .

De¬nition 2.1.9 (Gap Bilinear Dif¬e-Hellman Problem [84])