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 : $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 $g i$ denote a generator of $G i$ , where in the Type 1 setting we have $g 1 = g 2$ .

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

[edit]

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 $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.

[edit]

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-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₂ equivalent to the CDH in $G 2$
PG-CDH_i ≤_P CDH in $G i$ .

[edit]

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

[edit]

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 = 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.

[edit]

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 $g i 1 ˜ g j 1, g i 2 ˜ g j 2, g i 3 ˜ g j 3$ 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-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.

[edit]

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: 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.

[edit]

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 $(p,q,r,G,G_T,\hat t)$ . 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 $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

Retrieved from "http://www.ecrypt.eu.org/wiki/index.php/Product_Groups"

Product Groups

From Wiki

Product Groups

co-CDH: co-Computational Diffie-Hellman Problem

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

XDDH: External Decision Diffie-Hellman Problem

D-Linear2: Decision Linear Problem (version 2)

PG-DLIN: Decision Linear Problem for Product Groups

FSDH: Flexible Square Diffie-Hellman Problem

KSW1: Assumption $1$ of Katz-Sahai-Waters

Views

Personal tools

Navigation

Search

Toolbox

Product Groups

From Wiki

Product Groups

co-CDH: co-Computational Diffie-Hellman Problem

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

XDDH: External Decision Diffie-Hellman Problem

D-Linear2: Decision Linear Problem (version 2)

PG-DLIN: Decision Linear Problem for Product Groups

FSDH: Flexible Square Diffie-Hellman Problem

KSW1: Assumption 1 of Katz-Sahai-Waters

Views

Personal tools

Navigation

Search

Toolbox

KSW1: Assumption $1$ of Katz-Sahai-Waters