| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | January 30, 2019 |
| Latest Amendment Date: | January 30, 2019 |
| Award Number: | 1849899 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | March 1, 2019 |
| End Date: | February 28, 2021 (Estimated) |
| Total Intended Award Amount: | $175,000.00 |
| Total Awarded Amount to Date: | $175,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
341 PINE TREE RD ITHACA NY US 14850-2820 (607)255-5014 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
107 Hoy Road Ithaca NY US 14853-7501 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The essential goals of the project were to investigate the requirement of randomness in efficient computation, and further develop techniques for producing high-quality random bits for applications in cryptography. We summarize the progress we made on these directions:
(1) Derandomizing efficient randomized computation: A major goal in theoretical computer science is to prove that efficient computation does not require random bits. Towards this goal, we made progress on reducing randomness requirements for algorithms that have limited memory. In particular, our construction is optimal in certain important parameter regimes. This result was published in the Computational Complexity Conference in 2020.
In another research investigation in this theme, we made interesting progress on the problem of constructing pseudorandom generators (that provide a black-box way of reducing randomness) for classes of Boolean circuits that have remained elusive for decades. This result was published in the Symposium on Theory of Computing, 2020 (STOC 2020).
(2) Producing high-quality randomness and applications: A randomness extractor is an algorithm that purifies correlated randomness to produce independent, unbiased bits (i.e. high-quality randomness). A rich line of work investigates constructing such extractors in various settings, with motivations coming from a variety of applications in cryptography, distributed computing, complexity theory, etc. In this project, we make a number of advances in constructing extractors and finding applications in cryptography. In a paper published in STOC 2020, we study a new model of correlated sources that we call ?adversarial sources?, motivated by various settings in cryptography and show how to produce random bits from such sources. In a result published in the Symposium on Foundations of Computer Science 2020, we construct extractors that work even when an adversary learns non-trivial leakage of the randomness used by the extractor. Such extractors have natural applications in computational complexity theory and cryptography. Our other results include new randomness extractors that have applications in the theory of error-correcting codes. These results have been published in the International Cryptorgaphy Conference 2020 and Theory of Cryptography Conference 2020.
Last Modified: 06/26/2021
Modified by: Eshan Chattopadhyay
Please report errors in award information by writing to: awardsearch@nsf.gov.
