Cramer–Shoup cryptosystem

Cramer–Shoup cryptosystem

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.

Contents

Adaptive chosen ciphertext attacks

The definition of security achieved by Cramer–Shoup is formally termed "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 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. 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

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

Key generation

  • Alice generates an efficient description of a cyclic group G of order q with two distinct, random generators g1,g2.
  • Alice chooses five random values (x1,x2,y1,y2,z) from \{0, \ldots, q-1\}.
  • Alice computes c = {g}_{1}^{x_1} g_{2}^{x_2}, d = {g}_{1}^{y_1} g_{2}^{y_2}, h = {g}_{1}^{z}.
  • Alice publishes (c,d,h), along with the description of G,q,g1,g2, as her public key. Alice retains (x1,x2,y1,y2,z) as her secret key. The group can be shared between users of the system.

Encryption

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

  • Bob converts m into an element of G.
  • Bob chooses a random k from \{0, \ldots, q-1\}, then calculates:
    • u_1 = {g}_{1}^{k}, u_2 = {g}_{2}^{k}
    • e = h^k m \,
    • \alpha = H(u_1, u_2, e) \,, where H() is a universal one-way hash function (or a collision resistant cryptographic hash function, which is a stronger requirement).
    • v = c^k d^{k\alpha} \,
  • Bob sends the ciphertext (u1,u2,e,v) to Alice.

Decryption

To decrypt a ciphertext (u1,u2,e,v) with Alice's secret key (x1,x2,y1,y2,z),

  • Alice computes \alpha = H(u_1, u_2, e) \, and verifies that {u}_{1}^{x_1} u_{2}^{x_2} ({u}_{1}^{y_1} u_{2}^{y_2})^{\alpha} = v \,. If this test fails, further decryption is aborted and the output is rejected.
  • 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. \,

If the space of possible messages is larger than the size of G, then Cramer–Shoup may be used in a hybrid cryptosystem to improve efficiency on long messages. Note that it is not possible to split the message into several pieces and encrypt each piece independently, because the chosen-ciphertext security property is not preserved in this way.

References

  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.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Cramer-Shoup cryptosystem — 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… …   Wikipedia

  • Cramer–Shoup-Kryptosystem — Das Cramer–Shoup Kryptosystem ist ein von Ronald Cramer und Victor Shoup entwickeltes asymmetrisches Kryptosystem, das als eine Erweiterung des Elgamal Kryptosystems aufgefasst werden kann.[1] Es war das erste praktikable… …   Deutsch Wikipedia

  • Cramer — (  /ˈkreɪ …   Wikipedia

  • Paillier cryptosystem — The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n th residue classes is believed to be computationally difficult. This… …   Wikipedia

  • McEliece cryptosystem — In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance… …   Wikipedia

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia

  • Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… …   Wikipedia

  • Damgård–Jurik cryptosystem — The Damgård–Jurik cryptosystem[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ns + 1 where n is an RSA modulus and s a (positive) natural number. Paillier s scheme is the special case with s = 1. The order φ(ns + …   Wikipedia

  • Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”