Editing Cramer–Shoup cryptosystem (section)

==Adaptive chosen ciphertext attacks==

The definition of security achieved by Cramer–Shoup is formally termed "[[ciphertext indistinguishability|indistinguishability]] under [[adaptive chosen ciphertext attack]]" (IND-CCA2).  This security definition is currently the strongest definition known for a public key cryptosystem: it assumes that the attacker has access to a [[decryption oracle]] which will decrypt any ciphertext using the scheme's secret decryption key.  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).  The weaker notion of security against non-adaptive chosen ciphertext attacks (IND-CCA1) only allows the attacker to access the decryption oracle before observing the target ciphertext.

Though it was well known that many widely used cryptosystems were insecure against such an attacker, for many years system designers considered the attack to be impractical and of largely theoretical interest.  This began to change during the late 1990s, particularly when [[Daniel Bleichenbacher]] demonstrated a practical adaptive chosen ciphertext attack against [[Secure Sockets Layer|SSL]] servers using a form of [[RSA (algorithm)|RSA]] encryption.<ref>Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. Advances in Cryptology – CRYPTO '98.  [http://citeseer.ist.psu.edu/bleichenbacher98chosen.html]</ref>

Cramer–Shoup was not the first encryption scheme to provide security against adaptive chosen ciphertext attack.  Naor–Yung, Rackoff–Simon, and Dolev–Dwork–Naor proposed provably secure conversions from standard (IND-CPA) schemes into IND-CCA1 and IND-CCA2 schemes.  These techniques are secure under a standard set of cryptographic assumptions (without random oracles), however they rely on complex [[zero-knowledge proof]] techniques, and are inefficient in terms of computational cost and ciphertext size.  A variety of other approaches, including [[Mihir Bellare|Bellare]]/[[Phillip Rogaway|Rogaway]]'s [[Optimal Asymmetric Encryption Padding|OAEP]] and [[Fujisaki–Okamoto]] achieve efficient constructions using a mathematical abstraction known as a [[random oracle]].  Unfortunately, to implement these schemes in practice requires the substitution of some practical function (e.g., a [[cryptographic hash function]]) in place of the random oracle.  A growing body of evidence suggests the insecurity of this approach,<ref>Ran Canetti, [[Oded Goldreich]], Shai Halevi.  [http://doi.acm.org/10.1145/1008731.1008734 ''The Random Oracle Methodology, Revisited''].  Journal of the ACM, 51:4, pages 557–594, 2004.</ref> although no practical attacks have been demonstrated against deployed schemes.