Grant: Discovery Grants Program - Individual

Public-key cryptography is the bedrock of secure communication and computation in large-scale distributed computer systems. Our confidence in the security of most public-key schemes rests on two types of assumptions: number-theoretic (hardness of factoring and discrete logarithms) and lattice-theoretic (hardness of finding short integral solutions). The former are threatened by quantum computers. The latter are currently unbreakable but could be rendered insecure by advances in algorithms. The objective of this research program is to broaden the foundations of public-key cryptography by exploiting the average-case hardness of various problems in statistical inference, including random constraint satisfaction problems. Such problems exhibit statistical-computational gaps: There is a regime in which there is sufficient data to recover the signal, yet no efficient procedure is known. Recent advances provide explanations for this phenomenon, proving hardness against restricted classes of algorithms. This project aims to * develop new tools and methods for rigorously ascertaining the average-case hardness of statistical inference problems * investigate the design of new public-key encryption schemes * apply insights from cryptography towards understanding the relative complexity of statistical inference problems