# 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. Sep 18 '20 at 4:20

The two given tuples are computationally indistinguishable. Here's a proof

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

• One may want to note when reading this answer that computational indistinguishability is in general only transitive for a constant number of hops.
– SEJPM
Sep 18 '20 at 9:02
• @SEJPM: Could you explain why? I always thought it also worked for poly-many hops (this is how, for example, the hybrid argument works). The discussion in this lecture note also seems to agree. Sep 18 '20 at 15:07
• @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
• In the non-uniform model, the assumptions (finitely many) allow transitivity to go through for poly-many hops. In the uniform model, a strict proof is written as a probabilistic reduction and "poly-many hops" do not exist in the proof and are a pedagody device. Usually the proof can be uniform (i.e., written as probabilistic reduction) and it's routine to use "poly-many hops" exposition (or perhaps the authors don't care about uniform security). Sep 21 '20 at 5:51