Cryptography is built on a paradoxical idea: a system can look completely random even when it is not. This notion—pseudorandomness— is the cornerstone of modern cryptography and allows us to design encryption schemes that remain secure even when an adversary observes every ciphertext we produce.
To understand why pseudorandomness matters, we must first clarify what we mean by security.
Some encryption schemes provide a remarkably strong guarantee: they remain secure even against an adversary with unlimited computational power. Such schemes are called information-theoretically secure or perfectly secure.
In a perfectly secret encryption scheme, the ciphertext contains no information whatsoever about the plaintext, as long as the secret key is unknown. Formally, observing the ciphertext does not change the adversary’s probability distribution over possible messages.
The most famous example is the one-time pad, which achieves perfect secrecy by using a key that is:
Perfect secrecy does not rely on computational assumptions. No amount of computing power, clever algorithms, or future technological breakthroughs can break it. Its security is absolute.
However, this strength comes at a cost.
In practice, we cannot afford keys as long as the messages we wish to encrypt. Real-world systems typically use keys of length 128 or 256 bits.
To justify such choices, cryptography often relies on concrete security guarantees: numerical estimates of how unlikely a successful attack is.
For example:
From this perspective, choosing a 128-bit key seems overwhelmingly safe. But this raises an uncomfortable question:
Safe against whom?
Are we assuming consumer hardware? Specialized GPUs or ASICs? A single attacker or a nation-state? An attack running for two years or two centuries?
Concrete guarantees depend on assumptions about computing power, algorithmic efficiency, and technological progress—assumptions that may not hold in the future.
To escape these ambiguities, modern cryptography adopts an asymptotic approach, rooted in complexity theory.
Instead of assigning fixed numerical values, security is described in terms of a security parameter n. Both the adversary’s running time and its probability of success are viewed as functions of n.
An encryption scheme is considered secure if every probabilistic polynomial-time adversary succeeds in breaking it with only negligible probability—that is, a probability that decreases faster than the inverse of any polynomial in n.
For example, with a security parameter n = 500, even an adversary running for hundreds of years might succeed with probability no greater than 2−500.
The key advantage of this framework is scalability. As computing power increases or new algorithms are discovered, security can be restored simply by increasing the security parameter.
Perfect secrecy cannot be achieved when encrypting many messages with a single short key.
Given a ciphertext c, an unbounded adversary can try all possible keys, producing a list of all messages that could plausibly correspond to c. If the key space is smaller than the message space, some information is inevitably leaked.
Even worse, this attack runs in polynomial time, succeeds with non-zero probability (approximately 1/|K|), and cannot be prevented by any clever encryption design.
Security is impossible without restrictions on the adversary.
Modern cryptography therefore accepts two necessary relaxations:
Under these conditions, pseudorandomness becomes meaningful: encryption schemes can be designed so that their outputs are computationally indistinguishable from true randomness.
Perfect secrecy represents an ideal—beautiful, elegant, and unattainable at scale. Pseudorandomness and the asymptotic approach provide a pragmatic alternative: security that is not absolute, but robust, scalable, and future-proof.
By shifting the focus from concrete numbers to asymptotic behavior, cryptography frees itself from fragile assumptions about hardware and technology. Security becomes a mathematical property rather than a moving target—and that is what makes modern cryptography possible.