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 fK : ℳ→𝒞
• The decryption function fK−1 : 𝒞→ℳ

Instead of fK, in Chapter 4, Encryption and Decryption, we also wrote eK (for encryption), and dK (for decryption) instead of fK−1. 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 is defined by the following ingredients:

• The plaintext space ℳ and the cipher space 𝒞
• The keyspace 𝒦 is a set of key pairs {(PK1,SK1),…(PKn,SKn)}
• The encryption functions ePK : ℳ→𝒞
• The decryption functions dSK : 𝒞→ℳ, so that

for all m ∈ M and all key pairs

The security of public-key cryptography relies on the computational hardness of certain number-theoretical problems. This is also referred to as intractability. Recall from Chapter 3, A Secret to Share, that some mathematical problems are believed to be computationally intractable because for decades – or, in some cases, even centuries – no one managed to come up with an efficient algorithm for solving them. Efficient in this context refers to algorithms that run in polynomial time, at least for a non-negligible portion of all possible inputs.

To put it differently, we consider a mathematical problem to be easy (or tractable) if there is an algorithm that solves a non-negligible subset of all instances of that problem in polynomial time. On the other hand, a mathematical problem is hard if no efficient (that is, polynomial time) algorithms for solving it are known.

But how can we use such problems in public-key cryptography? The basic idea, as first formulated in [49], is to use so-called trapdoor or one-way functions. These are invertible mathematical functions that are easy to compute but computationally hard to invert. The easy part can be used for encrypting. The way to design a public-key cryptosystem is now to find a special piece of information, the private key, which makes the computation of the inverse function easy for the owner of the private key.

In what follows, we will explain the two most common mathematical problems used for public-key cryptography: the discrete logarithm and the factorization problem. The corresponding public-key-cryptosystems are the Diffie-Hellman key exchange protocol, the ElGamal cryptosystem, and the RSA cryptosystem.