# Proof of (in)distinguishability based on DDH/CDH/DL

I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group generator): Given the input tuple $$(g, g^{\alpha_1}, g^{\alpha_2}, g^{y}, g^{z})$$ where $$z \in \{y \alpha_1, y \alpha_2\}$$, the desired output is $$g^{\alpha_i}$$ (or simply $$i$$) such that $$z = y\alpha_i$$.

If it is not known, I would appreciate any suggestions for a reduction based proof.

• This is tightly equivalent to DDH. – Gee Law Sep 18 '20 at 4:20

Let tuples $$T_1=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_1y})$$ and $$T_2=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^{\alpha_2y})$$
Lets take a tuple $$T_3=(g, g^{\alpha_1}, g^{\alpha_2}, g^y, g^r)$$ where $$r \overset{}\leftarrow \mathcal{R}$$. That is, for the purpose of the proof we generate a tuple with the last element being a random element of the group.
It's easy to see that $$T_1 \approx T_3$$ ($$\approx$$: notation for compuational indistinguishability) because of DDH assumption. Same way, $$T_2 \approx T_3$$ as well. Since we know that computational indistinguishability is transitive, that means $$T_1 \approx T_2$$.
• @Occams_Trimmer It only works for poly-many hops if all the hops can be bound by the same negligble function. An example for a family of functions where each is negligible but the sum isn't is: $\varepsilon_i(n)=\begin{cases}1&i\geq n\\0&\text{else}\end{cases}$. Obviously each is individually neglgigble but if you consider $$p(n)=\sum^n_i \varepsilon_i(n)$$ it is obviously constantly $1$ and thus not negligible. Though also note that most proofs where an author errornously assumed that poly-many hops can be done can usually be fixed. – SEJPM Sep 18 '20 at 18:55