For every PPT distinguisher A there exists a negligible function $neg(·)$ such that for all $\lambda$

$|\Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^{ab}) = 1] - \Pr[A(1^\lambda, g,g_1^a,g_1^b,g_1^z) = 1]| \leq \textsf{negl}(\lambda)$

where $g$ is a generator of group $G$ of order $p$ where $p$ is a prime of length approximately $\lambda$, $g_1 = g^r \in G$, and $r,a,b,z$ are randomly chosen from $Z_p$


Hint: suppose we modify the problem so that $r, a, b, z$ are selected uniformly randomly from the interval $[1, p-1]$; how do the probability distributions of $(g^{ra}, g^{rb}, g^{rab})$ and $(g^{ra}, g^{rb}, g^{rz})$ compare?

Hint: if we actually select $r, a, b, z$ from $\mathbb{Z}_p$, what is the probability that at least one of them are selected outside the interval $[1, p-1]$? Can you show that this probability is negligible?

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.