Communications of the ACM
Pure Randomness Extracted from Two Poor Sources
Credit: Dan Tilert
Truly random numbers are critical for computing and cryptography. Although deterministic algorithms can generate numbers that seem random, critical applications depend upon truly unpredictable physical processes. Unfortunately, the resulting sequences can still contain hidden regularities, so theoretical computer scientists have long sought "extractors" that produce perfect randomness from these imperfect sources.
It has been known for 30 years that there should be many ways to combine two imperfect sources to generate nearly perfectly random numbers, but only now have researchers shown explicitly how to create such "two-source extractors." The work, which received a best-paper award at the 48th ACM Symposium on Theory of Computing (STOC 2016) last June, brought together developments from several disparate areas of computer science. "The search has been going on mainly in the past 10 or 15 years, and this is the culmination of this effort," said Avi Wigderson of the Institute for Advanced Study at Princeton University in Princeton, NJ. "It's a huge jump, both technically and also quantitatively."
No entries found