Pseudorandomness, Codes, and Cryptography

这个建议是关于伪随机性及其与编码理论和密码学的关系。 伪随机性研究中的一个基本对象是由Nisan和PI引入的提取器。 提取器是一种使用少量辅助高质量随机比特从低质量随机源中提取高质量随机性的算法。 最近，PI和合著者发现了提取器和编码理论之间有趣的联系。 具体来说，他们展示了如何使用Reed-Muller代码来构建良好的提取器，以及提取器如何生成良好的列表可解码代码。 虽然这些方法有所改进，但尚未实现最佳提取器，PI建议朝着这一目标努力。 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.