# Distinguishing between two DDH-like tuples

Given a group generator $$g$$ (in a group where DDH is hard). Let $$X_1=g^{x_1}$$ and $$X_2=g^{x_2}$$ be two public elements, where $$x_1$$ and $$x_2$$ are selected randomly and kept secret.

Consider a game where a challenger selects secretly some random $$r$$ and computes $$Y_1= X_1^r$$ and $$Y_2=X_2^r$$. The challenger hands $$Y_1$$ and $$Y_2$$ to the adversary. The adversary wins the game if it distinguishes $$(X_1, X_2,Y_1,Y_2)$$ from $$(X_1,X_2,Y_2,Y_1)$$.

Is there a way to prove that the adversary can't win this game with non-negligible probability (e.g., if there is there a security reduction that can be used to prove this)?

• Do you mean: "adversary wins if it distinguishes $(X_1,X_2,Y_1,Y_2)$ from $(X_1,X_2,Y_2,Y_1)$" ? Commented Nov 26, 2023 at 17:04
• Yes. That's exactly what I meant. Commented Nov 26, 2023 at 18:06
• I think you should use the DDH assumption to prove that both distributions are indistinguishable from uniform. Commented Nov 27, 2023 at 0:10
• The problem is that even if they are both indistinguishable from uniform, they may still be distinguishable from one another (e.g., if $Y_1=Y_2^2$, though this case is unlikely as $X_1$ and $X_2$ should be random elements in the group). Commented Nov 27, 2023 at 8:13
• What Mikero means is that using DDH, you can show that they are jointly indistinguishable from uniform. Commented Nov 27, 2023 at 9:28