Bilinear Pairings. Denote the additive cyclic group by G1 and the multiplicative group by G2, with both having high prime order q. Let P be a generator of G1. Then, the bilinear pairing e : G1 × G1 → G2 should satisfy the followings: • Bilinear: Given P1, P2, Q, Q2 ∈ G1, then e(P1 + P2, Q1) = e(P1, Q1)e(P2, Q1), e(P1, Q1 + Q2) = e(P1, Q1)e(P1, Q2) and e(aP1, bQ1) = e(abP1, Q1) = e(P1, abQ1) = e(bP1, aQ1) = e(P1, Q1)ab for any a, b ∈ Zq∗. • Nondegenerate: There exist P, Q ∈ G1, such that e(P, Q) /= 1, with 1 the identity element of G2. • Computable: For any P, Q ∈ G1, the value e(P, Q) is efficiently computed. The following related mathematical problems are considered. • The Elliptic Curve Discrete Logarithm Problem (ECDLP). This problem states that given two points R and Q of an additive group G, generated by an elliptic curve (EC) of order q, it is computationally hard for any polynomial-time bounded algorithm to determine a parameter x ∈ Zq∗, such that Q = xR. • The Elliptic Curve Diffie Xxxxxxx Problem (ECDHP). Given two points R = xP, Q = yP of an additive group G, generated by an EC of order q with two unknown parameters x, y ∈ Zq∗, it is computationally hard for any polynomial-time bounded algorithm to determine the EC point xyP.
Bilinear Pairings. In recent years, the bilinear pairings have been found various applications in cryptography and have been used to construct some new cryptographic primi- tives [1, 4]. Let G1 be a cyclic additive group and G2 be a cyclic multiplicative group × → of the same prime order q. We assume that the discrete logarithm problems in both G1 and G2 are hard. A bilinear pairing is a map e : G1 G1 G2 which satisfies the following properties: ∈ ∈
