True Randomness from Big Data.
Generating random bits is a difficult task, which is important for physical systems simulation, cryptography, and many applications that rely on high-quality random bits. Our contribution is to show how to generate provably random bits from uncertain events whose outcomes are routinely recorded in the form of massive data sets. These include scientific data sets, such as in astronomics, genomics, as well as data produced by individuals, such as internet search logs, sensor networks, and social network feeds. We view the generation of such data as the sampling process from a big source, which is a random variable of size at least a few gigabytes. Our view initiates the study of big sources in the randomness extraction literature. Previous approaches for big sources rely on statistical assumptions about the samples. We introduce a general method that provably extracts almost-uniform random bits from big sources and extensively validate it empirically on real data sets. The experimental findings indicate that our method is efficient enough to handle large enough sources, while previous extractor constructions are not efficient enough to be practical. Quality-wise, our method at least matches quantum randomness expanders and classical world empirical extractors as measured by standardized tests.
Rutgers University, MSIS, Piscataway, NJ 08853, USA.
Periklis A
PA
Papakonstantinou
IBM Research Almaden, San Jose, CA 95120, USA.
David P
DP
Woodruff
Institute for Computing Technology, CAS, Beijing, 100190, China.
Guang
G
Yang
Proc Natl Acad Sci U S A. 2012 Nov 20;109(47):19145-50
23125196
Sci Rep. 2013;3:1627
23568082
Nature. 2010 Apr 15;464(7291):1021-4
20393558
Sci Rep. 2014 Jun 30;4:5490
24976499
Proc Natl Acad Sci U S A. 1998 Sep 1;95(18):10367-72
9724709