13/07/2012, 15:00 — 16:00 — Room P4.35, Mathematics Building
André Souto, SQIG-IT
Individual Witness Hiding
In an interactive proof systems, there is a prover and a verifier
and the goal of the prover is to convince the verifier of the
validity of "'', for some language . A natural question
arises: "What knowledge does the verifier gain during the
interaction?'' The definitions of zero knowledge and witness hiding
are based on the existence of simulators or witness extractors. One
might raise some questions about such "operational'' definitions.
For instance, can there be protocols which actually leak no
information to the verifier, but which are so obfuscating that
there does not exist a simulator? Also, the existence of a
simulator might be too weak to guarantee that no information is
leaked to the verifier in any instances of the protocol. We propose
a new approach based on Kolmogorov complexity, a rigorous measure
of the amount of information contained in an object, usually a
string. It is the difference between the Kolmogorov complexity of
the witness when one does not see the conversation and one sees it.
We explore some of its properties, design an IWHP for all languages
in . This is a joint work with Luís Antunes, Sophie
Laplante, Paulo Mateus and Andreia Teixeira
