The paper "How to Construct Random Functions" by Oded Goldreich, Shafi Goldwasser, and Silvio Micali presents a constructive theory of randomness for functions based on computational complexity. The authors introduce the concept of poly-random functions, which are functions that cannot be distinguished from random functions by any probabilistic polynomial-time algorithm. They demonstrate how to construct such functions using one-way functions and a pseudorandom function generator (PRFG). The PRFG is a deterministic polynomial-time algorithm that transforms pairs $(g, r)$, where $g$ is a one-way function and $r$ is a random $k$-bit string, into polynomial-time computable functions $f_r: \{1, \ldots, 2^k\} \rightarrow \{1, \ldots, 2^k\}$. These functions are pseudorandom in the sense that no probabilistic polynomial-time algorithm can distinguish them from truly random functions. The paper also discusses the applications of poly-random collections in cryptography, random constructions, and complexity theory. It compares poly-random collections with one-way functions and cryptographically strong pseudorandom bit generators (CSB generators), showing that poly-random collections offer additional advantages in terms of efficiency and security. The authors provide a detailed construction of poly-random collections and prove that they pass all polynomial-time statistical tests for functions. They also show that poly-random collections cannot be polynomially inferred, making them robust against prediction problems. The paper concludes with cryptographic applications, including solutions to problems such as message authentication, storageless distribution of secret identification numbers, and fair contract signing protocols. The authors highlight the practical significance of their results and their potential impact on various cryptographic schemes.The paper "How to Construct Random Functions" by Oded Goldreich, Shafi Goldwasser, and Silvio Micali presents a constructive theory of randomness for functions based on computational complexity. The authors introduce the concept of poly-random functions, which are functions that cannot be distinguished from random functions by any probabilistic polynomial-time algorithm. They demonstrate how to construct such functions using one-way functions and a pseudorandom function generator (PRFG). The PRFG is a deterministic polynomial-time algorithm that transforms pairs $(g, r)$, where $g$ is a one-way function and $r$ is a random $k$-bit string, into polynomial-time computable functions $f_r: \{1, \ldots, 2^k\} \rightarrow \{1, \ldots, 2^k\}$. These functions are pseudorandom in the sense that no probabilistic polynomial-time algorithm can distinguish them from truly random functions. The paper also discusses the applications of poly-random collections in cryptography, random constructions, and complexity theory. It compares poly-random collections with one-way functions and cryptographically strong pseudorandom bit generators (CSB generators), showing that poly-random collections offer additional advantages in terms of efficiency and security. The authors provide a detailed construction of poly-random collections and prove that they pass all polynomial-time statistical tests for functions. They also show that poly-random collections cannot be polynomially inferred, making them robust against prediction problems. The paper concludes with cryptographic applications, including solutions to problems such as message authentication, storageless distribution of secret identification numbers, and fair contract signing protocols. The authors highlight the practical significance of their results and their potential impact on various cryptographic schemes.