Probabilistic Computation and Interactive Proof Systems

概率计算和交互式证明系统

• 批准号: 9009936
• 负责人: Lance Fortnow
• 金额: $ 3.69万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-08-01 至 1992-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9009936&HistoricalAwards=false
• 关键词: Probabilistic; Computation; Interactive; Proof; Systems

An interactive proof system consists of two players, an "infinitely" powerful prover and a probabilistic time-bounded verifier. The prover tries to convince the verifier of the validity of some statement. However, the verifier does not trust the prover and will only accept if the prover manages to convince the verifier of the validity of the statement. The prover and the verifier have a conversation with the verifier using random coins to ask questions to the prover until the verifier is or is not convinced of the validity of the statement. This project will examine the complexity of these interactive proof systems and the techniques used in the recent results showing every problem solvable in a reasonable amount of space has such a proof system. The new ideas, based on looking at certain hard problems with a simple algebraic characterization, may prove useful in tackling some of the other hard questions in structural complexity theory. Using certain cryptographic assumption, one can show every interactive proof system has an equivalent "zero-knowledge" proof system, i.e. the verifier receives no information from the protocol other than whether the statement was valid. This project will try to determine whether such a theorem is true without any cryptographic assumptions. Perhaps one could use the new ideas for interactive proofs using certain "hard" functions whose hardness do not depend on unknown assumptions. This project will also study how much more time is needed for a computer with access to random coins to be more powerful than a similar computer with less time. Standard techniques will not help to solve this problem but perhaps the techniques used for interactive proof systems may also prove this question. This project will also look at some complexity issues of multiple- prover interactive proof systems where there are two or more provers who can not communicate among themselves. While the complexity of multiple-prover interactive proof systems is known, this project will look at the complexity of such proof systems with a constant number of rounds of communication been the provers and the verifier and also various applications of the complexity of these proof systems.

一个交互式证明系统由两个参与者组成，一个“无限”强大的证明者和一个概率时间有限的验证者。证明者试图使验证者相信某些陈述的有效性。然而，验证者并不信任证明者，只有当证明者设法使验证者相信陈述的有效性时，验证者才会接受。证明者和验证者进行对话，验证者使用随机硬币向证明者提出问题，直到验证者相信或不相信该陈述的有效性。本项目将研究这些交互式证明系统的复杂性，以及在最近的结果中使用的技术，这些结果表明，在合理的空间内可解决的每个问题都具有这样的证明系统。这些新想法是基于用简单的代数表征来看待某些难题，可能对解决结构复杂性理论中的一些其他难题很有用。使用一定的密码学假设，可以证明每个交互式证明系统都有一个等效的“零知识”证明系统，即验证者除了声明是否有效之外，不会从协议中接收到任何信息。这个项目将尝试在没有任何密码学假设的情况下确定这样的定理是否成立。也许人们可以使用一些“硬”函数来进行交互式证明，这些函数的硬度不依赖于未知的假设。该项目还将研究一台可以访问随机硬币的计算机比一台时间更短的类似计算机更强大需要多少时间。标准技术将无助于解决这个问题，但也许用于交互式证明系统的技术也可以证明这个问题。本项目还将研究多证明者交互证明系统的一些复杂性问题，其中有两个或更多的证明者不能相互通信。虽然多证明者交互证明系统的复杂性是已知的，但本项目将通过恒定数量的证明者和验证者之间的通信来研究这种证明系统的复杂性，以及这些证明系统复杂性的各种应用。