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

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

• It seams to me that you have already answered your own question... May 30 '19 at 15:40
• @fkraiem :) still, if x is the next lottery number, could you manipulate it just by looking at g^x? May 30 '19 at 15:43

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.

• Of all encoding functions, probably the one that the adversary is not going to choose is a hash function, no? what information can an adversary gain from the hashed image of $A$? Jun 2 '19 at 6:25
• This is how one can prevent an adversary from learning $x$. It was unclear in the question that the adversary chose the encoding, not a standard state of affairs. Jun 4 '19 at 3:22
• I apologise if the question wasn't clear enough, although I can't see why what you describe would be a common practice. Perhaps I'm missing something. Jun 4 '19 at 9:25