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

PI的主要研究领域是交互证明系统、容错分布式计算、密码学。预计将在这些领域进行研究。由Goldwasser、Micali和Rackoff提出的交互式证明是对经典NP概念的扩展，即什么是可以有效验证的。添加了两个新的成分：验证者可能是概率的，并且略有误差，并且验证者可以与证明者交互。PI计划调查哪类问题足以让证明者自己解决问题。这一问题对程序测试具有直接的应用价值，是本文要探讨的问题。分布式系统的快速发展提出了一个自然的问题，即它们可以执行什么任务(特别是在发生故障时)。在过去的四年中，人们已经广泛地研究并在很大程度上理解了如何对分布在完整网络中的处理器之间的输入执行任何概率计算，从而使得处理器的故障子集不会获得任何附加信息或能够中断计算。密码学最近已经从一个主要是经验领域的特别技术发展成了一门正式的学科。伴随着这种严谨的是对系统的具体和实际的建议，这些系统在来自数论的各种候选难题下被证明符合新的安全标准。目前，在该领域的发展中应开展两个项目：第一，必须统一不同加密任务的定义。第二，应该找到新的困难问题(可能来自编码理论或数域的几何)，作为密码方案的基础。

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.