Interactive PCP

Yael Tauman Kalai, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations

Abstract

A central line of research in the area of PCPs is devoted to constructing short PCPs. In this paper, we show that if we allow an additional interactive verification phase, with very low communication complexity, then for some NP languages, one can construct PCPs that are significantly shorter than the known PCPs (without the additional interactive phase) for these languages. We give many cryptographical applications and motivations for our results and for the study of the new model in general. More specifically, we study a new model of proofs: interactive-PCP. Roughly speaking, an interactive-PCP (say, for the membership x ∈ L) is a proof-string that can be verified by reading only one of its bits, with the help of an interactive-proof with very small communication complexity. We show that for membership in some NP languages L, there are interactive-PCPs that are significantly shorter than the known (non-interactive) PCPs for these languages. Our main result is that for any constant depth Boolean formula Φ(z1,...,zk) of size n (over the gates ∧,∨,⊕,¬), a prover, Alice, can publish a proof-string for the satisfiability of Φ, where the size of the proof-string is poly(k). Later on, any user who wishes to verify the published proof-string needs to interact with Alice via a short interactive protocol of communication complexity poly(logn), while accessing the proof-string at a single location. Note that the size of the published proof-string is poly(k), rather than poly(n), i.e., the size is polynomial in the size of the witness, rather than polynomial in the size of the instance. This compares to the known (non-interactive) PCPs that are of size polynomial in the size of the instance. By reductions, this result extends to many other central NP languages (e.g., SAT, k-clique, Vertex-Cover, etc.). More generally, we show that the satisfiability of ∧i=1ni(z 1,...,zk) = 0], where each Φi(z 1,...,zk) is an arithmetic formula of size n (say, over double-struck G double-struck F[2]) that computes a polynomial of degree d, can be proved by a published proof-string of size poly(k,d). Later on, any user who wishes to verify the published proof-string needs to interact with the prover via an interactive protocol of communication complexity poly(d,logn), while accessing the proof-string at a single location. We give many applications and motivations for our results and for the study of the notion of interactive PCP in general. In particular, we have the following applications: Succinct zero knowledge proofs: We show that any interactive PCP, with certain properties, can be converted into a zero-knowledge interactive proof. We use this to construct zero-knowledge proofs of communication complexity polynomial in the size of the witness, rather than polynomial in the size of the instance, for many NP languages. Succinct probabilistically checkable arguments: In a subsequent paper, we study the new notion of probabilistically checkable argument, and show that any interactive PCP, with certain properties, translates into a probabilistically checkable argument [18]. We use this to construct probabilistically checkable arguments of size polynomial in the size of the witness, rather than polynomial in the size of the instance, for many NP languages. Commit-Reveal schemes: We show that Alice can commit to a string w of k bits, by a message of size poly(k), and later on, for any predicate Φ of size n, whose satisfiability can be proved by an efficient enough interactive PCP with certain properties, Alice can prove the statement Φ(w)=1, by a zero-knowledge interactive proof with communication complexity poly(logn). (Surprisingly, the communication complexity may be significantly smaller than k and n).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages536-547
Number of pages12
EditionPART 2
DOIs
StatePublished - Aug 14 2008
Externally publishedYes
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume5126 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008
CountryIceland
CityReykjavik
Period7/7/087/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Interactive PCP'. Together they form a unique fingerprint.

Cite this