18 May 2016 – Eric De Grasse, my Chief Technology Officer, has been prepping for the annual “Symposium on Theory of Computing” which will be held next month in Cambridge, MA. He has been getting slammed with papers to be presented at the event.
Note: it is a fascinating symposium. I attended several years ago when I began my artificial intelligence program. It hits all the buttons: algorithms and data structures, coding theory, computational complexity, cryptography, machine learning, privacy, randomness in computing, quantum computing, and a whole basket of theoretical aspects of areas such as databases, information retrieval, networks, and robotics. It was where I first learned of a text analytics program which we just beta-tested in London for an e-discovery review.
One of the interesting papers is by two University of Texas academics who have made what some experts believe is a breakthrough in random number generation that could have longstanding implications for cryptography and computer security. David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper this past March that will be presented at the Symposium.
The paper describes how the academics devised a method for the generation of high quality random numbers. The work is theoretical, but the authors say down the road it could lead to a number of practical advances in cryptography, scientific polling, and the study of other complex environments such as the climate.
Some background
The study of existing random number generators used in commercial applications has intensified since the Snowden documents were published; sometimes random numbers aren’t so random. Random numbers are important for computer encryption, lotteries, scientific modelling, and gambling. Current methods of generating random numbers can produce predictable results. There are currently two main methods for generating random numbers:
- In the first, a computer picks numbers according to an algorithm or from a pre-generated list. This method, while fast and not requiring much computer power, is not truly random, because the results are predictable.
- The second method introduces an unpredictable element from the real world into the algorithm. This might be a reading of air temperature, a measurement of background radiation, or variations in atmospheric noise. Some of these measurements, however, have their own patterns – and may not be truly random. They can also be difficult to acquire.
The problem of generating random numbers lies in the fact that computers are fundamentally predictable machines, running calculations and delivering answers based on mathematics.
What the experts are saying is this new method could generate higher-quality random numbers with less computer processing.
What these chaps have done
The new solution takes two “weak” random sources to generate a single, high-quality random number. That made it a faster, more practical solution for an almost-perfectly random number, and it could have implications for encryption and security. Why? Because in cryptography, random numbers are essential. Given enough time, all algorithms can be reverse-engineered. You have to build the algorithm so that it takes so long to reverse-engineer it’s not worth it. Random number equations are central to injecting this randomness.
And not everybody is shouting “IT’S PARTY TIME!” with this new method. One guy not impressed is Dr Mads Haahr of Trinity College Dublin. He created the online random number generator random.org which I wrote about awhile ago. Dr Haahr was quoted by the BBC and MIT Press as saying while the development was an improvement in efficiency, it was not a fundamental leap forward:
“While the paper might be a good contribution in the specific research area of randomness extraction, I would not call it a breakthrough … all those things are already possible with existing methods and have been for many years. If the authors’ claims hold up, we will be able to do these things faster than before, and with equipment of poorer quality, which is great, but the method doesn’t enable any applications that weren’t possible before. I’m glad to see there is good research going on to improve the state of the art. In many ways, randomness is the under-appreciated cornerstone of data security. As regular users of information technology, we tend not to appreciate how important it is.”
Note that Dr Haahr made a point about the vetting process. It has taken almost a year for other researchers to examine these new findings, expand upon the method, and for the original authors to add revisions.
You can read all of the delicious technical details in the full paper here: “Explicit Two-Source Extractors and Resilient Functions.”