Pairing Explained

Pairing should not be confused with one-to-one correspondence.

In mathematics, a pairing is an R-bilinear map from the Cartesian product of two R-modules, where the underlying ring R is commutative.

Definition

Let R be a commutative ring with unit, and let M, N and L be R-modules.

A pairing is any R-bilinear map

e:M x N\toL

. That is, it satisfies

e(r ⋅ m,n)=e(m,r ⋅ n)=r ⋅ e(m,n)

e(m_1+m_2,n)=e(m_1,n)+e(m_2,n)

and

e(m,n_1+n_2)=e(m,n_1)+e(m,n₂₎

for any

r\inR

and any

m,m_1,m₂\inM

and any

n,n_1,n₂\inN

. Equivalently, a pairing is an R-linear map

M ⊗ _RN\toL

where

M ⊗ _RN

denotes the tensor product of M and N.

A pairing can also be considered as an R-linear map

\Phi:M\to\operatorname{Hom}_R(N,L)

, which matches the first definition by setting

\Phi(m)(n):=e(m,n)

A pairing is called perfect if the above map

\Phi

is an isomorphism of R-modules and the other evaluation map

\Phi'\colonN\to\operatorname{Hom}_R(M,L)

is an isomorphism also. In nice cases, it suffices that just one of these be an isomorphism, e.g. when R is a field, M,N are finite dimensional vector spaces and L=R.

A pairing is called non-degenerate on the right if for the above map we have that

e(m,n)=0

for all

implies

n=0

; similarly,

is called non-degenerate on the left if

e(m,n)=0

for all

implies

m=0

When

N=M

, a pairing is called symmetric if

e(m,n)=e(n,m)

for all m, n, and alternating if

e(m,m)=0

for all m. In particular, this implies

e(m+n,m+n)=0

, while bilinearity shows

e(m+n,m+n)=e(m,m)+e(m,n)+e(n,m)+e(n,n)=e(m,n)+e(n,m)

. Thus, for an alternating pairing,

e(m,n)=-e(n,m)

Examples

For a vector space

over a field

, a pairing

V x V\tok

is also called a bilinear form. Examples include any scalar product on a real vector space V, or the determinant map (2 × 2 matrices over k) → k when viewed as a pairing

k² x k²\tok

M^*

, the evaluation map

M^{* x}M\toR

(λ,m)\mapstoλ(m)

is known as the natural pairing.

Other examples of pairings occur in various duality theories, such as Serre duality or Poincaré duality. See also Dual system.

Another example is the Yoneda product between Ext groups.

S³\toS²

written as

h:S² x S²\toS²

is an example of a pairing. For instance, Hardie et al.^[1] present an explicit construction of the map using poset models.

Pairings in cryptography

See main article: Pairing-based cryptography. In cryptography, often the following specialized definition is used:^[2]

Let

styleG_1,G₂

be additive groups and

styleG_T

a multiplicative group, all of prime order

stylep

. Let

styleP\inG_1,Q\inG₂

be generators of

styleG₁

and

styleG₂

respectively.

A pairing is a map:

e:G₁ x G₂ → G_T

for which the following holds:

Bilinearity:

style\foralla,b\inZ: e\left(aP,bQ\right)=e\left(P,Q\right)^ab

Non-degeneracy:

stylee\left(P,Q\right) ≠ 1

For practical purposes,

stylee

has to be computable in an efficient manner

Note that it is also common in cryptographic literature for all groups to be written in multiplicative notation.

In cases when

styleG₁=G₂=G

, the pairing is called symmetric. As

styleG

is cyclic, the map

will be commutative; that is, for any

P,Q\inG

, we have

e(P,Q)=e(Q,P)

. This is because for a generator

g\inG

, there exist integers

such that

P=g^p

and

Q=g^q

. Therefore

e(P,Q)=e(g^p,g^q)=e(g,g)^pq=e(g^q,g^p)=e(Q,P)

The Weil pairing is an important concept in elliptic curve cryptography; e.g., it may be used to attack certain elliptic curves (see MOV attack). It and other pairings have been used to develop identity-based encryption schemes.

Slightly different usages of the notion of pairing

Scalar products on complex vector spaces are sometimes called pairings, although they are not bilinear.For example, in representation theory, one has a scalar product on the characters of complex representations of a finite group which is frequently called character pairing.

References

Hardie K.A.1; Vermeulen J.J.C.; Witbooi P.J., A nontrivial pairing of finite T0 spaces, Topology and its Applications, Volume 125, Number 3, 20 November 2002, pp. 533–542.
Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, SIAM J. of Computing, Vol. 32, No. 3, pp. 586–615, 2003.

External links

The Pairing-Based Crypto Library