One-Way Functions for Public-Key Cryptography

Having stated the blueprint for a public-key cryptosystem, we now need to consider how such a public-key cryptosystem can be designed. The first step in this direction is to precisely state the properties we need public-key encryption to satisfy.

Trapdoor one-way functions

Public-key encryption can be thought of as a function that anyone should be able to compute since the encryption key is public. This function has these two obvious properties:

• The function should be ‘easy’ to compute: In other words, it should be computable in polynomial time. If this is not the case, it will be impractical to encrypt anything.

• The function should be ‘hard’ to reverse: In other words, an algorithm for finding the input from a given output should run in exponential time. If this is not the case, then an attacker might efficiently determine a plaintext from their knowledge of the ciphertext and the public encryption key.

A function having the properties above is often referred to as a one-way function.