PYI: Mathematical Foundations of Cryptography

点击翻译按钮获取中文摘要

PYI: New Foundations for Cryptography Research is in progress in the general area of computational complexity. The focus of this research is on cryptography and computational number theory. During the decade of the eighties cryptography was developed into a formal discipline in which notions such as "one-way function" and "proving that a protocol is correct" have a precise yet natural meaning. Rigor was accomplished by concrete proposals which were shown to comply with the new complexity standards under a few complexity assumptions. Unfortunately, the complexity assumptions made, for example the existence of one-way functions, are likely to remain unproven for quite a while longer. This situation provides motivation for establishing a new foundation for cryptography. Instead of making intractability assumptions about functions, physical assumptions about the model in which cryptography is being done (for example the kind of channel or layout used for communication by the network participants) are being made. Unconditionally secure communication protocols for the new model are sought. Results already achieved that involve proof- systems with a "distributed" prover may have applications to fault tolerant distributed computing. Such applications are being explored. Work is continuing on interactive proof systems. Using tools developed in this area an attempt is being made to clarify the complexity of previously unclassified optimization problems. Work in computational number theory is also continuing. Simpler and faster algorithms for primality testing and other algebraic computations are sought. The P.I. has been judged to be an outstanding computer scientist by the Presidential Young Investigator Panel.