True Randomness from Big Data.

Area of Science:

• Computer Science
• Information Theory
• Cryptography

Background:

• Generating high-quality random bits is essential for various applications, including physical systems simulation and cryptography.
• Existing methods for extracting randomness from large datasets often rely on statistical assumptions and can be computationally inefficient.

Purpose of the Study:

• To develop a general method for generating provably random bits from massive datasets.
• To introduce the concept of 'big sources' into the randomness extraction literature.
• To provide an efficient and practical solution for randomness generation from large-scale data.

Main Methods:

• Viewing large datasets as samples from a 'big source' (a random variable of at least a few gigabytes).
• Developing a novel randomness extraction technique applicable to these big sources.
• Empirically validating the method on real-world datasets.

Main Results:

• The proposed method provably extracts almost-uniform random bits from big sources.
• The method is computationally efficient and practical for handling large datasets.
• Empirical validation shows the method's quality matches or exceeds existing approaches like quantum randomness expanders.

Conclusions:

• This research establishes a new paradigm for randomness extraction from big data.
• The developed method offers an efficient and reliable way to generate high-quality random bits.
• The findings have significant implications for fields requiring robust randomness, such as cryptography and scientific simulations.