Before Elliptic Curve Became King of the Hill, Cramer-Shoup Looked Like a Winner

In 1998, Bruce Schierner wrote a blog on the Cramer-Shoup public key encryption method [here]:

Bruce wrote:

Cramer-Shoup is good work and a good academic paper. The results are suprising: provable security against adaptive chosen ciphertexts and only twice as slow and four times the data expansion. But the proofs are based on something called the Diffie-Hellman Decision Problem (not the Diffie-Hellman Problem), which is much weaker.

And:

The news was glowing, and predicted that this new algorithm would replace SSL, save the Internet, and cure cancer. Hype was everywhere, and facts were few

But time has shown the RSA continued it domiance, and Elliptic Curve has since taken over to be the King of the Hill (and even taking over SSL for its default key exchange — ECDH).

So what was it: Cramer-Shoup is a public key encryption method that is an extension to ElGamal but adds a one-way hashing method which protects against an adaptive chosen ciphertext attack. The following shows the basic key generation, encryption and decryption parts.

Key generation:

• Alice generates two random generators in the range 1 to p-1 (g1,g2).