12
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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? $\endgroup$
    – curious
    Nov 29, 2013 at 22:53

3 Answers 3

7
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Could you explain to me why "if x is a quadratic residue, then -x is not, and vice-versa"? Thanks $\endgroup$
    – user1086
    Nov 15, 2011 at 13:04
  • 2
    $\begingroup$ @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 !). $\endgroup$ Nov 16, 2011 at 15:20
  • $\begingroup$ 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? $\endgroup$
    – curious
    Nov 23, 2012 at 9:40
  • 1
    $\begingroup$ $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). $\endgroup$ Nov 23, 2012 at 12:13
  • $\begingroup$ Forgive my newness, but I don't see how this specific group is homomorphic on multiplication. If I change the mapping to $z=y$ if $y \leq q$, or $z=p-y$ otherwise, and the inverse mapping to $z^2\bmod p$, then multiplications within the group are homomorphic. Am I doing something wrong? $\endgroup$
    – Russ
    Sep 4, 2018 at 14:13
5
$\begingroup$

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]

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.