CAREER: Resource-Constrained Approaches to Cryptography

The world's infrastructure now critically depends upon cryptography for almost every task. While recent years have seen a blossoming of novel cryptographic techniques and applications, we still do not know if even our elementary cryptosystems are secure. Unlike most scientific domains, including much of computer science, it is impossible to empirically verify that a cryptosystem is secure. Instead, cryptographic security is founded on the conjectured existence of strong computational intractability: the inability of efficient algorithms to solve particular problems. The primary goal of this project is to strengthen the foundations of computational intractability needed for robust cryptography, which will yield a more robust cryptographic infrastructure. Another goal of this project is educational outreach, which will be presented through talks, tutorials, and lectures to encourage collaboration with diverse communities and, in turn, equip individuals with the ability to reason effectively about security. We propose exploring novel resource-constrained adversarial models to improve our cryptographic foundations. Traditionally, cryptographic attackers were modeled as probabilistic polynomial time algorithms. To circumvent barriers in this traditional setting and strengthen cryptographic security, we consider adversarial models that are alternately more powerful (e.g., algorithms with limited nondeterminism) and less powerful (e.g., algorithms with fixed polynomial time/space). We highlight two concrete aims: (1) improved cryptographic hardness amplification, yielding extremely hard problems from hard problems, and (2) understanding the feasibility of cryptographic security if it turns out that traditional cryptographic guarantees are impossible, planting our security on a firmer footing. 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.