Pseudorandomness, Codes, and Cryptography

伪随机性、代码和密码学

• 批准号: 0310960
• 负责人: David Zuckerman
• 金额: $ 25万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-05-01 至 2007-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0310960&HistoricalAwards=false
• 关键词: Pseudorandomness; Codes; Cryptography

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.

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