AF: Small: Average-Case Fine-Grained Complexity

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The modern world would be impossible without digital cryptography: email, electronic and ATM transactions, operations in the cloud, mobile phone calls, and many more interactions rely heavily on encryption and cryptographic protocols to ensure that the operations are performed securely and confidentially. While the commonly used cryptographic protocols are believed to be secure, their security is based on unproven (though widely believed) mathematical assumptions. If some of these assumptions were false, the protocols would be broken and secure transactions that the world relies on would be compromised. Because of this, cryptography is typically based on a variety of different believable assumptions. Nevertheless, practically all these assumptions require that P is not equal to NP, a widely believed but infamously difficult conjecture in theoretical computer science and mathematics. If complexity classes P and NP were equal, it is expected that practically all of modern cryptography would fail. A major part of this project is to investigate what types of secure cryptographic protocols are still possible, even if P=NP (an unlikely event, but it has not been ruled out). The main goal will be to develop average-case fine-grained complexity, which has many more applications beyond developing new cryptography, such as new algorithmic approaches to the Boolean satisfiability problem and the minimum circuit size problem. Fine-grained complexity studies the time complexity of problems in a more fine-grained way than traditional computational complexity, seeking to classify problems into those solvable in nearly-linear, subquadratic, subcubic runtime and so on, versus those that require essentially quadratic, cubic and more runtime, under plausible assumptions. While fine-grained complexity has had huge successes and is a more practically relevant notion of complexity, it has only been developed for worst-case running time. This project will study average-case notions of fine-grained complexity, from which one can build weak forms of cryptography from alternative foundations: one-way functions, public key cryptography and more, secure against (say) O(n^5)-time bounded adversaries. For very large n, such cryptography would still be secure in practice; more importantly, one could develop cryptography even if traditional foundations failed to provide secure cryptosystems (e.g., P = NP). Among the goals of this project are improved algorithms for average-case versions of Boolean Satisfiability and other important problems, worst-case to average-case fine-grained reductions for key problems in fine-grained complexity, and development of cryptographic primitives such as public-key cryptography based on fine-grained complexity assumptions. 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.