7.1 Preliminaries

Recall our earlier definition of a symmetric cryptosystem from Chapter 4, Encryption and Decryption. A symmetric cryptosystem has the following ingredients:

• The plaintext space ℳ and the cipher space 𝒞

• The keyspace 𝒦

• The encryption function f_K : ℳ→𝒞

• The decryption function f_K⁻¹ : 𝒞→ℳ

Instead of f_K, in Chapter 4, Encryption and Decryption, we also wrote e_K (for encryption), and d_K (for decryption) instead of f_K⁻¹. In an asymmetric cryptosystem, the sender and receiver use different keys for encrypting and decrypting, respectively. The sender uses the receiver’s public key, PK, for encrypting, and the receiver uses their private key, SK, for decrypting. This means the decrypting function d is not exactly the inverse function of e because it takes a different key as a parameter. In the present chapter, we are specifically interested in an asymmetric encryption system, which...