License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.18
URN: urn:nbn:de:0030-drops-83279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8327/
Go to the corresponding LIPIcs Volume Portal

Goldreich, Oded ; Rothblum, Guy N.

Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets

pdf-format:
LIPIcs-ITCS-2018-18.pdf (0.6 MB)

Abstract

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in P that are believed to have relatively high complexity. Specifically, such constructions are presented for t-CLIQUE and t-SUM. In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC). The proof systems presented by us are significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016), and can be implemented using a smaller number of rounds.

BibTeX - Entry

@InProceedings{goldreich_et_al:LIPIcs:2018:8327,
  author =	{Oded Goldreich and Guy N. Rothblum},
  title =	{{Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8327},
  URN =		{urn:nbn:de:0030-drops-83279},
  doi =		{10.4230/LIPIcs.ITCS.2018.18},
  annote =	{Keywords: Interactive proofs}
}

Keywords: Interactive proofs
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI