Abstract
We consider natural ways to extend the notion of ZeroKnowledge (ZK) Proofs beyond decision problems. Specifically, we consider search problems, and define zeroknowledge proofs in this context as interactive protocols in which the prover can establish the correctness of a solution to a given instance without the verifier learning anything beyond the intended solution, even if it deviates from the protocol.
The goal of this work is to initiate a study of Search ZeroKnowledge (searchZK), the class of search problems for which such systems exist. This class trivially contains search problems where the validity of a solution can be efficiently verified (using a single message proof containing only the solution). A slightly less obvious, but still straightforward, way to obtain zeroknowledge proofs for search problems is to let the prover send a solution and prove in zeroknowledge that the instancesolution pair is valid. However, there may be other ways to obtain such zeroknowledge proofs, and they may be more advantageous.
In fact, we prove that there are search problems for which the aforementioned approach fails, but still search zeroknowledge protocols exist. On the other hand, we show sufficient conditions for search problems under which some form of zeroknowledge can be obtained using the straightforward way.
BibTeX  Entry
@InProceedings{berger_et_al:LIPIcs:2018:9109,
author = {Ben Berger and Zvika Brakerski},
title = {{Brief Announcement: ZeroKnowledge Protocols for Search Problems}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {105:1105:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9109},
URN = {urn:nbn:de:0030drops91099},
doi = {10.4230/LIPIcs.ICALP.2018.105},
annote = {Keywords: ZeroKnowledge, Search Problems, Interactive Proofs}
}
Keywords: 

ZeroKnowledge, Search Problems, Interactive Proofs 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 