CAREER: Pseudorandom Objects and their Applications in Computer Science

职业：伪随机对象及其在计算机科学中的应用

• 批准号: 1845349
• 负责人: Xin Li
• 金额: $ 50万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845349&HistoricalAwards=false
• 关键词: CAREER; Pseudorandom; Objects; their; Applications

One of the most successful paradigms in computer science since the 1970s is the use of random bits (coin flips) in computation, which can be demonstrated from several broad aspects. For example, many simple randomized algorithms perform better than sophisticated deterministic algorithms, and random bits are widely used in modern cryptography to ensure security. Moreover, in certain applications regarding designing combinatorial objects (such as highly connected sparse networks), simply choosing a random object often achieves the best parameters. However, the use of random bits comes at a price: in practice high quality random bits are often too costly to obtain, and many applications such as the example of designing a sparse network require deterministic constructions rather than randomized ones. The overarching goal of this project is to understand the fundamental question of when and how one can replace the use of random bits or randomized objects by pseudorandom objects, which are objects that are deterministically constructed but behave like random ones. This will lead to a deeper understanding of the nature of random bits in computation, as well as more efficient and secure solutions to important questions both in theory and in practice. Examples of benefits include faster algorithms for handling large data sets, more robust networks, and more reliable communications in hostile environments. The project also involves plans for mentoring PhD students, integration of the research topics into courses and books that appeal to students from a variety of different backgrounds, and support of under-represented groups of students in computer science.The project contains three sets of specific goals. The first set of goals seeks to understand how to reduce the quantity or quality of random bits in computation generally, using two kinds of pseudorandom objects known as pseudorandom generators and randomness extractors. A pseudorandom generator is a function that stretches a short random seed into a long string that looks random to certain functions, and it can be used to reduce the quantity of random bits required. A randomness extractor is a function that transforms imperfect random sources into high quality random bits. The second set of goals investigates the connections of these pseudorandom objects to computational complexity theory. Specifically, the goal is to use the random-like property of these objects to give new constructions of deterministic objects that circumvent barriers in long-standing open problems, such as the question of sequential computation versus parallel computation. The third set of goals involves development of new techniques for constructions of error-correcting codes, which can be used both to protect against various tampering attacks from adversaries, and to achieve privacy or security in cryptographic systems. The study of these topics is based on techniques from several related areas such as probability theory, information theory, cryptography, combinatorics, and harmonic analysis, and will further foster the interactions among these areas towards breakthroughs.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.

自 20 世纪 70 年代以来计算机科学最成功的范式之一是在计算中使用随机位（硬币翻转），这可以从几个广泛的方面进行证明。例如，许多简单的随机算法比复杂的确定性算法表现更好，并且随机位广泛用于现代密码学中以确保安全性。此外，在设计组合对象（例如高度连接的稀疏网络）的某些应用中，简单地选择随机对象通常可以获得最佳参数。然而，使用随机位是有代价的：实际上，获得高质量随机位的成本往往太高，并且许多应用（例如设计稀疏网络的示例）需要确定性构造而不是随机构造。该项目的总体目标是了解何时以及如何用伪随机对象替换随机位或随机对象的基本问题，伪随机对象是确定性构造的但行为类似于随机对象的对象。这将导致人们更深入地了解计算中随机位的本质，并为理论和实践中的重要问题提供更高效、更安全的解决方案。好处的例子包括处理大型数据集的更快算法、更强大的网络以及在恶劣环境中更可靠的通信。该项目还包括指导博士生的计划、将研究主题整合到吸引不同背景的学生的课程和书籍中以及支持计算机科学领域代表性不足的学生群体。该项目包含三组具体内容目标。第一组目标旨在了解如何使用两种称为伪随机生成器和随机性提取器的伪随机对象来减少计算中随机位的数量或质量。伪随机生成器是一种将短随机种子拉伸为长字符串的函数，该长字符串对于某些函数来说看起来是随机的，并且可用于减少所需的随机位数。随机性提取器是将不完美的随机源转换为高质量随机位的功能。第二组目标研究这些伪随机对象与计算复杂性理论的联系。具体来说，目标是利用这些对象的类似随机的属性来给出确定性对象的新构造，从而绕过长期存在的开放问题中的障碍，例如顺序计算与并行计算的问题。第三组目标涉及开发构建纠错码的新技术，该技术既可用于防止对手的各种篡改攻击，又可用于实现密码系统的隐私或安全。这些主题的研究基于概率论、信息论、密码学、组合学和调和分析等多个相关领域的技术，并将进一步促进这些领域之间的相互作用以实现突破。该奖项反映了 NSF 的法定使命，并已通过使用基金会的智力优点和更广泛的影响审查标准进行评估，认为值得支持。

项目成果

Efficient Linear and Affine Codes for Correcting Insertions/Deletions

用于纠正插入/删除的高效线性和仿射码

• DOI: 10.1137/1.9781611976465.1
• 发表时间: 2021-01
• 期刊: SODA21: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms
• 作者: Cheng, Kuan;Guruswami, Venkatesan;Haeupler, Bernhard;Li, Xin
• 通讯作者: Li, Xin

Improved Decoding of Expander Codes

改进的扩展码解码

• DOI: 10.4230/lipics.itcs.2022.43
• 发表时间: 2022-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Chen, Xue;Cheng, Kuan;Li, Xin;Ouyang, Minghui
• 通讯作者: Ouyang, Minghui

Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering

用于交错篡改和篡改组合的不可延展代码、提取器和秘密共享

• DOI: 10.1007/978-3-030-64381-2_21
• 发表时间: 2020-12
• 期刊: Cham
• 作者: Chattopadhyay, Eshan;Li, Xin
• 通讯作者: Li, Xin

Low-Degree Polynomials Extract From Local Sources

从本地来源提取低次多项式

• 发表时间: 2022-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Alrabiah, Omar;Chattopadhyay, Eshan;Goodman, Jesse;Li, Xin;Ribeiro, Joao
• 通讯作者: Ribeiro, Joao

Extractors and Secret Sharing Against Bounded Collusion Protocols

针对有限共谋协议的提取器和秘密共享

• DOI: 10.1109/focs46700.2020.00117
• 发表时间: 2020-11
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Chattopadhyay, Eshan;Goodman, Jesse;Goyal, Vipul;Kumar, Ashutosh;Li, Xin;Meka, Raghu;Zuckerman, David
• 通讯作者: Zuckerman, David