# Special indistinguishability problem

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.

• 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

• what is DLin problem? Jul 3, 2023 at 12:56
• Jul 3, 2023 at 13:04
• @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. Jul 3, 2023 at 13:07
• 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. Jul 10, 2023 at 8:01

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