Cramer–Shoup cryptosystem

From Wikipedia, the free encyclopedia
  (Redirected from Cramer-Shoup cryptosystem)
Jump to: navigation, search

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.

Adaptive chosen ciphertext attacks[edit]



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 Bellare/Rogaway's 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,[2] although no practical attacks have been demonstrated against deployed schemes.

The cryptosystem[edit]

Cramer–Shoup consists of three algorithms: the key generator, the encryption algorithm, and the decryption algorithm.

Key generation[edit]

  • Alice generates an efficient description of a cyclic group G of order q with two distinct, random generators g_1, g_2.
  • Alice chooses five random values ({x}_{1}, {x}_{2}, {y}_{1}, {y}_{2}, z) from \{0, \ldots, q-1\}.
  • Alice publishes (c, d, h), along with the description of G, q, g_1, g_2, as her public key. Alice retains (x_1, x_2, y_1, y_2, z) as her secret key. The group can be shared between users of the system.


To encrypt a message m to Alice under her public key (G,q,g_1,g_2,c,d,h),


To decrypt a ciphertext (u_1, u_2, e, v) with Alice's secret key (x_1, x_2, y_1, y_2, z),

  • Otherwise, Alice computes the plaintext as m = e / ({u}_{1}^{z}) \,.

The decryption stage correctly decrypts any properly-formed ciphertext, since

 {u}_{1}^{z} = {g}_{1}^{k z} = h^k \,, and m = e / h^k. \,



  1. ^ Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. Advances in Cryptology — CRYPTO '98. [1]
  2. ^ Ran Canetti, Oded Goldreich, Shai Halevi. The Random Oracle Methodology, Revisited. Journal of the ACM, 51:4, pages 557–594, 2004.