1
$\begingroup$

In type 3 pairing ($e:G_1 \times G_2\rightarrow G_\tau$ where $G_1\ne G_2$ and no isomorphism from $G_2$ to $G_1$ is known) we have co-DHP* problem:

Given $H, aP \in G_1$ and $aQ\in G_2$ calculate $aH$

It looks like there should be equivalent problem in $G_2$:

Given $aP \in G_1$ and $H, aQ\in G_2$ calculate $aH$

yet I haven't found it anywhere in literature. Is such problem mentioned in any paper? Or maybe it's proven to be easy?

$\endgroup$
  • $\begingroup$ $P$ and $Q$ are generators of $G_1$ and $G_2$ respectively and $H$ is random element in $G_1$ or $G_2$ depending on line $\endgroup$ – Przemko Robakowski Dec 27 '17 at 21:23
2
$\begingroup$

In fact both assumptions you state are often implicitly made in the literature (I am, however, not aware of any explicit use of the latter). For instance various variants of the bilinear Diffie-Hellman problem in Type-3 groups imply the hardness of the assumptions you state, e.g., $\sf BDH\text{-}3$ [1; Definition 2] which we will recall below.

For the following explanations, let $\sf BGGen$ be an algorithm which, on input of a security parameter $\kappa$, outputs a bilinear group description ${\sf BG} := (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P, \hat P, e)$. Here $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_T$ are three groups of common prime order $p$, where $p$ is of bitlength $\kappa$. $P$ and $\hat P$ are generators of $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, and $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is a bilinear pairing. Finally, we let ${\bf g} := e(P, \hat P)$. The $\sf BDH\text{-}3$ assumption states that for every PPT adversary $\mathcal{A}$ there exists a negligible function $\varepsilon(\cdot)$ so that it holds that $$ \Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b,c \stackrel{R}{\gets} \mathbb{Z}_p,~ {\bf g}^{abc} \gets {\cal A}({\sf BG}, aP,bP,cP,b\hat P, c\hat P) \right] \leq \varepsilon(\kappa). $$

Now, it is not hard to show that any solver for one of the assumptions you stated implies a solver for $\sf BDH\text{-}3$. We will present an explicit reduction ${\cal R}$ for the second assumption (the reduction to the first one is left as an exercise). Before we do so we restate the assumption in our notation (wich we henceforth call ${\sf A}_1$).

Assumption ${\sf A}_1$ states that for every PPT adversary $\cal A$ there exists a negligible function $\varepsilon(\cdot)$ such that $$ \Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b \stackrel{R}{\gets} \mathbb{Z}_p,~ ab\hat P \gets {\cal A}({\sf BG}, aP, a \hat P, b \hat P)\right] \leq \varepsilon(\kappa). $$ It is easy to verify that ${\sf A}_1$ indeed resembles the second assumption from the question (let $\hat P := Q$ and $H := bQ$).

Reduction ${\cal R}$ is implemented as follows:

  • Firstly, it obtains a $\sf BDH\text{-}3$ instance $({\sf BG}, aP,bP,cP,b\hat P, c\hat P)$ from a $\sf BDH\text{-}3$ challenger.
  • Secondly, it starts the adversary against ${\sf A}_1$ on $({\sf BG}, bP, b\hat P, c\hat P)$ to obtain $bc \hat P$.
  • Finally, it outputs $e(aP, bc\hat P) = e(P, \hat P)^{abc}$ as a $\sf BDH\text{-}3$ solution.

To sum up, the existence of $\cal R$ and the assumed hardness of $\sf BDH\text{-}3$ contradict the existence of an efficient adversary against ${\sf A}_1$.

Sidenote 1: The assumptions you state are quite natural assumptions in the Type-3 bilinear group setting.

Sidenote 2: The plausibility of the assumptions can also easily be confirmed in the Uber assumption framework [2].

References:

[1] https://eprint.iacr.org/2009/480.pdf

[2] Xavier Boyen: The Uber-Assumption Family. Pairing 2008: 39-56

$\endgroup$
  • $\begingroup$ I know first one is natural and used (I've already seen [1]) and second one also feels like it should hold, I just never seen it used. Thanks for explicit reduction! $\endgroup$ – Przemko Robakowski Dec 29 '17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.