AF: Small: Average-Case Fine-Grained Complexity

没有数字加密，现代世界将是不可能的：电子邮件、电子和ATM交易、云中操作、移动的电话以及更多的交互都严重依赖加密和加密协议，以确保安全和保密地执行操作。虽然通常使用的加密协议被认为是安全的，但它们的安全性是基于未经证明（尽管被广泛认为）的数学假设。如果其中一些假设是错误的，协议将被破坏，世界所依赖的安全交易将受到损害。正因为如此，密码学通常基于各种不同的可信假设。然而，实际上所有这些假设都要求P不等于NP，这是一个在理论计算机科学和数学中被广泛相信但臭名昭著的困难猜想。如果复杂度等级P和NP相等，那么几乎所有的现代密码学都会失败。这个项目的一个主要部分是研究什么类型的安全加密协议仍然是可能的，即使P=NP（一个不太可能的事件，但它没有被排除）。主要目标是开发平均情况下的细粒度复杂性，它有更多的应用，而不仅仅是开发新的密码学，例如布尔可满足性问题和最小电路尺寸问题的新算法方法。细粒度复杂性以比传统计算复杂性更细的方式研究问题的时间复杂性，寻求将问题分类为近似线性，次二次，次立方运行时间等，与那些需要基本上二次、三次和更多运行时间的系统相比，在合理的假设下。虽然细粒度复杂性已经取得了巨大的成功，并且是一个更实用的复杂性概念，但它只是针对最坏情况的运行时间而开发的。这个项目将研究细粒度复杂性的平均情况概念，从中可以从其他基础上构建弱形式的密码学：单向函数，公钥密码学等等，对（比如）O（n^5）时间有界的对手安全。对于非常大的n，这样的密码学在实践中仍然是安全的;更重要的是，即使传统的基础不能提供安全的密码系统，人们也可以开发密码学（例如，P = NP）。该项目的目标之一是布尔可满足性和其他重要问题的平均情况版本的改进算法，细粒度复杂性中关键问题的最坏情况到平均情况细粒度约简，和密码原语的开发，如基于精细的公钥密码学，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准。

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.