FAW: Algorithmic Complexity in Cryptography, Distributed Computation and Interactive Proofs

FAW：密码学中的算法复杂性、分布式计算和交互式证明

• 批准号: 9023313
• 负责人: Shafrira Goldwasser
• 金额: $ 25万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-11-01 至 1997-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9023313&HistoricalAwards=false
• 关键词: FAW; Algorithmic; Complexity; Cryptography; Distributed

The PI's primary areas of research interest are interactive proof systems, fault tolerant distributed computation, cryptography. Research is projected in these areas. Interactive proofs, introduced by Goldwasser, Micali and Rackoff, are an extension of the classical NP notion of what can be efficiently verified. Two new ingredients are added: The verifier may be probabilistic and err slightly, and the verifier can interact with the prover. The PI plans to investigate for which class of problems it is sufficient for the prover to be able to solve the problem itself. This problem has direct application to program testing which will be explored. The rapid development of distributed systems raises the natural question of what tasks can be performed by them (especially when faults occur). In the last four years it has been extensively studied, and to a large extent understood, how to perform any probabilistic computation on inputs distributed among processors in a complete network so that no faulty subset of the processors gets any additional information or can disrupt the computation. Cryptography has recently developed from a primarily empirical field of ad-hoc techniques to a formal discipline. This rigor was accompanied by concrete and practical proposals of systems which were shown, under a variety of candidate hard problems from number theory, to comply with the new security standards. At this time in the development of the field two projects should be undertaken: first, the definitions for the different cryptographic tasks must be unified. And second, new hard problems should be found (possibly from coding theory or the geometry of numbers domain) on which to base cryptographic schemes.

PI的主要研究领域是交互式证明 系统、容错分布式计算、密码学。 计划在这些领域进行研究。 交互式证明，介绍了Goldwasser，Micali和Rackoff， 经典NP概念的扩展，即什么可以有效地 验证 添加了两个新成分：验证者可以是 概率和错误轻微，验证者可以与 证明者 PI计划调查这是哪一类问题 这足以让证明者自己解决问题。 这个问题直接应用于程序测试，这将是 探讨了 分布式系统的快速发展， 他们可以执行哪些任务的问题（特别是当 故障发生）。 在过去的四年里， 研究，并在很大程度上理解，如何执行任何 分布在处理器之间的输入的概率计算 完整的网络，使没有故障的处理器子集得到任何 额外的信息或可能会破坏计算。 密码学最近从一个主要经验的领域发展起来 ad-hoc技术到正式的学科。 这种僵硬是 同时提出了具体和切实可行的制度建议， 显示，根据数论的各种候选困难问题， 符合新的安全标准。 这个时候 应开展两个项目：第一， 不同密码任务的定义必须统一。 第二，应该发现新的难题（可能来自编码 理论或数域几何）的基础 密码方案