AF:Small:Pseudorandomness and Randomness Extraction

AF:Small:伪随机性和随机性提取

• 批准号: 1218723
• 负责人: David Zuckerman
• 金额: $ 40万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218723&HistoricalAwards=false
• 关键词: AF; Small; Pseudorandomness; Randomness; Extraction

Pseudorandomness and randomness extraction are motivated by the amazing utility of randomness in computing. When simulating complex phenomena, such as the weather or the economy, it is standard to include random components. Computer security is impossible without randomness. In practice, however, it is expensive to get truly random numbers, if it is possible at all. What can we do with a small amount of high-quality randomness, or a large amount of low-quality randomness? Pseudorandom generators are designed to attack the first question, and randomness extractors the second. The PI proposes to strengthen constructions of these fundamental objects.Not only will this help advance computer science, but it could enable progress in other fields of science which use randomized simulations. Moreover, constructions of such pseudorandom objects often have unexpected applications. For example, the PI recently showed how related pseudorandom objects -- ``expander graphs" -- can be used to construct financial derivatives that cannot be significantly manipulated. A more common application area is cryptography, the mathematical foundation of computer security.

伪随机性和随机性提取是由随机性在计算中的惊人效用所激发的。 在模拟复杂现象（例如天气或经济）时，通常包含随机成分。 没有随机性，计算机安全就不可能实现。 然而，在实践中，如果可能的话，获得真正的随机数是昂贵的。 我们可以用少量的高质量随机性或大量的低质量随机性做什么？ 伪随机生成器旨在解决第一个问题，随机性提取器旨在解决第二个问题。 PI 建议加强这些基本对象的构建。这不仅有助于推进计算机科学，而且可以促进使用随机模拟的其他科学领域的进步。 此外，这种伪随机对象的构造通常具有意想不到的应用。 例如，PI 最近展示了如何使用相关的伪随机对象（“扩展图”）来构建无法显着操纵的金融衍生品。更常见的应用领域是密码学，它是计算机安全的数学基础。