Asymmetric Cryptography

1Public-Key Encryption and Security Notions

Nuttapong ATTRAPADUNG and Takahiro MATSUDA

National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

Public-key encryption (PKE) allows a sender to use a receiver’s public key to encrypt a message under it and send it to the receiver, who possesses the corresponding secret key. There has been a tremendous amount of research on PKE since the first introduction of the concept by Diffie and Hellman (1976). One of the main goals would be to devise efficient PKE schemes that are provably secure in strong security notions using weak and reasonable computational assumptions. This chapter aims to provide some basic knowledge on PKE and its security notions and survey important results in this field.

We begin the chapter by centering around the security notion called indistinguishability against chosen-ciphertext attacks (IND-CCA), which is widely accepted as the de facto standard notion for PKE. In the first part, we study in detail the Cramer–Shoup (CS) PKE (Cramer and Shoup 1998), which is the first practical IND-CCA secure PKE under a reasonable assumption. This part may also serve as introductory material for a popular method to prove security, namely, using the game-based approach. In the second part, we provide a survey on specific and generic constructions for IND-CCA secure PKE. In the last part, we briefly cover some advanced recent research topics for PKE, such as tight security, key-dependent-message ...