New method of producing random numbers could improve cybersecurity

[Jim__]

From phys.org:

[center][/center]

With an advance that one cryptography expert called a "masterpiece," University of Texas at Austin computer scientists have developed a new method for producing truly random numbers, a breakthrough that could be used to encrypt data, make electronic voting more secure, conduct statistically significant polls and more accurately simulate complex systems such as Earth's climate.

The new method creates truly random numbers with less computational effort than other methods, which could facilitate significantly higher levels of security for everything from consumer credit card transactions to military communications.

...

The new method takes two weakly random sequences of numbers and turns them into one sequence of truly random numbers. Weakly random sequences, such as air temperatures and stock market prices sampled over time, harbor predictable patterns. Truly random sequences have nothing predictable about them, like a coin toss.

The new research seems to defy that old adage in computer programming, "Garbage in, garbage out." In fact, it's the latest, most powerful addition to a class of methods that Zuckerman pioneered in the 1990s called randomness extractors.

more ...

[MisterP]

1. "was that thunder or were you rolling Damage?"

[DetlefK]

2. This very strongly reminds me of a not-so-new method for generating random numbers:

Make various lists of random numbers with different methods. Draw a random entry from a random list.

I heard about this method about 10 years ago.

[Jim__]

3. Yes, randomness extractors have been around for over 20 years.

Their paper walks through some of the history. The major accomplishment of this method is using 2 weakly random sources to obtain a truly random output. From their paper:

...

The lack of progress on constructing two-source extractors motivated researchers to use more
than two sources. Several researchers managed to construct excellent extractors using a constant
number of sources <BIW06,Rao09a,RZ08,Li11,Li13a,Li13b> culminating in Li’s construction of a 3-
source extractor for polylogarithmic min-entropy <Li15c>. Recently Cohen <Coh15a> also constructed
a 3-source extractor with one source having min-entropy ?n, the second source having min-entropy
O(log n) and the third source having min-entropy O(log log n).

Another direction has been the construction of seeded extractors <NZ96>. A seeded extractor
uses one (n, k)-source and one short seed to extract randomness. There was a lot of inspiring work
over two decades culminating in almost optimal seeded extractors <LRVW03, GUV09, DKSS09>.
Such seeded extractors have found numerous applications; see e.g., Shaltiel’s survey <Sha02>.

However despite much attention and progress over the last 30 years, it remained open to explicitly
construct two-source extractors for min-entropy rate significantly smaller than 1/2.

Our main result is an explicit two-source extractor for polylogarithmic min-entropy.

...