Pseudorandomness, Codes, and Cryptography

这个建议是关于伪随机性及其与编码理论和密码学的关系。伪随机性研究的一个基本对象是由Nisan和Pi引入的抽取子。抽取器是一种使用几个辅助的高质量随机比特从低质量随机源中提取高质量随机性的算法。最近，PI和合著者发现了抽取器和编码理论之间有趣的联系。具体地说，他们展示了如何使用Reed-Muller码来构建良好的提取程序，以及提取程序如何产生良好的列表可解码代码。虽然这些方法有所改进，但还没有实现最佳的萃取器，和平倡议建议朝着这一目标努力。PI还计划研究编码理论中的相关问题。此外，PI还计划在密码学中使用低质量的随机性，因为密码学的工作较少。密码学还激发了确定性抽取器的概念，它从低质量的来源中提取随机性，而不需要任何辅助随机比特。虽然这对于一般的低质量来源是不可能的，但对于更专业的来源来说是可能的。例如，PI和一名学生为所谓的不经意的比特固定源构造了确定性萃取器。这适用于抗曝光的密码学，在这种密码学中，即使密钥的大部分被暴露，加密原语也可以工作。PI建议改进以前的结果并研究相关问题。广泛的影响许多科学家在蒙特卡罗模拟中使用伪随机发生器，并可能在不知道的情况下得到错误的答案。因此，伪随机发生器的进步可能意味着其他科学领域的进步。随着计算机安全与国家安全变得更加相关，密码学的进步对社会也很重要。该项目还具有教育效益：PI的研究与他的教学相结合，特别是在他对研究生和博士后的指导方面。

This proposal is about pseudorandomness and its relationship with coding theory and cryptography. A fundamental object in the study of pseudorandomness is the extractor, introduced by Nisan and the PI. An extractor is an algorithm which extracts high-quality randomness from a low-quality random source, using a few auxiliary high-quality random bits. Recently, the PI and co-authors have discovered interesting connections between extractors and coding theory. Specifically, they showed how to use Reed-Muller codes to build good extractors, and how extractors yield good list decodable codes. While there have been improvements in these methods, optimal extractors have not been achieved, and the PI proposes to work towards that goal. The PI also plans to work on related issues in coding theory.In addition, the PI plans to work on using low-quality randomness in cryptography, where less work has been done. Cryptography also motivates the notion of deterministic extractors, which extract randomness from low-quality sources without any auxiliary random bits. While this is impossible for general low-quality sources, it is possible with more specialized ones. For example, the PI and a student constructed deterministic extractors for so-called oblivious bit-fixing sources. This has applications to exposure-resilient cryptography, where cryptographic primitives are made to work even if large portions of keys are exposed. The PI proposes to improve previous results and work on related issues.Broader ImpactMany scientists use pseudorandom generators in Monte Carlo simulations,and may get wrong answers without knowing it. Advances in pseudorandom generators can therefore mean advances in other areas of science. Advances in cryptography are also important to society, as computer security becomes more relevant for national security. The project also has educational benefits: the PI's research is integrated with his teaching, especially in his mentoring of graduate students and postdocs.