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
Product Groups - Wiki

# Product Groups

#### Product Groups

We restrict in this section to products of two groups of known prime order. These problems arise usually in pairing based cryptography, but the underlying problems make no mention of the pairing. Please refer to Pairings for additional hard problems which do rely on the existence of a pairing.

We consider 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. We let gi denote a generator of Gi, where in the Type 1 setting we have g1 = g2.

For $a \in G_i, b \in G_j$, we write a˜b if $log_{g_i} a = log_{g_j} b$.

##### co-CDH: co-Computational Diffie-Hellman Problem

Definition: Given $g_i^a$ to compute $g_{3-i}^{a}$.

Reductions:

Algorithms: The best known algorithm is to solve DLP in Gi.

Use in cryptography: Boneh-Lynn-Shacham signatures.

References:

• D. Boneh, B. Lynn and H. Shacham, Short Signatures from the Weil Pairing, ASIACRYPT 2001, Springer LNCS 2248, 514-532.

##### PG-CDH: Computational Diffie-Hellman Problem for Product Groups

Definition: Given $g_i, g_i^x, g_i^y, g_{3-i},g_{3-i}^x,g_{3-i}^y$ to compute $g_i^{xy}$.

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 PG-CDHi.

Reductions:

• In the case of Type 1 products all six problems are equivalent to the CDH problem in G1.
• In the case of Type 2 products we have PG-CDH2 equivalent to the CDH in G2
• PG-CDHiP CDH in Gi.
##### XDDH: External Decision Diffie-Hellman Problem

Definition: Given $g_i^a, g_j^b$ and $v \in G_k$ determine whether $v = g_k^{ab}$.

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

Reductions:

• In the case of Type 1 products all six problems are equivalent to the DDH problem

in G1.

• In the case of Type 2 products we have
• In the case of Type 3 products all six instances have no known reductions between them.

If a Pairing exists on the product group then we have the following:

• In the case of Type 1 products this problem is NOT hard.
• In the case of Type 2 products ONLY the case XDDH1,1,1 is hard.
• In the case of Type 3 products the following cases are NOT hard XDDHi,2,k

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

History: The exact formulation of XDH and SXDH confuses me. (XXX Sort out the history!)

Use in cryptography:

References:

• G. Ateniese, J. Camenisch, B. de Medeiros, Untraceable RFID tags via insubvertible encryption, ACM Conference on Computer and Communications Security 2005, 92-101.

##### D-Linear2: Decision Linear Problem (version 2)

Definition: Given $g \in G_1, g^a, g^b, g^{ac}, g^{bd}$ and $g_2 \in G_2, g_2^a, g_2^b, v \in G_1$ to decide if v = gc + d.

Reductions: For product groups which have a pairing then D-Linear2P DBDH.

Algorithms: The best known algorithm for D-Linear2 is to solve the DLP in either G1 or G2.

Use in cryptography:

History: This problem first arose in the cyclic case, see D-Linear1

References:

• X. Boyen and B. Waters, Anonymous hierarchical identity-based encryption, CRYPTO 2006, Springer LNCS 4117, 290-307.

##### PG-DLIN: Decision Linear Problem for Product Groups

Definition: Given $g_{i1}, g_{i2}, g_{i3} \in G_i, g_{i1}^x, g_{i2}^y$ and $g_{j1},g_{j2},g_{j3} \in G_j, g_{k1}^x, g_{k2}^x$ such that gi1˜gj1,gi2˜gj2,gi3˜gj3 to decide if $v = g_{\ell 1}^{x+y}$.

Parameters: This is a parametrized problem, index by $i,j,k,\ell \in \{1,2\}$ thus this could correspond to 16 different problems, e.g., $(i,j,k,\ell) \in \{(1,1,1,1),(1,2,1,1),(1,2,2,1),(1,2,2,2),(1,2,2),(2,2,2,2)\}$.

We denote the corresponding problem by PG-DLINi,j,k,l.

Reductions:

##### FSDH: Flexible Square Diffie-Hellman Problem

Definition: Given $g_{2}^{a} \in G_{2}$, to compute a tuple $(h, h^{a}, h^{a^{2}})$ for some freely chosen $h \in G_{1}$.

Reductions: FSDHP Co-CDH (under the KEA1 assumption.)

Algorithms: The best known algorithm for FSDH is to solve the DLP.

Use in cryptography:

References:

• F. Laguillaumie, P. Paillier and D. Vergnaud, Universally Convertible Directed Signatures, ASIACRYPT 2005, Springer LNCS 3788, p. 682–701.

##### KSW1: Assumption 1 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 $Q_1,Q_2,Q_3\in G_q$, random $R_1,R_2,R_3\in G_r$, random $a,b,s\in Z_p$, and a random bit ν. Give to A the values $(N,G,G_T,\hat t)$ as well as $g_p,g_r,g_qR_1,g_p^b,g_p^{b^2},g_p^ag_q,g_p^{ab}Q_1,g_p^s,g_p^{bs}Q_2R_2.$ If ν = 0 give A the value $T=g_p^{b^2s}Q_3R_3$.

A outputs a bit ν' and succeeds if ν' = ν.

Reductions:

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

Use in cryptography: it was first used in the costruction 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