The 30-Year Randomness Problem That Could Help Secure the Quantum Future

Andrei Mihai

Randomness sounds like the simplest thing in the world. Flip a coin, and it lands heads or tails; toss a die, and you have a 1 in 6 chance of guessing the number. But in practice, true randomness is surprisingly hard to pinpoint.

Researchers who work on randomness tend to sidestep the philosophical aspects of whether true randomness exists and instead work on randomness from a practical perspective: a source is random enough if no test, algorithm, or adversary can reliably predict it, compress it, or distinguish it from an ideal stream of fair coin flips. In a sense, it’s practical randomness rather than true randomness.

This being said, how do you figure out if something is random enough to trust? Or in other words, given a messy, real-life source of information, can we transform its biased, correlated noise into bits that no efficient adversary can distinguish from ideal randomness?

In 2016, Eshan Chattopadhyay and David Zuckerman found a startling new way to do it. Their paper, “Explicit two-source extractors and resilient functions,” solved a central problem that had resisted understanding for nearly 30 years. In 2025, the work earned them the Gödel Prize, one of theoretical computer science’s highest honors.

Randomness and Computers

In addition to being a fascinating concept in itself, randomness is also one of the invisible gears that help turn modern life. The classic example is in cryptography, where randomness helps encrypt bank transactions and payments. Encryption keys, digital signatures, authentication codes, and secure protocols all depend on numbers that an attacker cannot predict. If the randomness is weak, biased, or reused, even a mathematically strong system can fail, and a hacker may be able to reconstruct a key.

The trouble is that the world rarely hands over perfect randomness. Instead, modern computers collect unpredictable data from sources such as electrical noise in hardware, timing variations in the processor, disk, or even things like mouse movements. Some chips also include special instructions that draw on hardware noise sources.

To make things even more complex, operating systems usually feed the raw input into a secure “randomness pool,” mix them together, and then use cryptographic algorithms to produce clean-looking random bits. This is what your computer uses when it creates encryption keys, secure web connections, passwords, tokens, or cryptographic nonces.

Yet even this process isn’t completely impervious. These sources can be biased, correlated, or partially predictable.

When they reason about such imperfect sources, computer scientists use a measure called min-entropy. Roughly speaking, min-entropy captures how hard it is to guess the outcome of a random source. A source with low-min entropy is more predictable; one with high min-entropy may not be perfectly random, but no single outcome is too likely.

The ideal dream would be to construct a randomness extractor, a deterministic procedure that turns a weak random source into a shorter string that looks almost perfectly random. But, of course, there is a catch.

For a single general weak source, deterministic extraction is impossible. No matter what function one chooses, there is always some large subset of inputs on which that function gives a constant answer. A source supported only on that subset can still have high min-entropy, but the extractor’s output will be completely predictable.

So what if instead of using one weak source, we used two?

Double Trouble

If two weak sources are independent, perhaps each can compensate for the flaws of the other. This was the model proposed in the 1980s by Miklos Santha, Umesh Vazirani, Benny Chor and Oded Goldreich. In principle, two-source extractors could work with remarkably little entropy. Here, entropy means the amount of real unpredictability inside a source of random-looking bits.

They also proved that some two-source extractors must exist, but they did not give an actual formula or efficient algorithm for building one. For any practical purposes, computer scientists needed explicit extractors (functions that could actually be computed efficiently).

For years, the best methods hit a wall. Chor and Goldreich showed that the inner product function could extract randomness from two weak sources, but only if each source still had a lot of entropy — more than half the maximum possible rate. In 2005, Jean Bourgain broke that “half barrier” with tools from Fourier analysis and additive combinatorics. It was a landmark advance, but it did not solve the problem. Bourgain’s methods worked for sources with a constant, significant fraction of entropy. The theoretical dream was to handle sources with far less.

Chattopadhyay and Zuckerman’s breakthrough was a new route around the obstacle. Their insight was (in a simplified manner) to use one weak source to build a structured table of values, then use the second weak source to sample from it. Most of the sampled entries behave almost as if they were independent and uniform. The challenge is to combine them in a way that survives those corrupted entries.

In order to do this, they connected the problem of extraction to non-malleable extractors, objects that had emerged from cryptography.

A normal randomness extractor tries to turn a weak random source into nearly perfect random bits. A non-malleable extractor has a harder duty. It still extracts randomness, but it also remains safe if an attacker tampers with the “seed” or input used in the extraction. In essence, a non-malleable extractor is designed to keep producing useful randomness even when an adversary tampers with a part of the process.

That is where another branch of computer science entered the story.

Distributed Computing

In the 1980s, distributed computing researchers studied “collective coin flipping.” Imagine many processors trying to agree on a shared random bit. Some processors may be malicious. They can wait, observe the honest processors’ messages, and then choose their own messages to bias the result.

To solve this problem, researchers turned to resilient Boolean functions: functions designed so that no small coalition of input bits can strongly influence the final output.

It’s an unlikely place to look for inspiration, but Chattopadhyay and Zuckerman used such functions inside their two-source extractor. After one source is used to sample many rows from a table generated using the other source, the sampled bits are fed into a carefully constructed resilient function. The point is that even if some of those sampled bits are “bad” or adversarially correlated, the resilient function can still produce a bit that is close to unbiased.

The last piece came from circuit complexity and pseudorandomness, the study of what simple computational circuits can and cannot detect. Mark Braverman proved that polynomial-size constant-depth circuits cannot distinguish limited independence from true randomness, as long as the amount of independence is polylogarithmic.

This limitation became a strength. Chattopadhyay and Zuckerman used the weakness of these circuits as a guarantee. In essence, their resilient function behaved as if its good inputs were fully random, even though they satisfied only a weaker form of independence.

In the end, they produced an explicit two-source extractor for sources with only polylogarithmic min-entropy. The amount of usable randomness required grew only like a power of the logarithm of the source length, far below previous explicit constructions.

Opening the Field

Their paper was published in 2015 as a technical report, and the conference version appeared in 2016. The final journal version was published in Annals of Mathematics in 2019 as “Explicit two-source extractors and resilient functions,” by Eshan Chattopadhyay and David Zuckerman.

“David and I were fantastically optimistic when we started this work – we had no idea if our approach would actually succeed,” said Chattopadhyay, who is a member of Cornell’s Theory of Computing group. “It’s been amazing to watch the field move forward since then – what once felt like distant goals are now active areas of progress and discovery. I’m deeply grateful to see our work play a part in that progress, and honored that it’s received this kind of recognition.”

The Gödel Prize was awarded in 2025, recognizing the result as the solution to a central open problem in computational complexity.

The Chattopadhyay-Zuckerman framework did not end the field. Rather, it opened it up for more innovation.

By replacing one sampling step with a more efficient object called a somewhere-random condenser, further work moved closer to the information-theoretic limit. Later work achieved explicit extractors requiring near-logarithmic min-entropy.

In mathematics and computer science, progress often comes from importing tools from one area into another. Here, the import was unusually elegant, using a limitation in one setting as a resource in another. The fact that constant-depth circuits are weak helped prove that an extractor was strong. But the result might also matter as computation enters a quantum era.

Quantum systems can generate randomness in a physical sense. A measurement of a quantum state can produce outcomes that are inherently unpredictable. Yet real quantum devices still suffer from noise, bias and possible adversarial influence. Raw physical randomness must still be certified and purified.

No doubt, randomness and computer science still have a lot to work on in the future.

The post The 30-Year Randomness Problem That Could Help Secure the Quantum Future originally appeared on the HLFF SciLogs blog.