AF: Small: Unconditional Lower Bounds in Approximability and Cryptography

AF：小：近似性和密码学的无条件下界

• 批准号: 1161812
• 负责人: Luca Trevisan
• 金额: $ 39.25万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161812&HistoricalAwards=false
• 关键词: AF; Small; Unconditional; Lower; Bounds

The focus of this project is on two related research programs, one concerned with unconditional lower bounds in the theory of approximation algorithms and one concerned with unconditional lower bounds in the foundations of cryptography.In the study of approximation algorithms, this project focuses on the complexity of finding approximate solutions to satisfiable constraint satisfaction problems; an example of such a problem is, given a 3-colorable graph, to efficiently find a 3-coloring that properly colors as many edges as possible. The well developed theory of "Unique Games," and its relationship with the power of Semidefinite Programming relaxations, does not apply to satisfiable instances. This project explores Khot's "2-to-1 games conjecture" and its role in such questions, considering issues such as the existence of integrality gap instances for Semidefinite Programming relaxation of 2-to-1 games, the existence of approximation algorithms for 2-to-1 games, and the possibility of a `"universality" results similar to the one proved by Raghavendra for unique games.In the foundations of cryptography, this project attacks problems in cryptoanalysis with theoretical computer science methods that have rarely been applied to such problems. The project will study generalizations and improvements of the Hellman-Fiat-Naor generic one-way function inverter, the security of Goldreich's one-way function candidate under various restricted forms of attack, and the security of efficient constructions of pseudorandom generators and hash functions under restricted forms of attack.Progress in the approximation algorithms component of the project will further develop one of the most active and successful current research programs in theoretical computer science, by clarifying an important but still poorly understood part of the theory. Past advances in this area have been of broad interest to theoretical computer scientists and pure mathematicians.Progress in the cryptography component of the project will bring a new connection between theoretical cryptography and cryptoanalysis, by applying techniques from the former research community to problems of interest to the latter. The project contributes to the long-term goal to develop new general tools that can be used to validate the security of cryptographic primitives.

该项目的重点是两个相关研究计划，这是一个涉及近似算法理论中无条件的下限，一个与密码学基础中无条件的下限有关的研究。找到可满足约束满意度问题的近似解决方案；给出了3色图的一个例子，可以有效地找到一个三色，可以正确颜色尽可能多的边缘。良好发展的“独特游戏”理论及其与半决赛编程放松的力量的关系不适用于令人满意的实例。该项目探讨了KHOT的“ 2-1游戏猜想”及其在此类问题中的作用，考虑到诸如存在2-1游戏的半决赛编程放宽的整数差距实例，以及2--存在近似算法的存在TO-1游戏以及与Raghavendra为独特游戏证明的“普遍性”结果相似的可能性。在密码学的基础上，该项目用理论计算机科学方法攻击了很少适用于这样的隐性计算机科学方法的问题问题。 该项目将研究Hellman-Fiat-noor通用单向功能逆变器的概括和改进，在各种受限制的攻击形式下，Goldreich的单向功能候选者的安全性以及伪随机发电机和哈希功能的有效结构的安全性攻击的限制形式。项目的近似算法组成部分将进一步开发理论计算机科学中最活跃，最成功的当前研究计划之一，并阐明一个理论的重要但知之甚少。该领域的过去进步一直是理论计算机科学家和纯数学家的广泛关注。项目的加密组成部分将通过将前研究社区的技术应用于利益问题的技术来引发理论加密和加密分析之间的新联系后者。该项目有助于开发新的通用工具的长期目标，该工具可用于验证加密原始图的安全性。