Pseudorandomness – Encryption and Decryption

4.5 Pseudorandomness

Computational security is built on the concept of pseudorandomness, the idea that bit strings (that is, ciphertexts) can look completely random even though they are not.

Pseudorandomness enables us to build (computationally) secure symmetric encryption schemes where a relatively short key, let’s say 128 bits long, is used to securely encrypt multiple terabytes of plaintext messages.

In a nutshell – the precise mathematical details are, of course, much more complex – this works because a polynomial-time attacker cannot distinguish between a pseudorandom string and a truly random string. This means that, for the attacker, the ciphertext looks like it has been produced by a one-time pad, using the pseudorandom string as a key.

Pseudorandom strings can be created using a pseudorandom generator. This is a deterministic algorithm that takes a short, truly random string as input and expands it into a long pseudorandom string [97]. Figure 4.8 shows a pseudorandom generator G takes as input a short, truly random string s and expands it into a much longer pseudorandom string t. In the computational security model, this allows us to construct secure encryption schemes that can encrypt a large number of messages using a single short key.

We have already come across pseudorandom generators in the earlier section on True randomness and pseudorandomness in Chapter 3, A Secret to Share, where we discussed their role in generating keys. Now we see that they can also be used to simulate a one-time pad.

Figure 4.8: A pseudorandom generator G

The short, truly random input of a pseudorandom generator is called a seed. The seed must be chosen uniformly at random to have sufficient entropy and must be kept secret. In addition, the seed must be large enough so that no polynomial-time attacker has enough time to test all possible seeds. Finally, an attacker should be practically unable to predict the next output bit of the pseudorandom generator (to put it more formally, an attacker using a polynomial-time algorithm should have a negligible advantage over pure guessing).

Figure 4.8 and the pseudorandom generator definition given earlier in this section tell us what its required behavior is but not how to achieve it. If we want to actually build a pseudorandom generator, we obviously need to find a mathematical function that Eve cannot invert. Otherwise, Eve could easily recover s by simply computing the inverse function G−1 for any given t.

Even though no mathematical proof of their existence has been found so far, there is a consensus in modern cryptography that pseudorandom generators exist because they can be constructed from so-called one-way functions.

A function f from a set X to a set Y is called a one-way function if f(x) is easy to compute for all x ∈ X, but for essentially all elements y ∈ Y it is computationally infeasible to find any x ∈ X such that f(x) = y. [117].

To make things even more complicated, there is also no mathematical proof for the existence of one-way functions. Proving this would be equivalent to solving the famous P versus NP problem, one of the six remaining most difficult mathematical problems selected by the Clay Mathematics Institute at the turn of the second millennium. However, mathematicians (and cryptographers) consider it very likely that one-way functions exist because there are several long-standing problems such as integer factorization that have no known algorithms that could solve them in polynomial time.