Cramer-Shoup cryptosystem
Encyclopedia
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.
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.
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, although no practical attacks have been demonstrated against deployed schemes.
to Alice under her public key 
,
with Alice's secret key 
,
The decryption stage correctly decrypts any properly-formed ciphertext, since
If the space of possible messages is larger than the size of
, 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.
Ronald Cramer
Ronald Cramer is a professor at the Centrum Wiskunde & Informatica in Amsterdam and the University of Leiden. He obtained his PhD from the University of Amsterdam in 1997...
and Victor Shoup
Victor Shoup
Victor Shoup is a computer scientist and mathematician. He obtained a PhD in computer science from the University of Wisconsin–Madison in 1989, and he did his undergraduate work at the University of Wisconsin-Eau Claire. He is currently a professor at the Courant Institute of Mathematical Sciences...
in 1998, it is an extension of the Elgamal cryptosystem
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
. In contrast to Elgamal, which is extremely malleable
Malleability (cryptography)
Malleability is a property of some cryptographic algorithms. An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext...
, 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
The definition of security achieved by Cramer–Shoup is formally termed "indistinguishabilityCiphertext indistinguishability
Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt...
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.
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
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
techniques, and are inefficient in terms of computational cost and ciphertext size. A variety of other approaches, including Bellare
Mihir Bellare
Mihir Bellare is a cryptographer and professor at the University of California, San Diego. He has published several seminal papers in the field of cryptography , many coauthored with Phillip Rogaway. Bellare has published a number of papers in the field of Format-Preserving Encryption...
/Rogaway
Phillip Rogaway
Phillip Rogaway is a professor of computer science at the University of California, Davis. He graduated with an BA in computer science from UC Berkeley and completed his PhD in cryptography at MIT, in the Theory of Computation group. He has taught at UC Davis since 1994.Dr...
's OAEP
Optimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
and Fujisaki–Okamoto achieve efficient constructions using a mathematical abstraction known as a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
. Unfortunately, to implement these schemes in practice requires the substitution of some practical function (e.g., a cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
) 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 cryptosystem
Cramer–Shoup consists of three algorithms: the key generator, the encryption algorithm, and the decryption algorithm.Key generation
- AliceAlice and BobThe names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
generates an efficient description of a cyclic groupCyclic groupIn group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
of order 
with two distinct, random generatorGenerating set of a groupIn abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
s
. - Alice chooses five random values
from 
. - Alice computes
. - Alice publishes
, along with the description of 
, as her public key. Alice retains 
as her secret key. The group can be shared between users of the system.
Encryption
To encrypt a message to Alice under her public key ,- Bob converts
into an element of 
. - Bob chooses a random
from 
, then calculates:
, where H is a universal one-way hash function (or a collision resistant cryptographic hash functionCryptographic hash functionA cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
, which is a stronger requirement).
- Bob sends the ciphertext
to Alice.
Decryption
To decrypt a ciphertext with Alice's secret key ,- Alice computes
and verifies that 
. If this test fails, further decryption is aborted and the output is rejected. - Otherwise, Alice computes the plaintext as
.
The decryption stage correctly decrypts any properly-formed ciphertext, since
-
, and 
If the space of possible messages is larger than the size of
, then Cramer–Shoup may be used in a hybrid cryptosystemHybrid cryptosystem
In cryptography, public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely . However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable...
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.