0
$\begingroup$

At a high level, the Uber assumption states that it is not possible to compute (distinguish) linearly independent elements. In the decisional version, the problem is restricted to $G_T$, but it is unclear whether the linearly independent elements can be from $G_1$.

Here is a simple example:

Let be type-3 pairing $E$: $(e, G_1, G_2, G_T, g, h)$ where $g$ and $h$ are generators over $G_1$ and $G_2$.

Given $(g^a, g^b, g^c, g^{ab}, h^a, h^b, E)$, the adversary can distinguish $g^{abc}$ or $g^z$?

$\endgroup$
1
  • $\begingroup$ In this case you can use MathJax / $\LaTeX$ simply by surrounding your variables / sets with dollar signs. I've performed an edit doing only that. $\endgroup$ Commented Jul 3, 2023 at 10:12

1 Answer 1

1
$\begingroup$

I'm not sure what you mean by linear independent elements, but your example problem is at most as strong as the weakest of a) decisional Diffie-Hellman problem in $\mathbb G_1$ (use the solver on the tuple $g,g^{ab},g^c, \mathrm{candidate}$ b) the computational Diffie-Hellman problem in $\mathbb G_2$ (use the CDH solver to find $h^{ab}$ then compare $e(g^c,h^{ab})$ with $e(\mathrm{candidate},h)$) and c) the decisional Diffie-Hellman in $\mathbb G_T$ (use the solver on the tuple $e(g,h^a),e(g^c,h^a),e(g^b,h^a),e(\mathrm{candidate},h)$).

Given that an adversary can already confirm the consistency of $g,g^a,g^b,g^{ab},h,h^a,h^b$, a more generic attack is to exhibit (not necessarily effectively) the existence of $z\in\mathbb G_2$ such that $e(g,z)=e(g^{ab},h)$ and $e(g^c,z)=e(\mathrm{candidate},h)$, though I cannot see how to express this terms of existing hardness assumptions.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.