# Message space when using the group of QR's for El Gamal Encryption

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?

• Could you add the name of your textbook and page number and edtion? Jan 17 '20 at 15:15
• Does this satisfies your question How to encode messages in Z∗p to be encrypted with ElGamal scheme? Jan 17 '20 at 15:20
• 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). Jan 17 '20 at 15:24
• @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? Jan 17 '20 at 15:36

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.