In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a pairing is an ''R''-
bilinear map
In mathematics, a bilinear map is a function combining elements of two vector spaces to yield an element of a third vector space, and is linear in each of its arguments. Matrix multiplication is an example.
Definition
Vector spaces
Let V, W ...
from the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of two ''R''-
module
Module, modular and modularity may refer to the concept of modularity. They may also refer to:
Computing and engineering
* Modular design, the engineering discipline of designing complex devices using separately designed sub-components
* Mo ...
s, where the underlying
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
''R'' is
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
.
Definition
Let ''R'' be a
commutative ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
with
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (alb ...
, and let ''M'', ''N'' and ''L'' be
''R''-modules.
A pairing is any ''R''-bilinear map
. That is, it satisfies
:
,
:
and
for any
and any
and any
. Equivalently, a pairing is an ''R''-linear map
:
where
denotes the
tensor product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otimes W ...
of ''M'' and ''N''.
A pairing can also be considered as an
''R''-linear map
, which matches the first definition by setting
.
A pairing is called perfect if the above map
is an isomorphism of ''R''-modules.
A pairing is called non-degenerate on the right if for the above map we have that
for all
implies
; similarly,
is called non-degenerate on the left if
for all
implies
.
A pairing is called alternating if
and
for all ''m''. In particular, this implies
, while bilinearity shows
. Thus, for an alternating pairing,
.
Examples
Any
scalar product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an algebra ...
on a real vector space ''V'' is a pairing (set , in the above definitions).
The determinant map (2 × 2 matrices over ''k'') → ''k'' can be seen as a pairing
.
The
Hopf map
In the mathematical field of differential topology, the Hopf fibration (also known as the Hopf bundle or Hopf map) describes a 3-sphere (a hypersphere in four-dimensional space) in terms of circles and an ordinary sphere. Discovered by Heinz H ...
written as
is an example of a pairing. For instance, Hardie et al. present an explicit construction of the map using poset models.
Pairings in cryptography
In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, often the following specialized definition is used:
[Dan Boneh, Matthew K. Franklin]
Identity-Based Encryption from the Weil Pairing
SIAM J. of Computing, Vol. 32, No. 3, pp. 586–615, 2003.
Let
be additive groups and
a multiplicative
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
, all of prime
order . Let
be
generators of
and
respectively.
A pairing is a map:
for which the following holds:
#
Bilinearity
In mathematics, a bilinear map is a function combining elements of two vector spaces to yield an element of a third vector space, and is linear in each of its arguments. Matrix multiplication is an example.
Definition
Vector spaces
Let V, W ...
:
#
Non-degeneracy:
# For practical purposes,
has to be
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
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
, the pairing is called symmetric. As
is
cyclic
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in s ...
, the map
will be
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
; that is, for any
, we have
. This is because for a generator
, there exist integers
,
such that
and
. Therefore
.
The
Weil pairing
Weil may refer to:
Places in Germany
*Weil, Bavaria
*Weil am Rhein, Baden-Württemberg
*Weil der Stadt, Baden-Württemberg
*Weil im Schönbuch, Baden-Württemberg
Other uses
* Weil (river), Hesse, Germany
* Weil (surname), including people with ...
is an important concept in
elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provide e ...
; e.g., it may be used to attack certain elliptic curves (se
MOV attack. It and other pairings have been used to develop
identity-based encryption ID-based encryption, or identity-based encryption (IBE), is an important primitive of ID-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user ( ...
schemes.
Slightly different usages of the notion of pairing
Scalar products on
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s are sometimes called pairings, although they are not bilinear.
For example, in
representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by ''representing'' their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. In essen ...
, one has a scalar product on the characters of complex representations of a finite group which is frequently called character pairing.
See also
*
Dual system
In mathematics, a dual system, dual pair, or duality over a field \mathbb is a triple (X, Y, b) consisting of two vector spaces X and Y over \mathbb and a non- degenerate bilinear map b : X \times Y \to \mathbb.
Duality theory, the study of dual ...
*
Yoneda product In algebra, the Yoneda product (named after Nobuo Yoneda) is the pairing between Ext groups of modules:
:\operatorname^n(M, N) \otimes \operatorname^m(L, M) \to \operatorname^(L, N)
induced by
:\operatorname(N, M) \otimes \operatorname(M, L) \to \o ...
References
External links
The Pairing-Based Crypto Library{{Use dmy dates, date=September 2016
Linear algebra
Module theory
Pairing-based cryptography