My textbook states, that the DDH-assumption is not satisfied when we use the group $\mathbb{Z}/p \mathbb{Z}$ and demonstrates an attack using Eulers Criterion. After that, it states that one should use the group of quadratic residues ($\operatorname{QR}$) over $\mathbb{Z}/p \mathbb{Z}$, where $p=2q+1$ is a safe prime.

I had a look at the El Gamal encryption scheme (which uses the DDH-assumption) and saw, that the message that we want to encrypt has to lie in the group that we choose. If this group is $\mathbb{Z}/p \mathbb{Z} = \{1,2,3,\ldots ,p-1\}$ we can encrypt every message, that is not greater than $p-1$. However, if we use the group of $\operatorname{QR}$'s over $\mathbb{Z}/p \mathbb{Z}$, I think that some messages (namely $(p-1)/2$ many) cannot be encrypted.

If this is true, how would one solve this in practice?

  • $\begingroup$ Could you add the name of your textbook and page number and edtion? $\endgroup$ – kelalaka Jan 17 at 15:15
  • $\begingroup$ Does this satisfies your question How to encode messages in Z∗p to be encrypted with ElGamal scheme? $\endgroup$ – kelalaka Jan 17 at 15:20
  • $\begingroup$ Joy of Cryptography by Mike Rosulek, the current version is available at web.engr.oregonstate.edu/~rosulekm/crypto. The first part is covered on page 250 (For what groups does the DDH-assumption hold?). The El Gamal Encrytpion can be found on page 257 (section 15.3). $\endgroup$ – David Lehnherr Jan 17 at 15:24
  • $\begingroup$ @kelalaka Kind of. Am I understaning it correctly, that my concern is valid because of information leak (last part of the first answers section)? Still, the QR group seems impractical to me. What group is used in practice? $\endgroup$ – David Lehnherr Jan 17 at 15:36

If this is true, how would one solve this in practice?

Actually, in practice, what we generally do is not use El Gamal at all, but instead use Integrated Encryption Scheme (IES), which solves the same problem based on the same hard problem, but where one doesn't worry about Quadratic Residues (or the homomorphic properties, or the need to compute inverses, which is doable but annoying).

Now, if we have to use El Gamal (e.g. because we need to take advantage of the homomorphic properties), well, one way to avoid the QR problem is to simply square the plaintext before encryption (and hence the plaintext that we encrypt is always a QR). Then, on decryption, we would compute the square root (and take the smaller of the two possible values). This implies that the plaintext is limited to the range $(0, (p-1)/2)$, but any value in that range can be encrypted.

| improve this answer | |
  • $\begingroup$ Thanks, that makes sense. I also thought about squaring the messages, but I only considered squaring messages that are not QRs (which got confusing). $\endgroup$ – David Lehnherr Jan 18 at 5:36

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.