# Product Groups

### From Wiki

#### 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** : *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. We let *g*_{i} denote a generator of *G*_{i}, where in the Type 1 setting we have *g*_{1} = *g*_{2}.

For , we write *a*˜*b* if .

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

Definition: Given to compute .

Reductions:

Algorithms: The best known algorithm is to solve DLP in *G*_{i}.

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 to compute .

Parameters: This is a parametrized problem, index by thus this could correspond to two different problems.

We denote the corresponding problem by PG-CDH_{i}.

Reductions:

- In the case of Type 1 products all six problems are equivalent to the CDH problem in
*G*_{1}. - In the case of Type 2 products we have PG-CDH
_{2}equivalent to the CDH in*G*_{2} - PG-CDH
_{i}≤_{P}CDH in*G*_{i}.

##### XDDH: External Decision Diffie-Hellman Problem

Definition: Given and determine whether .

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

Reductions:

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

in *G*_{1}.

- In the case of Type 2 products we have

XDDH_{i,j,2} ≤_{P} XDDH_{i,j,1}
and
XDDH_{i,2,k} ≤_{P} XDDH_{i,1,k}
and
XDDH_{2,j,k} ≤_{P} XDDH_{1,j,k}.

- 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 XDDH
_{1,1,1}is hard. - In the case of Type 3 products the following cases are NOT hard XDDH
_{i,2,k}

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

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 and to decide if *v* = *g*^{c + d}.

Reductions: For product groups which have a pairing then D-Linear2 ≤_{P} DBDH.

Algorithms: The best known algorithm for D-Linear2 is to solve the DLP in either *G*_{1} or *G*_{2}.

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 and such that *g*_{i1}˜*g*_{j1},*g*_{i2}˜*g*_{j2},*g*_{i3}˜*g*_{j3} to decide if .

Parameters: This is a parametrized problem, index by thus this could correspond to 16 different problems, e.g., .

We denote the corresponding problem by PG-DLIN_{i,j,k,l}.

Reductions:

- In the case of Type 1 products all problems are equivalent to the D-Linear1 problem in
*G*_{1}. - In the case of Type 2 products we have PG-DLIN
_{2,2,2,2}≤_{P}PG-DLIN_{i,j,k,l}. - In the case of Type 3 products all instances have no known reductions between them.
- D-Linear2 corresponds to PG-DLIN
_{1,2,1,1}.

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

Definition: Given , to compute a tuple for some freely chosen .

Reductions: FSDH ≡_{P} 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*(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 , random , random , and a random bit ν. Give to *A* the values as well as
If ν = 0 give *A* the value .

*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