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 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 of order with two distinct, random generators . 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 function, 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 cryptosystem to improve efficiency on long messages. References Ronald Cramer and Victor Shoup. "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack." in proceedings of Crypto 1998, LNCS 1462, p. 13ff (ps,pdf) Toy implementations of Cramer–Shoup in Emacs Lisp and Java 1998 vintage news coverage of Cramer and Shoup's publication in Wired News and in Bruce Schneier's Crypto-Gram Ronald Cramer and Victor Shoup: "Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption." in proceedings of Eurocrypt 2002, LNCS 2332, pp. 45–64. Full Version (pdf) Public-key encryption schemes