0
$\begingroup$

I need some help for the following simple game:

An adversary is given a multiplicative group $\mathbb{G}$ and the 4-tuple $(g_1, g_2, g_3, g_1^a \cdot g_2^b \cdot g_3^c)$ where $g_1$, $g_2$ and $g_3$ are random elements from $\mathbb{G}$, and $a$, $b$ $c$ are hidden.

During the challenge phase, the adversary either receives:

  • Case $b=1$: $(g_4, g_5, g_6, g_4^a \cdot g_5^b \cdot g_6^c)$,
  • Or case $b=0$: $(g_4, g_5, g_6, Z)$ where $g_4$, $g_5$, $g_6$ and $Z$ are random elements from $\mathbb{G}$.

The goal is to distinguish if $b=0$ or $b=1$.

My questions are the following:

  1. This problem does not seem to be related to DLin nor DDH, but seems hard if the number of elements in the product is large. Do you think this problem is hard?

  2. Do you know a problem related to it?

Thank you

$\endgroup$
4
  • $\begingroup$ what is DLin problem? $\endgroup$
    – Don Freecs
    Jul 3, 2023 at 12:56
  • $\begingroup$ @DonFreecs crypto.stackexchange.com/questions/11282/… en.wikipedia.org/wiki/Decision_Linear_assumption $\endgroup$
    – Adam54
    Jul 3, 2023 at 13:04
  • 1
    $\begingroup$ @DonFreecs you have two distributions $D_{1}=(u,\,v,\,h,\,u^{a},\,v^{b},\,h^{a+b})$ and $D_{2}=(u,\,v,\,h,\,u^{a},\,v^{b},\,\eta )$ where $\eta$ is randomly drawn. The DLIN assumption is that $D_1$ and $D_2$ are computationally indistinguishable. $\endgroup$
    – Adam54
    Jul 3, 2023 at 13:07
  • $\begingroup$ I guess this problem can be reduced to DDH. For example, given the adversary $\mathcal{A}_2$ a DDH instance $(g_1,g^a_1,g_4:=g^{a'}_1,Z'_a)$, where $Z'_a=g^{a\cdot a'}_1$ or $g^r_1$. In the challenge phase, $\mathcal{A}_2$ send the tuple embedding $(g_4,Z'_a)$ to $\mathcal{A}_1$, if $\mathcal{A}_1$ can distinguish $Z=Z'_a\cdot g^b_5\cdot g^c_6$ with non-negligible probability, then $\mathcal{A}_2$ can solve the DDH instance. With the same way, if $\mathcal{A}_1$ can distinguish $Z=Z'_b\cdot g^a_4\cdot g^c_6$ or $Z=Z'_c\cdot g^a_4\cdot g^b_5$, then $\mathcal{A}_2$ can solve DDH. $\endgroup$
    – X.H. Yue
    Jul 10, 2023 at 8:01

1 Answer 1

2
$\begingroup$

If $g_4$, $g_5$ and $g_6$ generate $\mathbb G$ (as is usually the case in cryptography) and the exponents are uniformly generated at random modulo the group order then the problem is impossible because the distribution of $g_4^ag_5^bg_6^c$ precisely matches that of $Z$.

If they do not generate $\mathbb G$ then the problem is easy to solve with advantage if we can test the corresponding element of $Z$ for membership of the subgroup generated by the elements. We can do this test for typical cryptographic groups of known order, but there are cases, for example multiplicative groups modulo an RSA number, where testing for subgroup membership is believed to be hard (specifically it will correspond to a residuacity problem).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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