CramerShoup cryptosystemFrom CryptoDox, The Online Encyclopedia on Cryptography and Information SecurityThe CramerShoup 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 DiffieHellman 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, CramerShoup adds additional elements to ensure nonmalleability even against a resourceful attacker. This nonmalleability is achieved through the use of a collisionresistant hash function and additional computations, resulting in a ciphertext which is twice as large as in Elgamal. Adaptive chosen ciphertext attacksThe definition of security achieved by CramerShoup is formally termed "indistinguishability under adaptive chosen ciphertext attack" (INDCCA2). 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 nonadaptive chosen ciphertext attacks (INDCCA1) 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 SSL servers using a form of RSA encryption. CramerShoup was not the first encryption scheme to provide security against adaptive chosen ciphertext attack. NaorYung, RackoffSimon, and DolevDworkNaor proposed provably secure conversions from standard (INDCPA) schemes into INDCCA1 and INDCCA2 schemes. These techniques are secure under a standard set of cryptographic assumptions (without random oracles), however they rely on complex zeroknowledge proof techniques, and are inefficient in terms of computational cost and ciphertext size. A variety of other approaches, including Bellare/Rogaway's OAEP and FujisakiOkamoto 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, although no practical attacks have been demonstrated against deployed schemes. The cryptosystemCramerShoup consists of three algorithms: the key generator, the encryption algorithm, and the decryption algorithm. The key generator works as follows:
The encryption algorithm works as follows: to encrypt a message m to Alice under her public key (G,q,g_{1},g_{2},c,d,h),
The decryption algorithm works as follows: to decrypt a ciphertext (u_{1},u_{2},e,v) with Alice's secret key (x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}),
The decryption stage correctly decrypts any properlyformed ciphertext, since , and . If the space of possible messages is larger than the size of G, then the message can be split into several pieces and each piece can be encrypted independently. Alternately, CramerShoup may be used in a hybrid cryptosystem to improve efficiency on long messages. References
