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

  • $\begingroup$ Could you please explain what $\mathbb Q \mathbb R_p$ is? $\endgroup$ – Hilder Vitor Lima Pereira Jan 29 '19 at 8:09
  • $\begingroup$ @HilderVítorLimaPereira $\mathbb{QR}_p = \{x^2 \; mod \; p: x \in \mathbb{Z}_p^*\}$ $\endgroup$ – 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.

| improve this answer | |

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.