Witness Hiding Without Extractors or Simulators

• Type: Article in International Conference Proceedings Book
• Date: 2018

Authors

souto, a (Author) Other; antunes, l (Author) FCUP; Mateus, P (Author) Other; teixeira, a (Author) Other

Conference proceedings International

Title: SAILING ROUTES IN THE WORLD OF COMPUTATION

Pages: 397-409

14th Conference on Computability in Europe (CiE)

Kiel, GERMANY, JUL 30-AUG 03, 2018

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 2 Citations

Other information

Authenticus ID: P-00R-0AS

DOI: 10.1007/978-3-319-94418-0_40

Abstract (EN): In a witness hiding protocol the prover tries to convince the verifier that he knows a witness to an instance of an NP problem without revealing the witness. We propose a new look at witness hiding based on the information conveyed in each particular instance of the protocol. We introduce the concept of individual witness hiding (IWH) and prove that zero-knowledge protocols for classical problems like HAM are not IWH. On the other hand, we show that all FewP problems have an IWH protocol. Finally, by introducing a Kolmogorov string commitment protocol we can show that all FewP problems have an IWH protocol that is zero-knowledge relative to an oracle.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13