The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions.
Its security is based on the computational intractability (widely assumed, but not proved) of the Decisional Diffie–Hellman assumption.
Developed by Ronald Cramer and Victor Shoup in 1998, it is an extension of the ElGamal cryptosystem.
In contrast to ElGamal, which is extremely malleable, Cramer–Shoup adds other elements to ensure non-malleability even against a resourceful attacker.
This non-malleability is achieved through the use of a universal one-way hash function and additional computations, resulting in a ciphertext which is twice as large as in ElGamal.
The definition of security achieved by Cramer–Shoup is formally termed "indistinguishability under adaptive chosen ciphertext attack" (IND-CCA2).
The "adaptive" component of the security definition means that the attacker has access to this decryption oracle both before and after he observes a specific target ciphertext to attack (though he is prohibited from using the oracle to simply decrypt this target ciphertext).
This began to change during the late 1990s, particularly when Daniel Bleichenbacher demonstrated a practical adaptive chosen ciphertext attack against SSL servers using a form of RSA encryption.
[1] Cramer–Shoup was not the first encryption scheme to provide security against adaptive chosen ciphertext attack.
A variety of other approaches, including Bellare/Rogaway's OAEP and Fujisaki–Okamoto achieve efficient constructions using a mathematical abstraction known as a random oracle.
A growing body of evidence suggests the insecurity of this approach,[2] although no practical attacks have been demonstrated against deployed schemes.