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

  • $\begingroup$ 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)$" ? $\endgroup$
    – Mikero
    Nov 26, 2023 at 17:04
  • $\begingroup$ Yes. That's exactly what I meant. $\endgroup$
    – Doron
    Nov 26, 2023 at 18:06
  • 3
    $\begingroup$ I think you should use the DDH assumption to prove that both distributions are indistinguishable from uniform. $\endgroup$
    – Mikero
    Nov 27, 2023 at 0:10
  • $\begingroup$ 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). $\endgroup$
    – Doron
    Nov 27, 2023 at 8:13
  • $\begingroup$ What Mikero means is that using DDH, you can show that they are jointly indistinguishable from uniform. $\endgroup$ Nov 27, 2023 at 9:28


Your Answer

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