Strict Standards: Declaration of APCBagOStuff::delete() should be compatible with BagOStuff::delete($key,$time = 0) in /usr/share/mediawiki1.7/includes/BagOStuff.php on line 499
Pairings - Wiki

# Pairings

#### 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 $\hat{t}: G_1 \times G_2 \rightarrow G_T$ and they come in three basic variants:

Type 1 : G1 = G2 is a group of prime order q

Type 2 : $G_1 \ne G_2$ are groups of prime order q, and there is an isomorphism $\psi : G_2 \rightarrow G_1$

Type 3 : $G_1 \ne G_2$ are groups of prime order q, and there is no isomorphism $\psi : G_2 \rightarrow G_1$

Due to the many possible groups involved there are various different versions of each problem. In the first three cases we let gi denote a generator of Gi, where in the Type 1 setting we have g1 = g2.

We write a˜b if $log_{g_1} a = log_{g_2} b$

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 $g_i^a$, $g_j^b$ and $g_k^c$ compute $\hat{t}(g_1,g_2)^{abc}$.

Parameters: This is a parametrized problem, index by $i,j,k \in \{1,2\}$ thus this could correspond to four different problems, $(i,j,k) \in \{(1,1,1),(1,1,2),(1,2,2),(2,2,2)\}$. We denote the corresponding problem by BDHPi,j,k.

Reductions:

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

In the case of Type 2 pairings we have BDHP2,2,2P BDHP1,2,2P BDHP1,1,2P BDHP1,1,1

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

Algorithms: The best known algorithm for BDHPi,j,k is to solve DLP in either Gi,Gj,Gk or GT

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 $g_i^a$, $g_j^b$, $g_k^c$ and $\hat{t}(g_1,g_2)^z$ determine whether $\hat{t}(g_1,g_2)^{abc}=\hat{t}(g_1,g_2)^z$.

Parameters: This is a parametrized problem, index by $i,j,k \in \{1,2\}$ thus this could correspond to four different problems, $(i,j,k) \in \{(1,1,1),(1,1,2),(1,2,2),(2,2,2)\}$. We denote the corresponding problem by DBDHi,j,k.

Reductions:

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

In the case of Type 2 pairings we have DBDH2,2,2P DBDH1,2,2P DBDH1,1,2P DBDH1,1,1

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

For all pairings we have DBDHi,j,kP BDHPi,j,k

Algorithms: The best known algorithm for DBDHi,j,k is to solve DLP in either Gi,Gj,Gk or GT

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 $g_{i1}, g_{i2}, g_{i3} \in G_i, g_{i1}^x, g_{i2}^y$ and $g_{3-i,1},g_{3-i,2},g_{3-i,3} \in G_{3-i}$ such that gi1˜g3 − i,1,gi2˜g3 − i,2,gi3˜g3 − i,3 and $g_{j1}^x, g_{j2}^x$ to decide if $v = \hat{t}(g_{11},g_{21})^{x+y}$.

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

Definition: Given $g_i^a, g_i^{a^2}, g_i^{a^3}, \ldots, g_i^{a^l}$ compute $\hat{t}(g_1,g_2)^{1/a}$.

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

Reductions:

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

In the case of Type 2 pairings we have l-BDHI2P l-BDHI1

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

Algorithms: The best known algorithm for l-BDHIi is to solve DLP in Gi

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 $g_i^a, g_i^{a^2}, g_i^{a^3}, \ldots, g_i^{a^l}$ and $v \in G_T$ determine whether $v = \hat{t}(g_1,g_2)^{1/a}$.

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

Reductions:

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

In the case of Type 2 pairings we have l-DBDHI2P l-DBDHI1

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

For all pairings we have l-DBDHIiP l-BDHIi

Algorithms: The best known algorithm for l-DBDHIi is to solve DLP in Gi

Use in cryptography:

References:

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

Definition: Given $g_i^a, g_i^{a^2}, g_i^{a^3}, \ldots, g_i^{a^l}$ and $g_j^{b}$ compute $\hat{t}(g_1,g_2)^{a^{l+1} b}$.

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

Reductions:

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

In the case of Type 2 pairings we have l-wBDHI2,2P l-wBDHI2,1P l-wBDHI1,1 and l-wBDHI2,2P l-wBDHI1,2P l-wBDHI1,1

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

Algorithms: The best known algorithm for l-wBDHIi,j is to solve DLP in Gi and Gj.

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 $g_i^a, g_i^{a^2}, g_i^{a^3}, \ldots, g_i^{a^l}, g_j^b$ and $v \in G_T$ determine whether $v = \hat{t}(g_1,g_2)^{a^{l+1} b}$.

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

Reductions:

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

In the case of Type 2 pairings we have l-wDBDHI2,2Pl-wDBDHI2,1P l-wDBDHI1,1 and l-wDBDHI2,2Pl-wDBDHI1,2P l-wDBDHI1,1

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

For all pairings we have l-wDBDHIi,jPl-wBDHIi,j

Algorithms: The best known algorithm for l-wDBDHIi,j is to solve DLP in Gi and Gj.

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(1n) is run to obtain $(p,q,r,G,G_T,\hat t)$. Set N = pqr, and let gp,gq,gr be generators of Gp, Gq, and Gr, respectively. Choose random $h\in G_p$ and $Q_1,Q_2\in G_q$, random $s,\gamma\in Z_q$, and a random bit ν. Give to A the values $(N,G,G_T,\hat t)$ as well as $g_p,g_q,g_r, h,g_p^s,h^sQ_1,g_p^{\gamma}Q_2,\hat t(g_p,h)^{\gamma}.$ If ν = 0 then give A the value $\hat t(g_p,h)^{\gamma s}$, while if ν = 1 then give A a random element of GT. 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 $B=(p,G_1,G_2,G_T,\hat t(\cdot,\cdot))$ be a bilinear map group system and let $\ell,m$ and t be three integers. Let g0 be a generator of G1 and h0 a generator of G2. Given two random coprime polynomials f and g, of respective orders $\ell$ and m, with pairwise distinct roots $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_m$ respectively, as well as several sequences of exponentiations

$\begin{matrix} x_1,\ldots,x_\ell, && y_1,\ldots,y_m, \\ g_0,g_0^\gamma,\ldots,g_0^{\gamma^{\ell+t-2}}, && g_0^{k\cdot\gamma\cdot f(\gamma)}, \\ g_0^{\alpha},g_0^{\alpha\cdot\gamma},\ldots,g_0^{\alpha\cdot\gamma^{\ell+t}}, \\ h_0,h_0^{\gamma},\ldots,h_0^{\gamma^{m-2}}, \\ h_0^\alpha,h_0^{\alpha\cdot\gamma},\ldots,h_0^{\alpha\gamma^{2m-1}}, && h_0^{k\cdot g(\gamma)}, \end{matrix}$

and $T\in G_T$, decide whether T is equal to $\hat t(g_0,h_0)^{k\cdot f(\gamma)}$ or to some random element of GT.

Algorithms: The best known algorithm for it is to solve DLP in either G1,G2 or GT.

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.