# Mapping between subgroups and the integers

This question is a companion to the equivalent question on elliptic curves.

### Preliminaries

Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime $p$. However, for security reasons, we do not use all the integers in $\mathbb{Z}^*_p$ but only a subset of them. The subset is of size $q<p$ and $q$ is also a prime number. The subset is also chosen so that it also forms a group, $\mathbb{G}_q$, with closure under multiplication (a multiplicative subgroup). Number theory tells us that such a group can be found iff $q$ divides $(p-1)$.

With Elgamal in particular, messages must be encoded into $\mathbb{G}_q$. If the message is an $\ell$-bit bitstring $\{0,1\}^\ell$ and $\ell<|q|$, then it can be treated like an integer and will be in $\mathbb{Z}_p$ (and $\mathbb{Z}_q$) (we'll ignore the corner case of all zeros). The problem is that it is unlikely to also be in $\mathbb{G}_q$ (depending on how much smaller $q$ is than $p$).

### Questions

How can you map numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

• $p=2q+1$
• $p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

(I'll accept the best answer for the second case) (As the second case appears not to be possible—see my answer—I've accepted an answer for the first case)

### Format

This question is somewhat rhetorical for me personally, but I think it is a good place to gather different answers in one place (and things have been slow). With that in mind, use one technique per answer. Also relevant could be encoding-free Elgamal (such as hashed Elgamal) that sidesteps the problem.

-
Can you elaborate more on the security reasons that we do not use all elements in $\mathbb{Z}_p^*$ but only a subset of them? –  curious Nov 29 '13 at 22:53

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:

• Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.

• If $x$ is a non-zero quadratic residue ($x = y^2 \mod p$ for some value $y$) then $x^q = y^{2q} = y^{p-1} = 1 \mod p$. Thus, every non-zero quadratic residue is a $q$-th root of $1$, therefore an element of $\mathbb{G}_q$.

• Since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$. This implies that if $x$ is a quadratic residue, then $-x$ is not, and vice versa. Thus, there are $(p-1)/2 = q$ non-zero quadratic residues.

This yields the following mapping:

• If $x \in \mathbb{G}_q$ then it is a square and has two square roots, $y$ and $-y$ for a value $y$. Computing the square root modulo $p$ is easy: $y = x^{(p+1)/4} \mod p$. $y$ can be viewed as an integer between $1$ and $p-1$. Set $z = y - 1$ if $y \leq q$, or $z = p - y - 1$ otherwise. This always yields a value such that $0 \leq z \lt q$, i.e. a value in $\mathbb{Z}_q$.

• For the inverse mapping, just compute $(z+1)^2 \mod p$.

-
Could you explain to me why "if x is a quadratic residue, then -x is not, and vice-versa"? Thanks –  user1086 Nov 15 '11 at 13:04
@sophie: when working modulo a prime $p$ which is equal to 3 modulo 4, $-1$ is not a square (there is no $z$ such that $z^2 = p-1 \mod p$). This implies that if $x$ is a (non-zero) square (there is a $y \neq 0$ such that $y^2 = x \mod p$) then $-x \mod p$ cannot be a square; and it also works in the other direction (if $x$ is not a square than $-x$ is a square). This can be linked to Fermat's theorem (not the famous one): $x^{p-1} = 1 \mod p$; hence $x^{(p-1)/2} = ±1 \mod p$. This implies that $y = x^{(p+1)/4} \mod p$ is a square root of either $x$ or $-x$ (try it !). –  Thomas Pornin Nov 16 '11 at 15:20
Can you also explain why since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$ and that implies that $x$ is a quadratic residue? –  curious Nov 23 '12 at 9:40
$q$ is a prime so it is odd ($2$ is the only even prime). Therefore $q = 2k+1$ for some integer $k$. So, $p = 2q+1 = 4k+3$, which means that $p = 3 \mod 4$. Whe computing modulo a prime $p$ which is equal to 3 modulo 4, $-1$ is not a quadratic residue, so $x$ and $-x$ cannot be both quadratic residues (but one of them necessarily is). –  Thomas Pornin Nov 23 '12 at 12:13

For the second case, mapping numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when:

• $p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160

It appears an efficient subgroup encoding/decoding scheme does not exist. Although it has not been proven that one cannot exist, notable cryptographers have conjectured it in the literature. For example, Chevallier-Mames, Paillier, and Pointcheval state:

(U)sing a group encoding remains incompatible with the optimization which consists in working in a small subgroup of $\mathbb{Z}^*_p$ of of prime order $q$ where $q$ is a 160-bit prime, a setting in which group exponentiations are much faster. [CPP06]

-

Probably the easiest solution for the case a=2 is to map $m\in\{1\ldots q\}$ to $(m/p)m$ where $(m/p)$ is the Legendre symbol. The inverse can be obtained by mapping a quadratic residue $x\in Z/(pZ)^*$ either to x or -x depending on which of the two residue classes contains an integer in $\{1\ldots q\}$.

This is of course a well know solution, but I can't find a reference at the moment.

-