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

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

• Could you please explain what $\mathbb Q \mathbb R_p$ is? – Hilder Vitor Lima Pereira Jan 29 '19 at 8:09
• @HilderVítorLimaPereira $\mathbb{QR}_p = \{x^2 \; mod \; p: x \in \mathbb{Z}_p^*\}$ – Rodrigo Jan 29 '19 at 9:00

$$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.