Need information on Bilinear Maps

Question

I've googled the following URL's and need more simple information regarding Bilinear Maps

Intro to Bilinear Maps -- by Bethencourt and

http://en.wikipedia.org/wiki/Bilinear_map

Lecture 25: Pairing-Based Cryptography -- MIT course

I would like to know in a simple to understand framework

1) what is a bilinear pairing -- an example would be great 2) how is it useful say in CP-ABE -- ciphertext policy attribute based encryption schema

Thanks

Answer 1

A pairing, in cryptography, is a way to make three-party operations.

Suppose that you have three groups G₁, G₂ and G₃, in which discrete logarithm is hard. Let's note group operation additively (with a '+' sign) in G₁ and G₂, and multiplicatively in G₃. A pairing e is a function which takes one element of G₁ and one element of G₂, and outputs an element of G₃, such that, for all integers a and b, and all group elements X₁ and Y₁ (from G₁) and X₂ and Y₂ (from G₂), you get:

e(X₁ + X₂, Y₁) = e(X₁, Y₁) e(X₂, Y₁) (pairing is linear in the first parameter)

e(X₁, Y₁ + Y₂) = e(X₁, Y₁) e(X₁, Y₂) (pairing is linear in the second parameter)

e(aX, bY) = e(X, Y)^ab (actually a consequence of the bilinearity explained above)

An example of a very weak pairing is the following: let p and q be two prime numbers such that q divides p-1. Let g be a multiplicative generator of a sub-group or order q modulo p (i.e. g is not 1, but g^q = 1 mod p). Define G₁ and G₂ to be the integers modulo q, with addition as group operation. Define G₃ to be the subgroup generated by g. Then, define e as: e(X, Y) = g^XY mod p. This gives you a non-degenerate pairing ("non-degenerate" means that the pairing can return values other than 1). But it is useless for cryptography because "discrete logarithm" in G₁ and G₂ is a matter of a simple modular division, i.e. very easy to compute efficiently (because we used integer addition as group law).

A non-weak pairing can be used for identity-based cryptography (where the public key of someone is their email address, not some mathematical object linked to the address through a signed certificate -- the point being, precisely, to avoid a PKI). It can also be used for three-party Diffie-Hellman, or more generally protocols which involve three entities at a time (e.g. protocols for "electronic cash" or some voting systems). See this page for some details and links.

The currently only known cryptographically strong pairings, but still usable in practice, are based on specially crafted elliptic curves. See Ben Lynn's PhD dissertation for a mathematical introduction, and PBC for the implementation. An "easy" variant will make G₁ and G₂ an elliptic curve over a field GF(p) (for a prime integer p), and G₃ will be a multiplicative subgroup of the invertible elements in GF(p²). Be warned that it is somewhat higher-level mathematics than "plain" elliptic curves (you have to know how field extensions work).