Public-Key Encryption - Introduction to Cryptography with Maple - page 500

sqroot is greater than q so this is not the square root we are looking for. Since
the two square roots are additive inverses of each other, the one we want must then
be − sqroot ∈ Z p :

− sqroot mod p which is the element p

> sqroot2 := p - sqroot;
7436209366774683086532086567482260098482727687760682110348247151216011001859463107\
26553421802330990675448187049196194483799883858511758002953862710913740650945905\
41939132300745837913126714560203454783147233272547976208797187133914584851982654\
0108582578260
The message can now be recovered by reversing the steps we took before. First
we convert this integer to base 256, which will give the list of extended ASCII codes
of its characters, and then we apply Maple's convert(-,bytes) to convert the
list of codes to a string of characters that will be equal to the original message:
> convert(convert(sqroot2, base, 256), bytes);
"This is an example of Elgamal encryption/decryption in the group of
quadratic residues modulo a safe prime"

Exercise 8.28 Write Maple functions for the Elgamal key generation, encryption,
and decryption algorithms, and use them to test encryption and decryption with the
data in the preceding example.

8.6 The Cramer-Shoup Encryption Scheme

Although the “plain” Elgamal encryption scheme studied in the previous section
has pretty good security properties—it compares very favorably, for example, with
plain RSA—it still falls short of the desirable security level for public-key encryption
schemes because, as we have seen, it is not IND-CCA secure.
We have already indicated how CCA secure encryption schemes may be built
from families of trapdoor permutations but these schemes are not efficient enough
for practical use. We have also seen that there are efficient public-key encryption
schemes—such as RSA-OAEP or Boneh's Rabin-SAEP—that are CCA secure in the
random oracle model, but until 1998 no scheme was known that was both practically
efficient and CCA secure without random oracles. Then the celebrated Cramer-
Shoup encryption scheme was introduced in [57]. It is a modification of Elgamal
encryption that is efficient—though not as much as, say, Rabin-SAEP—and achieves
IND-CCA under the sole assumption that the DDH problem is hard, without random
oracles. We next describe this scheme.

8.6.1 Cramer-Shoup Encryption and Its Security

The Cramer-Shoup encryption scheme works in groups of prime order q . Thus
encryption and decryption will use the operations of a group G such that

| |=

q ;
this group may be generated by the key generation algorithm and regarded as a
component of the public key or it may be regarded as a system parameter which is

G