NSF Young Investigator: Small Depth Boolean Circuits and Complexity - Theoretic Cryptography

NSF 青年研究员：小深度布尔电路和复杂性 - 理论密码学

• 批准号: 9257979
• 负责人: Russell Impagliazzo
• 金额: $ 23万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1997-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9257979&HistoricalAwards=false
• 关键词: NSF; Young; Investigator; Small; Depth

This award funds continuing investigations into two long-term interests: the complexity of small depth Boolean circuits, and the computational complexity foundations of cryptography. Computational complexity as a field strives to provide a mathematical foundation for computer science by developing techniques to evaluate the inherent difficulty of computational problems. The Boolean circuit seems the most natural and robust concrete model of computational complexity. Much work has gone into developing the theory of circuit complexity in the hope of resolving such questions as P vs. NP. There are strong connections between bounds on circuit depth and issues in the theory of parallel computation, logic (mostly proof theory), learning theory, and the theory of neural nets. Continuing projects in circuit complexity are: establishing links between circuit bounds and Frege proofs; examining the behavior of formulas under random restrictions, (also known as neural nets). Of course, circuit complexity is a dynamic area, and specific projects may change with new results. Work continues on the foundations of cryptography. Recent work in developing the structural complexity of cryptography has been so successful that perhaps all the major, tractable questions in the area have been resolved. Indeed, there seem to be some theoretical roadblocks to further progress in this direction. However, there are several important open questions regarding the relationship between average-case complexity and cryptography, and that between oblivious transfer and secret agreement. More importantly, a large gap remains between theory and practice. Another goal of the project is to develop theoretical tools that will actually lead to implementable cryptosystems, and to handle such questions as virus protection, secure electronic transfer of funds, and such issues as privacy vs. security for electronic mail.

该奖项基金继续对两个长期利益进行调查：小深度布尔电路的复杂性以及密码学的计算复杂性基础。 计算复杂性作为一个领域，努力通过开发技术来评估计算问题的固有难度来为计算机科学提供数学基础。 布尔电路似乎是计算复杂性的最自然，最稳定的混凝土模型。 为了解决Ps. NP等问题的希望，发展了电路复杂性的理论。 在电路深度上的界限与平行计算理论，逻辑（主要是证明理论），学习理论和神经网理论之间存在牢固的联系。 电路复杂性的持续项目是：在电路范围和弗雷格证明之间建立联系；在随机限制下（也称为神经网）检查公式的行为。 当然，电路复杂性是一个动态的领域，特定项目可能会随着新的结果而改变。 加密基础的工作仍在继续。 最近开发加密的结构复杂性的最新工作已经如此成功，以至于该地区所有主要的，可处理的问题都已得到解决。 确实，似乎有一些理论上的障碍可以在这个方向上进一步发展。 但是，关于平均案例复杂性和密码学之间的关系以及遗忘转移与秘密协议之间的关系，有几个重要的公开问题。 更重要的是，理论和实践之间仍然存在很大的差距。 该项目的另一个目标是开发理论工具，这些工具实际上会导致可实施的密码系统，并处理病毒保护，资金的安全电子转移以及诸如隐私与电子邮件安全性等问题。