What information does $g^x$ reveal about $x$?

Question

Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with 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?)

Answer 1

You state

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

One way to address this issue, let's call it the encoding of $A$ issue is to hide the obvious properties of $A.$ Thus the players can interact with a randomized encoding of $A.$ Specifically, for your case, we can define $A$ as the set of all numbers $x$ in the integers modulo $n$ such that $H(x)$ has a certain bit pattern $(a_1,a_2,\cdots, a_t)$ in its leading $t$ bits, where $H$ is a secure hash function.

So the game can be played on the hashed image of the relevant quantities.