CRII: AF: Pseudorandomness: New Frontiers and Techniques

随机性在计算中的作用非常重要，在计算机科学的各个分支中有着重要的应用，包括设计实际问题的快速算法，分布式计算，密码学和安全性。科学家和经济学家在物理和生物系统以及其他复杂环境的模拟中广泛使用随机性。然而，在实践中的一个主要问题是，随机性的物理来源是有缺陷的，只产生包含一些熵的相关位。 这就引出了一个基本问题：在多大程度上，随机性的使用是应用程序所固有的？我们能否减少执行这些任务所需的随机性的数量或质量？随机性在密码学中的大多数应用都是固有的。实际上，我们要求各种加密应用（如信用卡交易）的密钥是均匀随机的。 另一方面，不知道随机性的使用是否是设计有效算法的基础。 本项目旨在研究这些基本问题，特别是为密码学和安全中使用的随机性的质量提供理论保证，并减少有效算法设计中使用的随机性数量。伪随机性领域为上述问题提供了一种统一的方法，该领域的主要目标是有效地构建类似随机的确定性对象。这个想法是用一个类似随机的对象的显式构造来替换应用程序中使用的随机对象，从而消除了对随机位的需要。 这一领域的重要概念是随机抽取器和伪随机发生器。随机性提取器是从有缺陷的随机性源产生纯随机位的算法。这种提取器可以用于在执行重要的加密协议之前净化有缺陷的源。伪随机发生器是一种确定性算法，其采用短的均匀随机字符串并将其拉伸成对于适当的应用仍然"看起来随机"的长得多的字符串（例如，使用有限存储器的算法）。该项目旨在研究几个具体的方向，以扩展随机性提取器和伪随机发生器的有效构造的最新技术，从而解决计算复杂性理论和去随机化中的重要开放问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.