- Whether randomness truly exists in nature, that is, whether it behaves as we model it mathematically, is still unknown. But assuming that it does, one can ask whether sufficiently powerful enough computational models (e.g., Turing machines) can efficiently (i.e., polynomial time and using polynomial memory) emulate randomness in such a way that a very smart observer (e.g., a probabilistic polynomial-time algorithm) with access to powerfull tools (e.g. probabilitisc oracles) can be decived.
This question alongside essential theorems that are the foundation for the current SOTA cryptography algorithms and remarkable philosophical questions on learning are presented in this blog as a paper overview.
A constructive approach to Theory of Randomness for Functions
Notation and Conventions
Intruduction to the One-Way Functions Conjecture
Cryptographically Strong pseudorandom Bit generators (CSB generators)
Poly-Random Collections
Prediction Problems and Poly-Random Collections (motivations for learning theory arise)
Cryptographic Applications and Further Improvements