Pairing in cryptography is a way to do tripartite operations.
Suppose you have three groups G 1 , G 2 and G 3 in which the discrete logarithm . Let the notation of a group operation be additive (with a “+” sign) in G 1 and G 2 and multiplicative in G 3 . The pairing e is a function that takes one element from G 1 and one element from G 2 , and outputs an element from G 3 such that for all integers a and b and all elements of the group X 1 and Y 1 (from G 1 ) and X 2 and Y 2 (from G 2 ), you get:
e (X 1 + X 2 , Y 1 ) = e (X 1 , Y 1 ) e (X 2 , Y 1 ) (pairing is linear in the first parameter)
e (X 1 , Y 1 + Y 2 ) = e (X 1 , Y 1 ) e (X 1 , Y 2 ) (the pairing is linear in the second parameter)
e (aX, bY) = e (X, Y) ab (actually a consequence of the bilinearity described above)
An example of very weak pairing is the following: let p and q be two primes for which q divides p-1. Let g be a multiplicative generator of a subgroup or order q modulo p (i.e., G is not 1, but g q = 1 mod p). Define G 1 and G 2 as integers modulo q with addition as a group operation. Define G 3 as the subgroup generated by g. Then we define e as: e (X, Y) = g XY mod p. This gives you non-degenerate pairing (“non-degenerate” means that pairing can return values other than 1). But for cryptography this is useless, because the "discrete logarithm" in G 1 and G 2 is a matter of simple modular division, i.e. it is very easy to calculate efficiently (because we used the integer complement as a group law).
Negative pairing can be used for identification-based cryptography (where the public key for someone is their email address, and not some mathematical object associated with the address through a signed certificate, just to avoid PKI ). It can also be used for tripartite Diffie-Hellman protocols or more general protocols that include three objects at the same time (for example, protocols for electronic money or some voting systems). See this page for some details and links.
Currently, only known cryptographically strong pairs, but still used in practice, are based on specially created elliptic curves. See Ben Lynn PhD dissertation for a mathematical introduction and PBC for an implementation. The “easy” version will make G 1 and G 2 an elliptic curve over the field GF (p) (for prime integers p) and G 3 will be a multiplicative subgroup of invertible elements in GF (p 2 ). Be warned that this is a slightly higher level math than “simple” elliptic curves (you need to know how field extensions work).