Paper 2018/437
ZeroKnowledge Protocols for Search Problems
Ben Berger and Zvika Brakerski
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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Minor revision. ICALP
 Keywords
 Zero knowledgesearch problems
 Contact author(s)
 bnberger @ gmail com
 History
 20180514: received
 Short URL
 https://ia.cr/2018/437
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/437, author = {Ben Berger and Zvika Brakerski}, title = {ZeroKnowledge Protocols for Search Problems}, howpublished = {Cryptology ePrint Archive, Paper 2018/437}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/437}}, url = {https://eprint.iacr.org/2018/437} }