Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with prime order $q$ - again a large prime. Let $g$ be a generator of $G$.
Consider the following standard protocol for generating a random element $x \in \mathbb{Z}_P$:
- Player 1 generates a random number $x_1 \in \mathbb{Z}_p$ and outputs $g^{x_1}$ as a binding commitment.
- Player 2 generates a random number $x_2 \in \mathbb{Z}_p$ and outputs $g^{x_2}$ as a binding commitment.
- The two players reveal $x_1, x_2$, and after checking consistency with the commitments, the output of the whole process is defined as $x = x_1 +x_2 \ (\mathrm{mod}\ p)$.
Suppose now that Player 2 would like to manipulate $x$. Her strategy is the following: She sees $g^{x_1}$. She generates $n$ random number $a_1, ...,a_n$. She computes $g^{x_1+a_1}, ..., g^{x_1+a_n}$, see which one she likes best, and sets $x_2$ accordingly: $x_2 = a_i$ for some $1 \leq i \leq n$. Finally, she outputs a commitment $g^{x_2}$.
This scheme is not considered secure, since Player 2 can obviously affects the distribution of $g^{x_1+x_2}$ and therefore the distribution of $x$.
My question is, can Player 2 really manipulate $x$ to her benefit?
One way to formalise this question would be: Let $A \subset \mathbb{Z}_P^*$. If Player 2 is honest, we have
$$
\mathbb{P}[x \in A] = \frac{|A|}{p-1}.
$$
Can Player 2 increase this probability using the above strategy?
(Naturally, $A$ can be defined by "the set of all numbers $x$ in $\mathbb{Z}_p$ such that $g^x$ has a '1' in the last digit" and then Player 2 can easily make this probability equal 1, so this formalisation is not very good. Suggestions?)
