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.