The Cramer–Shoup cryptosystem

Notes on The Cramer–Shoup Public-Key Encryption Scheme (CS1), written as coursework at Hochschule Flensburg. The scheme and its security proof are the work of Ronald Cramer and Victor Shoup.

Abstract

Public-key encryption (PKE) allows secure communication over open networks without the need of a shared secret in advance. However, classical security notions for PKE often assume passive adversaries that only observe ciphertexts. This does not accurately reflect realistic network environments where attackers may interact with protocols and obtain partial decryption capabilities. The strongest standard security notion for PKE is indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2), where an adversary can query a decryption oracle before and after receiving a challenge ciphertext. This paper provides a detailed and accessible description of the Cramer–Shoup encryption scheme (CS1), the first practical PKE construction proven IND-CCA2 secure under standard assumptions without relying on the random oracle model. This paper includes the required background, the relevant security notions, a formal description of CS1 and the main soundness and security arguments based on the Decisional Diffie–Hellman (DDH) assumption and target collision resistant hashing (TCR).

Original paper

Ronald Cramer and Victor Shoup. Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack. SIAM Journal on Computing 33(1), 2003. Preprint: Cryptology ePrint Archive 2001/108.