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最近展示了相关的伪随机对象--"扩展图”--如何被用来构建不能被显著操纵的金融衍生品。 一个更常见的应用领域是密码学，计算机安全的数学基础。