3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Chipotle Jun 2 at 6:25
  • $\begingroup$ 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. $\endgroup$ – kodlu Jun 4 at 3:22
  • $\begingroup$ 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. $\endgroup$ – Chipotle Jun 4 at 9:25

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.