Pairing

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about the mathematics concept. For other uses, see Pair (disambiguation).

The concept of pairing treated here occurs in mathematics.

Definition[edit]

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

A pairing is any R-bilinear map e:M \times N \to L. That is, it satisfies

e(rm,n)=e(m,rn)=re(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_2)

for any r \in R and any m,m_1,m_2 \in M and any n,n_1,n_2 \in N . Or equivalently, a pairing is an R-linear map

M \otimes_R N \to L

where M \otimes_R N 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.

If  N=M a pairing is called alternating if for the above map we have  e(m,m) = 0 .

A pairing is called non-degenerate if for the above map we have that  e(m,n) = 0 for all m implies  n=0 .

Examples[edit]

Any scalar product on a real vector space V is a pairing (set M = N = V, R = R in the above definitions).

The determinant map (2 × 2 matrices over k) → k can be seen as a pairing k^2 \times k^2 \to k.

The Hopf map S^3 \to S^2 written as h:S^2 \times S^2 \to S^2 is an example of a pairing. In [1] for instance, Hardie et al. present an explicit construction of the map using poset models.

Pairings in cryptography[edit]

In cryptography, often the following specialized definition is used:[2]

Let \textstyle G_1, G_2 be additive groups and \textstyle G_T a multiplicative group, all of prime order \textstyle p. Let \textstyle P \in G_1, Q \in G_2 be generators of \textstyle G_1 and \textstyle G_2 respectively.

A pairing is a map:  e: G_1 \times G_2 \rightarrow G_T

for which the following holds:

  1. Bilinearity: \textstyle \forall a,b \in \mathbb{Z}_p^*:\ e\left(P^a, Q^b\right) = e\left(P, Q\right)^{ab}
  2. Non-degeneracy: \textstyle e\left(P, Q\right) \neq 1
  3. For practical purposes, \textstyle e has to be computable in an efficient manner

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

In cases when \textstyle G_1 = G_2 = G, the pairing is called symmetric. If, furthermore, \textstyle G is cyclic, the map  e will be commutative; that is, for any  P,Q \in G , we have  e(P,Q) = e(Q,P) . This is because for a generator  g \in G , there exist integers  p ,  q 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 pairing 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[edit]

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[edit]

  1. ^ A nontrivial pairing of finite T0 spaces Authors: Hardie K.A.1; Vermeulen J.J.C.; Witbooi P.J. Source: Topology and its Applications, Volume 125, Number 3, 20 November 2002 , pp. 533-542(10)
  2. ^ Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)

External links[edit]