Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP

William Aiello, Sandeep Bhatt, Rafail Ostrovsky, S. Raj Rajagopalan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

39 Scopus citations

Abstract

Under a computational assumption, and assuming that both Prover and Verifier are computationally bounded, we show a one-round (i.e., Verifier speaks and then Prover answers) witness-indistinguishable interactive proof for NP with poly-logarithmic communication complexity. A major application of our main result is that we show how to check in an efficient manner and without any additional interaction the correctness of the output of any remote procedure call.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
EditorsUgo Montanari, Jose D. P. Rolim, Emo Welzl
Pages463-474
Number of pages12
DOIs
StatePublished - 2000
Event27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland
Duration: 9 Jul 200015 Jul 2000

Publication series

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

Conference

Conference27th International Colloquium on Automata, Languages and Programming, ICALP 2000
Country/TerritorySwitzerland
CityGeneva
Period9/07/0015/07/00

Fingerprint

Dive into the research topics of 'Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP'. Together they form a unique fingerprint.

Cite this