Witness Hiding Without Extractors or Simulators

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2018

Autores

souto, a (Autor) Outra; antunes, l (Autor) FCUP; Mateus, P (Autor) Outra; teixeira, a (Autor) Outra

Ata de Conferência Internacional

Título: SAILING ROUTES IN THE WORLD OF COMPUTATION

Páginas: 397-409

14th Conference on Computability in Europe (CiE)

Kiel, GERMANY, JUL 30-AUG 03, 2018

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 2 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13