Elgamal problem on $\mathbb{QR}_p$ with $p$ a safe prime

Question

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:

1. Determine the distribution of $s(g^{ab})$ for $a,b$ chosen uniformly in $\mathbb{Z}_q$.
2. Explicitly formulate Elgamal wrt $\mathbb{QR}_p$ modulo a safe prime $p$. Use $s(x)$ from above for Dec.
3. 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).

Answer 1

$P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$.

We assume that $g$ is a generator of $\mathbb{QR}_p = \mathbb Z_q$. Then, as you said, in order to study the probability that $g^{ab} = i = g^c$ for a fixed $c$, we can calculate the probability that $ab = c\bmod q$.

In general, the probability that a random pair $(a,b)\in\mathbb Z_q\times\mathbb Z_q$ gives you a fixed non-zero number $c$ is $(q-1)/q^2$, and if $c=0$ then this probability is $(2q-1)/q^2$.

2) I don't currently see how to take $s$ into play here.

ElGamal encryption scheme allows you to encrypt elements $m\in\mathbb{QR}_p$ as $m\cdot g^{ab}$. However, the message you want to encrypt is likely not to be an element of this set. In practice, you encrypt bit-strings, which are easier to map into $\{1,\ldots,(p-1)/2\}$. Then you take an element $y$ in this interval and map it to $m\in\mathbb{QR}_p$ via $m = y^2$, and use $m$ as above. Now you can see that you need $s$ for decryption in order to recover $y$ from $m$.

3) I believe the reasoning is equal to point 1).

Agreed. The idea is that with a safe prime $p = 2q+1$ you know that $\mathbb{QR}_p = \mathbb{Z}_q$, whereas in general this structure could be more involved. However, once you're working over $\mathbb{Z}_q$, the analysis is the same.