CRII: AF: Pseudorandomness: New Frontiers and Techniques

Cornell University, Ithaca NY

Investigators

Abstract

The role of randomness in computation is extremely important with crucial applications to various branches of computer science including design of fast algorithms for practical problems, distributed computing, cryptography, and security. Scientists and economists use randomness extensively in simulations of physical and biological systems and other complex environments. However, a major problem in practice is that physical sources of randomness are defective and only produce correlated bits that contain some entropy. This leads to the following fundamental question: To what extent is the use of randomness inherent in applications? Can we reduce the amount or quality of randomness required to perform these tasks? Most applications of randomness in cryptography are inherent. Indeed, we require the secret keys for various cryptographic applications, such as credit card transactions, to be uniformly random. On the other hand, it is not known if the use of randomness is fundamental in designing efficient algorithms. This project intends to study these fundamental questions, and in particular, provide theoretical guarantees on the quality of randomness used in cryptography and security, and reduce the amount of randomness used in design of efficient algorithms. The area of Pseudorandomness provides a unified approach to the above problems and a major goal in this area is to efficiently construct deterministic objects that are random-like. The idea is to replace a random object used in an application, with an explicit construction of a random-like object, thus removing the need for random bits. Important notions in this area are randomness extractors and pseudorandom generators. A randomness extractor is an algorithm that produces purely random bits from defective sources of randomness. Such extractors can be used in purifying defective sources before carrying out important cryptographic protocols. A pseudorandom generator is a deterministic algorithm that takes a short uniformly random string and stretches it into a much longer string that still "looks random" to the appropriate application (e.g., algorithms that use limited memory). This project intends to study several concrete directions to extend the state-of-art on efficient constructions of randomness extractors and pseudorandom generators that will lead to resolving important open problems in computational complexity theory and derandomization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.