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

From Wiki

Jump to: navigation, search


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.


Personal tools