# Pairings

### From Wiki

#### Pairings General

We restrict in this section to pairings over groups of known prime order.

Pairings based problems are written in the form of general assymetric pairings and they come in three basic variants:

**Type 1** : *G*_{1} = *G*_{2} is a group of prime order *q*

**Type 2** : are groups of prime order *q*, and there is
an isomorphism

**Type 3** : are groups of prime order *q*, and there is
no isomorphism

Due to the many possible groups involved there are various different versions of each problem.
In the first three cases we let *g*_{i} denote a generator of *G*_{i}, where
in the Type 1 setting we have *g*_{1} = *g*_{2}.

We write *a*˜*b* if

Please refer to Product Groups for additional hard problems in this situation, in particular those problems which do not rely on the existance of a pairing.

##### BDHP: Bilinear Diffie-Hellman Problem

Definition: Given , and compute .

Parameters: This is a parametrized problem, index by thus this
could correspond to four different problems,
.
We denote the corresponding problem by BDHP_{i,j,k}.

Reductions:

In the case of Type 1 pairings all four problems are equivalent.

In the case of Type 2 pairings we have
BDHP_{2,2,2} ≤_{P} BDHP_{1,2,2} ≤_{P} BDHP_{1,1,2} ≤_{P} BDHP_{1,1,1}

In the case of Type 3 pairings all four instances have no known reductions between them.

Algorithms: The best known algorithm for BDHP_{i,j,k} is to solve DLP
in either *G*_{i},*G*_{j},*G*_{k} or *G*_{T}

Use in cryptography:

References:

- A. Joux, A one round protocol for tripartite Diffie-Hellman, ANTS IV, Springer LNCS 1838 (2000) 385-394.
- D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, CRYPTO 2001, Springer LNCS 2139, 213-229.
- General version???

##### DBDH: Decision Bilinear Diffie-Hellman Problem

Definition: Given , , and determine whether .

Parameters: This is a parametrized problem, index by thus this
could correspond to four different problems,
.
We denote the corresponding problem by DBDH_{i,j,k}.

Reductions:

In the case of Type 1 pairings all four problems are equivalent.

In the case of Type 2 pairings we have
DBDH_{2,2,2} ≤_{P} DBDH_{1,2,2} ≤_{P} DBDH_{1,1,2} ≤_{P} DBDH_{1,1,1}

In the case of Type 3 pairings all four instances have no known reductions between them.

For all pairings we have
DBDH_{i,j,k} ≤_{P} BDHP_{i,j,k}

Algorithms: The best known algorithm for DBDH_{i,j,k} is to solve DLP in either *G*_{i},*G*_{j},*G*_{k} or *G*_{T}

Use in cryptography: Boneh-Franklin ID-based encryption scheme

References:

- D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, CRYPTO 2001, Springer LNCS 2139, 213-229.

##### B-DLIN: Bilinear Decision-Linear Problem

Definition: Given and such that *g*_{i1}˜*g*_{3 − i,1},*g*_{i2}˜*g*_{3 − i,2},*g*_{i3}˜*g*_{3 − i,3} and
to decide if .

##### l-BDHI: *l*-Bilinear Diffie-Hellman Inversion Problem

Definition: Given compute .

Parameters: This is a parametrized problem, index by thus this
could correspond to two different problems.
We denote the corresponding problem by l-BDHI_{i}.

Reductions:

In the case of Type 1 pairings the two problems are equivalent.

In the case of Type 2 pairings we have
l-BDHI_{2} ≤_{P} l-BDHI_{1}

In the case of Type 3 pairings all the instances have no known reductions between them.

Algorithms: The best known algorithm for l-BDHI_{i} is to solve DLP in *G*_{i}

Use in cryptography:

References:

- D. Boneh and X. Boyen, efficient selective-ID secure identity-based encryption without random oracles, EUROCRYPT 2004, Springer LNCS 3027, 223-238.

##### l-DBDHI: *l*-Bilinear Decision Diffie-Hellman Inversion Problem

Definition: Given and determine whether .

Parameters: This is a parametrized problem, index by thus this
could correspond to two different problems.
We denote the corresponding problem by l-DBDHI_{i}.

Reductions:

In the case of Type 1 pairings the two problems are equivalent.

In the case of Type 2 pairings we have
l-DBDHI_{2} ≤_{P} l-DBDHI_{1}

In the case of Type 3 pairings all the instances have no known reductions between them.

For all pairings we have
l-DBDHI_{i} ≤_{P} l-BDHI_{i}

Algorithms: The best known algorithm for l-DBDHI_{i} is to solve DLP in *G*_{i}

Use in cryptography:

References:

##### l-wBDHI: *l*-weak Bilinear Diffie-Hellman Inversion Problem

Definition: Given and compute .

Parameters: This is a parametrized problem, index by thus this
could correspond to four different problems.
We denote the corresponding problem by l-wBDHI_{i,j}.

Reductions:

In the case of Type 1 pairings the four problems are equivalent.

In the case of Type 2 pairings we have
l-wBDHI_{2,2} ≤_{P} l-wBDHI_{2,1} ≤_{P} l-wBDHI_{1,1}
and
l-wBDHI_{2,2} ≤_{P} l-wBDHI_{1,2} ≤_{P} l-wBDHI_{1,1}

In the case of Type 3 pairings all the instances have no known reductions between them.

Algorithms: The best known algorithm for l-wBDHI_{i,j} is to solve DLP in *G*_{i} and *G*_{j}.

Use in cryptography:

References:

- D. Boneh, X. Boyen and E.-J. Goh, Hierarchical Identity Based Encryption with Constant Size Ciphertext, EUROCRYPT 2005, Springer LNCS 3494, 440-456.

##### l-wDBDHI: *l*-weak Decisional Bilinear Diffie-Hellman Inversion Problem

Definition: Given and determine whether .

Parameters: This is a parametrized problem, index by thus this
could correspond to four different problems.
We denote the corresponding problem by l-wDBDHI_{i,j}.

Reductions:

In the case of Type 1 pairings the four problems are equivalent.

In the case of Type 2 pairings we have
l-wDBDHI_{2,2} ≤_{P}l-wDBDHI_{2,1} ≤_{P} l-wDBDHI_{1,1}
and
l-wDBDHI_{2,2} ≤_{P}l-wDBDHI_{1,2} ≤_{P} l-wDBDHI_{1,1}

In the case of Type 3 pairings all the instances have no known reductions between them.

For all pairings we have
l-wDBDHI_{i,j} ≤_{P}l-wBDHI_{i,j}

Algorithms: The best known algorithm for l-wDBDHI_{i,j} is to solve DLP in *G*_{i} and *G*_{j}.

Use in cryptography:

References:

##### KSW2: Assumption 2 of Katz-Sahai-Waters

Definition:
For all p.p.t. adversary *A*, the following experiment is negligible in the security parameter *n*:

*G*(1^{n}) is run to obtain . Set *N* = *p**q**r*, and let *g*_{p},*g*_{q},*g*_{r} be generators of *G*_{p}, *G*_{q}, and *G*_{r}, respectively.
Choose random and , random , and a random bit ν. Give to *A* the values as well as
If ν = 0 then give *A* the value , while if ν = 1 then give *A* a random element of *G*_{T}.
*A* outputs a bit ν' and succeeds if ν' = ν.

Reductions:

Algorithms: To break the assumption, it is sufficent to factorize *N*.

Use in cryptography: it was first used in the construction of a predicate encryption scheme supporting the inner product.

References: Jonathan Katz, Amit Sahai and Brent Waters, Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, Springer LNCS 4965, 146-162

##### MSEDH: Multi-sequence of Exponents Diffie-Hellman Assumption

Definition: Let be a bilinear map group system and let and *t* be three integers.
Let *g*_{0} be a generator of *G*_{1} and *h*_{0} a generator of *G*_{2}. Given two random coprime polynomials *f* and *g*, of respective orders and *m*, with pairwise distinct
roots and respectively, as well as several sequences of exponentiations

and , decide whether *T* is equal to or to some random element of *G*_{T}.

Algorithms: The best known algorithm for it is to solve DLP in either *G*_{1},*G*_{2} or *G*_{T}.

Use in cryptography: Delerabl{\'e}e and Pointcheval dynamic threshold public-key encryption scheme.

References: C{\'e}cile Delerabl{\'e}e and David Pointcheval, Dynamic Threshold Public-Key Encryption, CRYPTO 2008, Springer LNCS 5157, 317-334.