AF: Small: Average-Case Fine-Grained Complexity

AF：小：平均情况的细粒度复杂性

基本信息

批准号：
1909429
负责人：
Virginia Williams
金额：
$ 50万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-01 至 2022-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909429&HistoricalAwards=false
关键词：
AF Small Average Case Fine

项目摘要

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.

没有数字加密图：电子邮件，电子和ATM交易，云中的操作，手机电话以及更多的其他互动在很大程度上取决于加密和加密协议，以确保操作是安全和机密的，这将是不可能的。尽管人们认为常用的加密协议是安全的，但其安全性基于未经证实的（尽管被广泛认为）数学假设。如果其中一些假设是错误的，则协议将被破坏并确保世界所依赖的交易将受到损害。因此，密码学通常基于各种可信的假设。然而，实际上所有这些假设都要求p不等于NP，这是一种普遍认为但在理论计算机科学和数学中臭名昭著的猜想。如果复杂性类别P和NP平等，则预计几乎所有现代密码学都将失败。该项目的主要部分是研究哪种类型的安全加密协议，即使P = NP（不太可能的事件，但尚未排除）。 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在合理的假设下，那些基本需要二次，立方体和更多运行时。虽然细粒度的复杂性取得了巨大的成功，并且是一个更实际的复杂性概念，但它仅在最差的运行时间内才开发出来。该项目将研究平均循环概念的细粒度复杂性，从中可以从替代基础中构建弱形式的加密形式：单向功能，公共密钥密码学等等，更安全地抵抗（例如）o（n^5） - 时间有限的对手。对于很大的n，这种加密在实践中仍然是安全的。更重要的是，即使传统基金会未能提供安全的密码系统（例如，p = np），也可以发展加密。该项目的目标之一是改进了布尔值满意度和其他重要问题的平均案例版本的算法，对平均案例的细粒度降低了细粒度复杂性的关键问题的平均细粒度减少以及加密原始的发展，以及基于良好的基础奖励的依据，并反映了NSF的基础奖励，并反映了NSF的基础奖励。更广泛的影响审查标准。

项目成果

期刊论文数量（14）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Public-Key Cryptography in the Fine-Grained Setting

细粒度环境中的公钥密码学

DOI：
10.1007/978-3-030-26954-8_20
发表时间：
2019
期刊：
Advances in Cryptology {\textendash} {CRYPTO} 2019
影响因子：
0
作者：
LaVigne, R.;Lincoln, A.;Vassilevska Williams, V.
通讯作者：
Vassilevska Williams, V.

Faster Random k-CNF Satisfiability

DOI：
10.4230/lipics.icalp.2020.78
发表时间：
2019-03
期刊：
影响因子：
0
作者：
Andrea Lincoln;Adam B. Yedidia
通讯作者：
Andrea Lincoln;Adam B. Yedidia

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

列出可避免顶点的新下界和上限

DOI：
发表时间：
2022
期刊：
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022
影响因子：
0
作者：
Deng, Mingyang;Vassilevska Williams, Virginia;Zhong, Ziqian
通讯作者：
Zhong, Ziqian

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

来自非平凡去随机化的几乎所有电路下界