I need some orientation to solve the following problem:
Let $p = 2q+1$ be a safe prime and $s(x)$ the smallest of the two square roots of $x$ modulo $p$. Then:
- Determine the distribution of $s(g^{ab})$ for $a,b$ chosen uniformly in $\mathbb{Z}_q$.
- Explicitly formulate Elgamal wrt $\mathbb{QR}_p$ modulo a safe prime $p$. Use $s(x)$ from above for Dec.
- Let $G = \langle g \rangle$ be any group of prime order $q$. Determine the distribution of $g^{ab}$ for $a,b$ uniformly distributed on $\mathbb{Z}_q$.
My solution
1) It seems I have to study the distribution of $ab \; mod \; q = c$. Because the mapping $s^{-1}: \{1,\ldots,\frac{p-1}{2}\} \to \mathbb{QR}_p$ is one-to-one and efficiently invertible. Since $g$ can be assumed to be a generator of $\mathbb{QR}_p$ then it is sufficient to study the exponents (each exponent will correspond exactly to one "smallest" square root.
Now, considering the possible $q^2$ pairs. There are $q+(q-1)$ pairs yielding a zero. For $c \neq 0$, one can fix $a$ and solve immediately for $b$ which yields $q-1$ possibilities for $c$. Adding up, we have $2q-1+(q-1)^2 = q^2$ as expected.
So the distribution is $P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$.
2) I don't currently see how to take $s$ into play here.
3) I believe the reasoning is equal to point 1).